题解 | #小乐乐走台阶#
小乐乐走台阶
https://www.nowcoder.com/practice/ebf04de0e02c486099d78b7c3aaec255
#include <stdio.h>
/*
递推：
目标是想求n级台阶有多少种走法，现在先假设已经走完了n级台阶同时假设存在f(n)种走法可以走完n级台阶，
现在退回到走完这n级台阶的上一步，即走完这n级台阶的最后一步，最后一步有两种可能的情况，
第一种情况是这一步只走了1级台阶，即完成最后一步之前已经走了n-1级台阶，假设走完n-1级台阶存在f(n-1)种走法；
第二种情况是最后一步走了两级台阶，即完成最后一步之前已经走了n-2级台阶，又假设走完n-2级台阶存在f(n-2)种走法，
那么理一下思路：完成n级台阶最后一步之前需要走完n-1级台阶或者n-2级台阶，
因为n级存在台阶f(n)种走法，n-1级台阶存在f(n-1)种走法，n-2级台阶存在f(n-2)种走法，所以f(n)=f(n-1)+f(n-2);
继续递推，完成n-1级台阶的最后一步时之前肯定走了n-2或n-3级台阶，再继续递推，走完n-2级台阶的最后一步时之前肯定走了n-3或n-4级台阶，
一直递推下去，则有：f(n) = f(n-1)+f(n-2) , f(n-1) = f(n-2)+f(n-3) , f(n-2) = f(n-3)+f(n-4) , f(n-3) = f(n-4)+f(n-5) , ...... , f(4) = f(3)+f(2) , f(3) = f(2)+f(1) 至此，递推结束。
那么如果只有一个台阶只有一种解法f(1)=1;f(2)=2有两种可以一次一级台阶也可以一次跨两个台阶
*/
int fun(int n)
{
if(n<=2)
return n;
else
return fun(n-1)+fun(n-2);
}
int main() {
int n;
int cnt=0;
scanf("%d",&n);
cnt=fun(n);
printf("%d\n",cnt);
}
//法二循环
int main()
{
int n;
int a[50]={0};
int cnt=0;
scanf("%d",&n);
a[0]=0;
a[1]=1;
a[2]=2;
for(int i=3;i<=n;i++)
{
a[i]=a[i-1]+a[i-2];
}
printf("%d\n",a[n]);
}
C语言刷题 文章被收录于专栏
自己从头开始刷的C语言
查看11道真题和解析