程序面试算法问题

Question

A,B,C,D,E五个人捕鱼后已凌晨，大家便睡觉。早上A第一个醒来，将鱼均分成五份，把多余的一条鱼扔掉，拿走自己的一份，B第二个醒来，也将鱼均分为五份，把多余的一条鱼扔掉，拿走自己的一份。CDE依次醒来，也按同样的方法拿鱼，问他们合伙至少捕了几条鱼。

9

31

3121

3906

在别的地方看到的面试题，自己算是3906，据说答案是3121，完全想不通，求教。

Answer 1

/**&nbsp; &nbsp; &nbsp;* 设第一个人分鱼时总数为a1,每人人分的k1，有：t1 = 5*k1+1.剩下的鱼为t2 = t1-k1-1;&nbsp; &nbsp; &nbsp;* 同理，第二个人鱼时有 t2 = 5*k2+1;&nbsp; &nbsp; &nbsp;* 结合以上，得出k1 = (5*k2+1)/4,同时要满足k1,k2为整数.&nbsp; &nbsp; &nbsp;* 假设最后每人平分数为k5=t,递归的到k1,就可求出总数&nbsp; &nbsp; &nbsp;*/&nbsp; &nbsp; &nbsp; &nbsp; public static void main(String... args) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int k = 1;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int t = k;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; int i = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; while (i < 5){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; if((t*5+1) % 4 == 0){&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t = (t*5+1)/4;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; t = ++k;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i = 0;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; i++;&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; System.out.println(5*t+1);&nbsp; &nbsp; &nbsp; &nbsp; }

Answer 2

你算的等于3906是按照&nbsp;y=(x-1)/5这种方式迭代的吧？题目里面是每个人只是拿走了一份，并不是只留了一份。考虑每个人分完都拿走了一份，剩下4份，公式应该是&nbsp;y=4(x-1)/5暴力代码如下：function fish() {&nbsp; &nbsp; for(var j = 0; j < 10000; j++) {&nbsp; &nbsp; &nbsp; &nbsp; if(canSplit(j)) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; console.log(j);&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }}function canSplit(count) {&nbsp; &nbsp; for(var i = 0; i < 5;i++) {&nbsp; &nbsp; &nbsp; &nbsp; if((count - 1) % 5 === 0) {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; count = (count - 1) * 4 / 5;&nbsp; &nbsp; &nbsp; &nbsp; } else {&nbsp; &nbsp; &nbsp; &nbsp; &nbsp; &nbsp; return false;&nbsp; &nbsp; &nbsp; &nbsp; }&nbsp; &nbsp; }&nbsp; &nbsp; return true;}fish();10000以内的三个结果是：312162469371