程序面试算法问题

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

9
31
3121
3906

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

阅读 4.3k
6 个回答

你算的等于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

/**
     * 设第一个人分鱼时总数为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);
        }

为什么是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

图片描述

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

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 ]
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;
}
推荐问题
宣传栏