PythonでN番目のフィボナッチ数を求めるプログラム

数値 n が与えられたとき、n番目のフィボナッチ数を求めるプログラムをPythonで作成してみましょう。

フィボナッチ数列とは、i番目の項が f(i) = f(i-1) + f(i-2) という漸化式で定義される数列です。最初の2項は 0 と 1 であり、それ以降の各項は直前の2つの項の和になります。数列を並べると「0, 1, 1, 2, 3, 5, 8, 13, 21, ...」のように続いていきます。

例えば、入力が 15 の場合、15番目のフィボナッチ数である 610 が出力されます。

解き方の手順

この問題は反復処理（ループ）を使うことで効率的に解けます。手順は以下の通りです。

• 変数 first を 0、second を 1 で初期化します（最初の2項に対応）。
• i を 2 から n まで繰り返し処理を行います。
  • temp に first + second の値を代入します。
  • first に second の値を移し替えます。
  • second に temp の値を移し替えます。
• ループ終了後、second の値を返します。

この方法では、各項を一度だけ計算すればよいため、時間計算量は O(n)、空間計算量は O(1) と非常に効率的です。再帰を使う方法と比べて、同じ計算を何度も繰り返す無駄がありません。

実装例

以下のコードで実際の動作を確認してみましょう。

class Solution:
    def solve(self, n):
        first = 0
        second = 1
        for _ in range(2, n+1):
            temp = first + second
            first = second
            second = temp
        return second

ob = Solution()
print(ob.solve(15))

入力

15

出力

610

コードの解説

このコードでは、まず Solution クラスの中に solve メソッドを定義しています。メソッド内では、最初の2項となる first = 0 と second = 1 を設定した後、range(2, n+1) によって n-1 回のループを実行します。

各ループでは、現在の2項の合計を temp に保存し、first と second を一つずつ前にずらしていきます。これにより、n回目のループが終わった時点で second には n番目のフィボナッチ数が格納されていることになります。

まとめ

フィボナッチ数を求める問題は、動的計画法の基本的な考え方を学ぶのに最適な題材です。今回紹介した反復アプローチはシンプルながら効率的で、大きな n の値にも対応できます。ぜひ実際にコードを動かして、挙動を確かめてみてください。