HDU (超级楼梯)

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

题目大意:

有一楼梯共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;
}

 

登录 *


loading captcha image...
(输入验证码)
or Ctrl+Enter