白駿1003号:フィボナッチ関数

リンク:https://www.acmicpc.net/problem/1003
各試験例は1行からなり、Nが与えられる.Nは40以下の自然数または0である.
どうして条件を読まないのですか.読んでください40以下の条件を守っていなくて、ずっと间违っています^~^いいですね.本当に目玉がありません.

#include <iostream>
using namespace std;

int main() {
	int num, elem;
	int a[41]{ 0,1 };

	for (int j = 2; j <= 40; j++) {
		a[j] = a[j - 1] + a[j - 2];
	}

	cin >> num;
	for (int i = 0; i < num; i++) {
		cin >> elem;
		if (elem == 0)
			cout << "1 0" << endl;
		else
			cout << a[elem-1] << " " << a[elem] << endl;
	}
	return 0;
}

しかし、あなたが苦労している以上、分析してみましょう.
まず,再帰関数を用いて問題を解くと,タイムアウトの味がする.そのため、再び家に帰るのではなく、方向を繰り返し調整しなければならない.
フィボナッチ数列の創造を繰り返す.

int a[41]{ 0,1 };

for (int j = 2; j <= 40; j++) {
	a[j] = a[j - 1] + a[j - 2];
}

まず0と1をデフォルト設定に変換し、jを2から40にかけて点火式を繰り返す.a[j] = a[j - 1] + a[j - 2]というフィボナッチの点火式はよく知っているので、スキップしましょう.
次は最も考えにくい部分で、実際に検索して知った部分です.復習しましょう.
index (fibo)zeroone (==fibo)0 (0)101 (1)012 (1)113 (2)124 (3)235 (5)356 (8)587 (13)813
次のようにindexが0と1であるほか,規則的に移動することも見られる.

n-1의 zero + n-1의 one => n의 one

n-1의 one => n의 zero

しかしよく見ると、oneの値は実際のfibonacchiの値と同じであることがわかります!従って、n−1のone呼び出し数はnのfibonacchi値に等しいことがわかる.同じ方向において、nのzero呼び出し数はn−1のone呼び出し数に等しく、n−1のfibonacchi値に等しい.
したがって,再統計しなくてもa[elem-1]で0,a[elem]で1を知ることができる.
困難やってみなければ頭が痛くなるに違いないが、もうやってみたので、未来にもっと早く解けることを期待している.
最後にfibonacchi再帰関数を復習します.

int fibonacci(int n) {
    if (n == 0)
        return 0;
    else if (n == 1)
        return 1;
    else
    	return fibonacci(n-1) + fibonacci(n-2);
}