全文预览

关于猴子分桃的算法讲解

上传者:似水流年 |  格式:doc  |  页数:5 |  大小:15KB

文档介绍
满足条件记为真,不满足记为假。只要5轮都为真则找到x否则x继续++。实现下一次5轮判断。*/namespace递归法_猴子分桃子{classProgram{staticintfen()//返回海滩上原来最少多少桃子{intm;boolcheck=false;//用于判断是否执行了五次,亦可用j==5作为判//断条件inti=0;while(true){i++;m=i;for(intj=0;j<5;j++){if((m-1)%5!=0)//判断m-1是否被//整除,亦可用(m-1)%5!=0代替{check=false;break;}else{m=(m-1)*4/5;check=true;}}if(check==true){returni;}}}//递归算法/*递归算法数学抽象,与非递归刚好相反,递归是倒退,从最后一只猴子向上推理。假设当前猴子有x个桃子,那么它对于下一轮的猴子来说,x-1要能分5份,而对上一轮的猴子还说,它是上一轮的5分之一。算法设计:一个变量记录当前是第几只猴子。一个变量记录当前猴子面前有原来桃子的总数。如果当前就剩1只猴子则返回所有的桃子总数,否则判断当前的桃子-1时候够下一轮猴子平分5分,而且对于上一轮的猴子我是不是上面的4/5求上一轮x*5%4==0如果是则上一轮的桃子是自己的5倍多1个而且都在总数--否则不满足条件则当前猴子总数不变,桃子总数++。继续探测。*/publicstaticinthouzi3(intmonkey,intpech){if(monkey==1){returnpech;}else{if((pech*5+1)%4==1)//if((pech-1)%5==0&&(pech-1)%4==0){returnhouzi3(--monkey,(pech*5+1));}else{returnhouzi3(monkey,++pech);}}}

收藏

分享

举报
下载此文档