精华内容
下载资源
问答
  • 题目标题: 第39级台阶 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右...


    题目标题: 第39级台阶

    小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!

    站在台阶前,他突然又想着一个问题:

    如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完39级台阶,有多少种不同的上法呢?


    请你利用计算机的优势,帮助小明寻找答案。

    要求提交的是一个整数。
    注意:不要提交解答过程,或其它的辅助说明文字。

     

    思路: 这题很明显是一道递归的题目。 f(n)为n阶台阶的总走法数,则f(n) = 以下四种情况走法数的总和

    (1)第一次左脚走一级,最后一次右脚走一级,中间剩余n-2阶台阶的走法有f(n-2)种

    (2)第一次左脚走一级,最后一次右脚走两级,中间剩余n-3阶台阶的走法有f(n-3)种.

    (3)第一次左脚走两级,最后一次右脚走一级,中间剩余n-3阶台阶的走法有f(n-3)种

    (4)第一次左脚走两级,最后一次右脚走两级,中间剩余n-4阶台阶的走法有f(n-4)种

    即有: f(n) = f(n-2) + 2*f(n-3) + f(n-4), 求f(39)即可

    但是这样写成递归的话栈会溢出,所以可以将其改成循环的形式,如下所示代码:

     1 #include<iostream>
     2 
     3 using namespace std;
     4 
     5 int f[40];  //使用递归会导致栈溢出,所以使用数组保存结果,用循环代替递归
     6 
     7 int main()
     8 {
     9     //先手算出前4项
    10     f[2] = 1;
    11     f[3] = 2;
    12     f[4] = 2;
    13     f[5] = 4;
    14     for (int i = 6; i < 40; ++i)
    15         f[i] = f[i - 2] + 2 * f[i - 3] + f[i - 4];
    16 
    17     cout << f[39] << endl;
    18 
    19     return 0;
    20 }

    最终结果:51167078

    转载于:https://www.cnblogs.com/FengZeng666/p/10551798.html

    展开全文
  • /*小明刚刚看完电影《第39级台阶》 * 离开电影院的时候,他数了数礼堂前的台阶数, * 恰好是39级! 站在台阶前,他突然又想着一 * 个问题: 如果我每一步只能迈上1个或2个台阶。 * 先迈左脚,然后左右交替,...

    /*小明刚刚看完电影《第39级台阶》
    * 离开电影院的时候,他数了数礼堂前的台阶数,
    * 恰好是39级! 站在台阶前,他突然又想着一
    * 个问题: 如果我每一步只能迈上1个或2个台阶。
    * 先迈左脚,然后左右交替,最后一步是迈右脚,
    * 也就是说一共要走偶数步。那么,上完39级台阶,
    * 有多少种不同的上法呢?
    * 请你利用计算机的优势,帮助小明寻找答案。
    */
    public class Di39JiTaiJie {
    public static int f(int n,int k) {
    if(n==0 && k %2 ==0) return 1;//k是走的步数
    if(n<0) return 0;
    int x = f(n-1,k+1)+f(n-2,k+1);
    return x;
    }
    public static void main(String [] args) {
    System.out.println(f(39,0));

    }
    

    }

    展开全文
  • 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也...

    小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!

    站在台阶前,他突然又想着一个问题:
    如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。那么,上完39级台阶,有多少种不同的上法呢?

    请你利用计算机的优势,帮助小明寻找答案。

    答案:51167078
    
    #include <iostream>  
    using namespace std;  
    int sum;  //记录走法的总数
    void dfs(int n,int k)  //n走到了第几层,k表示花了几步
    {  
        if(n>39) return;  
        if(n==39&&k%2==0)  //走到三十层的时候,并且只花了偶数步
        {  
            sum++;  
            return;  
        }  
        dfs(n+1,k+1); //一步走一层 
        dfs(n+2,k+1);  //一步走两层
    }  
    int main()  
    {  
        sum=0;  
        dfs(0,0);  //
        cout<<sum<<endl;  
        return 0;  
    }  
    
    #include <iostream>  
    using namespace std;  
    int sum;  //记录走法的总数
    void dfs(int n,int k)  //n走到了第几层,k表示花了几步
    {  
        if(n<0) return;  
        if(n==0&&k%2==0) 
        {  
            sum++;  
            return;  
        }  
        dfs(n-1,k+1);
        dfs(n-2,k+1); 
    }  
    int main()  
    {  
        sum=0;  
        dfs(39,0);  //
        cout<<sum<<endl;  
        return 0;  
    }  
    
    展开全文
  • 蓝桥杯39级台阶

    2018-03-25 19:37:26
    小明刚刚看完电影《第39级台阶》。离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级。站在台阶前,他突然又想着一个问题:如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也...

    小明刚刚看完电影《第39级台阶》。离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级。

    站在台阶前,他突然又想着一个问题:

    如果我每一步只能迈上1个或2个台阶。

    先迈左脚,然后左右交替,最后一步是迈右脚,也就是说一共要走偶数步。

    那么,上完39级台阶,有多少种不同的上法呢?

    请你利用计算机的优势,帮助小明寻找答案。


    要用到间接递归,两个函数相互调用

    解:

    public class Main {
    
    	static int step = 39;
    
    	static int left(int n) {
    		// 因为最后一步是迈右脚,所以跳出的判断是放在左脚
    		if (n == step)// 当步数刚好为39时,算是一种走法
    			return 1;
    		if (n > step)// 当步数大于39时,不算,要退回去换一种走法
    			return 0;
    		return right(n + 1) + right(n + 2);// 左脚可以迈一步或两步
    	}
    
    	static int right(int n) {
    		return left(n + 1) + left(n + 2);// 右脚可以迈一步或两步
    	}
    
    	public static void main(String[] args) {
    		System.out.println(left(0));// 先迈左脚
    	}
    }
    展开全文
  • 小明刚刚看完电影《第39级台阶》。离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,...
  • #include"stdio.h" //定义全局变量 int res=0; void f(int n,int step) { if(n<0){ return;... //灵活运用斐波那契数列,递归进行计算 f(n-1,step+1); f(n-2,step+1); } int main() { ...
  • 【问题描述】小明刚刚看完电影《第39级台阶》。离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!站在台阶前,他突然又想着一个问题:如果我每...分析:递归寻找走完39级台阶用了偶数步的数量public class Main...
  • 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,...
  • 题目标题: 第39级台阶 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右...
  • 39级台阶——蓝桥杯

    2019-03-14 13:25:58
    小明刚刚看完电影《第39级台阶》。离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也...
  • 39级台阶: 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步...
  • 题目:第39级台阶(13年) 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右...
  • 蓝桥杯39台阶

    2016-06-08 09:20:12
    3、题目标题: 第39级台阶(满分8分) 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。...
  • 39级台阶 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是...
  • 问题描述:小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是...
  • 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也...
  • 小明刚刚看完电影《第39级台阶》。离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也...
  • 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,...
  • 可以说是自己做的第一道递归题了Problem Description小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个...
  • 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级!站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶,先迈左脚,然后左右交替,最后一步是迈右脚,也...
  • 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后一步是迈右脚,也...
  • 39级台阶 小明刚刚看完电影《第39级台阶》,离开电影院的时候,他数了数礼堂前的台阶数,恰好是39级! 站在台阶前,他突然又想着一个问题: 如果我每一步只能迈上1个或2个台阶。先迈左脚,然后左右交替,最后...

空空如也

空空如也

1 2 3
收藏数 48
精华内容 19
关键字:

蓝桥杯39级台阶递归