递推cc教学内容

递推cc2解题思路: 假定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/53写成一般式

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,…,24分析上式１.当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]不能不是整数，这个结论同样可以用至fish[3],fish[2]和fish[1]53.按题意要求5人合伙捕到的最少鱼数，可以从小往大枚举，可以先让E所看到的鱼数最少为6条，即fish[5]初始化为6来试，之后每次增加5再试，直至递推到fish[1]得整数且除以5之后的余数为1。根据上述思路，我们可以构思如下的程序框图：67该图可分为三部分(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]。8 当由break语句让程序退出循环时，意味着某人看到的鱼数不是整数，当然不是所求，必须令fish[5]加5后再试，即重新进入直到型循环dowhile的循环体。 当着正常退出for循环时，一定是控制变量i从初值4，一步一步执行到终值1，每一步的鱼数均为整数，最后i=0，表示计算完毕，且也达到了退出直到型循环的条件。(3)

输出计算结果9//************************************//*程序名：3-30.cpp（五人合伙捕鱼）*//*作者：ghq*//*编制时间：2011年3月2日*//*主要功能：递推算法的实现*//************************************#include<iostream> //预编译命令usingnamespacestd;intmain() //主函数{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循环

else fish[i]=fish[i+1]*5/4+1;//计算第i人看到的鱼数}}while(i>=1);//当i>=1继续做do循环for(i=1;i<=5;i++)cout<<fish[i]<<endl;//输出计算结果return0;}10intmain() //主函数{

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循环

else fish[i]=fish[i+1]*5/4+1;//计算第i人看到的鱼数}}while(i>=1);//当i>=1继续做do循环for(i=1;i<=5;i++)//输出计算结果 cout<<fish[i]<<endl;

return0;}11do{

fish[5]=fish[5]+5;//让E看到的鱼数增5。

for(i=4;i>=1;i--){Tif(fish[i+1]%4!=0)F

break;

//跳出for循环else

fish[i]=fish[i+1]*5/4+1;

//计算第i人看到的鱼数}}while(i>=1);//当i>=1继续做do循环

12//输出计算结果for(i=1;i<=5;i++) cout<<fish[i]<<endl;3121A2496B1996C1596D1276E13递推数列的定义一个数列从某一项起，它的任何一项都可以用它前面的若干项来确定，这样的数列称为递推数列。表示某项与前面若干项的关系称为递推公式(表达式）。例如：1!,2!,…,(n-1)!,n!

令fact(n)为n的阶乘

fact(n)=n*fact(n-1)(通项公式)

fact(1)=1(边界条件)14递推算法的程序实现

自学90页内容：[任务6.4]王小二切饼

递归及其实现 递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。就递归算法而言并不涉及高深数学知识，只不过初学者要建立起递归概念不十分容易。16[任务6.5]用递归算法求n!定义：函数fact(n)=n! fact(n-1)=(n-1)!

则有 fact(n)=n

fact(n-1)

已知 fact(1)=1该问题也可以用递推方法解决17为了表述得直观清晰，我们定义两个结点：或结点和与结点。图示的直观性与思维助力。1、或结点A为“或结点”，A依不同条件会有两种不同的取值,B或C。结点用表示。18如果有多于2种取值，可用下图：条件为Z1,Z2,…,Zn,取值为B或C,…或G192、与结点 与结点要涂黑，相关联的B与C之间要用弧线连起来。 A为与结点，A的最终取值为C结点的值，但为了求得C的值，得先求出B结点的值，C是B的函数。20仍以求n!为例画出如下与或图 A为或结点；B为直接可解结点，值为1； C为与结点，当n>1时，A的取值即C的值，而C的值即E的值，为了求得E的值，需要先求出D的值。D值fact(n-1)乘以n即为E的值。21与结点可能有多个相关联的点，这时可描述为下图 A结点的值最终为D的值，但为了求D需先求B和C。从图上看,先求左边的点才能求最右边的点的值，我们约定最右边D点的值就是A结点的值。22 下面我们以3！为例来画与或结点图，目的是体会递归的含义。C=1D=2*C=2B=D=2E=3*B=3*2=6A=E=623下面画出了调用和返回的递归示意图24 从图可以想象： 欲求fact(3)，先要求fact(2)；要求fact(2)先求fact(1)。就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到1的阶乘，其值为1，到达了递归的边界。然后再用fact(n)=n*fact(n-1)这个普遍公式，从里向外倒推回去得到fact(n)的值。 为了把这个问题说得再透彻一点。我们画了如下的流程图：2526为了形象地描述递归过程，将上图改画成下图27 在这个图中“内层”与“外层”有着相同的结构。它们之间“你中有我，我中有你”，呈现相互依存的关系。 为了进一步讲清递归的概念，将递归与递推做一比较。仍以求阶乘为例。 递推是从已知的初始条件出发，逐次去求所需要的阶乘值。如求3！初始条件 fact(1)=1 fact(2)=

2*fact(1)=2 fact(3)=3*fact(2)=628 这相当于从菜心“推到”外层。而递归算法的出发点不放在初始条件上，而放在求解的目标上，从所求的未知项出发逐次调用本身的求解过程，直到递归的边界（即初始条件）。就本例而言，读者会认为递归算法可能是多余的，费力而不讨好。但许多实际问题不可能或不容易找到显而易见的递推关系，这时递归算法就表现出了明显的优越性。下面我们将会看到，递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，具有良好的可读性，易于理解，许多看来相当复杂，或难以下手的问题，如果能够使用递归算法就会使问题变得易于处理。下面举一个尽人皆知的例子哈诺（Hanoi）塔问题。29故事： 相传在古代印度的Bramah庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中恪守下述规则：每次只允许移动一只盘，且大盘不得落在小盘上面。有人会觉得这很简单，真的动手移盘就会发现，如以每秒移动一只盘子的话，按照上述规则将64只盘子从一个柱子移至另一个柱子上，所需时间约为5800亿年。30怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。1、在A柱上只有一只盘子，假定盘号为1，这时只需将该盘从A搬至C，一次完成，记为

move1fromAtoC(演示)ABC1312、在A柱上有二只盘子，1为小盘，2为大盘。第（1）步将1号盘从A移至B，这是为了让2号盘能移动；第（2）步将2号盘从A移至C；第（3）步再将1号盘从B移至C； 这三步记为（演示）：ABC21move1fromAtoB;move2fromAtoC;move3formBtoC;323、在A柱上有3只盘子，从小到大分别为1号，2号，3号第（1）步将1号盘和2号盘视为一个整体；先将二者作为整体从A移至B，给3号盘创造能够一次移至C的机会。这一步记为move(2,A,C,B)意思是将上面的2只盘子作为整体从A借助C移至B。第（2）步将3号盘从A移至C，一次到位。记为

move3fromAtoC第（3）步处于B上的作为一个整体的2只盘子，再移至C。这一步记为 move(2,B,A,C) 意思是将2只盘子作为整体从B借助A移至C。 所谓借助是什么意思，等这件事做完了不言自明。33move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(2,B,A,C)ABC213演示：移动3个盘子的分解34move(3,A,B,C)move(2,A,C,B)move(1,A,B,C)move(1,A,C,B)move(1,C,A,B)move(1,A,B,C)move(2,B,A,C)move(1,B,C,A)move(1,B,A,C)move(1,A,B,C)ABC213354、从题目的约束条件看，大盘上可以随便摞小盘，相反则不允许。在将1号和2号盘当整体从A移至B的过程中move(2,A,C,B)实际上是分解为以下三步 第（1）.1步：move1formAtoC; 第（1）.2步：move2formAtoB; 第（1）.3步：move1formCtoB;36 经过以上步骤，将1号和2号盘作为整体从A

移至B，为3号盘从A

移至C

创造了条件。同样，3号盘一旦到了C，就要考虑如何实现将1号和2号盘当整体从B

移至C的过程了。实际上move(2,B,A,C)

也要分解为三步： 第（3）.1步：move1formBtoA; 第（3）.2步：move2formBtoC; 第（3）.3步：move1formAtoC;375、看move(2,A,C,B)

是说要将2只盘子从A

搬至B，但没有

C

是不行的，因为第（1）.1步就要将1盘从A

移到C，给2盘创造条件从A

移至B，然后再把1盘从C

移至B。看到这里就能明白借助C

的含义了。因此，在构思搬移过程的参量时，要把3个柱子都用上。386、定义搬移函数move(n,A,B,C)，物理意义是将n只盘子从A经B搬到C 考虑到前面已经研究过的(1)(2)(3)步，可以将搬移过程用如下的与或结点图表示。39 这里用与或结点的含义是分解为(1)(2)(3)步。这3步是相关的，相互依存的，而且是有序的，从左至右执行。move(n,A,B,C)

分解为3步(1)move(n-1,A,C,B)理解为将上面的n-1只盘子作为一个整体从A经C移至B；(2)输出n：AtoC，理解将n号盘从A移至C，是直接可解结点；(3)move(n-1,B,A,C)理解为将上面的n-1只盘子作为一个整体从B经A移至C。40 这里显然是一种递归定义，move(n-1,A,C,B)可分解为3步：第1步：将上面的n-2只盘子作为一个整体从A经B到C，move(n-2,A,B,C)；第2步：第n-1号盘子从A直接移至B，即n-1:AtoB；第3步：再将上面的n-2只盘子作为一个整体从C经A移至B，move(n-2,C,A,B)；下面，我们还是以3只盘子为例画出递归的与或图。41这个图很象一颗倒置着的树，结点move(3,A,B,C)是树根，与结点是树的分枝，叶子都是直接可解结点。424344//*******************************************//*程序名：6_hanoi2002.cpp*//*作者：wuwh*//*编制时间：2002年10月13日*//*主要功能：用递归求解Hanoi问题*//*******************************************#include<iostream> //预编译命令usingnamespacestd;intstep=1; //整型全局变量,预置1,步数voidmove(int,char,char,char); //声明要用到的被调用函数intmain() //主函数{ //主程序开始 intn; //整型变量,n为盘数, cout<<"请输入盘数n="; //提示信息 cin>>n; //输入正整数n cout<<"在3根柱子上移" //输出提示信息 <<n<<"只盘的步骤为:"<<endl;move(n,'a','b','c'); //调用函数move(n,'a','b','c')return0;} //主函数结束45//以下函数是被主程序调用的函数//函数名：move//输入：m，整型变量，表示盘子数目// p，q，r为字符型变量，表示柱子标号//返回值：无voidmove(intm,charp,charq,charr){ //自定义函数体开始 if(m==1) //如果m为1,则为直接可解结点, { //直接可解结点,输出移盘信息 cout<<"["<<step<<"]move1#from"<<p<<"to"<<r<<endl; step++; //步数加1 } else //如果不为1,则要调用move(m-1) { move(m-1,p,r,q); //递归调用move(m-1) //直接可解结点,输出移盘信息 cout<<"["<<step<<"]move"<<m