程序面试算法问题

Question

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

9
31
3121
3906

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

Answer 1

你算的等于3906是按照 y=(x-1)/5这种方式迭代的吧？题目里面是每个人只是拿走了一份，并不是只留了一份。
考虑每个人分完都拿走了一份，剩下4份，公式应该是 y=4(x-1)/5
暴力代码如下：

function fish() {
    for(var j = 0; j < 10000; j++) {
        if(canSplit(j)) {
            console.log(j);
        }
    }
}

function canSplit(count) {
    for(var i = 0; i < 5;i++) {
        if((count - 1) % 5 === 0) {
            count = (count - 1) * 4 / 5;
        } else {
            return false;
        }
    }
    return true;
}

fish();

10000以内的三个结果是：
3121
6246
9371

Answer 2

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

Answer 3

为什么是3121呢？如果答案是3121，那么第一次平均分，每个人得到的鱼是(3121-1)/5=624,A拿着624条鱼走了，B醒来，有鱼624条，怎么分成5份还剩一条？？？这里就走不通了

---

我算出的答案是3131
第一次分，A拿走(3131-1)/5=626条，
第二次分，B拿走(626-1)/5=125条,
第三次分，C分鱼之前，鱼的数量是A第一次分的鱼626加上B第二次分的鱼125条，即分过之后的鱼数量是(626+125-1)/5=150条
第四次分，D目前手中的鱼是A+B+C给的鱼总和，也就是(626+125+150),分过之后(626+125+150-1)/5=180
第五次类似，E目前有的鱼A+B+C+D(即626+125+150+180),分过之后(626+125+150+180-1)/5=216

Answer 4

老实说我觉得这个问题理解语义的难度大于算法的难度...

Answer 5

function cal(total, i, result) {
  if(i > 5) return result;
  if(total < 0 || !Number.isInteger((total - 1) / 5)) return false;

  result.push((total - 1) / 5);
  var left = 4 * (total - 1) / 5;
  return cal(left, i + 1, result);
}

var x = 5;
var ret = cal(x, 1, []);
while(ret === false) {
  x = x + 1;
  ret = cal(x, 1, []);
}
console.log(x); //3121
console.log(ret); //[ 624, 499, 399, 319, 255 ]

Answer 6

public static void main(String[] args) {
    int n = 0;
    while (!check(n++));
    System.out.println(n-1);
}

public static boolean check(int x) {
    for (int i = 0; i < 5; i++) {
        if (--x % 5 == 0) x -= (x / 5);
        else return false;
    }
    return x >= 0;
}