64,662
社区成员
发帖
与我相关
我的任务
分享李政道猴子分桃问题
#include <stdio.h>
//判断能否被合理的分配
int divide(int n,int m)
{
if(n/5==0 || n%5!=1)
{//不足5个或不能分5份多1个，分配失败
return 0;
}
if(m==1)
{//分到最后一个猴子，说明能分配成功
return 1;
}
return divide(n-n/5-1,m-1);
}
void main()
{
int n;//桃子数量
for(n=1;;n++)
{
if(divide(n,5))
{//判断能否被合理的分配
printf("%d\n",n);
break;
}
}
}哪位大虾帮忙解释一下这个李政道猴子分桃问题，这个代码是怎么实现的的，看不懂，有什么正确更好的算法？
//判断能否被合理的分配
int divide(int n,int m)
{
if(n/5==0 || n%5!=1)
{//不足5个或不能分5份多1个，分配失败
return 0;
}
if(m==1)
{//分到最后一个猴子，说明能分配成功
return 1;
}
return divide(n-n/5-1,m-1);
}
void main()
{
int n;//桃子数量
for(n=1;;n++)
{
if(divide(n,5))
{//判断能否被合理的分配
printf("%d\n",n);
break;
}
}
}哪位大虾帮忙解释一下这个李政道猴子分桃问题，这个代码是怎么实现的的，看不懂，有什么正确更好的算法？
...全文
请发表友善的回复…
发表回复
zhaoZero41 2012-08-16
- 打赏
- 举报
int monkeyPickPeach(int monkeyNum)
{
int resultNum = 1;
int monkeyPicked = 0;
int temp = 0;
int tempSum = 0;
bool isTemp = false;
while (monkeyPicked < monkeyNum)
{
temp = resultNum / 4 + 1;
if (!isTemp)
{
tempSum = 0;
}
if ((resultNum+temp) % 5 == 1 && resultNum % 4 == 0)
{
resultNum = resultNum + temp;
tempSum += temp;
monkeyPicked++;
isTemp = true;
}
else
{
if (isTemp)
{
resultNum -= tempSum;
}
resultNum++;
monkeyPicked = 0;
isTemp = false;
}
}
return resultNum;
}摘录了一段别人写的代码，答案和递归的一样，楼主可以看一下。
nice_cxf 2012-08-16
- 打赏
- 举报
最简单的算法就是先计算最少的那个：
（（（（1＋1*5）*5+1)*5+1)*5+1)*5+1
后续的每个+5*5*5*5*5，直到超过制定范围为止
（（（（1＋1*5）*5+1)*5+1)*5+1)*5+1
后续的每个+5*5*5*5*5，直到超过制定范围为止
zhaoZero41 2012-08-16
- 打赏
- 举报
五只猴子分桃。半夜，第一只猴子先起来，它把桃分成了相等的五堆，多出一只。于是，它吃掉了一个，拿走了一堆； 第二只猴子起来一看，只有四堆桃。于是把四堆合在一起，分成相等的五堆，又多出一个。于是，它也吃掉了一个，拿走了一堆；......其他几只猴子也都是 这样分的。问：这堆桃至少有多少个？
楼主贴出的代码是运用了递归进行运算的。
是这个算法的重点，假设一共有n个桃子，分配成功，那么应该是分成相等的五堆多一个，猴子吃掉一个拿走一堆，剩下的就是(n - n/5 - 1)个桃子，和(m - 1)只猴子。然后继续分配，直到猴子的数目为1并且最后也分配成功。
这个算法其实不好，更好的思路是从最后一只猴子开始入手，反推上去。
楼主贴出的代码是运用了递归进行运算的。
return divide(n-n/5-1,m-1); 是这个算法的重点，假设一共有n个桃子，分配成功，那么应该是分成相等的五堆多一个，猴子吃掉一个拿走一堆，剩下的就是(n - n/5 - 1)个桃子，和(m - 1)只猴子。然后继续分配，直到猴子的数目为1并且最后也分配成功。
这个算法其实不好，更好的思路是从最后一只猴子开始入手，反推上去。
fzamygsd 2012-08-16
- 打赏
- 举报
李政道猴子分桃问题，这个题目偶不太清楚。。。
楼主可搜 递归及其相关的帖子
楼主可搜 递归及其相关的帖子
