|
五猴分桃题解析（C语言 5 种解法 ）
本人喜欢探索各种算法。80年代听闻五猴分桃题，颇感兴趣。曾尝试求解，得小学算术解法和迭代（递增，递减）算法。那时还没有PC是用算盘计算的，那”二弹一星”据说也是用算盘计算的。今见网上各种解法，感觉大同小异，不值一哂。故复提起兴趣再次索解，又得三种解法，即小学奥数解法、另一奥数解法、穷举解法。
解法一：小学算术解法
解题思路：理解题意，确立起算基数，试求中间差，立运算式试算解题。
确立基数 A ：
A - 1 能整除 5 ， 满足前行运算，同时能整除 4 ，满足后续运算。
则 ( A - 1 ) / 5 = A / 4 （需是整数）
自然数序列中 1…6…11…(16)…21…26…31…(36)…
最小符合条件的数是 16 ， 所以 A = 16
求中间差 mid ：
后续运算要求的数应为能整除 4 和 5 的数，
则为 4， 5 的最小公倍数 ， mid = 4 * 5 = 20
试算求解：
因 A = 16 ，先拟J = 16，i = ( 0 … 15 ) = 16
J ( i ) = 16 + i * 20
J ( i ) : 16 36 56 76 96 116 136 156 176 196 216 236 256 276 296 316
316 + i * 20 = 316 + 16 * 20 = 636
636 + 16 * 20 = 956
956 + 16 * 20 = 1276
以 316，636，956，1276 来试算
Ps = J i / 4 * 5 + 1 ( 后续 4 次运算 ）
前行运算是逆运算
前三数试算不符合整数要求 （ 过程略 ）
下面试算 J i = 1276 ：
255 * 5 + 1 = [ 1276 ] / 4 = 319
319 * 5 + 1 = 1596 / 4 = 399
399 * 5 + 1 = 1996 / 4 = 499
499 * 5 + 1 = 2496 / 4 = 624
624 * 5 + 1 = 3121 符合题目要求：成功
解得 桃子总数 Ps = 3121
解法二：迭代公式解法
公式：几猴 M几次 n >>> M^n - M + 1
解释：几个猴子的几次方减去几个桃子加 1
公式由数学教授专家推导证明（详数学通报1980年 4 期）。
设：任一猴到时桃子数为 x ， 离去时剩余数 y，
则 5y = 4x - 1
A= (x-1) /5
y = 4A = (x-1) /5 * 4 = 4/5 (x-1)
得 函数关系式 y = 4/5 (x-1)
若设总数为 x , 则函数式连续 5次，
此为迭代x0 … x5 , y0 … y5
则： 迭代函数式 f (x) = 4/5 (x-1)
则 桃子总数 Ps = f (f (f (f (f (x)))))
= f [5] (x) (迭代5次)
因 f(x) = 4/5 (x-1) 不易计算
改为 f (x) = (4/5)x - (4/5)
=(4/5)x+(16/5)-(20/5)
= (4/5) (x+4)-4
由是得 f [5 ] (x) = (4/5)^ 5 (x+4) - 4
因桃子总数 Ps 需为最小整数解，则需满足Ps+4 能被 5^5 = 3125 整除
Ps = 5^5 - 4 = 3125 - 4 = 3121
所以桃子总数 Ps = 3125 - 5 + 1 = 3121
公式：Ps = M^ n - M + 1 解几猴迭代几次
算法三：小学奥数解法
奥数是什么？奥数就是在竞赛时奇思妙想，突发奇想，不按常理常规，把题目解出来。
对此五猴分桃题，五猴 设 M = 5，分桃 5次，
先来个 4次，n = 4，
找个起算点 J i , 4猴的4次方乘以 5猴 减去 5猴 加上 1，
降次的奥妙在于找起算点，也就是最后那猴子所看见到的桃子数量。
由此逆推4次 ( J i ) / 4 *5 + 1 就能求得桃子总数。
剩余数很好算：第5猴见到的桃子数就是 J i ，
吃掉 1个，分成 5份拿走 1份，还余4份。
计算如下：
起算： 降次 n = M - 1 , n = 5 - 1 = 4
J i = ( M - 1 )^ n * M - M + 1
= ( 5 - 1 ) ^ 4 * 5 - 5 + 1
= 1276
逆推运算 4次：
Ps=J i ; //末次起算
for (i=1;i<M;i++){ Ps= Ps/(M-1)*M+1 ; }
运算 4次得桃子总数 Ps = 3121
剩余： yu = (J i - 1) / M * n
= ( 1276 - 1 ) / 5 * 4
= 1020
算法四：另一奥数算法
设：几猴为 M ，几次为 n
桃子总数为：M 的 n次方 减去M 加 1
这个算法不是奇思妙想，他套用了迭代公式
Ps = M ^ n -M + 1
不同的是计算方法和过程。
剩余数为：(M-1) 的 n次方 减去M 加 1
计算如下：
Ps=1 ; // 起算
for (i=0;i<M;i++){ Ps=PsM; } // 运算 n 次
Ps=Ps-M+1;
桃子总数 Ps = 3121
n = M - 1 ; temp = M - 1;
for (i=0;i<n;i++){ temp=tempn; }
yu=temp-M+1;
剩余桃子数 yu = 1020
算法五： 穷举解法
穷举法也就是暴力算法。
网上介绍的从1到1万套用算式试算 ，直至得到满足条件的结果。
这种方法很耗计算时间，效率不高。本文介绍的算法是改进过的优化算法。
起算基数 A： ( A - 1 ) / 5 = A / 4 （需是整数）
自然数序列中 最小符合条件的数是 16 ，
所以 A = ( M - 1 ) * ( M - 1 ) = 16
运算步长mid ：后续运算要求的数应为能整除 4 和 5 的数，
则为 4， 5 的最小公倍数 ，
mid = ( M - 1 ) * M = 4 * 5 = 20
计算过程：
Scan_Ps : //Ps = A = 16 起算
Ps = Ps + mid ; //每次运算增加步长 20 试算
temp = Ps ; // temp 运算数值
for (i=0;i<M-1;i++){ //以计算式试算
if (temp-temp/(M-1)*(M-1)==0){
// 若是整数则得到结果
temp=temp/(M-1)*M+1; }else { goto scan_Ps ; }
} //运算M - 1次
得到结果：桃子总数为 Ps = 3121
此方法运算次数为 64 次。计算9 猴要7776 次，优化了也很耗时。
今在此将几种算法推荐给各位同好，望大咖小咖们不吝指教，批评指正。
下面的代码就是用Myspringc在安卓手机上编写的，可制作成安卓手机桌面app应用程序。此样例可复制黏贴到编译器直接使用，用 Myspringc 编译调试通过。
代码如下：
//*******************************************
// 五猴分桃 5 种解法
// Myspringc v2.7 编译
// 编译人：张纯叔（micelu@126.com ）
//*******************************************
//因 int 类型数值运算限制，只能计算到 9 猴
//将 int 改为 Long 可计算得到 18 猴的整数解
string sMenu[50];
int nMenu[50];
string sBarDes[10];
int nBarId[10];
int M; //几猴
int n ; //几次
int i , j ;
main(){
setDisplay (0);
sBarDes[0]=“输入几猴”;
nBarId[0]=100;
sBarDes[1]=“算术解法”;
nBarId[1]=101;
sBarDes[2]=“迭代公式”;
nBarId[2]=102;
sBarDes[3]=“奥数解法”;
nBarId[3]=103;
sBarDes[4]="退出程序 ";
nBarId[4]=104;
setToolBarHeight(10);
setButtonTextSize(15);
setToolBarBackgroundColor(255,192,192,192);
setButtonColor(255,0,0,240);
setButtonTextColor(255,255,245,0);
setToolBar(100,myToolBarProc,sBarDes,nBarId,5);
sMenu[0]=“输入几猴”;
nMenu[0]=200;
sMenu[1]=“小学算术解法”;
nMenu[1]=201;
sMenu[2]=“迭代公式解法”;
nMenu[2]=202;
sMenu[3]=“小学奥数解法”;
nMenu[3]=203;
sMenu[4]=“奥数解法（2）”;
nMenu[4]=204;
sMenu[5]="穷举法求解 ";
nMenu[5]=205;
sMenu[6]=“退出”;
nMenu[6]=206;
setMenu(200,myMenuProc,sMenu,nMenu,7);
setTitle(“五猴分桃”);
M=5 ; //init Monkey at start
while (){}
}//main ()
calculate1 (){//小学算术解法
clearOutput ();
int A; //基数
int mid; //间差
int Ji; //起算
int temp;
int yu; //最后剩余数
int Ps; //结果 总数
print "**** 小学算术解法 ";
n=M;
print ”Input >> 几猴几次 “,M,” 猴， M = “,M,” , n = ",n;
print " ";
print “计算如下：”;
n=M-1;
A= (M-1)(M-1);
print “基数： 需满足 (A-1)/”,M," , A/",n," 能整除的最小正整数 ";
print " A = (M-1)(M-1) = ",A;
mid=(M-1)M;
print "间差：能整除 (M-1) 和 M 即二数的公倍数 ";
print " mid = (M-1) * M = ",mid;
temp=M-1; //
for (i=1;i<n-1;i++){ //temp^(n-1) 次方
temp=tempn; }
Ji=tempmid-M+1;
print "起算：最末猴所见桃子数起算逆推。n=M-2 ";
print " Ji = (M-1)^nmid-M+1 = ",Ji;
yu=(Ji-1)/Mn;
print "剩余： yu = (Ji-1)/Mn = ",yu;
Ps=Ji; //末次起算
for (i=1;i<M;i++){ //M-1 次
Ps=(Ps/(M-1)*M+1) ; }
print " ";
print "总数： Ps = (Ji/(M-1)*M+1) 运算 n 次 ";
print " all Peaches = ",Ps;
print " ";
print "计算结果： “;
print " “,M,” 个猴子，分桃 “,M,” 次”;
print " 桃子总数 = ",Ps;
print " 剩余桃子 = ",yu;
}//calculate1 ()
calculate2 (){//迭代公式解法
int Ps; //桃子数
int yu; //最后剩余数
clearOutput ();
print “**** 迭代公式解法 ****”;
print "公式：几猴 M 几次 n >>> M^n - M + 1 ";
print “解释：几个猴子的几次方减去几个桃子加 1 “;
print " 公式由数学教授专家推导证明，”;
print " 详数学通报1980年 4 期”;
// 设：任一猴到时桃子数为 x ，
// 离去时剩余数 y，则 5y = 4x-1
// A= (x-1) /5 y = 4A = (x-1) /5 * 4= 4/5 (x-1)
// 函数关系式 y = 4/5 (x-1)
// 迭代函数式 f (x) = 4/5 (x-1)
// 则 M = f (f (f (f (f (x))))) = f^5 (x)
// f (x) = (4/5)x - (4/5) =(4/5)x+(16/5)-(20/5)
// = (4/5) (x+4)-4
// f^5 (x) = (4/5)^5 (x+4)-4
// N+4 能被 5^5 = 3125 整除
// N = 3125 - 4 = 3121
print " ";
n=M;
print ”Input >> 几猴几次 “,M,” 猴， M = “,M,” , n = ",n;
print " ";
print “计算如下：”;
Ps=1;
for (i=0;i<M;i++){ //M 次方
Ps=PsM;
print i+1," . ","桃子数 = ",Ps; }
yu=M-1;
for (i=1;i<M;i++){ //M-1 次方
yu=yu(M-1) ; }
yu=yu-M+1;
print "剩余： yu = (M-1)^n-M+1 = ",yu;
print " ";
print "计算结果： “;
print " “,M,” 个猴子，分桃 “,M,” 次”;
print " 桃子总数 = ",Ps-M+1;
print " 剩余桃子 = ",yu;
}//calculate2 ()
calculate3 (){//小学奥数解法
clearOutput ();
int n; //运算次数
int Ji; //起算
int temp;
int yu; //最后剩余数
int Ps; //总数
print "**** 小学奥数解法 ";
print “最末猴所见桃子数起算逆推。”;
print "起算数 Ji = (M-1)^n * M - M + 1 ";
print “逆推 n 次得到总数。”;
print " ";
n=M;
print ”Input >> 几猴几次 “,M,” 猴， M = “,M,” , n = ",n;
print " ";
print “计算如下：”;
n=M-1;
temp=n; //M-1
for (i=1;i<n;i++){ //(M-1)^n 次方
temp=tempn; }
Ji=tempM-M+1;
print "起算： n=M-1, Ji = (M-1)^nM-M+1 = ",Ji;
yu=(Ji-1)/Mn;
print "剩余： yu = (Ji-1)/M*n = ",yu;
Ps=Ji; //末次起算
for (i=1;i<M;i++){ //M-1 次
Ps=(Ps/(M-1)*M+1) ; }
print " ";
print "总数： Ps = (Ji/(M-1)*M+1) 运算 n 次 ";
print " all Peaches = ",Ps;
print " ";
print "计算结果： “;
print " “,M,” 个猴子，分桃 “,M,” 次”;
print " 桃子总数 = ",Ps;
print " 剩余桃子 = ",yu;
}//calculate3 ()
calculate4 (){//小学奥数解法
clearOutput ();
int temp;
int yu; //最后剩余数
int Ps; //总数
print "**** 奥数解法 (2) ***";
print "设：几猴为 M ，几次为 n ";
print "桃子总数为：M 的 n次方 减去M 加 1 ";
print "剩余数为：(M-1)的 n次方 减去M 加 1 ";
print " ";
n=M;
print ”Input >> 几猴几次 ",M, " 猴。 M = “,M,” , n = ",n;
print " ";
print “计算如下：”;
n=M-1;
Ps=1 ; // =M
for (i=0;i<M;i++){ // M n次方
Ps=PsM; }
Ps=Ps-M+1;
print "桃子总数： Ps = M^n - M + 1 = ",Ps;
temp=M-1;
for (i=0;i<n;i++){ //M 次
temp=temp*n; }
yu=temp-M+1;
print "剩余： yu = (M-1)^n - M + 1 = ",yu;
print " ";
print " ";
print "计算结果： “;
print " “,M,” 个猴子，分桃 “,M,” 次”;
print " 桃子总数 = ",Ps;
print " 剩余桃子 = ",yu;
}//calculate4 ()
calculate5(){ //穷举解法
clearOutput ();
int A; //基数
int mid; //间差
int k; //运算次数
int Ji; //起算
int temp;
int yu; //最后剩余数
int Ps; //总数
print "**** 穷举法 求解 **";
print "起算基数： A = (M-1) * (M-1) ";
print "运算步长：mid = (M-1) * M ";
print " ";
if (M>7){ print “Input >> “,M,” 猴。运算时间超长，不利计算。降次计算。”; M=7 ; }
k=1;
print ”Input >> 几猴几次 ",M, " 猴。 M = “,M,” , n = ",n;
Ps=(M-1)(M-1); //起算
A= (M-1)(M-1);
mid=(M-1)*M;
print "起算基数： A = ",A;
print "运算步长：mid = ",mid;
scan_Ps:
k=k+1;
Ps=Ps+mid;
temp=Ps ;
// print " Ps = ",Ps ;
for (i=0;i<M-1;i++){
if (temp-temp/(M-1)*(M-1)==0){
temp=temp/(M-1)*M+1;
// print " temp = ",temp;
}else { goto scan_Ps ; }
} //运算M-1 次
print " ";
print "计算结果： “;
print " “,M,” 个猴子，分桃 “,M,” 次”;
yu=Ps/M*(M-1) ;
Ps=temp;
print " 桃子总数 = ", Ps;
print " 剩余桃子 = ", yu;
print " ";
print " scan_Ps 次数 = “,k,” 次 ";
// 5 猴 k = 64 次， 7 猴 k = 7776 次 ( 耗时 )
}//calculate5()
inputmonkey (){//输入
double m;
m=doubleInput (" 输入几猴（几次分桃） “,” 数字 3 – 9， ( 整数运算限制 )\n 输入 [ 空 ] 退出 " ) ;
M=(int)m;
if (m==0)M=5;
if (m<3)M=3;
if (m>9)M=9;
clearOutput ();
print "input 几猴分几次 = ",M;
calculate1 ();
}//inputmonkey ()
myToolBarProc(int nBtn,int nContext)
if(nBtn100){//输入几猴
inputmonkey ();
}
if(nBtn101){//算术解法
calculate1 ();
}
if(nBtn102){//迭代解法
calculate2 ();
}
if(nBtn103){//奥数解法
calculate3 ();
}
if(nBtn==104){//退出程序
clearOutput();
setDisplay (0);
exit (0);
}
}//myToolbar ()
myMenuProc(int nMen,int nContext)
{
if(nMen200){
print “输入几猴”;
inputmonkey ();
}
if(nMen201){//算术解法
calculate1();
}
if (nMen202){//迭代解法
calculate2();
}
if (nMen203){//奥数解法
calculate3();
}
if(nMen204){//奥数解法(2)
calculate4 ();
}
if(nMen205){//穷举解法
calculate5 ();
}
if (nMen==206){//Exit
clearOutput();
exit (0); }
}//myManu()
//**** end ***********g
|