打印的方式來達到第n個樓梯

Question

我最近遇到這個問題在接受採訪時

有n樓梯，站在底部的人想要達到頂峯。該人一次可爬上1個樓梯或2個樓梯。

打印所有可能的方法人可以達到頂部。

例如，n=4輸出：

1 2 3 4 
1 2 4 
1 3 4 
2 3 4 
2 4 

但我無法正確地編寫此。如何爲此編碼解決方案？

Answer 1

您可以嘗試一些遞歸解決方案，您可以通過遞歸調用CanClimb(n-1)和CanClimb(n-2)來可視化可能的方式。在C＃

樣品溶液：

public static void ClimbWays(int n, int currentIndex, int[] currectClimb) 
{ 
    if (n < 0) return; 

    if (n == 0) 
    { 
     for (var i = currentIndex - 1; i >= 0; i--) 
     { 
      Console.Write(currectClimb[i] + " "); 
     } 

     Console.WriteLine(); 
     return; 
    } 

    currectClimb[currentIndex] = n; 
    ClimbWays(n - 1, currentIndex + 1, currectClimb); 
    ClimbWays(n - 2, currentIndex + 1, currectClimb); 
} 

輸出爲ClimbWays(4, 0, new int[4]);：

1 2 3 4 
2 3 4 
1 3 4 
1 2 4 
2 4 

如果你想算了算他們，你可以使用可以反覆計算衆所周知的斐波那契序列：

public static int Fibonacci(int n) 
{ 
    int a = 0; 
    int b = 1; 
    // In N steps compute Fibonacci sequence iteratively. 
    for (int i = 0; i < n; i++) 
    { 
     int temp = a; 
     a = b; 
     b = temp + b; 
    } 
    return a; 
} 

Answer 2

要打印多少種方式，您可以先了解如何計算方式的數量，調整，使每個「計數」將代替打印算了算：

D(0) = 1 
D(-1) = 0 
D(i) = D(i-1) + D(i-2) 

若要調整爲實際的打印，需要「記住」你所做的選擇，並按照同樣的邏輯。僞代碼：

printWays(curr, n, soFar): 
    if curr > n: 
     return 
    soFar.append(curr) 
    if n == curr: 
     print soFar 
     soFar.removeLast() 
     return 
    printWays(curr+1,n,soFar) 
    printWays(curr+2,n,soFar) 
    soFar.removeLast() 

的理念是：

• SOFAR是當前一系列你做的步驟。
• curr是您目前的步驟。
• n是你需要去的最後一個樓梯。
• 在每個點上，您要麼爬上一個或兩個樓梯。你檢查兩個選項。