《算法设计与分析》实验一_14210501

学号1421050102《算法设计与分析》实验报告一学生姓名Cherish专业、班级地理指导教师唐国峰成绩计算机与信息工程学院软件工程系2017年3月14日实验一：递归策略运用练习一、实验目的本次实验是针对递归算法的算法设计及应用练习，旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。二、实验步骤与要求1．实验前复习课程所学知识以及阅读和理解指定的课外阅读材料；2．学生独自完成实验指定内容；3．实验结束后，用统一的实验报告模板编写实验报告。4．提交说明：（1）电子版提交说明：a需要提交Winrar压缩包，文件名为“《算法设计与分析》实验一_学号_姓名”，如“《算法设计与分析》实验一_09290101_张三”。b压缩包内为一个“《算法设计与分析》实验一_学号_姓名”命名的顶层文件夹，其下为两个文件夹，一个文件夹命名为“源程序”，另一个文件夹命名为“实验报告电子版”。其下分别放置对应实验成果物。（2）打印版提交说明：a不可随意更改模板样式。b字体：中文为宋体，大小为10号字，英文为TimeNewRoman，大小为10号字。c行间距：单倍行距。（3）提交截止时间：2017年3月28日16:00。三、实验项目1．运用递归策略设计算法实现下述题目的求解过程。题目列表如下：【必做题】（1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。（2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？（3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？（4）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？（5）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？（6）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此……，第六天读完了最后的三页，问全书有多少钱页？（7）日本著名数学游戏专家中村义作教授提出这样一个问题：父亲将2520个桔子分给六个儿子。分完后父亲说：“老大将分给你的桔子的1/8给老二；老二拿到后连同原先的桔子分1/7给老三；老三拿到后连同原先的桔子分1/6给老四；老四拿到后连同原先的桔子分1/5给老五；老五拿到后连同原先的桔子分1/4给老六；老六拿到后连同原先的桔子分1/3给老大”。结果大家手中的桔子正好一样多。问六兄弟原来手中各有多少桔子？（8）某种传染病第一天只有一个患者，前5天为潜伏期，不发作也不会传染人，第6天开始发作，从发作到治愈需要5天时间，期间每天传染3个人，求第N天共有多少患者。【选做题】（5选3）（1）为了保障社会秩序，保护人民群众生命财产安全，警察叔叔需要与罪犯斗智斗勇，因而需要经常性地进行体力训练和智力训练！某批警察叔叔正在进行智力训练：123456789=110;请看上边的算式，为了使等式成立，需要在数字间填入加号或者减号（可以不填，但不能填入其它符号）。之间没有填入符号的数字组合成一个数，例如：12+34+56+7-8+9就是一种合格的填法；123+4+5+67-89是另一个可能的答案。请你利用计算机的优势，帮助警察叔叔快速找到所有答案。每个答案占一行。形如：12+34+56+7-8+9123+4+5+67-89（2）递归将一个整数输出。形如654321，输出1,2,3,4,5,6（3）用递归实现分解质因数。形如：12=2*2*3（4）50个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法？（5）电话号码对应的字符组合。题目：在电话或者手机上，一个数字如2对应着字母ABC，7对应着PQRS。那么数字串27所对应的字符的可能组合就有3*4=12种（如AP，BR等）。现在输入一个3到11位长的电话号码，请打印出这个电话号码所对应的字符的所有可能组合和组合数。四、实验过程以下程序都是在VS2010下编译与VC6.0代码稍有不同。（1）运动会开了N天，一共发出金牌M枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第N天刚好还有金牌N枚，到此金牌全部发完。编程求N和M。题目分析依据题目可写出递归式：(F(n)-n)*6/7=F(n+1);F(n)是第n天奖牌总数即第n-1天剩余的包括第n天发的和剩下的。每天发放的金牌数：当天天数+（前一天剩余金牌-当天天数）/7，所以判别递归的条件是（前一天剩余金牌-当天天数）为7的整数倍，第i+1天的金牌数即i天剩下的必须是6的整数倍。算法构造递归函数：nSum(i+1,n)=(nSum(i,n)-i)*6/7.筛选条件：(nSum(i,n)-i)%7==0&&(nSum(i,n)%6==0)算法实现#includestdio.h#definedevide7;//不知什么原因这样定义下面不能用？vc6.0未安上，不知与vs2010有和区别？intnSum(inti,intn)//nSum()函数定义第i天的金牌数即i-1天剩下.{intresult=0;if(i==n){returnn;}else{result=((nSum(i+1,n)*7)/6+i);//递归函数：nSum(i+1,n)=(nSum(i,n)-i)*6/7.}returnresult;}voidmain(){for(intn=2;n=10;n++)//递增比赛天数逐个验证{intskip=0;for(inti=1;i=n;i++)//依次筛选从i=1到n符合条件的n值{if((nSum(i,n)-i)%7==0&&(nSum(i,n)%6==0))//每天发放的金牌数：当天天数+（前一天剩余金牌-当天天数）/7，即（前一天剩余金牌-当天天数）为7的整数倍{intskip=1;//递归函数：nSum(i+1,n)=(nSum(i,n)-i)*6/7即nSum(i,n)=nSum(i+1,n)*7/6+i，第i+1天的金牌数即i天剩下的必须是6的整数倍printf(共有金牌%d枚,共进行%d天\n,nSum(1,n),n);//金牌总数即第一天金牌数for(intj=1;j=n;j++){printf(第%d天,发放%d+%d枚,还剩%d枚\n,j,j,(nSum(j,n)-j)/7,(nSum(j,n)-j)*6/7);}break;}}if(skip==1)//用于跳出双层循环结构即n递增时第一个满足时即可输出，可运行结果却不然break;//会有在n上界内更多的结构输出，只有第一个n值满足不知为何？？}getchar();}运行结果经验归纳递归式容易想出，但是相对的筛选条件比较难确定。（2）国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；……；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？题目分析这道国王分财产的题和上题运动会发金牌类似，不过在筛选条件仅由题意略不同其实质也是一样，每个儿子分到的财产相同即：E(i+1,n)-E(i,n)=E(i,n)-E(i-1,n)，且第i个儿子分i份及剩下的1/10，即E(i,n)-i的差是10的整数倍。算法构造递归函数：E(i+1,n)=(E(i,n)-n)*9/10;E(i,n)为当要分给第i个儿子时还有的份数；筛选条件：每个儿子分到的财产相同即E(i+1,n)-E(i,n)=E(i,n)-E(i-1,n)；且第i个儿子分i份及剩下的1/10，即E(i,n)-i的差是10的整数倍。算法实现#includestdio.h#definedevide10;//这样定义到后面不知怎么却出错。intE(inti,intn)//递归函数：E(i+1,n)=(E(i,n)-n)*9/10;E(i,n)为当要分给第i个儿子时还有的份数；{intsum=0;if(i==n)returnn;//当份到最后一个儿子时分完，往前求解；elsesum=(E(i+1,n)*10)/9+i;//依次递归；returnsum;}voidmain(){for(intn=3;n=10;n++){intskip=0;for(inti=2;in;i++){//每个儿子分到的财产相同即E(i+1,n)-E(i,n)=E(i,n)-E(i-1,n)；//且第i个儿子分i份及剩下的1/10，即E(i,n)-i的差是10的整数倍；if((2*E(i,n)-E(i-1,n)-E(i+1,n)==0)&&(E(i,n)-i)%10==0)//用这两个条件筛选；{intskip=1;printf(国王共有%d个儿子,财产共分成%d份。\n,n,E(1,n));//总份数即要分第一个儿子时有的分数E(1,n)for(intj=1;j=n;j++)printf(第%d个儿子，分%d+%d份，还剩%d份。\n,j,j,(E(j,n)-j)/10,(E(j,n)-j)*9/10);break;}}if(skip==1)break;}getchar();}运行结果经验归纳由于和第一题类似，此题较为顺利，类似多练习也会得心应手。（3）出售金鱼问题：第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？题目分析与上题类似出口为第四次买之前还有减去第四次买的还有11条。算法实现#includestdio.h#definen4;intFish(inti)//构造函数Fish(i)为第i天卖之前还剩多少，Fish(1)即为总鱼数；{intresult=0;if(i4)result=(Fish(i+1)+(Fish(i+1)+1)/i);elsereturn14;//第四天卖之前的-第四天卖的=11，即Fish(4)-(Fish(4)/5+1/5)=11,F(4)=11returnresult;}voidmain(){printf(共有金鱼%d条。\n,Fish(1));for(inti=1;i=4;i++){printf(第%d天,卖%d条，还剩%d条。\n,i,(Fish(i)+i)/(i+1),(Fish(i)-(Fish(i)+i)/(i+1)));}getchar();}运行结果经验归纳：以上题目类似可类比做出。4.某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客，到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个……，到了