题目描述
小明很喜欢爬楼梯,但是小明腿不够长,每次小明最多只能一步跨越两个阶梯。比如他初始在楼底,跨越一个阶梯到达 1号阶梯,或者跨越两个阶梯到达 2 号阶梯。
为了选出一种最轻松的爬楼梯的方式,小明想把所有不同的到达楼顶的方式都尝试一遍。对于一共有 n 个阶梯的楼梯,小明一共有多少总方法从楼底到达楼顶。
由于最后答案可能很大,输出最后的答案对100007 取模的结果。
输入格式
第一行输入一个整数 n(1≤n≤1000)。
输出格式
输出最后答案对于100007 取模的结果。
题解
每层楼梯方式数量
- 1
- 2
- 3
- 5
- 8
- 13
.......
由此可推出该数列是一个斐波那契数列(a[i]=a[i-1]+a[i-2]);
代码
60分代码
#include<bits/stdc++.h>
using namespace std;
int a[1001];
int main(){
int n;
cin>>n;
a[1]=1;
a[2]=2;
for(int i=3;i<=n;i++){
a[i]=(a[i-1]+a[i-2]);
}
cout<<a[n]%100007;
return 0;
}
由于 n非常大,所以会导致int爆;
AC代码
#include<bits/stdc++.h>
using namespace std;
int a[1001];
int main(){
int n;
cin>>n;
a[1]=1;
a[2]=2;
for(int i=3;i<=n;i++){
a[i]=(a[i-1]+a[i-2])%100007;
}
cout<<a[n]%100007;
return 0;
}