猴子分桃问题猴子分桃问题
5只猴子分一堆桃子,怎么也不能分成5等份,只好先去睡觉,准备第二天再分。夜里1只猴子偷偷爬起来,先吃掉1个桃子,然后将其分成5等份,藏起自己的一份就去睡觉了;第2只猴子又爬起来,吃掉1个桃子后,也将桃子分成5等分,藏起自己的一份睡觉去了;以后的3只猴子都先后照此办理。问最初至少有多少个桃子,
倒过来想问题:
要假设第五只猴子时,平均每个猴子得到n个桃子
第五只猴子吃掉一个桃子后剩5n个
第四只猴子吃掉一个桃子后剩5(5n+1)/4=25n/4+5/4
第三只猴子吃掉一个桃子后剩5(25n/4...
猴子分桃问题
5只猴子分一堆桃子,怎么也不能分成5等份,只好先去睡觉,准备第二天再分。夜里1只猴子偷偷爬起来,先吃掉1个桃子,然后将其分成5等份,藏起自己的一份就去睡觉了;第2只猴子又爬起来,吃掉1个桃子后,也将桃子分成5等分,藏起自己的一份睡觉去了;以后的3只猴子都先后照此办理。问最初至少有多少个桃子,
倒过来想问题:
要假设第五只猴子时,平均每个猴子得到n个桃子
第五只猴子吃掉一个桃子后剩5n个
第四只猴子吃掉一个桃子后剩5(5n+1)/4=25n/4+5/4
第三只猴子吃掉一个桃子后剩5(25n/4+5/4+1)/4=125n/16+45/16 第二只猴子吃掉一个桃子后剩5(125n/16+45/16+1)/4=625n/64+305/64 第一只猴子吃掉一个桃子后剩5(625n/64+305/64+1)/4=3125n/256+1845/256 原来共有桃子3125n/256+1845/256+1=3125n/256+2101/256=(12n+8)+53(n+1)/256
这里是突破口:53(n+1)/256 是整数
桃子数是整数 所以n=255 桃子总数3121个。
C++代码实现,使用递归算法: int count = 0;
int func(int num)
{
int temp = num-1;
if(temp%5 == 0 && count<5)
{
count++;
return func(temp/5*4);
}
else
return num; }
int main(void)
{
int i;
for(i = 1;i<40000;i++)
{
if((i-1)%5==0) //代码优化
{
count = 0;
if( func(i)!=-1 && count==5)
{
cout<<"总共有: "<
本文档为【猴子分桃问题】,请使用软件OFFICE或WPS软件打开。作品中的文字与图均可以修改和编辑,
图片更改请在作品中右键图片并更换,文字修改请直接点击文字进行修改,也可以新增和删除文档中的内容。
该文档来自用户分享,如有侵权行为请发邮件ishare@vip.sina.com联系网站客服,我们会及时删除。
[版权声明] 本站所有资料为用户分享产生,若发现您的权利被侵害,请联系客服邮件isharekefu@iask.cn,我们尽快处理。
本作品所展示的图片、画像、字体、音乐的版权可能需版权方额外授权,请谨慎使用。
网站提供的党政主题相关内容(国旗、国徽、党徽..)目的在于配合国家政策宣传,仅限个人学习分享使用,禁止用于任何广告和商用目的。