[伯俊]17175号ピボナッチ遊びに飽きた~

1312 ワード
白駿 DP ps フィボナッチ テキストリンク
[伯俊]17175号ピボナッチ遊びに飽きた~ 내말그말1.質問
赫晋はアルゴリズムの問題を作るように催促され、プレッシャーが大きかった.しかし、フィボナッチ問題については、私は見すぎて、うんざりしました.しかし、問題を作る時間がない赫晋はフィボナッチ問題を応用して問題を作りたいと思っている.
int fibonacci(int n) { // 호출
  if (n < 2) {
    return n;
  }  
  return fibonacci(n-2) + fibonacci(n-1);
}
上記符号化時にfibonacci(n)を入力したときにfibonacci関数を呼び出す回数を算出する.
2.入力
fibonacci関数にnをパラメータとして入力します.(0 ≤ n ≤ 50)
3.出力
fibonacci関数呼び出しの回数を出力します.
出力値が非常に大きい可能性があるため、正解を10000000に分割し、残りを出力します.
4.解答
  • 2fibo(n) = fibo(n-1) + fibo(n-2)であるため、呼回数はDPでアレイに格納してもよい.でも、最初は一度自分を呼ぶので、1をプラスします.
  • 点火式:fibo(n) = fibo(n-1) + fibo(n-2) + 1
    • 5.コード
    #include <iostream>

using namespace std;

int fibo[51];

int main(void) {
    cin.tie(NULL);
    ios_base::sync_with_stdio(false);
   
    int n;
    cin >> n;
    fibo[0] = 1;
    fibo[1] = 1;

    for (int i = 2; i <= n; i++)
    {
        fibo[i] = (fibo[i - 2] + fibo[i - 1] +1) % 1000000007;
    }
    cout << fibo[n];
}
    server1_nobinlog, Error: Too many connections
    KerbernetesにおけるDMANの実行