遍歷樓梯的不同方法

我想在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)

來源

2017-09-03 Rik

你的問題是什麼？這太寬泛了。你有什麼嘗試？什麼沒有用？ – 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步驟，但如果您對某些輸入有預期的結果，那麼使這些「一次性」修改應該很容易。

來源

2017-09-04 08:26:50

非常感謝！這是我正在尋找的答案。 – Rik

遍歷樓梯的不同方法

回答

相關問題