用C ++爬楼梯

  • Z时代
  • 2024-01-10
  • 分类：综合

有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

    以上是 用C ++爬楼梯 的全部内容， 来源链接： utcz.com/z/331497.html

    回到顶部