猴子吃桃

呵呵，今天做了个猴子吃桃的东东，列在下面哈。

猴子分桃问题－－C/C++源程序

2007-08-31 12:30

5个猴子摘了一堆桃子，约好第二天早上来分。第一只猴子来得早，它将桃子平分成5堆，多出一个，它把多出的一个吃了，把属于自己的一堆拿走了，将剩下的还混成一堆。其他猴子来了也正好按一样的方法处理。编程求出原来有多少个桃子。（用递归函数） （用C++编写）

提问者：  - 

最佳答案

*********************************************************** 
************************ 答案: 3121 *********************** 
*********************************************************** 

思路一: （逆） 
假设还有最后第6个猴子F,最后剩下给它的果子数为f=last(剩下的可能是f=0). 
那么可知,E得到的果子数是:e=4*f(e为整数,因为果子数是整的),由这里可见: f是4的倍数!!!!!!!!!(注意这里,这是程序里f=0;f=f+4的原因!!) 
于是 D 分到的果子数是:d=(5*e+1)/4; 
同理:c=(5*d+1)/4; b=(5*c+1)/4; a=(5*b+1)/4 ; 

思路二： （正） 
假设分前的果子数为fisrt,A分到的果子数为a=(first-1)/5+1,这里可见(first-1)%5==0也就是5的倍数!!(因为果子数是整数) 
b=(4*(a-1)-1)/5+1,同理，c=(4*(b-1)-1)/5+1,d=(4*(c-1)-1)/5,e=(4*(d-1)-1)/5+1 

**********(到最后我们试着比较两个思路的出的程序各有什么优缺点??)********** 

******************程序本身不多-注释挺详细****************** 

C++程序实现: (逆) 
#include 
using namespace std; 
int fenyu(int e,int n) ; 
void main() 
{ 
int f,n=5,first; 
for(f=0;!(first=fenyu(f/4,n));f+=4) ; 
cout<<"first="<<<" last="<} 
int fenyu(int e,int n) 
{/* e:表示第n个猴子的果子数; n:表示他是第n个分的,因每个猴子分到的果子是整数，所以(5*e+1)是4的倍数,故用整除*/ 
if(n==1) return (5*e+1); /*** n==1 返回 未分前的果子数目 ***/ 
else if((5*e+1)%4==0) return fenyu((5*e+1)/4,n-1); /*递归检验前一个猴子得到的果子是不是整数*/ 
else return 0; /**** 只要分到的果子不是整数，就返回0 ***/ 
} 


C++程序实现:(正) 
#include 
using namespace std; 
int fenyu(int a,int n) ; 
void main() 
{ 
int f,last; 
for(f=1;!(last=fenyu(f/5+1,1));f+=5) ; 
cout<<"first="<<<" last="<} 
int fenyu(int a,int n) 
{/*a:表示第n个猴子的果子数; n:表示他是第n个分的,因每个猴子分到的果子是整数，所以下一个猴子分前的4*(a-1)-1是5的倍数,故用整除*/ 
if(n==5) return 4*(a-1); /*** 返回 最后剩余的果子数目 ***/ 
else if((4*(a-1)-1)%5==0) return fenyu((4*(a-1))/5+1,n+1); /*递归检验前一个猴子得到的果子是不是整数*/ 
else return 0; /**** 只要分到的果子不是整数，就返回0 ***/ 
} 

现在说说,这两种相反思路,编写的不同: 
顺向思路: 
for()中的循环是以开始的果子数为循环量,从答案来看,需要3121次循环, 但由于分配前果子量是A得到果子数的(a-1)的5倍多1个,也就是说,分配前果子量减1整除5,这样,就变成了(3121-1)/5=624次循环!!!! 

而反向思路: 
for()中的循环是以剩余的果子数为循环量,从结果来看,理论需要1020次循环,但由于剩余量是E得到果子数的4倍,也就是说,剩余量整除4,这样,就变成了1020/4=255次循环!!!! 

当然并不是说这就很好,还有其他更好的!!! 

!!!!!!!!!!!!!!!!!!!!!!!!!!! The End !!!!!!!!!!!!!!!!!!!!!!!!!!! 
最后PS一下,如需要了解本题的 "数学解法" ,请参照: 

优美的数学解法。

5的5次方+1-5=3121 

先给这些猴子4个桃子， 
第1只猴子多了4个桃子正好分成五份，拿走自己的部分（一堆多1个，给他的4个桃子留给第二个猴子）； 
第2只猴子多了4个桃子正好分成五份，拿走自己的部分（一堆多1个，给他的4个桃子留给第三个猴子）； 
第5只猴子多了4个桃子正好分成五份，拿走自己的部分（一堆多1个，给他的4个桃子留给第6个猴子）； 

这就是说，有了这4个桃子，每次猴子都可以平均分成5份，可见，原来的总数必须是5的5次方的倍数，即3125，所以原来有3121个。

我的理解。。

  猴子的桃子是很优美的三个队列，每一次拿剩下的桃子都可以被4整除，吃掉一个后就可以被5整除。那么只要这这样三个队列就可以了。

最小的可以被4整除，减一可以被5整除的是16. 然后16+20 ， 16+20+20 ， 16+20+20 都是。

我们把组合列出来。

5的因子X，    4的因子Y       X*5+1 = Y*4

  3              4             16

 7               9             36

 11              14            56

 15              19            76

19               24            96

。                 。          。

。                。           。

X是一个4为差值的数列，Y是一个5为插值的序列， RES是一个20为插值的序列。

其实在X和Y中找到 Yi=Xj， Yj=Xk，Yk=Xl，Yl=Xm 这样的一个序列，i j k l m 可以逐渐增多。 可以解决任何这种问题。

偶的程序。。呵呵。

/* for the monkey program */

#include

#include

int main()

{

  int array4[10240];

  int array5[10240];

  int i,j,k,l;

/*  int find=0;*/

  array4[0]=3;

  array5[0]=4;

  for(i=1;i<10240;i++)

  {

    array4[i]=array4[i-1]+4;

    array5[i]=array5[i-1]+5; 

  }

  for(i=0;i<10240;i++)

  {

     if(array5[i]%10==9)

     {

for(j=i+1;j<10240;j++)

{

   if(array4[j]==array5[i]&&array5[j]%10==9)

   {

   for(k=j+1;k<10240;k++)

   {

   if(array4[k]==array5[j]&&array5[k]%10==9)

       {

   for(l=k+1;l<10240;l++)

   {

       if(array4[l]==array5[k])

     {

  /* for(m=l+1;m<10240;m++)

    {

   

    }    */

  printf("find the answer %d > %d > %d> %d . the res is %d \n",array5[i],array5[j],array5[k],array5[l],array5[l]*5+1);

/*   find=1;*/

  break;

   }

   if(array4[l]>array5[k])

   {

   break;

   }

   

   }  

   

 }

    if(array4[k]>array5[j])

     {

   break;

    }    

   }    

   }

   if(array4[j]>array5[i])

   {

   break;

   }

}    

     } 

  }

  return 0;

}

运行结果：

find the answer 319 > 399 > 499> 624 . the res is 3121 

find the answer 639 > 799 > 999> 1249 . the res is 6246 

find the answer 959 > 1199 > 1499> 1874 . the res is 9371 

find the answer 1279 > 1599 > 1999> 2499 . the res is 12496 

find the answer 1599 > 1999 > 2499> 3124 . the res is 15621 

find the answer 1919 > 2399 > 2999> 3749 . the res is 18746 

find the answer 2239 > 2799 > 3499> 4374 . the res is 21871 

find the answer 2559 > 3199 > 3999> 4999 . the res is 24996 

find the answer 2879 > 3599 > 4499> 5624 . the res is 28121 

find the answer 3199 > 3999 > 4999> 6249 . the res is 31246 

find the answer 3519 > 4399 > 5499> 6874 . the res is 34371 

find the answer 3839 > 4799 > 5999> 7499 . the res is 37496 

find the answer 4159 > 5199 > 6499> 8124 . the res is 40621 

find the answer 4479 > 5599 > 6999> 8749 . the res is 43746 

find the answer 4799 > 5999 > 7499> 9374 . the res is 46871 

find the answer 5119 > 6399 > 7999> 9999 . the res is 49996 

find the answer 5439 > 6799 > 8499> 10624 . the res is 53121 

find the answer 5759 > 7199 > 8999> 11249 . the res is 56246 

find the answer 6079 > 7599 > 9499> 11874 . the res is 59371 

find the answer 6399 > 7999 > 9999> 12499 . the res is 62496 

find the answer 6719 > 8399 > 10499> 13124 . the res is 65621 

find the answer 7039 > 8799 > 10999> 13749 . the res is 68746 

find the answer 7359 > 9199 > 11499> 14374 . the res is 71871 

find the answer 7679 > 9599 > 11999> 14999 . the res is 74996 

find the answer 7999 > 9999 > 12499> 15624 . the res is 78121 

find the answer 8319 > 10399 > 12999> 16249 . the res is 81246 

find the answer 8639 > 10799 > 13499> 16874 . the res is 84371 

find the answer 8959 > 11199 > 13999> 17499 . the res is 87496 

find the answer 9279 > 11599 > 14499> 18124 . the res is 90621 

find the answer 9599 > 11999 > 14999> 18749 . the res is 93746 

find the answer 9919 > 12399 > 15499> 19374 . the res is 96871 

find the answer 10239 > 12799 > 15999> 19999 . the res is 99996 

find the answer 10559 > 13199 > 16499> 20624 . the res is 103121 

find the answer 10879 > 13599 > 16999> 21249 . the res is 106246 

find the answer 11199 > 13999 > 17499> 21874 . the res is 109371 

find the answer 11519 > 14399 > 17999> 22499 . the res is 112496 

find the answer 11839 > 14799 > 18499> 23124 . the res is 115621 

find the answer 12159 > 15199 > 18999> 23749 . the res is 118746 

find the answer 12479 > 15599 > 19499> 24374 . the res is 121871 

find the answer 12799 > 15999 > 19999> 24999 . the res is 124996 

find the answer 13119 > 16399 > 20499> 25624 . the res is 128121 

find the answer 13439 > 16799 > 20999> 26249 . the res is 131246 

find the answer 13759 > 17199 > 21499> 26874 . the res is 134371 

find the answer 14079 > 17599 > 21999> 27499 . the res is 137496 

find the answer 14399 > 17999 > 22499> 28124 . the res is 140621 

find the answer 14719 > 18399 > 22999> 28749 . the res is 143746 

find the answer 15039 > 18799 > 23499> 29374 . the res is 146871 

find the answer 15359 > 19199 > 23999> 29999 . the res is 149996 

find the answer 15679 > 19599 > 24499> 30624 . the res is 153121 

find the answer 15999 > 19999 > 24999> 31249 . the res is 156246 

find the answer 16319 > 20399 > 25499> 31874 . the res is 159371 

find the answer 16639 > 20799 > 25999> 32499 . the res is 162496 

find the answer 16959 > 21199 > 26499> 33124 . the res is 165621 

find the answer 17279 > 21599 > 26999> 33749 . the res is 168746 

find the answer 17599 > 21999 > 27499> 34374 . the res is 171871 

find the answer 17919 > 22399 > 27999> 34999 . the res is 174996 

find the answer 18239 > 22799 > 28499> 35624 . the res is 178121 

find the answer 18559 > 23199 > 28999> 36249 . the res is 181246 

find the answer 18879 > 23599 > 29499> 36874 . the res is 184371 

find the answer 19199 > 23999 > 29999> 37499 . the res is 187496 

find the answer 19519 > 24399 > 30499> 38124 . the res is 190621 

find the answer 19839 > 24799 > 30999> 38749 . the res is 193746 

find the answer 20159 > 25199 > 31499> 39374 . the res is 196871 

find the answer 20479 > 25599 > 31999> 39999 . the res is 199996 

find the answer 20799 > 25999 > 32499> 40624 . the res is 203121 

find the answer 21119 > 26399 > 32999> 41249 . the res is 206246 

find the answer 21439 > 26799 > 33499> 41874 . the res is 209371 

find the answer 21759 > 27199 > 33999> 42499 . the res is 212496 

find the answer 22079 > 27599 > 34499> 43124 . the res is 215621 

find the answer 22399 > 27999 > 34999> 43749 . the res is 218746 

find the answer 22719 > 28399 > 35499> 44374 . the res is 221871 

find the answer 23039 > 28799 > 35999> 44999 . the res is 224996 

find the answer 23359 > 29199 > 36499> 45624 . the res is 228121 

find the answer 23679 > 29599 > 36999> 46249 . the res is 231246 

find the answer 23999 > 29999 > 37499> 46874 . the res is 234371 

find the answer 24319 > 30399 > 37999> 47499 . the res is 237496 

find the answer 24639 > 30799 > 38499> 48124 . the res is 240621 

find the answer 24959 > 31199 > 38999> 48749 . the res is 243746 

find the answer 25279 > 31599 > 39499> 49374 . the res is 246871 

find the answer 25599 > 31999 > 39999> 49999 . the res is 249996 

find the answer 25919 > 32399 > 40499> 50624 . the res is 253121