java算法题,话说某天一艘海盗船被天下砸下来的一头牛给击中了,5个倒霉的家伙只好逃难到一个孤岛,发现岛上孤零零的,幸好
java算法题,
话说某天一艘海盗船被天下砸下来的一头牛给击中了,5个倒霉的家伙只好逃难到一个孤岛,发现岛上孤零零的,幸好有有棵椰子树,还有一只猴子?
大家把椰子全部采摘下来放在一起,但是天已经很晚了,所以就睡觉先.
晚上某个家伙悄悄滴起床,悄悄滴将椰子分成5份,结果发现多一个椰子,顺手就给了幸运的猴子,然后又悄悄滴藏了一份,然后把剩下滴椰子混在一起放回原处,最后还是悄悄滴回去睡觉了.
过了会儿,另一个家伙也悄悄滴起床,悄悄滴将剩下滴椰子分成5份,结果发现多一个椰子,顺手就又给了幸运的猴子,然后又悄悄滴藏了一份,把剩下滴椰子混在一起放回原处,最后还是悄悄滴回去睡觉了.
又过了一会 ...
...
又过了一会 ...
总之5个家伙都起床过,都做了一样的事情 :blush;
早上大家都起床,各自心怀鬼胎的分椰子了,这个猴子还真不是一般的幸运,因为这次把椰子分成5分后居然还是多一个椰子,只好又给它了.
这堆椰子最少有多少个?
import java.util.GregorianCalendar;
public class MonkeyTest {
public static int I = 1;
public static int T = 1;//两个静态变量,用于记录运算次数
public static int getHai(int n,int a) {//根据输入的最后分配数和分配次数,查找可能是的初始数.
I++;//每进入方法一次,计数加1
int num = 5 * a + 1;
if (n == 0) {
return num;
} else {
return getHai(n - 1,num / 4);//第一次符合则继续向下递归
}
}
public static boolean isHai(int n,int a) {//判断所输入的数是不是符合分配规则
I++;//进入方法一次计数加1
T++;//直接判断时每进入一次计数加1
int num = a / 5;
if (a % 5 = 1)
return false;
else if (n == 0)
return true;
else {
return isHai(n - 1,4 * num);//一次符合时递归下次
}
}
public static void main(String[] args) {
int i = 1,sum = 0,n = 1,k = 1;
GregorianCalendar gc = new GregorianCalendar();
long time = gc.getTimeInMillis();
while (true) {//先查找可能符合标准的数,再判断是不是真的符合标准
sum = getHai(5,i);
if (isHai(5,sum)) {
System.out.println(sum + ":" + i + ":" + MonkeyTest.I);
break;
}
i++;//可直接记录查找次数
}
System.out.println(gc.getTimeInMillis() - time);//显示用时毫秒数
time = gc.getTimeInMillis();
while (true) {//用直接判断的方式查找
if (isHai(5,n)) {
System.out.println(n + ":" + k +":"+MonkeyTest.T);
break;
}
n += 5;//该数起码减1之后可以整除一次5,因而直接每次加5
k++;//记录运行次数
}
System.out.println(gc.getTimeInMillis() - time);
}
}
测试结果时间都消耗很少,结果未15621,先查找后判断的方法运算次数较少!
程序看的不是很明白,请大家帮我写清楚,
我看的不是很明白,
