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

《《算法设计与分析》实验一-14210501》由会员分享，可在线阅读，更多相关《《算法设计与分析》实验一-14210501（23页珍藏版）》请在装配图网上搜索。

1、学 号 算法设计与分析实验报告一学生姓名heish专业、班级地理指引教师唐国峰成绩计算机与信息工程学院软件工程系 年 3 月 4日实验一:递归方略运用练习一、实验目的本次实验是针对递归算法的算法设计及应用练习,旨在加深学生对该算法原理的理解，提高学生运用该算法解决问题的能力。二、实验环节与规定.实验前复习课程所学知识以及阅读和理解指定的课外阅读材料;2学生独自完毕实验指定内容；3实验结束后,用统一的实验报告模板编写实验报告。4.提交阐明: （1）电子版提交阐明：a 需要提交Winrar压缩包,文献名为“算法设计与分析实验一_学号_姓名”，如“算法设计与分析实验一_09200_张三”。 b 压缩

2、包内为一种“算法设计与分析实验一学号_姓名”命名的顶层文献夹,其下为两个文献夹，一种文献夹命名为“源程序”，另一种文献夹命名为“实验报告电子版”。其下分别放置相应实验成果物。 （2)打印版提交阐明：a不可随意更改模板样式。 b字体:中文为宋体，大小为0号字,英文为i Ne Roman,大小为10号字。 c 行间距：单倍行距。(3)提交截止时间：月28日6:0。三、 实验项目1.运用递归方略设计算法实现下述题目的求解过程。题目列表如下：【必做题】 (1)运动会开了天，一共发出金牌M枚。第一天发金牌1枚加剩余的七分之一枚,第二天发金牌枚加剩余的七分之一枚，第天发金牌枚加剩余的七分之一枚,后来每天都

3、照此办理。到了第N天刚好尚有金牌枚,到此金牌所有发完。编程求N和。 (2)国王分财产。某国王临终前给儿子们分财产。她把财产分为若干份，然后给第一种儿子一份,再加上剩余财产的1/1;给第二个儿子两份,再加上剩余财产的/0;；给第i个儿子i份,再加上剩余财产的/1。每个儿子都窃窃自喜。觉得得到了父王的偏爱,孰不知国王是“一碗水端平”的。请用程序回答,老国王共有几种儿子？财产共提成了多少份？()发售金鱼问题:第一次卖出所有金鱼的一半加一半条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼;第四次卖出剩余金鱼的五分之一加五分之一条金鱼；目前还剩余11条金

4、鱼，在发售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？（4)某路公共汽车,总共有八站，从一号站发轩时车上已有n位乘客,到了第二站先下一半乘客,再上来了六位乘客;到了第三站也先下一半乘客,再上来了五位乘客,后来每到一站都先下车上已有的一半乘客,再上来了乘客比前一站少一种,到了终点站车上尚有乘客六人,问发车时车上的乘客有多少？(5)猴子吃桃。有一群猴子摘来了一批桃子,猴王规定每天只准吃一半加一只（即第二天吃剩余的一半加一只，以此类推)，第九天正好吃完,问猴子们摘来了多少桃子？（6）小华读书。第一天读了全书的一半加二页，第二天读了剩余的一半加二页,后来每天如此,第六天读完了最后的

5、三页，问全书有多少钱页?（7)日本出名数学游戏专家中村义作专家提出这样一种问题:爸爸将220个桔子分给六个儿子。分完 后爸爸说：“老大将分给你的桔子的/给老二;老二拿到后连同原先的桔子分1给老三;老三拿到后连同原先的桔子分1/给老四;老四拿到后连同原先的桔子分1/5给老五;老五拿到后连同原先的桔子分1/给老六；老六拿到后连同原先的桔子分1给老大”。成果人们手中的桔子正好同样多。问六兄弟本来手中各有多少桔子？（）某种传染病第一天只有一种患者，前5天为潜伏期,不发作也不会传染人,第6天开始发作，从发作到治愈需要5天时间，期间每天传染个人，求第N天共有多少患者。【选做题】(选3) (）为了保障社会秩

6、序，保护人民群众生命财产安全,警察叔叔需要与罪犯斗智斗勇,因而需要常常性地进行体力训练和智力训练！某批警察叔叔正在进行智力训练: 2 34 5 6 789 =11; 请看上边的算式,为了使等式成立,需要在数字间填入加号或者减号(可以不填，但不能填入其他符号）。之间没有填入符号的数字组合成一种数,例如：12+345+7+9 就是一种合格的填法;12+5+6-89是另一种也许的答案。 请你运用计算机的优势,协助警察叔叔迅速找到所有答案。 每个答案占一行。形如：14+5+78+9123+5+67-89(2）递归将一种整数输出。形如521，输出1,2,3，4,6(3）用递归实现分解质因数。形如：12=

7、2*23（）50个阶梯,你一次可以上一阶或两阶,走上去，共有多少种走法?(5）电话号码相应的字符组合。题目:在电话或者手机上，一种数字如2相应着字母ABC,7相应着PQRS。那么数字串2所相应的字符的也许组合就有3*4=1种（如P,BR等)。目前输入一种到11位长的电话号码,请打印出这个电话号码所相应的字符的所有也许组合和组合数。四、实验过程如下程序都是在VS下编译与VC60代码稍有不同。（)运动会开了N天,一共发出金牌枚。第一天发金牌1枚加剩余的七分之一枚,第二天发金牌2枚加剩余的七分之一枚,第天发金牌3枚加剩余的七分之一枚,后来每天都照此办理。到了第N天刚好尚有金牌枚，到此金牌所有发完。编

8、程求N和M。题目分析根据题目可写出递归式：(F(n）-n)6=F(n+1);(n)是第n天奖牌总数即第-1天剩余的涉及第天发的和剩余的。每天发放的金牌数:当每天数（前一天剩余金牌-当每天数)/7，因此鉴别递归的条件是（前一天剩余金牌-当每天数)为7的整数倍,第i+1天的金牌数即i天剩余的必须是6的整数倍。算法构造递归函数:Sm(+1,n)=（nSum(i,n)-)*/7.筛选条件：(nSm(i,n)-i)%70&（Su(i,n)6=)算法实现#nludstdioh#ei devide 7;/不知什么因素这样定义下面不能用？vc.0未安上,不知与vs有和区别？int nSum(in i,int

9、n)/nSum（)函数定义第i天的金牌数即i天剩余. int reult=；f(=) urn n;eseresut=(nSum(i+1,n)*7)/6+i);/递归函数：num(1,n)=(nSum（i,n)-i)*6/7.eturn sult;oi i(）for(in =;n=10;n)/递增比赛天数逐个验证int kip=0;fo(i i1;i=n;i）/依次筛选从i=1到符合条件的n值if（(num(i,n)i)%7=&(nSm(i,)6=0)/每天发放的金牌数:当每天数(前一天剩余金牌-当每天数)/7,即（前一天剩余金牌-当每天数）为7的整数倍 int skp=; /递归函数:nSu(

10、i+1,）(nSum（,）-i）*6/7即nS(i,n)=nSm（,n）7/6+，第i+1天的金牌数即天剩余的必须是6的整数倍 pritf（共有金牌%d枚,共进行%d天,nSum(1,），n);/金牌总数即第一天金牌数 fr(in j=1;=n;j+)prnf(第%天,发放%+d枚,还剩%d枚n,j,j,(nS(j,)-)/7，（nSu（j,）-j）67); break;if(ski=1)/用于跳出双层循环构造即n递增时第一种满足时即可输出,可运营成果却否则rak；/会有在n上界内更多的构造输出，只有第一种n值满足不知为什么？?etca();运营成果经验归纳递归式容易想出，但是相对的筛选条件比

11、较难拟定。(2）国王分财产。某国王临终前给儿子们分财产。她把财产分为若干份,然后给第一种儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的11;给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。觉得得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几种儿子?财产共提成了多少份?题目分析这道国王分财产的题和上题运动会发金牌类似,但是在筛选条件仅由题意略不同其实质也是同样，每个儿子分到的财产相似即:E(i+1,)-(i，n)E(i,)E(i-，n），且第i个儿子分i份及剩余的1,即E(i,n）-的差是10的整数倍。算法构造递归函数：E（1,）

12、=（(i，)-)*9/0;(i,n）为当要分给第i个儿子时尚有的份数；筛选条件:每个儿子分到的财产相似即E(，n)-E(，n)=（i,n)E(i-,n);且第i个儿子分i份及剩余的1/1,即(i,)-i的差是0的整数倍。算法实现#inclde#dfie evid 10；/这样定义到背面不知怎么却出错。 (int ,int n）/递归函数:E（+1,n)=（E(,)n)*10；(i,n）为当要分给第i个儿子时尚有的份数； sm=0;if（i=)retun n;/当份到最后一种儿子时分完，往前求解;ese=(E（i+1,n）*1)+;/依次递归;returum;voidmn()for(nt n=3

13、;n；n+）intsi=0；fr(int i=2;n；i+) /每个儿子分到的财产相似即E（i1，n)E（,n）=（，n)-E(i,）;/且第i个儿子分i份及剩余的1/10,即(i,n)i的差是0的整数倍;if(2*E(,n)E(i1，n)-E(i+1,n)=0)&(E(i,n）%10=0)/用这两个条件筛选；in skip=1;print（国王共有%个儿子,财产共提成%d份。n，n,(1,n）;/总份数即要分第一种儿子时有的分数(，n)fr(nt j=1；j=;j+)pitf（第d个儿子,分%d+%d份,还剩%d份。,j，,(E（j,n)j)/10,(E(j,n）-j)9/1）；brk;i(

14、skip=1)beak；gtca（）;运营成果经验归纳由于和第一题类似，此题较为顺利，类似多练习也会得心应手。（)发售金鱼问题:第一次卖出所有金鱼的一半加一半条金鱼;第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼;第四次卖出剩余金鱼的五分之一加五分之一条金鱼;目前还剩余11条金鱼，在发售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？题目分析与上题类似出口为第四次买之前尚有减去第四次买的尚有11条。算法实现#ncludestd.h#ine n ;int Fi（nt i）构造函数Fih(i)为第i天卖之前还剩多少，Fish（1）即为总鱼

15、数;nt sult=0;if（)resut=(Fish(i+1)+(Fish(i+1）+1)/i);ereturn1;/第四天卖之前的第四天卖的1，即Fsh(4)-（Fih(4)/5+1/)=11，F(4）=11reureu；vod main()pritf(共有金鱼%d条。n,Fih（1);for(in i=1;i=4;+)prnt（第%d天,卖%d条，还剩%d条。n,i,(Fish（i)+i)(i+1），(Fsh(i)-(Fish(i)+i)/（i1)；getcar（);运营成果经验归纳:以上题目类似可类比做出。4.某路公共汽车,总共有八站，从一号站发轩时车上已有n位乘客,到了第二站先下一半

16、乘客,再上来了六位乘客；到了第三站也先下一半乘客,再上来了五位乘客，后来每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一种，到了终点站车上尚有乘客六人，问发车时车上的乘客有多少?题目分析此题与以上几题类似，略有不同而已。算法构造由于从第一站出发没有任何变动，故将第二站作为始发站；函数us(i）为达到第i站尚未上下乘客时车上人员数量；算法实现#icludent Bu(n i)/由于从第一站出发没有任何变动，故将第二站作为始发站; 函数Bs(i)为达到第i站尚未上下乘客时车上人员数量；int sum=0;if（6）/m=（us(+1)+-);/有递归函数:Bs(i+1)Bus(i）/27

17、-i;lsereturn 10;/由最后还剩6人推的Bu（6)10;rtur sm；void man()rn(发车时车上共有%d人。n，B()；fr（int =；i6;i+)ritf（第%站,上来%d人,下去%d人,剩余%人n,i+,(7-i)，(s()/2),Bs(+1）);getcr（);运营成果（5)猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩余的一半加一只，以此类推)，第九天正好吃完,问猴子们摘来了多少桃子?题目分析与上题类似算法构造递推函数nky(i)表达第天吃的和剩余的和;由Monkey（i+1）=Monkey（）2-推得;由Mone（9)onke

18、y（9）2+1,得出口Mnk(9）=2。算法实现#nclue Mokey(nt )/递推函数Monkey(i)表达第天吃的和剩余的和；in su0;if(i9)=（key(i+1)+1);/由Monkey(i1）=Mney(i)/-1推得;elsereurn 2;/由onkey(9)=oney(9)/2+,得出口Moke(9)=2;retunum;void in(）prif(共有桃子%d个。n，Monkey（1);fr（it i=;i9；i+)pntf(第d天,吃%d%个，剩余%个。,i,okey(i)2,1,Monkey(i）2-1)；getchar();运营成果（6)小华读书。第一天读了全

19、书的一半加二页,第二天读了剩余的一半加二页,后来每天如此，第六天读完了最后的三页，问全书有多少页？题目分析与以上题目类似。算法构造构造递推函数:ook(i）;表达第i天要读时还剩的页数；由Bok(i+1）oo(i）-(Bo()/2+2）得出;由Boo(5)(Bok()+）=3可得出口;算法实现#cludeitBok(int i)/构造递推函数:Book（);表达第i天要读时还剩的页数;in u=0；if(i)sm=2*(Bok（i1)+2)；/由Book（+1)=Bok（i)(Bok()/2+2)得出；eeretur0;/由Bo（5)-(ok（5)+2)可得出口;rersm;vod an（)r

20、intf(全书共%d页。n，Book(）)；for(int i=1;=5;i+)rint(第%天,看%d+%d页,还剩%d页。n，,ook()2，2,Book()-);getchar();运营成果（)日本出名数学游戏专家中村义作专家提出这样一种问题：爸爸将25个桔子分给六个儿子。分完 后爸爸说:“老大将分给你的桔子的18给老二;老二拿到后连同原先的桔子分1/7给老三;老三拿到后连同原先的桔子分/给老四;老四拿到后连同原先的桔子分/5给老五;老五拿到后连同原先的桔子分1给老六；老六拿到后连同原先的桔子分1/3给老大”。成果人们手中的桔子正好同样多。问六兄弟本来手中各有多少桔子?题目分析由老大开始

21、分给老二,当老大拿到老六的后总数达到平均数,以此为入口进行递推。算法构造第一种孩子从国王那里分到的桔子总数应为平均数减去最后一种孩子分出去的部分后乘以87。算法实现#iclde stdio.dfine DENOMINATO_M 8/分母最大值#dfin DNONATR_MIN 3 /分母最小值/ai0表达第i个孩子分出的桔子总数/ai1表达第i个孩子从国王那里分到的桔子总数nt Ora(n a52，it i） intavrge250; intp; if (i=) /第一种孩子从国王那里分到的桔子总数应为平均数减去最后一种孩子分出去的部分后乘以8/。 ai (avrage-aveg/(DENOM

22、INATOR_MIN-1)*（ENOMNATOR_MAX-i)/(ENOMITOR_-1); /第一种孩子分给第二个孩子的桔子数量。 i0 = i1 - (averge-aerage/(DENOINAON-1）); else /第i个孩子从国王那里分到的桔子总数。 a average*(DENOINATOR_MA)/(DNOINATOR_MAX-i) - ane(,i1)； /第i个孩子分给第i+1个孩子的桔子数量。 aiai1 One(a，-1) -average; =ai0; er p; /主函数 voi mn() int ora52=0,0，0,0,0，,0，0; ge(r,5）; fo

23、(int j=0;j=5；j+) pintf（第d个孩子分出%d个橘子。n,j+1,oa0）; pitf(国王最初分派桔子状况如下所示：n); r(it k0;=5;k） pritf(第%d个孩子从国王那里分得%d个橘子。n,1，ak1)； gethar(); 运营成果(8）某种传染病第一天只有一种患者,前5天为潜伏期，不发作也不会传染人,第天开始发作，从发作到治愈需要5天时间，期间每天传染3个人，求第N天共有多少患者。题目分析第天的病总人数涉及n-天潜伏的和发作的在当天又传染的人数再去掉当天治愈的；算法构造递推函数：该病五天内潜伏第六天发病后五天内治愈。Day()=ay(n-5)3+Dy(n

24、-1);算法实现incluestdiohicudein ay(in )/递推函数:该病五天内潜伏第六天发病后五天内治愈。insum=0;if（n5)/五天内只有一种潜伏病人。retu 1;lsesum=ay(n-5)*+Day(n-1);/第n天的病总人数涉及n天潜伏的和发作的在当天又传染的人数再去掉当天治愈的； /y()Da(n）*+Da（n-1);return ;void min()i npritf（请输入传染病发生后的天数:n);scfs（%,&n,2)；for(in i=1;i=n;)printf（第%天，得病的人数%dn,Da（i);ssem(pae);运营成果选做题:（5选3）（）

25、5个阶梯，你一次可以上一阶或两阶，走上去，共有多少种走法?题目分析这道题让我想到高中时做过的同样的一道排列组合题,但此题要用计算机编程求出具体数字，不像高中时只用代数式体现。算法构造假设为20阶：C( 20)+(1 1）+ C(2 1）+C(3 17）+ C(6)+ （ 15）+ C(6 14)+ C（7 ）+ C（812) C(91）+ C（10 1）算法实现#inud#incldeinttar（intn）if(n=1)retur1;f(n=)reun 1;returnstar(1)+stairs(2);/根据有1阶依次往上递推发现符合斐波那契数列 /n=-1+an-2vod mai()in

26、tj;printf(请输入楼梯阶数：n)；sca_s(%d,j,2);or(int i=;i=j;i+）prinf(当有%d阶楼梯，共有%d种走法。,，trs（);system（puse);运营成果数据也许过大或者电脑太o等了几分钟未见成果,根据后几阶时可判断是对的。经验归纳有些题看似困难当理清思路也可有据可循。（2)递归将一种整数输出。形如6532,输出1,2,3,4,5，6题目分析将一种整数逆序输出可以看做把一种字符串逆序输出,用指针逐个输出。算法构造reverse（ontchr*）字符串递推函数:设定字符串指针*p;算法实现程序源代码#incdevoid revrs(const char

27、 *p)/字符串递推函数:设定字符串指针p；i(*=0）/指针从右向左移动由于判断字符串尾部位置；return;reerse(p1);/指针向前移动p+1rnf(%c，,*）;/输出目前指针指向的字符；odain（)ch *tig；pStrng1356；print(输入的字符串:sn,Sring)；reve（Srn)；getchr（);运营成果经验归纳巧用字符串指针可以简化程序。(3)用递归实现分解质因数。形如：12=22*3题目分析质因数n即只能被自身和整除的数,在2到n-间筛选能被整除且是质因数的数即可分解。算法构造bol Isme(intnm）/判断质因数;if(（IsPime（i）)&

28、(nu% = 0)/判断除数与否为质因数；um = um /i;rmeFacoriztion(num);若是其一则保存对剩余的商继续鉴别；算法实现#ilude #incue/质因数判断函数olIPrim（in nm)/判断质因数； int ; fo(i = 2； m;+) if ( nm i= )/如果从2到num-1的数里有能被整除的,阐明u不是质因数。etun alse; /如果从2到num-1的数里没有能被整除的,阐明num是质因数。 ertrue; viPrimeFctrizat(itnum） n i;for （=; i=u; +） if（i= )ritf(%,）; elsif(IsPime（i)&（ num % i = )/质因数判断函数；/将找到的质因数追加到字符串中。intf(%d,i);/将剩余部分递归分解。= nu / ；PrimeFactorztin(num）;brak； voidain（) itnum;pintf（请输入一种不不小于0位的整数：); can_(%d,nm,10)；printf(质因数分解：n%d=,num);/调用分解质因数函数。 Prmactorizion(num);prnt(n）;yse(pase)；运营成果经验归纳弄清题目核心字的概念对编程很是核心。五、实验总结 编程蛮故意思,在这里可以格物致知看到不同样的世界。