穿越楼梯的不同方法

2024-03-29 10:05:02 发布

您现在位置:Python中文网/ 问答频道 /正文

我试图用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)

Tags: ofto代码numberreturn方式resprogram
1条回答
网友
1楼 · 发布于 2024-03-29 10:05:02

这似乎是一种广义的Fibonacci序列,只是不是{}而是{}。您的代码应该可以工作,但是对于较大的n值,大量的递归会给您带来非常高的复杂度(如果我没弄错的话,大约是O(m^n)的顺序)。解决这类问题的关键是在列表中记住较低输入值的结果:

def ways_up_stairs(n, m):
    ways = [1] + [None] * n
    for i in range(1, n+1):
        ways[i] = sum(ways[max(0, i-m):i])
    return ways[n]

输入和输出示例:

^{pr2}$

如果需要实际的步骤序列,而不是求和,则可以使用嵌套列表理解轻松地相应地调整代码:

def ways_up_stairs(n, m):
    ways = [[(0,)]] + [None] * n
    for i in range(1, n+1):
        ways[i] = [w + (i,) for ws in ways[max(0, i-m):i] for w in ws]
    return ways[n]

print(ways_up_stairs(4,2))
# [(0, 2, 4), (0, 1, 2, 4), (0, 1, 3, 4), (0, 2, 3, 4), (0, 1, 2, 3, 4)]

请注意,您可能需要对代码进行一点调整,例如,“最多跳过m个步骤”是否意味着您可以执行1..m或{}步骤,但如果您对某些输入有预期的结果,那么进行这些“一次性”调整应该很容易。在

相关问题 更多 >