伯準1003フィボナッチ関数の概念と解(C++)

テキスト
ソース:https://www.acmicpc.net/problem/1003

きほんほうしき

最初は,再帰関数を単純に用いて問題に必要なfibonacci(0),fibonacci(1)の回数を計算するだけであった.しかし、問題の鍵は単純な解決ではなく、「効率的」に解決することだ.私は1つの方法の解答で白準から“タイムアウト”の情報を受け取りました;白俊の初日からコーリンを悲しませた刃のような判決に少し戸惑ったが、必要以上のメモリは白俊が浪費を放棄したコードの哲学が認めた今だ.
緒論長かえって簡単になります.フィボナッチ数列自体が旧値の和からなる数列である.また,再帰的に解読したフィナッチコードにおいても,最終的にはそれを分割し,最も簡単な方法で分離したコードを用いた.

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);
    }
}

上のコードは以下のように簡単に説明します.

フィボナッチラ数列は、前の数列の2つの値の和であり、この2つの値も前の数列の和である.フォローを続けると、最終的には初期条件に達します.その初期条件はf(0)=1,f(1)=1である.
直感的に見ると,フィボナッチ数列の値はf(0)とf(1)の規則とからなり,次いでf(0)とf(1)の一連の規則値の和である.
初期条件f(0)とf(1)を除いて、f(2)はf(2)=f(0)+f(1)に等しく、2=1+1に等しい.f(3)の場合、f(3)=f(2)+f(1)であり、これは3=2+1である.異なる場合は、f(3)=2 f(1)+f(0)と書くことができます.次のように整理されます.
f(2) = f(1)+f(0)
f(3) = 2f(1) + f(0) = 3
f(4) = 3f(1) + 2f(0) = 5
f(5) = 5f(1) + 3f(0) = 8
f(6) = 8f(1) + 5f(0) = 13
.
.
.
以上のように、f(0)およびf(1)の個数も、フィボナッチ数列に従う.

コード#コード#

テキスト

#include <iostream>
using namespace std;
int main() {
	int testcase = 0, a = 0;
	cin >> testcase;
	int* arr;
	while (testcase--) {
		cin >> a;
		if (a < 2) {
			if (a == 0) {
				cout << "1 0" << endl;
			}
			else {
				cout << "0 1" << endl;
			}
		}
		else {
			arr = new int[41];
			arr[0] = 1, arr[1] = 1;
			for (int i = 2; i <= a; i++) {
				arr[i] = arr[i - 1]+ arr[i-2];
			}
			cout << arr[a - 2] << " " << arr[a - 1] << endl;
		}
	}
	return 0;
}

の最後の部分

実は最初は動的割当てで問題を解くためにnewint[a]を使っていたのですが、ランタイムエラー(AssertionFailed)はその値がどのくらいなのか分からないので、なぜ表示されるのか分かりません.後で探してみましょう.