我试图用python编写一个代码,用于以下内容:有n个楼梯。我想显示从楼梯1到达楼梯n的不同方式(不是总路径数)。这里的问题是我一次能跳过不超过米的楼梯。请帮忙。注:m和n由用户输入。 下面的代码显示了方法的总数。但不是所有不同的方式都是:
# A program to count the number of ways to reach n'th stair
# Recursive function used by countWays
def countWaysUtil(n,m):
if n <= 1:
return n
res = 0
i = 1
while i<=m and i<=n:
res = res + countWaysUtil(n-i, m)
i = i + 1
return res
# Returns number of ways to reach s'th stair
def countWays(s,m):
return countWaysUtil(s+1, m)
# Driver program
s,m = 4,2
print "Number of ways =",countWays(s, m)
这似乎是一种广义的Fibonacci序列,只是不是{}而是{}。您的代码应该可以工作,但是对于较大的
n
值,大量的递归会给您带来非常高的复杂度(如果我没弄错的话,大约是O(m^n)
的顺序)。解决这类问题的关键是在列表中记住较低输入值的结果:输入和输出示例:
^{pr2}$如果需要实际的步骤序列,而不是求和,则可以使用嵌套列表理解轻松地相应地调整代码:
请注意,您可能需要对代码进行一点调整,例如,“最多跳过m个步骤”是否意味着您可以执行}步骤,但如果您对某些输入有预期的结果,那么进行这些“一次性”调整应该很容易。在
1..m
或{相关问题 更多 >
编程相关推荐