遍历楼梯的不同方法

问题描述：

我想在python中编写以下代码：有n个楼梯。我想展示从楼梯1到达楼梯的不同方式（不是总数）。这里的接点是我可以一次跳过不超过m个楼梯。请帮忙。注意：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)

你的问题是什么？这太宽泛了。你有什么尝试？什么没有用？ – Carcigenicate

如果你有这个问题的实际规格，你会发布它吗？我必须同意@Carcigenicate，这是非常广泛的。 – GerryMcBride

答

这似乎是一种广义Fibonacci序列的，除非你有f(n) = f(n-1) + ... + f(n-m)，与其f(n) = f(n-1) + f(n-2)。你的代码应该可以工作，但是如果我没有弄错的话，大规模的递归会给你很大的复杂度，以适应更大的值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]

一些示例输入和输出：

print(ways_up_stairs(4,2)) # 5 
print(ways_up_stairs(4,3)) # 7 
print(ways_up_stairs(4,4)) # 8

如果你想实际步骤序列，没有资金，你可以很容易地适应相应的代码，使用嵌套列表理解：

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或1..m+1步骤，但如果您对某些输入有预期的结果，那么使这些“一次性”修改应该很容易。

非常感谢！这是我正在寻找的答案。 – Rik

遍历楼梯的不同方法

相关推荐