0

我把自己困在递归函数中，并在网上搜索了一些问题，以更多地了解它们是如何工作的。我遇到了一个叫做楼梯的问题，这是为它设计的代码-

#include<bits/stdc++.h>

using namespace std;

int staircase(int n){
    if(n<0){            //Base Case 1
        return 0;
    }

    if(n==0){           //Base Case 2
        return 1;
    }

    int count = 0;
    count += staircase(n-1);    //Stepping 1 step
    count += staircase(n-2);    //Stepping 2 step
    count += staircase(n-3);    //Stepping 3 step

    return count;
}

int main(){
    int n;
    cout<<"Enter number of stairs\n";

    cin>>n;

    cout<<"No of ways to climb stairs are ";
    cout<<staircase(n)<<endl;

    return 0;
}

如果有人可以帮助我从“int count”{我已经理解基本案例}中理解楼梯功能，那将非常有帮助！

4

2 回答 2

0

在每个函数调用中，您都有n楼梯要爬。一次尝试，你可以爬一个楼梯，两个楼梯或三个楼梯。因此，您再次调用该函数n = n - 1并将其结果添加到count. 这个调用代表你只爬了一个楼梯（还有n-1楼梯要爬）的情况。同样，您将爬 2 层楼梯后可能n = n - 2的方式数 ( ) 和爬 3 层楼梯后的可能方式数( ) 相加n = n - 3。请注意，这个函数是指数函数，如果 n 是一个很大的数字，它会花费很长时间。您可以通过使用 memoization 来解决这个问题。

#include<bits/stdc++.h>

using namespace std;

const int MAX_SIZE = 100;

long long mem[MAX_SIZE];

int staircase(int n){
    if(n<0){            //Base Case 1
        return 0;
    }

    if(n==0){           //Base Case 2
        return 1;
    }

    if (mem[n] != -1)
        return mem[n];

    int count = 0;
    count += staircase(n-1);    //Stepping 1 step
    count += staircase(n-2);    //Stepping 2 step
    count += staircase(n-3);    //Stepping 3 step

    return mem[n] = count;
}

int main(){

    for (int i = 0; i < MAX_SIZE; i++)
        mem[i] = -1;

    int n;
    cout<<"Enter number of stairs\n";

    cin>>n;

    cout<<"No of ways to climb stairs are ";
    cout<<staircase(n)<<endl;

    return 0;
}

这是使用 memoization 后的代码。请注意，如果没有记忆，计算所需的时间将非常长。n = 50例如，尝试运行您的代码，并尝试使用此代码。另请注意，即使您可以设置MAX_SIZE为 100,000 之类的值，结果也会非常大n = 100。如果你真的想计算 的大值的结果n，你可以使用所谓的“大整数”。

于 2020-04-20T21:17:44.580 回答
0

从本质上讲，这段代码试图找出有多少种方法可以到达第 n 步。如果您可以执行 1、2 或 3 个步骤，那么您可以从步骤 n-1、n-2 和 n-3 进入步骤 n。因此，到达第 n 步的路数是到达第 n-1、n-2 和 n-3 步的路数之和。该代码使用递归来实现这一点，通过使用不同的步骤号调用自身 3 次。

于 2020-04-20T21:14:41.270 回答