程序设计基础课件第09章－递归－方阵-组合-快排

课前思考题你认为以下三个公式有区别吗？

2第九章

递归思想与相应算法32002014.11.24相传，在古代印度名为Bramah的庙中，僧人们整天把三根柱子上的金盘倒来倒去，原来他们想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去。在盘子的移动过程中，要求恪守下述规则：每次只允许移动一只盘，且大盘不得摞在小盘上面。请你帮助他们制定移盘的步骤！3印度神庙僧侣的金盘任务有人可能会觉得这个问题很简单，而实际上，如果真的动手进行数学推算就会发现：即便一秒钟移动一只盘子，按照上述规则，要将64只盘子从一个柱子移至另一个柱子上，需要大约5800亿年！这个僧侣移盘问题，通常被称为汉诺(Hanoi)塔问题。解决这个问题最经典的算法就是递归。4任务递归算法在可计算性理论中占有重要地位，它是算法设计的有力工具，对于拓展编程思路非常有用。

递归算法不涉及高深数学知识，不过初学者要建立起递归概念并不十分容易。9.1

递归及其实现5为了帮助我们思考和表述递归算法的思路，使算法更直观和清晰，我们定义两个结点：或结点和与结点。1、或结点A为“或结点”，A依不同条件会有两种不同的取值,B或C。结点用

表示。6辅助递归算法设计的工具如果有多于

2种取值，可用下图：

条件为

Z1,Z2,…,Zn,A取值为

B或

C,…或

G72、与结点

与结点要涂黑，相关联的

B与

C之间要用弧线连起来。A为与结点，A的最终取值为

C结点的值，但为了求得

C的值，得先求出

B结点的值,C是B的函数。8与结点可能有多个相关联的点，这时可描述为下图A结点的值最终为

D的值，但为了求

D需先求

B和

C。先求左边的点才能求最右边的点的值，约定最右边

D点的值就是

A结点的值。9例：试编写一个函数fact(n)，求解阶乘

n!10下面分别使用“枚举”、“递推”、“递归”等三种不同的算法思想来实现该函数，请注意对比不同方法的代码内容。什么样的程序是递归程序？设fact(n)是一个求

n!的函数11///使用枚举思想，求解正整数的阶乘#include<iostream>usingnamespacestd;intfact(intn){intm=1;for(inti=1;i<=n;i++)m=m*i;returnm;}intmain(){cout<<"fact(3)="<<fact(3)<<endl;return0;}

设fact(n)是一个求

n!的函数12///使用递推思想，求解正整数的阶乘#include<iostream>usingnamespacestd;intfact(intn){intm[10];

///假设求10以内整数的阶乘m[1]=1;///递推的起始值for(inti=2;i<=n;i++)m[i]=m[i-1]*i;returnm[n]; ///返回递推的终值}intmain(){cout<<"fact(3)="<<fact(3)<<endl;return0;}

设fact(n)是一个求

n!的函数13///使用递归算法，求解正整数的阶乘#include<iostream>usingnamespacestd;intfact(intn){if(n==1) ///递归的终止条件

return1; ///直接返回结果

returnn*fact(n-1); ///n*(n-1)!}///自己调用自己：递归intmain(){cout<<"fact(3)="<<fact(3)<<endl;return0;}

下面是fact(3)的调用和返回的示意图14从图可以想象：

欲求

fact(3)，先要求

fact(2)；要求

fact(2)先求

fact(1)。

就象剥一颗圆白菜，从外向里，一层层剥下来，到了菜心，遇到

1的阶乘，其值为1，到达了递归的边界。然后再用

fact(n)=n*fact(n-1)这个普遍公式，从里向外倒推回去得到

fact(n)的值。

在这个图中“内层”与“外层”有着相同的结构。它们之间“你中有我，我中有你”，呈现相互依存的关系。15以

n=3为例，与或结点图如下（请大家注意体会“递归”的含义）：C=1D=2*C=2B=D=2E=3*B=3*2=6A=E=616对于fact(n)的递归实现，它的与或图如下：A为或结点；B为直接可解结点，值为1；C为与结点，当

n>1时，A的取值即

C的值，而

C的值即

E的值，为了求得

E的值，需要先求出

D的值。D值

fact(n-1)乘以

n即为

E的值。17递归算法的出发点不是在初始条件上，而是在求解目标上，即从所求的未知项出发，逐次调用本身直到递归边界（即初始条件）的求解过程。就本例而言，大家或许会认为使用递归算法没有必要，费力不讨好。但有许多实际问题往往不可能或很难找到显而易见的递推关系，这时，递归算法就表现出明显的优越性。我们将通过不同类型的示例问题来说明：递归算法比较符合人的思维方式，逻辑性强，可将问题描述得简单扼要，可读性强，易于理解。许多看来相当复杂或难以下手的问题，如果能够使用递归算法，就会变得易于处理。18199.2递

归

算

法

举

例

——方阵填充20

数字旋转方阵

120191817162213231301532233362914423343528135242526271267891011

2112019181716221323130153223336291442334352813524252627126789101122

用与或图来分析算法思路（流程）size==0size==1size>1returnp[begin][begin]=number

填一圈数字；

准备好下一个number;Fill(number,begin,size-2)Fill(number,begin,size)23

D1120191817162213231301532233362914A142334352813C15242526271267891011

B124填写SIZE*SIZE大小方阵的步骤:（1）填写外围一圈数字（2）填写内部小方阵（边长为SIZE-2）“（1）填写外围一圈数字”的步骤: 1.1填写左上角 1.2填写左边（从上至下） 1.3填写下边（从左至右） 1.4填写右边（从下至上） 1.5填写上边（从右至左）25

令size表示方阵的尺寸，初始时size=N

h表示行

v表示列

begin表示每层的起始位置值

number表示当前要填的数字26

先填第一层的第一个数

number(=1)

该数的位置:

行

:h=begin;(begin=0)

列

:v=begin;(begin=0)

将第一个数

number放入数组中

p[h][v]=number;

27让

number=number+1(=2)自上而下，填

A1h:01begin=0;size=612h=begin;v=begin;23for(i=0;i<size-1;i++)34{h++;45

p[h][v]=number;56number++;}28从左至右，填B1begin=0;number=7;size=6h=5;v=begin;for(i=0;i<size-1;i++){v++;

p[h][v]=number;number++;h=57891011}v:1234529自下而上，填C1v=5begin=0;number=12;h:016h=5;v=5;size=6;115for(i=0;i<size-1;i++)214{h--;313

p[h][v]=number;412number++;}30从右至左，填D1begin=0;number=17;size=6注意

h=begin;v=5;

for(i=0;i<size-2;i++)

{v--;

p[h][v]=number;

number++;h=020191817}v:123431

D1120191817162213231301532233362914A142334352813C15242526271267891011

B132

D22132313022333629A223343528C224252627

B2

33

D2

3336A23435C2

B2

34

D3

3336C3A33435B3

35124232221201922540393837187*7326414838361742742494635165*5528434445341562930313233143*3789101112131*1SIZE是奇数时36源代码略379.2递

归

算

法

举

例——组合数计算38我们画出与或图来阐述求解思路：39源代码40#include<iostream>usingnamespacestd;intC(intm,intn){if(m<0||n<0||m<n)return0;if(m==n)return1;if(n==1)returnm;returnC(m-1,n)+C(m-1,n-1);}intmain(){cout<<"C(6,2)="<<C(6,2)<<endl;return0;}翻译！递归程序的调用堆栈9.2递

归

算

法

举

例

——快速排序42“与或图”对应的快速排序思路：1、将待排序的数据放入数组

a中，下标从

z到

y；2、令sort(z,y)为将数组元素从下标为

z到下标为

y的

y–z+1个元素从小到大排序。3、取

a[z]放变量

k中，通过分区处理，为

k选择应该排定的位置——

将比

k大的数放右边，比

k小的数放左边。当

k到达最终位置后，由

k划分左右两个集合。然后再用同样的思路处理左集合与右集合。43

z

y

k

z

m

ym-1m+1

zm-1mm+1y44我们画出与或图来阐述快速排序的思路：函数sort有两个参数（z和y），分别表示数组中一个片段的起始与终止下标值。

Asort(z,y)z>=yz<yBC

不做事DEF

分区处理

sort(z,m-1)sort(m+1,y)STEP1.比array[z]小的元素交换到数组左边，大的元素交换到数组右边STEP2.将array[z]元素放到新位置上，下标是m45分区处理：

k1、让

k=a[z]a<

<2、将

k放在

a[m]zmy3、使

a[z],a[z+1],…,a[m-1]<=a[m]4、使

a[m]<a[m+1],a[m+2],…,a[y]A结点表示将数组

a[z],a[z+1],…,a[y]中的元素

按由小到大用快速排序的思路排序。B结点表示如果

z>=y，则什么也不做。这是直接可解结点。C结点是在

z<y情况下

A结点的解。C是一个与结点。要对

C求解需分解为三步。依次为：461、先解

D结点，D结点是一个直接可解结点，功能是进行所谓的分区处理，规定这一步要做的事情是（1）将

a[z]中的元素放到它应该在的位置上，比如

m位置。这时

a[m]a[z]；（2）让下标从

z到

m-1的数组元素小于等于a[m]；（3）让下标从

m+1到

y的数组元素大于a[m]；

比如:

a数组中

a[z]=5，经分组处理后，5送至

a[4]。5到位后，其左边

a[0]～a[3]的值都小于

5；其右边

a[5],a[6]都大于

5。52617345261734472、再解

E结点，这时要处理的是

a[0]～a[3]；3、再解

F结点，处理a[5],a[6]。下面按照这种思路构思一个快速排序的程序框图。484952617340123456zyk52617345>45>25<65>35>15<750动画演示下面举例说明排序过程图1a数组中有7个元素待排序1让

k=a[z]=a[0]=552617340123456zy图

15k512进入直到型循环执行（1）a[y]=a[6]=4不满足当循环条件，y不动。执行（2）z<y，做两件事：a[z]=a[y]，即a[0]=a[6]=4，z=z+1=0+1=1，见图242617340123456zy图

25k52执行（3）图2中的a[1]<k，满足当循环条件，z=z+1=2，z增1后的情况如图3。图3的情况不再满足当循环条件。6>542617340123456zy图

35k53执行（4）a[y]=a[z]，即a[6]=a[2]=6，见图4。这时

z!=y还得执行直到型循环的循环体。42617360123456zy图

45k54执行（1）a[y]=a[6]=6，6>k满足当循环的条件， y=y-1=6-1=5

见图5，之后退出当循环，因为

a[y]=3<k(k=5)42617360123456zy图

55k55执行（2）a[z]=a[y]，并让

z=z+1=3，见图6

42317360123456zy图

65k56执行（3）由于a[3]=1<k，满足当循环条件，让

z=z+1=4。a[4]=7>k，退出循环。见图7

42317360123456zy图

75k57执行（4）a[z]=a[y]，a[5]=7。见图8

这时仍然

z<y，应继续执行直到型循环的循环体。42317760123456zy图

85k58执行（1），a[y]=7>k，让

y=y-1=4。见图942317760123456zy图

95k59之后，z=y，退出直到型循环，做

a[z]=k，z=4，

a[4]=5，这是

5的最终位置，5将整个数据分成左右两个集合，见图10。42315760123456zy图

10左右5k60用上述思路去排左边的部分从

z=0到

y=3，见图11。让

k=a[z]=a[0]=4，然后进到直到型循环，执行（1）a[y]=1<k，不满足当循环的条件，y不动。执行（2）a[z]=a[y]，z=z+1=1,见图1212310123zy图

1242310123zy图

114k61执行（3）a[z]<k，z=z+1=2，a[2]<k，z=z+1=3，这时z=y，不会执行（4），同时退出直到型循环，见图13。然后做

a[z]=k，即a[3]=4，见图14，左边也排好了。12340123图

1412310123zy图

13zy4k4k624、用上述思路去排右边的部分，见图15，让k=a[z]=a[5]=7，进入直到型循环；执行（1）a[y]=6<k，y不动执行（2）a[z]=a[y]=6，z=z+1=5+1=6，见图16图

167656zy图

156656zy7k63

这时

z=y，不再执行（3）（4），退出直到型循环后，做

a[z]=k，见图17。图

176756zy7k64在有了递归调用函数之后，主程序很容易写，主程序中应包含1、

定义整型变量：数组

a[10]，i；2、

用循环结构输入待排序的数，将其放入

a数组；3、

调用

sort函数，使用三个实际参数

a——将数组

a当实参； 0——数组下标下界； 9——数组下标上界；4、

输出排序结果下面给出参考程序（分两页）65//*******************************************//*程

序：6_6.cpp*//*作

者：wuwh*//*编制时间：2002年10月28日*//*主要功能：快速排序*//*******************************************#include<iostream> //coutusingnamespacestd;voidsort(intarray[],intzz,intyy) //被调用函数，数组array,zz,yy为形参{ intz,y,i,k; //定义变量 if(zz<yy){ //如果zz<yy,则做下列7件事: //7件事开始 z=zz;y=yy;k=array[z];//第1件事 do{ //第2件事(开始)while((z<y)&&(array[y]>=k))y--;//2.1,右边的元素>=k,让y往中间移 if(z<y) //2.2,右边的元素<k,让 {array[z]=array[y];//array[y]送给array[z]， z=z+1; //同时让z往中间移 } while((z<y)&&(array[z]<=k))z++;//2.3,左边的元素<=k,让z往中间移 if(z<y) //2.4,左边的元素>k,让array[z] array[y]=array[z];//送给array[y]}while(z!=y);//第2件事(结束)66 array[z]=k; //第3件事,k已排到位 for(i=zz;i<=yy;i++)//第4件事，输出 {cout<<"a["<<i<<"]="<<array[i]<<";";} cout<<endl; //第5件事，换行 sort(array,zz,z-1);//第6件事，排左边部分 sort(array,z+1,yy);//第7件事，排右边部分 } //7件事结束} //函数体结束intmain(){ //主函数开始 inta[10],i; //整型变量 cout<<"请输入10个整数\n"; //提示信息 for(i=0;i<10;i++) //输入10个整数 cin>>a[i]; sort(a,0,9); //调用sort函数,实参为数组a和0，9 cout<<"排序结果为:"; //提示信息 for(i=0;i<10;i++) cout<<a[i]<<";"; //输出排序结果 cout<<endl;return0;} //主函数结束

67/********************************//*程

序：6_6.cpp*//*作

者：wuwh*//*编制时间：2002年10月28日*//*主要功能：快速排序*//********************************68#include<iostream> //coutusingnamespace;voidsort(intarray[],intzz,intyy) //被调用函数，数组array,zz,yy为形参{//函数体开始intz,y,i,k;//定义变量if(zz<yy) //如果zz<yy,则做下列7件事:69{//7件事开始 z=zz;y=yy;k=array[z];//第1件事70do{//第2件事(开始)

while((z<y)&&(array[y]>=k))y--;//2.1,右边的元素>=k,让y往中间移

if(z<y)//2.2,右边的元素<k,让 {//array[y]送给array[z]，

//同时让z往中间移

array[z]=array[y];

z=z+1;}

while((z<y)&&(array[z]<=k))z++;