计算到达第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