はじめに
どんな問題を解決するか
多くのものは、それまでにあったものの上に積み重なって増えていきます。古典的なパズルのウサギの数、ヒマワリのらせん、1段か2段ずつ上がる階段の上り方などです。フィボナッチ数列はそのパターンのいちばん簡単なモデルで、計算するとループの1回分から次の回へ値を受け渡す方法が身につきます。
身近なたとえ
メモ用紙に2つの数が書いてあると考えてください。今の数と、次の数です。毎回、今の数を読み上げます。そのあと、次の数が今の数になり、新しい次の数は古い2つの数を足したものになります。覚えておく必要があるのは、いつも最後の2つの数だけです。
メモ用紙の2つの数からコードへ
a, b = 0, 1📝 最初の2つの数を書くa, b = b, a + b🔄 次の数が今の数になり、新しい次の数は2つの和になるfor _ in range(count):🔁 必要な個数だけくり返すprint(a, end=" ")📣 今の数を読み上げるひと言でいうと
フィボナッチ数列は0と1から始まり、それ以降の各項は直前の2つの項の和です。
重要なポイント
a, b = 0, 1で数列の最初の2項を保存します。print(a, end=" ")は今の項を表示し、同じ行にとどまります。a, b = b, a + bは、どちらかに代入する前に古い値から新しい2つの値を計算します。for _ in range(count):は10回繰り返します。_は使わないループ変数によく使う名前です。
どんな場面で使う?
- ある回から次の回へ状態を受け渡すループの練習。
- 各値が前の値に依存する数列を理解する。動的計画法への第一歩です。
- 面接や試験の定番問題。
使わなくてよいとき
- 10,000番目のような巨大な1項だけを求める場合:すべての項をループするより速い公式があります。
- キャッシュのない再帰:
fib(n - 1) + fib(n - 2)は同じ値を何度も計算し直し、とても遅くなります。
サンプルコード
main.py
count = 10
a, b = 0, 1
for _ in range(count):
print(a, end=" ")
a, b = b, a + b
実行結果
0 1 1 2 3 5 8 13 21 34
コードの解説
変数aとbは、数列の隣り合う2つの数を保存しています。aを表示した後、a, b = b, a + bで2つの変数を同時に更新するので、次の数の計算にはaの古い値がそのまま使われます。この方法はO(n)の時間で動き、追加のメモリは一定量しか使いません。
値を変更し、PythonをインストールせずにCodeUtilityオンラインPythonコンパイラで実行できます。
発展問題
下のヒントにしたがってコードを書き換えてみましょう。自分で変えて結果を確かめると、コードを読むだけよりずっと深く理解できます。
- 入力データを変え、実行する前に結果を予想してから確かめる。
- データが空のときや不正なときのチェックを追加する。
- 処理を別の関数にまとめ、いろいろなデータで試す。
よくある間違い
変数を1つずつ更新する
a = b のあと古い a が失われるので、b に間違った値が入ります。
問題
a = b
b = a + b
修正
a, b = b, a + b
このレッスンを終えましたか?
学習済みにすると進み具合を記録できます。
進み具合はこのブラウザーに保存されています ログインすると、どのデバイスでも引き継げます。
チャレンジで練習する
このレッスンの内容を使って実際の問題を解きましょう。各チャレンジはブラウザで動き、すぐにテストされ、AI のレビューも受けられます。
すべてのチャレンジ