递推c,c++.ppt

《递推c,c++.ppt》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、递推法2递推是计算机数值计算中的一个重要算法，可以将复杂的运算化为若干重复的简单运算，充分发挥计算机长于重复处理的特点。递推3【任务】A、B、C、D、E五人合伙夜间捕鱼，凌晨时都疲惫不堪，各自在河边的树丛中找地方睡着了，日上三竿，A第一个醒来，他将鱼平分作五份，把多余的一条扔回湖中，拿自己的一份回家去了，B第二个醒来，也将鱼平分为五份，扔掉多余的一条，只拿走自己的一份，接着C、D、E依次醒来，也都按同样的办法分鱼。问五人至少合伙捕到多少条鱼？每个人醒来后看到的鱼数是多少条？4解题思路:假定A、B、

2、C、D、E五人的编号分别为1、2、3、4、5，整数数组fish[k]表示第k个人所看到的鱼数。fish[1]表示A所看到的鱼数，fish[2]表示B所看到的鱼数……fish[1]为五人合伙捕鱼的总鱼数fish[2]=(fish[1]-1)*4/5fish[3]=(fish[2]-1)*4/5fish[4]=(fish[3]-1)*4/5fish[5]=(fish[4]-1)*4/55写成一般式fish[i]=(fish[i-1]–1)*4/5i=2,3,…,5这个公式可用于知A看到的鱼数去推算B看

3、到的，再推算C看到的，…….。现在要求的是A看到的，能否倒过来，先知E看到的再反推D看到的，……，直到A看到的。为此将上式改写为：fish[i-1]=fish[i]*5/4+1i=5,4,…,26分析上式１.当i=5时，fish[5]表示E醒来所看到的鱼数，该数应满足被５整除后余１，即fish[5]%5==12.当i=5时，fish[i-1]表示D醒来所看到的鱼数，这个数既要满足fish[4]=fish[5]*5/4+1又要满足fish[4]%5==1显然，fish[4]不能不是整数，这个结论同样

4、可以用至fish[3],fish[2]和fish[1]73.按题意要求5人合伙捕到的最少鱼数，可以从小往大枚举，可以先让E所看到的鱼数最少为6条，即fish[5]初始化为6来试，之后每次增加5再试，直至递推到fish[1]得整数且除以5之后的余数为1。根据上述思路，我们可以构思如下的程序框图：89该图可分为三部分(1)是说明部分：包含定义数组fish[6]，并初始化为1和定义循环控制变量i，并初始化为0。(2)是do….while直到型循环，其循环体又含两块：(2).1是枚举过程中的fish[5]

5、的初值设置，一开始fish[5]=1+5;以后每次增5。(2).2是一个for循环，i的初值为4，终值为1，步长为-1，该循环的循环体是一个分支语句，如果fish[i+1]不能被4整除，则跳出for循环（使用break语句）;否则，从fish[i+1]算出fish[i]。10当由break语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令fish[5]加5后再试，即重新进入直到型循环dowhile的循环体。当着正常退出for循环时，一定是控制变量i从初值4，一步一步执行到终值

6、1，每一步的鱼数均为整数，最后i=0，表示计算完毕，且也达到了退出直到型循环的条件。(3)输出计算结果11//************************************//*程序名：3-30.cpp（五人合伙捕鱼）*//*作者：ghq*//*编制时间：2011年3月2日*//*主要功能：递推算法的实现*//************************************#include//预编译命令usingnamespacestd;intmain()//

7、主函数{intfish[6]={1,1,1,1,1,1};//整型数组，记录每人醒来后看到的鱼数inti=0;do{fish[5]=fish[5]+5;//让E看到的鱼数增5。for(i=4;i>=1;i--){if(fish[i+1]%4!=0)break;//跳出for循环elsefish[i]=fish[i+1]*5/4+1;//计算第i人看到的鱼数}}while(i>=1);//当i>=1继续做do循环for(i=1;i<=5;i++)cout<

8、果return0;}12intmain()//主函数{intfish[6]={1,1,1,1,1,1};//数组，记录每人看到的鱼数inti=0;do{fish[5]=fish[5]+5;//让E看到的鱼数增5。for(i=4;i>=1;i--){if(fish[i+1]%4!=0)break;//跳出for循环elsefish[i]=fish[i+1]*5/4+1;//计算第i人看到的鱼数}}while(i>=1);//当i>=1继续做do循环for(i=1;i<=5;i++)/