递推cc.ppt

递推法*递推是计算机数值计算中的一个重要算法,可以将复杂的运算化为若干重复的简单运算,充分发挥计算机长于重复处理的特点。递推*【任务】 A、B、C、D、E五人合伙夜间捕鱼,凌晨时都疲惫不堪,各自在河边的树丛中找地方睡着了,日上三竿,A第一个醒来,他将鱼平分作五份,把多余的一条扔回湖中,拿自己的一份回家去了,B第二个醒来,也将鱼平分为五份,扔掉多余的一条,只拿走自己的一份,接着C、D、E依次醒来,也都按同样的办法分鱼。问五人至少合伙捕到多少条鱼?每个人醒来后看到的鱼数是多少条?*解题思路:假定A、B、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/5 fish[3]=(fish[2]-1)*4/5 fish[4]=(fish[3]-1)*4/5 fish[5]=(fish[4]-1)*4/5*写成一般式fish[i]=(fish[i-1]–1)*4/5 i=2,3,…,5 这个公式可用于知A看到的鱼数去推算B看到的,再推算C看到的,…….。现在要求的是A看到的,能否倒过来,先知E看到的再反推D看到的,……,直到A看到的。为此将上式改写为: fish[i-1]=fish[i]*5/4+1 i=5,4,…,2*=5时,fish[5]表示E醒来所看到的鱼数,该数应满足被5整除后余1,即 fish[5]%5===5时,fish[i-1]表示D醒来所看到的鱼数,这个数既要满足 fish[4]=fish[5]*5/4+1又要满足 fish[4]%5==1显然,fish[4]不能不是整数,这个结论同样可以用至fish[3],fish[2]和fish[1]*,可以从小往大枚举,可以先让E所看到的鱼数最少为6条,即fish[5]初始化为6来试,之后每次增加5再试,直至递推到fish[1]得整数且除以5之后的余数为1。根据上述思路,我们可以构思如下的程序框图:**该图可分为三部分(1)是说明部分:包含定义数组fish[6],并初始化为1和定义循环控制变量i,并初始化为0。(2)是do….while直到型循环,其循环体又含两块: (2).1是枚举过程中的fish[5]的初值设置,一开始fish[5]=1+5;以后每次增5。 (2).2是一个for循环,i的初值为4,终值为1,步长为-1,该循环的循环体是一个分支语句,如果fish[i+1]不能被4整除,则跳出for循环(使用break语句);否则,从fish[i+1]算出fish[i]。*当由break语句让程序退出循环时,意味着某人看到的鱼数不是整数,当然不是所求,必须令fish[5]加5后再试,即重新进入直到型循环dowhile的循环体。 当着正常退出for循环时,一定是控制变量i从初值4,一步一步执行到终值1,每一步的鱼数均为整数,最后i=0,表示计算完毕,且也达到了退出直到型循环的条件。(3)输出计算结果