提问:一只青蛙一次可以跳上
1
级台阶,也可以跳上
2
级。求该青蛙跳上一个
n
级的台阶总共有多少种跳法。
由于打印了青蛙跳的步骤,所以运行速度非常慢。
import java.util.Date;
public class Frag {
public static int STEP;
public static int TOT = 0;
public static String tmpprint;
public static void goNextJump(int currentStep, int length, String print) {
if (currentStep == STEP) {
if (!print.equals(tmpprint)) {
TOT = TOT + 1;
System.out.println(print + "(TOT=" + TOT + ")");
tmpprint = print;
}
return;
} else {
if (currentStep + length <= STEP) {
print = print + "-->" + length;
currentStep = currentStep + length;
goNextJump(currentStep, 1, print);
goNextJump(currentStep, 2, print);
}
return;
}
}
public static int getTot(int step) {
STEP = step;
if (step == 0) {
return 0;
}
if (step == 1) {
return 1;
}
String print = "0";
goNextJump(0, 1, print);
goNextJump(0, 2, print);
return TOT;
}
public static void main(String[] args) {
Date start = new Date();
System.out.println(getTot(20));
Date end = new Date();
System.out.println(end.getTime() - start.getTime());
}
}
我的同事Vivi给出了强大的答案
/**
* @description 一只青蛙一次可以跳上 1 级台阶,也可以跳上2 级。求该青蛙跳上一个n 级的台阶总共有多少种跳法
* @author vivi_zhao
* @date Dec 30, 2011
*/
public class Frog {
public long[] a;
public boolean[] isExist;
void init(int n) {
a = new long[n + 1];
isExist = new boolean[n + 1];
}
long hoopWithMemory(int n) {
if (n < 0)
return 0;
if (n == 0)
return 1;
if(!isExist[n]) {
isExist[n] = true;
return a[n] = hoopWithMemory(n - 2) + hoopWithMemory(n - 1);
}
return a[n];
}
long hoopWithoutMemory(long n) {
if(n < 0)
return 0;
if(n == 0)
return 1;
return hoopWithoutMemory(n - 1) + hoopWithoutMemory(n - 2);
}
public static void main(String[] args) {
Frog frog = new Frog();
int count = 50;
long start = System.currentTimeMillis();
//hoop with memory
frog.init(count);
start = System.currentTimeMillis();
System.out.println(frog.hoopWithMemory(count));
long end = System.currentTimeMillis();
System.out.println(frog.hoopWithoutMemory(count));
long end2 = System.currentTimeMillis();
System.out.println("(hoop with memory = " + (end - start) + ") << (hoop without memory = " + (end2 - end) + ")");
}
}
分享到:
相关推荐
青蛙跳测试智商青蛙跳测试智商青蛙跳测试智商青蛙跳测试智商
青蛙跳HTML5游戏源码,运行需要服务器环境,已经反复测试,放心使用。
一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。求该青蛙跳上一个n级的台阶总共有多少种跳法? 若把条件修改成一次可以跳一级,也可以跳2级...也可以跳上n级呢?
同学让我帮忙写了一个模拟青蛙跳实现过程的小程序,在网上找了找没找到,于是自己写了一个,可以让左侧的青蛙先跳,也可以让右侧的青蛙先跳,通过动态的青蛙来展现整个实现过程。
青蛙跳,想必很多人小时候都玩过。现在这个是我做的android 小游戏,喜欢玩得朋友可以下载。学习android的一定要下载哦,里面带有源码的
一种新型仿青蛙弹跳腿设计,张伟,樊继壮,设计了一种新型仿青蛙弹跳腿,腿机构采用气动肌肉作为跳跃驱动单元,并采取双关节驱动形式,在增加气动肌肉驱动关节转角的大小同
小游戏源码-青蛙跳.rar
Flash游戏制作教程:青蛙跳荷叶.pdf
小学数学一年级青蛙跳—数轴练习题一步计算两步计算.doc
青蛙跳台阶问题(斐波那契数列变形)一只青蛙一次可以跳上 1 级台阶,也可以跳上 2 级台阶。示例 1:输入:n = 2 输出:2示例 2:输入:n = 7 输出
用C#开发的一款小游戏,可以实现青蛙在石头上的跳动,是一款智力小游戏。
可以复制到FLASH中,简单方便效果还不错,希望你们可以用到
表格模板-青蛙跳河.ett
讓左右兩邊青蛙交換位置,通常年薪50万水準的人,三分鐘內可以完成 ^_^ 。...1:用鼠标点青蛙头部,它会向前跳; 2:它最多只能跳过一个青蛙; 3:按红色箭头,游戏复原。 4:此题肯定有解,不要怀疑。
小学数学一年级青蛙跳数轴练习题集一步计算两步计算.doc
面试题10- II. 青蛙跳台阶问题题目链接面试题10- II. 青蛙跳台阶问题题目描述一只青蛙一次可以跳上1级台阶,也可以跳上2级台阶。示例 1:输入:n =
Unity模仿Flash小游戏《青蛙跳》而实现的算法,其实很简单,看代码就知道
scratch小程序-超能射击-青蛙跳跳跳
在本文里我们给大家讲解一下如何用PHP解决经典实例青蛙跳台阶的问题,对此有需要的朋友们可以学习下。
NULL 博文链接:https://as3.iteye.com/blog/949597