資料結構
網路
關係資料庫管理系統 (RDBMS)
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C語言程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
服裝學
法學C++爬樓梯
假設有n階樓梯。一個人要從第1階走到第n階。一次最多能跨越的臺階數也是給定的。根據這些資訊，我們需要找到到達第n階樓梯的所有可能方法。假設一個人每次最多能跨越兩階樓梯。那麼我們可以找到遞迴關係來解決這個問題。一個人可以從(n-1)階或(n-2)階走到第n階。所以ways(n) = ways(n-1) + ways(n-2)。
例如，樓梯數為10，一次最多能跨越的臺階數為2，則輸出將是89種可能的方法。
要解決這個問題，請遵循以下步驟：
- 定義一個與樓梯數大小相同的陣列count
- count[0] := 1
- 對於 i := 2 到 stair -1，執行：
- count[i] := 0
- 對於 j = 1 到 i 且 j <= max，執行：
- count[i] := count[i] + count[i - j]
- 返回 count[stair - 1]
讓我們來看一下實現，以便更好地理解
示例 (C++)
#include<iostream>
using namespace std;
int stairClimbWays(int stair, int max){
int count[stair]; //fill the result stair using bottom up manner
count[0] = 1; //when there are 0 or 1 stair, 1 way to climb
count[1] = 1;
for (int i=2; i<stair; i++){ //for stair 2 to higher
count[i] = 0;
for(int j=1; j<=max && j<=i; j++)
count[i] += count[i-j];
}
return count[stair-1];
}
int countWays(int stair, int max){ //person can climb 1,2,...max stairs at a time
return stairClimbWays(stair+1, max);
}
int main (){
int stair, max;
cout << "Enter number of stairs: "; cin >> stair;
cout << "Enter max stair a person can climb: "; cin >> max;
cout << "Number of ways to reach: " << countWays(stair, max);
}輸入
Stairs = 10 Max stairs a person can climb: 2
輸出
Enter number of stairs: 10 Enter max stair a person can climb: 2 Number of ways to reach: 89
更新於: 2020年4月28日
562 次瀏覽
廣告