渔夫分鱼算法 求解
A,B,C,D,E五个渔夫夜间合伙捕鱼,凌晨都疲惫不堪,各自在草丛中熟睡。第二天清晨A先醒来,他把鱼均分五份,把多余的一条扔回湖中,便拿了自己的一份回家了,B醒来后,也把鱼均分五份,把多余的一条扔回湖中,便拿了自己的一份回家了,C,D,E也按同样方法分鱼。问5人至少捕到多少条鱼?
程序是:
/**
* 渔夫分鱼
* @param n
* 人数
* @return
* 原始总鱼数
*/
static int devideFish(int n) {
for (int i = 0; i < Integer.MAX_VALUE; i++) {
int sum = i;
for (int j = 0; j < n; j++) {
if (sum % n == 1)
sum = (sum / n) * 4;
else
sum = 0;
}
if (sum != 0)
return i;
}
return -1;
}
运行过后的答案是:3121 求那么大哥帮我讲解一下这个程序的意思!小弟感激不尽 算法
[解决办法]
这是一个穷举方式来获得值的:从0开始一直到Integer能表示的最大整数,一个一个判断符合要求的整数(鱼的个数)。另外,这个方法是想扩展下问题,n渔夫的场景,只是方法里的4不合理,应改为(n-1)。具体注释如下:
//n表示几个渔夫,本题填5
static int devideFish(int n) {
//从0开始,一直到Integer的最大值,挨个查找符合要求的整数
for (int i = 0; i < Integer.MAX_VALUE; i++) {
//用sum存储i值
int sum = i;
//从0号开始到n-1号结束,循环每个渔夫(实际上就是n个渔夫了)
for (int j = 0; j < n; j++) {
//如果总数取余n渔夫数,余数为1,符合要求,则直接除以渔夫数目,再乘以(n-1)(因为自己拿走了一份)
if (sum % n == 1)
sum = (sum / n) * (n-1);
else //否则,此整数不符合要求,置0
sum = 0;
}
//若sum不为0,说明此整数合法,返回即可。
if (sum != 0)
return i;
}
return -1;
}