黑马程序员技术交流社区
标题:
求解答,微软面试题~!才学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