[白俊]2003回フィボナッチ関数-Python

5151 ワード
パイ python 白駿 アルゴリズム#アルゴリズム# テキストリンク

質問する


次のソースはN番目のフィボナッチ数を求めるC++関数である.
int fibonacci(int n) {
    if (n == 0) {
        printf("0");
        return 0;
    } else if (n == 1) {
        printf("1");
        return 1;
    } else {
        return fibonacci(n‐1) + fibonacci(n‐2);
    }
}
fibonacci(3)を呼び出すと、次のことが起こります.
  • Fibonacci(3)Fibonacci(2)とFibonacci(1)(最初の呼び出し)を呼び出す.
  • Fibonacci(2)Fibonacci(1)(2番目の呼び出し)とFibonacci(0)を呼び出す.
  • 2回目の呼び出しのfibonacci(1)は1を出力して1を返す.
  • fibonacci(0)は0を出力し、0を返します.
  • Fibonacci(2)Fibonacci(1)とFibonacci(0)の結果を得て、1を返す.
  • 初回呼び出しのfibonacci(1)は1を出力し、1を返す.
  • Fibonacci(3)Fibonacci(2)とFibonacci(1)の結果を得て、2を返す.
    • 1出力2回、0出力1回です.nが与えられると、fibonacci(n)が呼び出されると、0と1がそれぞれ何回出力されるかを計算するプログラムが作成される.

    入力


    第1行は、試験例の個数Tを与える.
    各試験例は1行からなり、Nが与えられる.Nは40以下の自然数または0である.

    しゅつりょく


    各試験例の出力0の回数と出力1の回数は、スペースで区切られている.

    サンプルI/O



    解答方法

    f0 = [1, 0, 1]
f1 = [0, 1, 1]

def fibonacci(N) :
    length = len(f0)
    if length <= N :
        for i in range(length, N+1) :
            f0.append(f0[i-1] + f0[i-2])
            f1.append(f1[i-1] + f1[i-2])
    print(f0[N], f1[N])
    
T = int(input())

for _ in range(T) :
    fibonacci(int(input()))
  • f 0、f 1の数字ごとに0と1のコール回数をリストに保存
  • 数字が0の場合に呼び出される0は1回、1は0回
  • 数字が1の場合に呼び出される0は0、1は1
  • 数字が2の場合呼び出しの0は1回、1は1回
  • fibonacci(n) = fibonacci(n-1) + fibonacci(n-2)応用概念
  • 上記概念を適用して計算し、値をアレイに追加
  • for入力の回数で回転するために変数Tに入力してT回で繰り返し文を実行する
    • 白駿1003号:フィボナッチ関数
    カッコを回転[プログラマー]
    FileStreamコンストラクタ