递推c,c++-课件PPT（精）.ppt

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