返回信息流捕鱼和分鱼
A、B、C、D、E五人在某天夜里合伙去捕鱼，到第二天凌晨时都疲惫不堪，于是各自找地方睡觉，日上三竿，A会把鱼均分成五份，把多余的一条鱼扔掉，拿走自己的一份。B第二个醒来，也将把鱼均分成五份，把多余的一条鱼扔掉，拿走自己的一份，C、D、E以同样的方法拿鱼。问他们合伙至少捕了多少条鱼？（只要写出程序和算法）
ps：用java语言
这是一条镜像帖。来源：北邮人论坛 / java / #20079同步于 2011/9/16
该镜像源已超过 30 天没有更新，可能在源站已被删除。
Java机器人发帖
求解创新工场的编程笔试题
ArvinW
2011/9/16镜像同步25 回复
订阅后，新回复会通过你的通知中心匿名送达。
9 条回复
public int fishNumbers(int n) {
if (n == 5)
return 1*5+1;
return fishNumbers(n+1)*5+1;
}
暴力破解的
至少要3121鱼
最初有3121条鱼
第1个人丢掉了1条鱼，剩余3120条鱼，分成5份，每份624条,他拿走了624条，剩余2496条
第2个人丢掉了1条鱼，剩余2495条鱼，分成5份，每份499条,他拿走了499条，剩余1996条
第3个人丢掉了1条鱼，剩余1995条鱼，分成5份，每份399条,他拿走了399条，剩余1596条
第4个人丢掉了1条鱼，剩余1595条鱼，分成5份，每份319条,他拿走了319条，剩余1276条
第5个人丢掉了1条鱼，剩余1275条鱼，分成5份，每份255条,他拿走了255条，剩余1020条
public class DividingFish {
public static void main(String[] args) {
int begin = 1;
int mans = 5;
int beforeDivide = 0;
int each = begin;
while (mans > 1) {
beforeDivide = each * 5 + 1;
if (beforeDivide % 4 == 0) {
mans--;
each = beforeDivide / 4;
}
else {
mans = 5;
begin += 2;
each = begin;
}
}
System.out.println("至少要" + (beforeDivide * 5 / 4 + 1) + "鱼");
displayDividing(beforeDivide*5/4+1);
}
public static void displayDividing(int fishnum) {
System.out.println("最初有" + fishnum + "条鱼");
for (int i = 1; i <= 5; i++) {
System.out.println("第" + i + "个人丢掉了1条鱼，" +
"剩余" + (fishnum - 1) + "条鱼，" +
"分成5份，每份" + (fishnum - 1) / 5 + "条," +
"他拿走了" + (fishnum - 1) / 5 + "条，" +
"剩余" + (fishnum - 1) / 5 * 4 + "条");
fishnum = (fishnum - 1) / 5 * 4;
}
}
}
class Div {
public static void main(String [] args){
int f = 6;
int p = 5;
boolean bingo = false;
do{
int i = f, j=1;
for(; j<=p; j++){
if((i - 1)%p != 0){
f++;
break;
}else{
i = (i - 1)*(p-1)/p;
}
}
if(j == p+1)
bingo = true;
}while(!bingo);
System.out.println(f);
}
}
【 在 ArvinW (Arvin) 的大作中提到: 】
: 捕鱼和分鱼
: A、B、C、D、E五人在某天夜里合伙去捕鱼，到第二天凌晨时都疲惫不堪，于是各自找地方睡觉，日上三竿，A会把鱼均分成五份，把多余的一条鱼扔掉，拿走自己的一份。B第二个醒来，也将把鱼均分成五份，把多余的一条鱼扔掉，拿走自己的一份，C、D、E以同样的方法拿鱼。问他们
: ps：用java语言
: ...................
public class test3 {
public static void main(String[] args){
int x=6;
while(!Num(x)){
x++;
}
System.out.println(x);
}
public static boolean Num(int n){
int k=n;
for( int i=0;i<5;i++){
if((k-1)%5==0&&k>5){
k=((k-1)/5*4);
}
else{return false;}
if(i==4&&k>5)return true;
}
return false;
}
}
输出：3121
package com.tang.study;
public class Fish {
public static void main(String[] args) {
System.out.println(getFish(5));
}
public static int getFish(int m) {
int nums = 6;
while (true) {
if (isOK(nums, m)) {
break;
}
nums++;
}
return nums;
}
private static boolean isOK(int nums, int m) {
if (m == 0) {
return true;
}
if (nums % 5 != 1) {
return false;
} else {
nums = nums - (nums - 1) / 5 - 1;
return isOK(nums, m - 1);
}
}
}
result:3121
【 在 ox 的大作中提到: 】
: 暴力破解的
: 至少要3121鱼
: 最初有3121条鱼
: ...................
有没比小贝这种方法枚举的数字更少的?有没公式解法？
两种思路，一种从初始总鱼数开始枚举，另一种从最后剩下的鱼数开始枚举。第一种从6开始递增，步进值为5（至少要过了第一次划分）；第二种从4开始递增，步进值为4（同理，剩下的是四份，需要被4整除）。
我说下我的思路吧，我首先用暴力破解，得出结果是３１２１，然后又试着分析了一下，发现可以从不同的角度以很简单的方法解出这道题。
假设最后e分后还剩x条鱼，那么d拿鱼后，还剩5/4x+1,那么c分后还剩5/4(5/4x+1),...依些类推，可以推出a分之前的总鱼数为pow(5/4,5)x+pow(5/4,4)+pow(5/4,3)+...+1;后面就是等比数列，可以手算，4*pow(5/4,5)-4;所以总结果为pow（5/4,5）*(x+4)-4,所以这个问题在这里已经水落石出了，就是求得x+4可以整除pow(4,5)的最小数，pow(4,5)=1024,所以最后至少剩102４-4＝1020条鱼，总的结果代入进去即可，为pow(5,5)-4=3121条鱼。
public class Fish {
public static void main(String args[])
{
int personNum = 5;
int fishNum = personNum + 1;
while(true)
{
int tempPersonNum = personNum;
int tempFish = fishNum;
while(tempPersonNum > 0)
{
if(tempFish <= personNum || tempFish % personNum != 1)
{
fishNum += 1;
while(fishNum % personNum != 1)
{
fishNum++;
}
break;
}
tempFish -= (tempFish / personNum + 1);
tempPersonNum--;
}
if(tempPersonNum == 0)
{
break;
}
}
System.out.println(fishNum);
}
}