UVA12459 Bees' ancestors 题解

题目传送门

题目大意

雌蜂有一个父亲一个母亲，而雄蜂只有母亲。

计算出 Willy 的祖先中，哪一代有多少祖先。

解题思路

已知 Willy 为雄蜂，从 Willy 开始向前推：

• 有一个母亲（1）；

• 母亲有一父一母（2）；

• 祖父有一母，祖母有一父一母（3）；

• 曾祖母一父一母，曾祖父一母，曾祖母有一父一母（5）；

• 高祖父有一母，高祖母有一父一母，高祖母有一父一母，高祖父有一母，高祖母有一父一母（8）；

• \(\ldots\)

将每一代的人数放在一起看，就会发现，这其实是斐波那契数列；

也就是：\(f[i]=f[i-1]+f[i-2]\)。

代码

递推即可：

#include<bits/stdc++.h>
using namespace std;
long long f[100],n;
int main() {
	f[1]=1;
	f[2]=2;
	for(int i=3; i<=88; i++)
		a[i]=a[i-1]+a[i-2];
	while(cin>>n) {
		if(!n) break;
		cout<<a[n]<<'\n';
	}	return 0;
}

注意不要用递归，递归要重复调用一个数，会超时的！