黑马程序员技术交流社区

标题: 求解答,微软面试题~!才学C一个星期 [打印本页]

作者: yu2323637    时间: 2016-5-28 10:28
标题: 求解答,微软面试题~!才学C一个星期
题目:一只青蛙一次可以跳一级台阶,也可以一次跳两级台阶,求该青蛙跳上n级台阶总共有多种跳法。

目前就学到for循环,求到目前掌握的知识的解答方式~
作者: 酱油    时间: 2016-5-28 19:23
这个好像是个斐波拉切数列。。。我忘了。。
作者: 王子鹏    时间: 2016-5-29 10:53
本帖最后由 王子鹏 于 2016-5-29 11:03 编辑

首先 数学分析:  如果有一层  方法有一种                   两层          2种
            三层         3中
            四层          5种
           五层           8中
  看出逻辑了吗


代码编辑:
递归实现:
public int JumpFloor(int n)  //一共要跳的层数
     {

        
         if (n < 0)                 
             return 0;
         int[] fibArry = { 0, 1, 2 };

         //如果层数小于3
         if (n < 3)
             return fibArry[n];


      //层数大于3 时  都是上一层的数加上上一层
         return JumpFloor(n - 1) + JumpFloor(n - 2);
     }


非递归实现:
public int JumpFloor(int n)
        {

          //如果层数小于3
            if (n < 0)
                return 0;
            int[] fibArry = { 0, 1,2 };   //数组角标分别是 0 1 2  而楼层不会是0  所以有个0
            if (n < 3)
                return fibArry[n];   
            long count = 0;       //总共的方法
            long fibFirst=1;
            long fibTwo=2;
            for (int i = 3; i <= n; i++)        //开始循环
            {
                count = fibFirst + fibTwo;  // 将一层的方法加上2层的方法数之和  等于第三层的方法数和
                fibFirst=fibTwo ;               //  将第二层的赋值给第一层  作为下次的第一层

                fibTwo = count;                //  将第三层的赋值给第二层  作为下次的第二层
            }
            return count ;   
        }




希望能帮到你 共同学习 加油!



作者: 非洲小孩    时间: 2016-5-29 22:59
一楼是我们班的吗?大神啊
作者: oyjs1989    时间: 2016-5-30 23:29
我的算法和1楼不一样
//
//  main.c
//  青蛙跳台阶的算法
//
//  Created by Lennon on 16/5/29.
//  Copyright © 2016年 Lennon. All rights reserved.
//

#include <stdio.h>

int main() {
    // insert code here...
    int n = 0 ,totalsum = 0;
    printf("请输入台阶数:");
    scanf("%d",&n);
    //   实际方法为一串组合累加  1+Cn 1 +Cn-1 2+......+Cn/2 n/2
    //   每多跳2层,跳的次数就减少1,数组下标减少1, 而两层的次数+1
    //   比如 输入5  第一次 假定为全部为单层  方法为1
    //             第二次 假定一次双层     方法为C下标为n-1  商标为n的组合的值 即 n-1 4
    //             第三次  假定二次双层     方法次数  为n-2*n-3   即为 6
    //   依次类推
    for(int i = 0;i<=n;i++,n--) {      //每多一次2级跳 i+1    跳的次数则减1   n-1
        int k = n;
        int sum = 1;
        // 跳i次双层时  可以有几种方法
        for(int j = 1;j<=i;j++){
            sum = sum*k/j;
            k--;
        }
        // 统计全部方法
        totalsum = totalsum+sum;
    }
    // 输出方法
    printf("青蛙可以调的次数是%d\n",totalsum);
    return 0;
}

作者: Hyperion    时间: 2016-5-31 21:45
顶一下!




欢迎光临 黑马程序员技术交流社区 (http://bbs.itheima.com/) 黑马程序员IT技术论坛 X3.2