1、第七讲递推与递归算法学习重点1、掌握基本的算法递推。特别是迭代公式的建立。2、了解递归算法的思想。学习过程递推算法是小学生竞赛中常用的方法，也是我们在辅导学生学习中需要注意的地方。递推算法主要是找出其迭代公式，分为顺推和逆推两种。1、顺推从已知条件出发，逐步推算出要解决的问题的方法叫顺推。如斐波拉契数列、杨辉三角形都是用的这种方法。例1：【问题描述】有一个数列：第1项的值为0，第2项的值为1，从第3项起为其前两项之和。其第20项的值是多少？（斐波那契数列）【问题分析】开始的条件：a(1)=0a(2)=1从第3项起其迭代表达式为a(i)=a(i-1)+a(i-2)【程序清单】FORi=3
2、TO20a(i)=a(i-1)+a(i-2)NEXTiPRINTa(20)最后输出a(20)就得出问题的结果。我们再来理解下面的一道题目，这是2003年信息学奥赛复赛的第4题。例2：【问题描述】对一个正整数，求出的所有拆分，并统计输出其中回文数列的个数。所谓回文数列是指该数列中的所有数字，从左向右或从右向左看都相同。例如：4时，有如下的拆分：41111回文数列1112121回文数列221122回文数列31331回文数列共有3个【输入】一个正整数（1 4、6和7时，它们的方案数是相同的；K为8和9时，方案数也是相同的。并可找出输入K与结果的关系：S=2(K2)-1【程序清单】INPUTKS=2(K2)-1PRINTSEND【运行示例】输入：10输出：31例3：【问题描述】将正方形纸片由下往上对折，再由左向右对折，称为完成一个操作。按上述完成N次操作以后，剪去所得小正方形的左下角。求：当展开这张正方形纸片后，一共有多少个小洞孔？【问题分析】一次操作后，层数由1变为4，若剪去所得小正方形左下角，展开后只有1个小洞孔，恰是大正方形的中心。连续两次操作后，折纸层数为42，剪去所得小正方形左下角，展开后大正方形留有4(2-1)=4个小洞孔；连续三 5、次操作后，折纸层数为43，剪去所得小正方形左下角，展开后大正方形上留有4(3-1)=16个小洞孔；按上述规律可推导出迭代公式：S=4(N-1)【程序清单】INPUTNN为操作次数S=4(N-1)S为小洞孔的个数PRINTSEND【运行示例】输入：5输出：256例4：【问题描述】将自然数排成如下的螺旋状：21222324252620789102719612112818543121716151413第一个拐弯处的数是2，第二个拐弯处的数是3，第20个及第25个拐弯处的数各是多少？（111170）（P167例10）【问题分析】由图可知，前几个拐弯处的数依次是：2，3，5，7，10，13， 6、17，21，26，这是一个数列，有什么规律呢？把数列的后一项减去前一项，得一新数列：1，2，2，3，3，4，4，5，5，把原数列的第一项2添在新数列的前面，得到2，1，2，2，3，3，4，4，5，5，于是，原数列的第n项an就等于上面数列的前n项和，即a1=2=1+1=2a2=2+1=1+(1+1)=3a3=2+1+2=1+(1+1+2)=5a4=2+1+2+2=1+(1+1+2+2)=7所以，第20个拐弯处的数是：A20=1+(1+1+2+2+3+3+4+4+10+10)=1+2*(1+2+10)=111第25个拐弯处的数是：A25=1+(1+1+2+2+12+12+13)=1+2*(1+2 7、+12)+13=170请试着写出程序清单。2、逆推从已知问题的结果出发，用迭代表达式逐步推算出问题的开始的条件，称为逆推。例5：【问题描述】分西瓜。某次比赛奖品是一批西瓜，第一名分得西瓜总数的一半加半只，第二名分得剩下的西瓜的一半加半只，第三名分得再次剩下的西瓜的一半加半只，西瓜正好分完，在分的过程中并没有用刀切西瓜。请编程计算西瓜总数有多少？【问题分析】最后结果：西瓜为0，即S=0最后一次（即第三次）分西瓜数为：S=(S+0.5)*2=(0+0.5)*2=1倒数第二次（即第二次）分西瓜数为：S=(S+0.5)*2=(1+0.5)*2=3倒数第三次（即第一次）分西瓜数为：S=(S+0.5)*2 8、=(3+0.5)*2=7其迭代表达式为：s=(s+0.5)*2【程序清单】S=0FORi=3TO1STEP-1S=(S+0.5)*2NEXTiPRINT“西瓜总数=”；S“分西瓜”这样一类题还可用正向迭代来解。不过程序要复杂些。请阅读下列程序：n=0DOn=n+1:s=nFORi=1TO3s=s/21/2NEXTiLOOPUNTILs=0PRINTn【思考】（1）正向迭代为什么要用两重循环？外层循环为什么要用条件循环而不用计数循环？（2）第三行中的s=n有什么用？（3）最后输出为什么是n而不是s？（4）正向迭代表达式能否用逆向迭代表达式推导出来？3、分物 9、迭代的通用程序正向迭代逆向迭代n=0DOn=n+1:s=ns=FORi=FORi=s=s=NEXTINEXTiLOOPUNTILs=PRINT“总数=”；sPRINT“总数=”；n这样的分物问题有下列题目，请填充：（1）小华读书。第一天读了全书的一半加二页，第二天读了剩下的一半加二页，以后天天如此，第六天读完了最后的三页，问全书有多少钱页？（2）猴子吃桃。有一群猴子摘来了一批桃子，猴王规定每天只准吃一半加一只（即第二天吃剩下的一半加一只，以此类推），第九天正好吃完，问猴子们摘来了多少桃子？（3）某路公共汽车，总共有八站，从一号站发轩时车上已有n位乘客， 10、到了第二站先下一半乘客，再上来了六位乘客；到了第三站也先下一半乘客，再上来了五位乘客，以后每到一站都先下车上已有的一半乘客，再上来了乘客比前一站少一个，到了终点站车上还有乘客六人，问发车时车上的乘客有多少？（4）出售金鱼。第一次卖出全部金鱼的一半加二分之一条金鱼；第二次卖出乘余金鱼的三分之一加三分之一条金鱼；第三次卖出剩余金鱼的四分之一加四分之一条金鱼；第四次卖出剩余金鱼的五分之一加五分之一条金鱼；现在还剩下11条金鱼，在出售金鱼时不能把金鱼切开或者有任何破损的。问这鱼缸里原有多少条金鱼？上述题目的参考答案如下：（1）1TO5S/2-2335TO1STEP-1(S+2) 11、*2（2）1TO9S/2-1009TO1STEP-1(S+1)*2（3）2TO7S/2+(8-i)667TO2STEP-1(S-(8-i)*2（4）1TO4S-(S+1)/(i+1)11114TO1STEP-1(s+1/(i+1)*(i+1)请大家来自学信息学教材P217的例10-14，这是2000年信息学奥赛复赛的第4题：求数组元素，理解如何推导出其迭代公式的。4、递归自学信息学教材P185-P192，理解SUB过程的建立与应用及FUNCTION函数的建立与应用。我们把函数或过程调用其本身称为递归。递归在解决某些问题中 12、，是一个十分有用的方法。它可以使某些看起来不易解决的问题变得容易解决，写出的程序较简短。例6：【问题描述】用递归过程求斐波拉契数列:数列的第1项的值为0，第2项的值为1，从第3项起为其前两项之和。其第20项的值是多少？【问题分析】前面我们介绍用递推公式来求斐波拉契数列，我们来换一种角度来进行思考。数列的第n项可计算：0i=1a(n)=1i=2a(i-1)+a(i-2)i>=3按照这个递推公式，可以将a(n)的问题，变成求a(i-1)的问题。因为当a(i-1)求出以后，再加上a(i-2)就是a(i)。而a(i-2)的问题，又可以变成求a(i-3)的问题。如此反复，直到最后求a 13、(1)、a(2)的问题，而a(1)=0、a(2)=1。再反过程依次求出a(3)、a(4)，直到最后求出a(n)。【程序清单】DECLARESUBA(N)INPUTNCALLA(N)PRINTA(N)ENDREM子程序SUBA(N)IFN=1THENA(1)=0IFN=2THENA(2)=1ELSEA(N)=A(N-1)+A(N-2)ENDIFENDIFENDSUB再请自学信息学教材P226的例10-17用递归过程计算N！，理解递归在解决这类题目时的思想。本讲作业：1、运动会开了M天，一共发出金牌N枚。第一天发金牌1枚加剩下的七分之一枚，第二天发金牌2枚加 14、剩下的七分之一枚，第3天发金牌3枚加剩下的七分之一枚，以后每天都照此办理。到了第M天刚好还有金牌M枚，到此金牌全部发完。编程求M和N。2、国王分财产。某国王临终前给儿子们分财产。他把财产分为若干份，然后给第一个儿子一份，再加上剩余财产的1/10；给第二个儿子两份，再加上剩余财产的1/10；给第i个儿子i份，再加上剩余财产的1/10。每个儿子都窃窃自喜。以为得到了父王的偏爱，孰不知国王是“一碗水端平”的。请用程序回答，老国王共有几个儿子？财产共分成了多少份？3、将自然数按如下顺序排列：126715163581417491318101219112021在这样的排列下，数字3排在第2行第1列，数字13排在第3行第3列。求：数字168排在第几行第几列？（提示：本题中数列的排放有规律可循，奇数斜行中的数字由下向上递增，偶数斜行由上向下递增，第N斜行