跳台阶问题-经典递归练习题-C++

Bertha 。 2022-12-11 14:00 125阅读 0赞

将台阶分解，一次可以跳1节或者2节，所以就是`return f(n - 1) + f(n - 2)`分解成两部分

![在这里插入图片描述][20201002213035481.png_pic_center]

所以，如果能走一格，就还剩下三个。走两个，就还剩下两个。最后到边界条件。  
Java：

/** * 案例2 分治算法 走楼梯 * 一个台阶总共有n级，如果一次可以走1级，也可以一次走2级，求总共有多少种走法。 * 分析： * 如果只有1级台阶，则只有一种走法，如果有2级台阶，则有2种走法：一次走1级或一次走2级 * 假设有三级台阶，则可以一次走1级或一次走2级，如果一次走1级则还剩2级台阶，产生2种走法（上面已经说了）， * 一次走2级则还剩1级只有一种走法，总共的走法就是2+1=3. * 3 * /\ *剩余级数 2 1 * 走法 2 + 1 = 3 * 由此可见，n>2时，走法数就是第一次走1级后剩余级数的走法数+第一次走2级后剩余级数的走法数，这正是递归 *可以归纳出公式： * f(n) = 1 n=1 * = 2 n=2 * =f(n-1) + f(n-2) n>2 * 观察公式可发现，这其实是斐波那契数列！ * * **/
    public class zoulouti { 
        public static void main(String[] args){ 
            int res = solution(3);
            System.out.println(res);
        }
     
        static int solution(int n){ 
            if (n==1) return 1;
            if (n==2) return 2;
            return solution(n-1) + solution(n-2);
        }
    }

C++：

// Recursion-走楼梯.cpp : 此文件包含 "main" 函数。程序执行将在此处开始并结束。
    //
    
    #include <iostream>
    using namespace std;
    int dfs(int n)
    { 
        if (n == 1) return 1;
        if (n == 2) return 2;
        return dfs(n - 1) + dfs(n - 2);
    }
    int main()
    { 
        int f, ans;
        cin >> f;
        ans = dfs(f);
        cout << ans << endl;
        cout << "hello world" << endl;
        return 0;
    }
    
    // 运行程序: Ctrl + F5 或调试 >“开始执行(不调试)”菜单
    // 调试程序: F5 或调试 >“开始调试”菜单
    
    // 入门使用技巧: 
    // 1. 使用解决方案资源管理器窗口添加/管理文件
    // 2. 使用团队资源管理器窗口连接到源代码管理
    // 3. 使用输出窗口查看生成输出和其他消息
    // 4. 使用错误列表窗口查看错误
    // 5. 转到“项目”>“添加新项”以创建新的代码文件，或转到“项目”>“添加现有项”以将现有代码文件添加到项目
    // 6. 将来，若要再次打开此项目，请转到“文件”>“打开”>“项目”并选择 .sln 文件

[20201002213035481.png_pic_center]: /images/20221123/20e8365b81b64b1ca4236cff8e66fae7.png