C语言程序设计五猴分桃问题实验报告
课 程 设 计 报 告
学院、系:吉林大学珠海学院计算机科学与技术系专业名称:软件工程课程设计科目C语言程序课程设计所在班级:10班学生学号:学生姓名:赵学文指导教师:郭晓燕完成时间:3月-5月
五猴分桃问题
设计任务与目标
关于五猴分桃问题,已经有很多人思考和尝试建立了一些程序解决。五猴分桃,五只猴子合作摘了很多桃子,感到累了,决定先去睡觉,醒后再分。不知过了多久,第一只猴子醒了,看见其它猴子都没有醒,就把所有桃子分为五堆,发现多一个,就吃了一个,拿走一堆,把剩下的又堆在一起走了。第2只猴子醒来,以为自己是第一个,也是把桃子分为五堆,也是多一个,就吃了一个,拿走一堆,剩下的又堆在一起走了。第3,4,5只猴子都是这样归根究底是一个数学上的问题,但在程序员眼中,解决一个问题,不仅要得出答案,还要以最简便的方法,在最短的时间内得出答案。所以,即使这是一个耳熟能详的问题,不同程序员眼里,也有不同的方法。在复杂之中提取捷径便是我的目的,完成这个设计,能提高自我能动性,并联系数学实际。我希望通过这次设计,增强自我独立能力,并进一步激发我对编程这一方面的兴趣。
二、方案设计与论证
对于这一个问题,难就难在每次分时都多出1个桃子。这又关系到数学问题,每次少1个,数据不确定,如果从大方面去考虑的话,计算过程确实比较复杂。既然如此,何不从另一个角度入手?我们没必要先去猜这堆桃子到底总共有多少个,大概范围为多少。实际上可以理解桃子里少了4个;于是,我们可借给它们4个再分。为什么?因为尽管多了四个,但每个猴子分得的桃子不会多,也不会少,且每次都可以被5整除。怎样借?方法其实很简单,就是数学的假设问题。我们不妨先设借到4个桃子后的总数为X,原来桃子的总数为Y。则有Y=X-4。
第一只猴子分完后的总数为:A=X/5*4;
第二只猴子分完后的总数为:B=A/5*4=X/25*16;
第三只猴子分完后的总数为:C=B/5*4=X/125*64;
第四只猴子分完后的总数为:D=C/5*4=X/625*256;
第五只猴子分完后的总数为:E=D/5*4=X/3125*1024;
事实上每次分前,猴子的数量都不变。分后,桃子的堆数也不变。于是,各猴子分桃便有上式这样的一种关系。通过分析,很明显,借到4个桃子后,每次分完时总数都是整数。X从第五只猴子分完后至少能被3125整除,所以X至少为3125。猴子至少摘了桃子Y=3125-4=3121;
第一只猴子至少分得:3125/5=625;
第二只猴子至少分得:2500/5=500;
第三只猴子至少分得:2000/5=400;
第四只猴子至少分得:1600/5=320;
第五只猴子至少分得:1280/5=256;
所以最后还剩桃子为1280-256-4=1020个桃子。
整个过程看似繁琐复杂,但事实上在添加法后,程序变得更加简明易懂。
三、程序框图或流程图,程序清单与调用关系
图1
Main函数:程序的主函数
定义整型变量i,x,y,num1,num2,num3,num4,num5,z
i代表程序循环的次数
x代表加上5个桃子后摘下桃子的总数
y代表摘下桃子的总数
num1,num2,num3,num4,num5分别代表连续五个猴子分到的桃子数
z代表最后一只猴子拿走桃子后剩下的数量
四、全部源程序清单
#include
void main() /*主函数*/
{
int i,x,y;
int num1,num2,num3,num4,num5,z;
for(i=1;i<10000;i++) /*从1至10000枚举*/
{
x=i+4;
if(x%(5*5*5*5*5) == 0) /*在以上范围内找出解*/
{
y=x-4;
printf("总数=%d \n",y);
num1=x/5;
num2=(x-num1)/5;
num3=(x-num1-num2)/5;
num4=(x-num1-num2-num3)/5;
num5=(x-num1-num2-num3-num4)/5;
z=y-num1-num2-num3-num4-num5;
printf("第一只猴子最少获得数=%d \n",num1);
printf("第二只猴子最少获得数=%d \n",num2);
printf("第三只猴子最少获得数=%d \n",num3);
printf("第四只猴子最少获得数=%d \n",num4);