用C ++爬楼梯
有n个楼梯。一个人会走到第1到第n阶。还给出了他/她一步可以越过的最大楼梯数量。有了这些信息,我们必须找到可能的方法去第n个楼梯。让我们考虑一个步骤,每个步骤最多可以跨越两个楼梯。因此我们可以找到递归关系来解决此问题。一个人可以从第(n-1)个楼梯或从第(n-2)个楼梯移至第n个楼梯。因此Ways(n)=Ways(n-1)+Ways(n-2)。
假设阶梯数为10,即一步可以跳的最大阶梯数为2,那么输出将是89种可能的方式。
为了解决这个问题,请遵循以下步骤-
定义与楼梯号相同大小的数组数
计数[0]:=1
对于我:=2到楼梯-1,做
count[i]:=count[i]+count[i-j]
count[i]:=0
当j=1到i并且j<=max;做
返回计数[楼梯-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