创新工厂面试题详解：共打了多少鱼

最近看到一个创新工厂的面试题，很有意思，下面给出算法实现（Java代码）。如果哪位有更好的算法，请跟贴。

abcde五人打渔，打完睡觉，a先醒来，扔掉1条鱼，把剩下的分成5分，拿一份走了；b再醒来，也扔掉1条，把剩下的分成5份，拿一份走了；然后cde都按上面的方法取鱼。问他们一共打了多少条鱼，写程序和算法

共打了多少条鱼的结果有很多。但求最少打的鱼的结果是3121条鱼（应该找这5个人问问，用什么工具打了这么多条鱼）

大家可以先用计算器验证一下3121是否正确。

a开始拿鱼： （3121 - 1） / 5 = 625

同理，bcde分别获得的鱼数（不包括其扔掉的鱼）b:499 c:399 d:319e:255

这道题最简单的方法就是枚举。从最小值开始，先看看代码（Java实现）。

public class Test

{

public static void main(String[] args)

{

// 分别保存a至e获取的鱼数（为了方便，包括其扔掉的鱼）

int[] everybody_fish = new int[5];

//临时数组，保存当前鱼数减1后除5的余数，只有都为0，才满足条件

int[] temp = new int[5];

// 从1扫描到10000

for (int x = 1; x <= 10000; x++)

{

//当前已被取走多少鱼（包括被扔的鱼）

int sum = 0;

int i = 0;

//计算abcde各获取的鱼数

for (i = 0; i < everybody_fish.length; i++)

{

temp[i] = (x - 1 - sum) % everybody_fish.length;

// 只要有一个人不能平均分配剩余的鱼，就不满足条件

if (temp[i] != 0)

break;

everybody_fish[i] = (x - 1 - sum) / everybody_fish.length + 1;

sum += everybody_fish[i];

}

//for循环正党结束，满足条件，输出相应的值。

if (i == everybody_fish.length)

{

System.out.print("共钓了" + x + "条鱼 ");

for (i = 0; i < everybody_fish.length; i++)

{

System.out.print((char) ('a' + i) + ":"

+ (everybody_fish[i] - 1) + " ");

}

System.out.print("最后剩余" + (x - sum) + "条鱼");

System.out.println("扔了" + everybody_fish.length + "条鱼");

}

}

}

}

运行上面的代码，会输出如下三行信息

共钓了3121条鱼a:624 b:499 c:399d:319 e:255 最后剩余1020条鱼 扔了5条鱼

共钓了6246条鱼a:1249 b:999 c:799d:639 e:511 最后剩余2044条鱼 扔了5条鱼

共钓了9371条鱼a:1874 b:1499 c:1199d:959 e:767 最后剩余3068条鱼 扔了5条鱼

在10000以内只有三个数满足这个条件。上面的代码是通用的，如将两个数组的长度改为6，将10000改成50000，会输出如下信息。

共钓了46651条鱼a:7775 b:6479 c:5399d:4499 e:3749 f:3124最后剩余15620条鱼 扔了6条鱼

也就是说一共6个人。每个人也是先扔一条鱼，然后再将剩余的鱼6等分，取走一份。 在50000以内只有46651满足这个条件。

在本题中只有如下的代码是核心算法，其他的都是枚举和输出结果的代码。

for (i = 0; i < everybody_fish.length; i++)

{

temp[i] = (x -1 - sum) % everybody_fish.length;

// 只要有一个人不能平均分配剩余的鱼，就不满足条件

if (temp[i] !=0)

break;

everybody_fish[i] = (x - 1 - sum) / everybody_fish.length + 1;

sum +=everybody_fish[i];

}