题目一：爬楼梯
在你面前有一个n阶的楼梯，你一步只能上1阶或2阶。请问计算出你可以采用多少种不同的方式爬完这个楼梯。
输入描述:
一个正整数n(n<=100)，表示这个楼梯一共有多少阶
输出描述:
一个正整数，表示有多少种不同的方式爬完这个楼梯
示例1
输入
5
输出
8
第一次想到是使用递归来实现，但是时间超时了，通过率只有40%。
int function(int statehigh) { if(statehigh <= 0) return 0; if(statehigh == 1) return 1; else if(statehigh == 2) return 2; else function(statehigh - 1) + function(statehigh - 2); }
测试代码：
int main() { int state; scanf("%d",&state); printf("%d\n",function(state)); return 0; }
主要是设计到了一个BigInteger算法需要处理大树问题，因为以上的递归到了100的时候，时间会超时。
完整实现大数相加代码如下：
参考链接：https://www.nowcoder.com/questionTerminal/b178fcef3ed4448c99d7c0297312212d
#include <stdio.h> #define Lenght 101 int Function(int first[],int second[],int target[]) { int i; for(i = 0; i < Lenght; i++){ target[i] = first[i] + second[i]; //斐波考那契数列特点就是后一个数为前两个数相加 } //当数列的数值每一个进位大于10，就再往高一个为位进1。 //比如，前两个数是5,8。此时的数值为13，但是13>10，所要取余数，高位进1，得到为3|1，再后一个数据为8,13，由于个位数值是8与3，相加为11>10，所以十位再进1，得到为1|2. for(i = 0; i < Lenght; i++){ if(target[i] >= 10){ //每一个进位大于10时 target[i] = target[i] % 10; //取余数 target[i+1]++; //更高位进1 } } } int main() { int i; int data[Lenght][Lenght] = {0}; data[1][0] = 1; //斐波考那契数列赋予初始值 data[2][0] = 2; for(i = 3; i < Lenght; i++){ //从第3个开始处理数据 Function(data[i-2],data[i-1],data[i]); } int num; scanf("%d",&num); for(i = Lenght - 1; data[num][i] == 0; i--); //去掉末尾的0 for(;i >= 0; i--){ //从后往前依次打印出来的数值就是所要的数 printf("%d",data[num][i]); } return 0; }
题目二：爬楼梯二
递归规律为f(n) = f(n-1) + f(n-3)，与上一题没有多大区别。
代码如下：
#include <stdio.h> #include <string.h> #define MAXnumber 501 int main() { int a[MAXnumber][MAXnumber] = {0}; int i, j, x; //初始化值 a[1][0] = 1; a[2][0] = 1; a[3][0] = 2; //从4开始不断累加 for (i = 4; i < MAXnumber ; i++) { for (j = 0; j < MAXnumber; j++) { a[i][j] = a[i - 1][j] + a[i - 3][j];//递归规律为f(n) = f(n-1) + f(n-3) } for (x = 0; x < MAXnumber; x++) { if (a[i][x] >= 10) { a[i][x] = a[i][x] % 10; a[i][x + 1]++; } } } int num; scanf("%d",&num); //反转输出 for (i = MAXnumber - 1; a[num][i] == 0; i--); for (; i >= 0; i--) { printf("%d", a[num][i]); } return 0; }
