金寨地震,揭阳招聘,条形码打印机
原创
2018-03-18
问题描述：
有N阶台阶，每一步可以走1步台阶或者2步台阶，求出走到第N阶台阶的方法数。
解题思路：
1 2
1 2 1 2
1 2 1 2 1 2 1 2
…….. ........
如上，建立一棵根节点为1和一棵根节点为2的二叉树，分别表示台阶第一步跨1步和跨2步，
第二层各有两种选择，分别是跨1步和2步，接下来的每一层都有这两种选择，如何跨
越的阶数等于N，计数变量+1，如果大于N，返回继续走其他路径。
(由于n到45左右时数据已经爆炸，这种暴力递归法在n较大时系统出不来数据了)
我要评论 1 #include<stdio.h>
2
3 int count; //计数变量
4
5 void sos(int n,int step)
6 {
7 if(step>n) //大于n，这种方法不行
8 return;
9 if(step==n)
10 {
11 count++;
12 return;
13 }
14
15 sos(n,step+1); //树1
16 sos(n,step+2); //树2
17 }
18
19 int main()
20 {
21 int n;
22 scanf("%d",&n); //n阶台阶
23
24 sos(n,0);
25 printf("%d",count);
26 return 0;
27 }
2. 动态规划法
有一个规律： F（n）= F（n-1）+ F（n-2）；
F（n）表示当有n阶台阶时有F（n）种方法；比如F（1）= 1；F（2）= 2；F（3）= F（1）+ F（2）= 3；
下面我用我的思路尽可能让大家理解这个公式：
1. 可以这样想，需要跨越n层阶梯，那么第一步我跨1层阶梯，那么剩下n-1层阶梯，跨越这n-1阶台阶的方法
就有F（n-1）方法； 同理，第一步跨2层阶梯，那么跨越剩下的n-2层阶梯就有F（n-2）种方法。
所以跨越n层阶梯的方法数 F（n）= F（n-1）+ F（n-2）；
2. 如果上面大家不理解，还可以这样理解，假如我们已经知道了F（n-1）和F（n-2），求F（n）；
在F（n-2）的基础上，我们可以通过一次跨2层阶梯到达第n层，也可以通过先跨1步，再跨1步的方式到达
第n层。 我们可以这样理解，如果一次性跨2层阶梯，我们只是在每一种跨越n-2层阶梯方式的基础上再加上
2就能到达第n层阶梯了，所以方法还是F（n-2）；
如果先跨1步，这样加上原来的n-2步，就一共走了n-1步了，方法数就是F（n-1）了，然后再跨多1步，同
上，我们只是在每一种跨越n-1层阶梯方式的基础上再加上1就能到达第n层阶梯了，所以方法还是F（n-1）。
希望这样说大家能理解。
如有疑问和建议，非常欢迎大家发表评论。
1 #include<stdio.h>
2 #include<stdlib.h>
3
4 int sos(long long *arr,int n)
5 {
6 if(n<0)
7 return 0;
8 if(n==0 || n==1 || n==2)
9 return n;
10
11 if(arr[n-1]==0) //等于0表示没有被算出
12 arr[n-1]=sos(arr,n-1); //没有被算出,就先算出
13
14 if(arr[n-2]==0) //同理
15 arr[n-2]=sos(arr,n-2);
16
17 return arr[n-1]+arr[n-2]; //等到算出arr[n-1]和arr[n-2]后就可以算出arr[n]了
18 }
19
20 int main()
21 {
22 int n;
23 scanf("%d",&n); //输入台阶数
24
25 long long *arr;
26 arr=(long long *)malloc(sizeof(long long)*(n+1)); //分配n+1个空间
27
28 int i;
29 for(i=0;i<=n;i++) //数组全部元素置0
30 arr[i]=0;
31
32 printf("%I64d",sos(arr,n));
33
34 free(arr);
35 return 0;
36 }
版权声明：本文为原创文章，转载时请标注：
如对本文有疑问，请在下面进行留言讨论，广大热心网友会与你互动！！ 点击进行留言回复
如何在没有core文件的情况下用dmesg+addr2line定位段错误
用QT制作3D点云显示器——QtDataVisualization
网友评论