有一楼梯共n级,刚开始时你在第一级,若每次只能跨上一级或二级,要走上第n级,共有多少种走法?
现在给你一个正整数n(0<n<40),请你输出不同的走法数。
def digui(n):
return (n == 1 or n == 2) and 1 or (digui(n-1) + digui(n-2))
print digui(n)
此程序可改写为:
def digui(n: int) -> int:对于主程序语句
return (n == 1 or n == 2) and 1 or (digui(n - 1) + digui(n - 2))来说,它由被or分隔开的两个语句构成。首先or左边的语句
return (n == 1 or n == 2) and 1此语句相当于使用if条件语句做的一个基本条件,即用来终结递归语句的进行,防止无限递归的发生。相当于:
意思是当楼梯只有一层或两层时,直接输出1,因为只有一种走法(1层时原地不动,2层时只能向上走一步)。
然后or右边的语句
or digui(n - 1) + digui(n - 2)这句中的or相当于if语句中的
else:即若不属于
n == 1 or n == 2的情况时,开始执行如下递归步骤,步骤为
这里要有一个递归思想,假设有n阶楼梯,走第一步时只有两种选择,要么跨两阶要么跨一阶,那么:
第一步跨一阶:
那么此时还剩(n - 1)阶楼梯,这n - 1阶的跨楼方法自然变成digui(n - 1)
第一步跨两阶:
那么此时还剩(n - 2)阶楼梯,这n - 2阶的跨楼方法自然变成digui(n - 2)
所以对于n阶楼梯来说,总共的跨楼方法是
digui(n - 1) + digui(n - 2)种。
对于n - 1或n - 2级楼梯来说,他们各自又会有
digui(n - 1) + digui(n - 2) # 注意这里的n代表的是的n - 1或者n - 2,而不是 # 最初的n。 种方法,如此循环下去,便形成了一个递归,直到楼梯数目n减为1或者2时,进入基本条件,递归终止。
说句题外话,其实此问题就是一个斐波那契数列的应用,抽象成数学问题就是:
有斐波那契数列 1,1,2,3,5,8,13,21,…… 从第三个数开始,每个数都是前两个数之和,求第n个数的值。
如果变成这样的问题可能更好思考一些。
谢谢,不过只能采纳一个答案,所以……
你考虑得很周到,是我的疏忽,其实原题中还有一句话我没复制:
如n=2,则输出1(你只有一种走法,走一步,从第一级到第二级)
原题就是求n-1阶楼梯的走法
def digui(n):
return n if n<=2 else digui(n-1)+digui(n-2)
print digui(n-1)
这个程序和你给出的程序结果基本一致,除了n==1,人在第一级楼梯上原地不动应返回 0
我说的是最后还剩下两级楼梯时有两种走法,你那个程序少算了一次digui(n-2),结果就是digui(n)-digui(n-2)=digui(n-1),但不能作出一个比较直观的解释。
对别人已经说过的意思进行“艺术加工"居然能算专业,呵呵