資料結構
網路
關係資料庫管理系統
作業系統
Java
MS Excel
iOS
HTML
CSS
Android
Python
C 程式設計
C++
C#
MongoDB
MySQL
Javascript
PHP
物理學
化學
生物學
數學
英語
經濟學
心理學
社會學
時尚學
法律學計算到達第 n 級臺階的方法
有 n 個臺階。一個人將從第 1 個臺階走到第 n 個臺階。還會給出他/她一次最多可以跨過臺階數的最大值。有了這些資訊，我們必須找到到達第 n 個臺階的可能方法。
讓我們考慮一下，可以每一步最多跨過兩個臺階。因此，我們可以找到遞迴關係來解決此問題。可以從第 (n-1) 個臺階或從第 (n-2) 個臺階移動到第 n 個臺階。因此，ways(n) = ways(n-1) + ways(n-2)。
輸入和輸出
Input: The number of stairs, say 10 the maximum number of stairs that can be jumped in one step, say 2 Output: Enter number of stairs: 10 Enter max stair a person can climb: 2 Number of ways to reach: 89
演算法
stairClimpWays(stair, max)
輸入 − 臺階數、一次最大跨越臺階數。
輸出 − 可以到達的可能方法數。
Begin define array count of size same as stair number count[0] := 1 count[0] := 1 for i := 2 to stair -1, do count[i] := 0 for j = 1 to i and j <= max; do count[i] := count[i] + count[i - j] done done return count[stair - 1] End
示例
#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);
}輸出
Enter number of stairs: 10 Enter max stair a person can climb: 2 Number of ways to reach: 89
更新於：16-Jun-2020
323 次瀏覽
廣告