HDU （超级楼梯）

spoiler posted @ 2011年4月24日 15:28 in Fibonacci 的相关规律题及计算 , 1840 阅读

题目大意：

有一楼梯共M级，刚开始时你在第一级，若每次只能跨上一级或二级，要走上第M级，共有多少种走法？

题目分析：
画个图也许您就明白了，如果您再加上一个台阶，图中就会多出两条线，一个是从n-2那里引来的，一条是从n-1那里引来的，所以F[N]=F[N-1]+F[N-2]
想必猜出来了这是什么了吧呵呵
这就是典型的feibonacci数
公式：
f[n]= $\frac{1.0}{\sqrt{5}}$ { ${(\frac{1+\sqrt{5}}{2})}^{n}$ - ${(\frac{1-\sqrt{5}}{2})}^{n}$ }
但是这里直接模拟求解就可以了
代码：

#include<iostream>
#include<cstdio>
using namespace std;
long long s[45];
int main(){
	int i,n,cas;
	s[1]=1;
	s[2]=1;
	for(i=3;i<=40;i++)
		s[i]=s[i-1]+s[i-2];
	cin>>cas;
	while(cas--){
		scanf("%d",&n);
		printf("%lld\n",s[n]);
	}
	return 0;
}