求教:一个算法。N级台阶,可以一步跨一阶或两阶,问共有多少种走法?

发布网友发布时间：2022-04-18 14:10

我来回答

共3个回答

懂视网时间：2022-04-18 18:31

这篇文章主要介绍了Python解决N阶台阶走法问题的方法,简单描述了走台阶问题,并结合实例形式分析了Python使用递归与递推算法解决走台阶问题的相关操作技巧,需要的朋友可以参考下

本文实例讲述了Python解决N阶台阶走法问题的方法。分享给大家供大家参考，具体如下：

题目：一栋楼有N阶楼梯，兔子每次可以跳1、2或3阶，问一共有多少种走法？

Afanty的分析：

遇到这种求规律的问题，自己动动手推推就好，1阶有几种走法？2阶有几种走法？3阶有几种走法？4阶有几种走法？5阶有几种走法？

对吧，规律出来了！

易错点：这不是组合问题，因为第1次走1阶、第2次走2阶不同于第1次走2阶、第2次走1阶

下面是Python的递归实现代码：

def allMethods(stairs):
 '''''
 :param stairs:the numbers of stair
 :return:
 '''
 if isinstance(stairs,int) and stairs > 0:
 basic_num = {1:1,2:2,3:4}
 if stairs in basic_num.keys():
 return basic_num[stairs]
 else:
 return allMethods(stairs-1) + allMethods(stairs-2) + allMethods(stairs-3)
 else:
 print 'the num of stair is wrong'
 return False

当然也可以用非递归的方法来实现，下面就是基于递推法的代码：

def allMethod(stairs):
 '''''递推实现
 :param stairs: the amount of stair
 :return:
 '''
 if isinstance(stairs,int) and stairs > 0:
 h1,h2,h3,n = 1,2,4,4
 basic_num = {1:1,2:2,3:4}
 if stairs in basic_num.keys():
 return basic_num[stairs]
 else:
 while n <= stairs:
 temp = h1
 h1 = h2
 h2 = h3
 h3 = temp + h1 + h2
 return h3
 else:
 print 'the num of stair is wrong'
 return False

好的，

热心网友时间：2022-04-18 15:39

你算：走两阶时隔的这一阶，在N阶中隔的这一阶，最少有0种，最多有N/2种，后面自己看着算吧

热心网友时间：2022-04-18 16:57

#include <stdio.h>
#define max 100
int total = 0;
int out[max];

void print(int step)
{
int i;
printf("%d: ", total+1);
for (i=0; i < step; i ++)
printf("%d->", out[i]);
printf("|\n");
}

void find(int N, int step)
{
if (N == 0)
{
print(step);
total ++;
return;
}
if (N >= 1)
{
out[step]=1;
find(N-1, step+1);
}
if (N >= 2)
{
out[step]=2;
find(N-2, step+1);
}
}

int main()
{
unsigned int N;
scanf("%u", &N);
if (N >= max) return (1);//不超过100级
find(N, 0);
printf("total %d", total);
return 0;
}
迭代法计算，测试正确