爬楼梯（升级版）

【题目描述】

假期时，TFLSOIers最喜欢的事情是到学校学习C++编程，糟糕的是学习编程的机房在11层，世界上最痛苦的事莫过于爬楼梯。假设爬到11层共有N个台阶，TFLSOIers从下往上爬楼梯，一步可以跨一级台阶，也可以跨两级台阶。问：他们爬到第N个台阶有多少种走法？

【输入格式】

一行一个整数n（n的取值范围见下方提示，请认真分析）

【输出格式】

一个整数，表示爬到第n级台阶有多少种走法。

【输入样例】

【输出样例】

【提示】

30%数据 1≤n≤45

30%数据46≤n≤91

40%数据92≤n≤100

根据分析可知，其实考查斐波那契数列数列，只是初始值有所变化，注意初始值的特判

一、20分代码：本题用递归写的话会超时因为第3个测试点就是45，可模拟一下运算过程，会发现有很多重复运算，所有很耗时，正好提一下斐波那契数列的时间复杂度

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 long long  tj(int n){
 4     if(n==1)return 1;
 5     if(n==2)return 2;
 6     if(n>=3)return tj(n-1)+tj(n-2);
 7 }
 8 int main(){
 9     int n;
10     cin>>n;
11     cout<<tj(n);
12     return 0; 
13 }

二、30分代码：使用循环写斐波那契，超过45就会超出int数据范围

 1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 {
 5     
 6     int n, f1=1, f2=2, fn;
 7     cin>>n;
 8     if(n==1)fn=1;//注意加特判
 9     if(n==2)fn=2;//注意加特判
10     for(int i=3; i<=n; i++)
11     {
12         fn=f1+f2;
13         f1=f2;
14         f2=fn;
15     }
16     cout<<fn<<endl;
17     
18     return 0;
19 }

三、60分代码：n超过91答案就会超出long long 数据范围

 1 #include<iostream>
 2 using namespace std;
 3 int main()
 4 {
 5     
 6     int n;
 7     long long f1=1, f2=2, fn;
 8     cin>>n;
 9     if(n==1)fn=1;
10     if(n==2)fn=2;
11     for(int i=3; i<=n; i++)
12     {
13         fn=f1+f2;
14         f1=f2;
15         f2=fn;
16     }
17     cout<<fn<<endl;
18     
19     return 0;
20 }

四、100分代码：40%数据要求使用高精度运算，也就是把上述方法结合高精度运算，要求灵活准确理解高精度。此题对于基础不牢的同学一定要认真模拟，多加测试代码观察代码运行情况。

 1 #include<bits/stdc++.h>
 2 using namespace std;
 3 int f1[105], f2[105], ans[105];
 4 void inf(){
 5     f1[0]=1, f2[0]=2;//初始化相当于f1=1000000..., f2=2000000...
 6 }
 7 void fib(){
 8     int jw=0, i=0;
 9     for(; i<=100; i++){
10         int t=jw+f1[i]+f2[i];
11         ans[i]=t%10;
12         jw=t/10;
13     }
14     ans[i]=jw;//jw值放在数组最高位，别忘了 
15 }
16 void change(int a[], int b[]){//相当于a=b;只不过封装成一个函数 
17     for(int i=0; i<=100; i++){
18         a[i]=b[i];
19     }
20 }
21 void output(int t[]){
22     int l=100;
23     while(t[l]==0){
24         l--;
25     }//从后往前去除前导0
26     for(int i=l; i>=0; i--)cout<<t[i];
27 }
28 int main()
29 {   
30     inf();//初始化相当于f1=1, f2=2 
31     int n;
32     cin>>n;
33     if(n==1)output(f1);
34     else if(n==2)output(f2);
35     else {
36         for(int i=3; i<=n; i++){
37         
38 //        output(f1);cout<<endl;//测试代码
39 //        output(f2);cout<<endl;//测试代码
40         fib();//高精度求 ans=f1+f2
41 //        output(ans); cout<<endl; //测试代码 
42         change(f1,f2);//将f2赋值给f1相当于  f1=f2
43         change(f2,ans);//将f1赋值给 f2=ans    
44     }
45     
46     //输出ans 
47     output(ans);
48         
49     }
50     
51     return 0;
52 }

洛谷相似题目连接：https://www.luogu.com.cn/problem/P1255

此题区分度很好，综合了递归、数组、高精度、算法效率分析，可精讲精练！

此题数组作者自造，如有疑问可留言索取！