C-阶梯算法问题

C-阶梯算法问题

清晨说ぺ晚安 发布于 2017-09-30 字数 65 浏览 1086 回复 2

50个阶梯,你一次可以上一阶或两阶,走上去,共有多少种走法?

发布评论

需要 登录 才能够评论, 你可以免费 注册 一个本站的账号。

评论(2

偏爱自由 2017-10-15 2 楼

数学归纳法:

假设现在有K(K>=4)个阶梯,共有M种走法,现将M划分为三类a,b,c,分别表示走的最后一步迈的是1,2,3个台阶,那么有:a+b+c=M。现在只需求出有K+1个阶梯的时候有多少种走法。
(1)如果K阶梯时最后一步迈了一阶,现在多了一个阶梯,那我可以再迈一阶(1,1),或者直接迈两阶(2,0)到达终点,所以在a类情况下,K+1个阶梯共有2a种走法。
(2)如果K阶梯时最后一步迈了两阶,现在多了一个阶梯,那我可以再迈一阶(2,1),或者直接迈三阶(3,0)到达终点,所以在b类情况下,K+1个阶梯共有2b种走法。
(3)如果K阶梯时最后一步迈了三阶,现在多了一个阶梯,那么我只能再迈一阶(3,0)到达终点,所以在c类情况下,K+1个阶梯共有c种走法。
综上,K+1个阶梯的情况共有2a+2b+c=(2M-c)种走法。
所以接下来就是计算c的值,因为c表示有K个阶梯的情况下,且最后一步迈三阶的情况数(即c的值),该值等于有(K-3)个台阶的时候的走法总数(不明白的自己稍微理解下,就是这么个情况)。

当有1个台阶时,共1种走法
当有2个台阶时,共2种走法
当有3个台阶时,共4种走法
当有4个台阶时,共7种走法

int a[49];
a[0]=1,a[1]=2,a[2]=4,a[3]=7;

for(int i=4,i<50,i++ )
{
a[i] = 2a[i-1] - a[i-4] ; //即 2M - c 或 M(K+1)=2M(K)-M(k-3)
}

a[49]即是共有50个台阶的总走法数

PS: 其实还有一种解法
因为c表示有K个阶梯的情况下,且最后一步迈三阶的情况数(即c的值),该值等于有(K-3)个台阶的时候的走法总数。
a表示有K个阶梯的情况下,且最后一步迈一阶的情况数(即a的值),该值等于有(K-1)个台阶的时候的走法总数。
a表示有K个阶梯的情况下,且最后一步迈二阶的情况数(即b的值),该值等于有(K-2)个台阶的时候的走法总数。
故 M(K) = a+b+c;
M(k-1)= a;
M(k-2)= b;
M(k-3)= c;

因为M(K+1) = 2a+2b+c; 即M(K+1) = M(K) + M(K-1) + M(K-2) 也=2*M(K)-M(k-3)

后面的等式就是上面的循环实现,前面的等式可以将上面的循环可以改为:
for(int i=4,i<50,i++ )
{
a[i] = a[i-1] + a[i-2] + a[i-3] ;//即 M(K+1)=M(K)+M(K-1)+M(K-2)
}

这是我回答的一次可以走三个阶梯的情况:
走两个可以这么算:M(K+1) = 2a + b = M(K) + M(K-1)
int a[49];
a[0]=1,a[1]=2,a[2]=3,a[3]=5;

for(int i=4,i<50,i++ )
{
a[i] = a[i-1] + a[i-2] ; //即 2M(K+1)=M(K)+M(k-1)
}

偏爱自由 2017-10-12 1 楼

#include "stdafx.h"
#include "iostream.h"
int Katrina(int n)
{
if(n==0)
return 0;
else
if(n==1)
return 1;
else if(n==2)
return 2;
else if(n>2)
return Katrina(n-1)+Katrina(n-2);
}

void main()
{

int m,result=0;
cout<<"cout the m "<<endl;
cin>>m;
result=Katrina(m);
cout<<result<<endl;
}

网上的这个算法,输入40多层都没问题,50层就算不出来。
经过验证:果然是两个问题造成的。1.递归层次太多,栈溢出。2. 32整数表示不了结果。换成非递归的,64位整数,速度快很多了,而且正常显示了。
居然不知道64位整型怎么写,以及printf %I64d怎么写,找李老师帮忙了。我基础还是不扎实啊。

#include "stdafx.h"
#include "iostream.h"

void main()
{
__int64 a1=1,a2=2,a3=0;
for (int i=3;i<50;i++)
{
a3=a1+a2;
a1=a2;
a2=a3;
}
printf("result:%I64d",a3);
}

结果:12586269025。