c语言_递归算法

《c语言_递归算法》由会员分享，可在线阅读，更多相关《c语言_递归算法（117页珍藏版）》请在装配图网上搜索。

1、Click to edit Master title style,,Click to edit Master text styles,,Second level,,Third level,,Fourth level,,Fifth level,,*,*,*,,117,计算机语言与程序设计,谌 卫 军,清华大学软件学院,Introduction to Computer Programming,第,八章 递归算法,1,3,2,基本概念,基于回溯策略的递归,基于分治策略的递归,从前有座山，山上有座庙，庙里有一个老和尚,,和一个小和尚，老和尚正在给小和尚讲故事。,,讲的是什么故事呢？他说，从前,……

2、,Recursion,,-,See,,",Recursion,",.,,,",In order to understand recursion, one must first understand recursion.,",C,语言允许嵌套地调用函数，也就是说，在调用,,一个函数的过程中，又去调用另一个函数,。,函数的嵌套调用,void main( ),,{,,…,,,study_english,( );,,,…,,},void,study_english,( ),,{,,reading( );,,listening( );,,,writing( ),,},void listening(

3、 ),,{,,,…,,…,,…,,},函数的嵌套调用有一个特例，即递归调用，也就,,是说，在调用一个函数的过程中，又出现了直接,,或间接地去调用该函数本身,。,void tell_story( ),,{,,int old_monk, young_monk;,,tell_story ( ); // tell_story,函数的递归调用,,},函数的递归调用,?,void tell_story( ),,{,,static int old_monk, young_monk;,,,old_monk = old_monk + 1; //,年龄大了一岁,,,young_monk

4、 = young_monk + 1;,,if(old_monk <= 60) //,递归形式,,,tell_story ( );,,else,,printf(",对不起，已退休！,"); //,递归边界,,},在语法上（简单）,,递归即为普通的函数调用。,,在算法上（难）,,如何找到递归形式？,,如何找到递归边界？,如何编写递归程序？,递归算法的类型,递归算法可以分为两种类型：,,基于分治策略的递归算法；,,基于回溯策略的递归算法。,第,八章 递归算法,1,3,2,基本概念,基于回溯策略的递归,基于分治策略的递归,分而治之（,divide-and-conquer,）的算法,,设计

5、思想：,,Divide,：把问题划分为若干个子问题；,,Conquer,：以,同样的方式,分别去处理各个子问题；,,Combine,：把各个子问题的处理结果综合起来，形成最终的处理结果。,8.2.1,,分而治之,玛特露什卡,……,调用,调用,……,调用,调用,……,调用,调用,如何编写基于分治策略的递归程序？,,在算法分析上，要建立分治递归的思维方式。,,在编程实现上，要建立,递归信心,（,To turst the recursion,,,Jerry Cain,, stanford,）。,如何建立分治递归的思维方式？,,基本原则：,目标驱动,！,,计算,n,!,：,n,! =,n,* (,n

6、,-1)!,，且,1! = 1,。,递归形式,递归边界,调用,调用,fact(3),fact(2),fact(1),void main( ),,{,,int,n,;,,printf(",请输入一个整数：,");,,scanf("%d", ,,printf("%d! = %d \n", n, fact(n));,,},,int fact(int n),,{,,if(n == 1) return(1);,,else return(n * fact(n-1));,,},请输入一个整数：,3,,3! = 6,调用和返回的递归示意图,,如何建立递归信心？,,函数

7、的递归调用到底是如何进行的呢？在递归调用时，执行的是不是相同的代码？访问的是不是相同的数据？如果是的话，那么大家会不会相互干扰、相互妨碍？,main,的栈帧,m,3,void main( ),,{,,int,m,;,,printf(",请输入一个整数：,");,,scanf("%d", ,,printf("%d! = %d\n", m, fact(m));,,},,int fact(int n),,{,,if(n == 1) return(1);,,else return(n * fact(n-1));,,},3,n,fact,的栈帧,2,n,fact,的栈帧,1,n,fact,的栈帧,

8、8.2.2,,寻找最大值,问题描述：,,给定一个整型数组,a,，找出其中的最大值。,,如何设计相应的,递归算法,？,如何来设计相应的递归算法？,,目标：,max{a[0], a[1], … a[n-1]},,可分解为：,max{a[0], max{a[1], … a[n-1]}},,另外已知,max{x},＝,x,,这就是递归算法的,递归形式,和,递归边界,，据,,此可以编写出相应的递归函数。,int Max(int a[], int first, int n),,{,,int max;,,,if(first == n-1) return a[first];,,max = Max(a, f

9、irst+1, n);,,if(max < a[first]),,return a[first];,,else return max;,,},Max(a,0,n),调用,Max(a,1,n),调用,…,调用,,Max(a,n-1,n),返回,返回,返回,8.2.3,,折半查找法,问题描述：,,查找（,Searching,）：根据给定的某个值，在一组数据（尤其是一个数组）当中，确定有没有出现相同取值的数据元素。,,顺序查找、折半查找。,前提：数据是有序排列的；,,基本思路：,,将目标值与数组的中间元素进行比较；,,若相等，查找成功。否则根据比较的结果将查找范围缩小一半，然后重复此过程。,412

10、0243,4276013,4328968,4397700,4462718,4466240,4475579,4478964,4480332,4494763,4499043,4508710,4549243,4563697,4564531,4565926,4566088,4572874,请问：,,4565926,是否在,,此列表当中？,4120243,4276013,4328968,4397700,4462718,4466240,4475579,4478964,4480332,4494763,4499043,4508710,4549243,4563697,4564531,4565926,456608

11、8,4572874,请问：,,4565926,是否在,,此列表当中？,数组正,,中间的,,元素。,4120243,4276013,4328968,4397700,4462718,4466240,4475579,4478964,4480332,4494763,4499043,4508710,4549243,4563697,4564531,4565926,4566088,4572874,请问：,,4565926,是否在,,此列表当中？,不予考虑,4120243,4276013,4328968,4397700,4462718,4466240,4475579,4478964,4480332,44947

12、63,4499043,4508710,4549243,4563697,4564531,4565926,4566088,4572874,请问：,,4565926,是否在,,此列表当中？,正中间,,的元素,4120243,4276013,4328968,4397700,4462718,4466240,4475579,4478964,4480332,4494763,4499043,4508710,4549243,4563697,4564531,4565926,4566088,4572874,请问：,,4565926,是否在,,此列表当中？,正中间,,的元素,不予考虑,4565925,？,void m

13、ain(),,{,,int b[] = {05, 13, 19, 21, 37, 56, 64, 75,,,80, 88, 92};,,int x = 21;,,,printf("x,位于数组的第,%d,个元素,\n",,,bsearch(b, x, 0, 10));,,},如何用递归来实现？,函数原型：,int bsearch(int b[], int x, int L, int R);,,递归的,形式,？,,递归的,边界,？,问题分析,int bsearch(int b[], int x, int L, int R),,{,,int mid;,,,if(L > R) return(-1)

14、;,,mid = (L + R)/2;,,if(x == b[mid]),,return mid;,,else if(x < b[mid]),,return bsearch(b, x, L, mid-1);,,else,,return bsearch(b, x, mid+1, R);,,},8.2.4,,汉诺(Hanoi)塔问题,相传在古印度,Bramah,庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把,64,个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中遵守以下规则：每次只允许移动一只盘，且大盘不得落在小盘上（简单吗？若每秒移动一只盘子，需,5800,亿年,）,A

15、,B,C,怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。,1,、在,A,柱上只有一只盘子，假定盘号为,1,， 这时只需将该盘直接从,A,搬至,C,，记为,,,move,,from,,A,,to,,C,A,B,C,1,2,、在,A,柱上有二只盘子，,1,为小盘,2,为大盘。,,分三步进行：,A,B,C,2,1,move from,A,,to,B;,,move from,A,,to,,C,;,,move form,B,,to,C;,3,、在,A,柱上有,3,只盘子，从小到大分别为,1,号，,2,号，,3,号。,怎么移？,A,B,C,2,1,3,分七步！,,分三步

16、进行：,,,move,,2,,discs from,,A,,to,,B,using,,C,；,,move from,,A,,to,,C,；,,,move,,2,,discs from,,B,,to,,C,using,,A,；,A,B,C,2,1,3,4,、在,A,柱上有,n,个盘子,,,从小到大分别为,1,号、,2,号、,3,号、,…,、,n,号。,,第,1,步：将,1,号、,2,号、,…,、,n-1,号盘作为一个整体， 在,C,的帮助下，从,A,移至,B,；,,第,2,步：将,n,号盘从,A,移至,C,；,,第,3,步：再将,1,号、,

17、2,号、,…,、,n-1,号盘作为一个整 体，在,A,的帮助下，从,B,移至,C,；,,这三步记为：,,,move,,n-1,,discs from,,A,,to,,B,using,,C,；,,move,,1,,discs from,,A,,to,,C,；,,,move,,n-1,,discs from,,B,,to,,C,using,,A,；,递归形式！,定义函数,move(int n,,,char L,,,char M,,,char,,R);,,表示,,move,,n,,discs from,,L,,to,,R,,using,,

18、M,；,,如果,n = 1,，即表示,,move from,,L,,to,,R,；,移动的是谁？,#include ,,void move(int n, char L, char M, char R);,,void main( ),,{,,int n;,,printf(",请输入一个整数：,");,,scanf("%d", ,,move(n, 'A', 'B', 'C');,,},// L: Left post, M: Middle post, R: Right post,,void move(int n, char L, char

19、 M, char R),,{,,if(n == 1),,printf("move #1 from %c to %c\n", L, R);,,else,,{,,move(n-1, L, R, M);,,,printf("move #%d from %c to %c\n", n, L, R);,,move(n-1, M, L, R);,,},,},请输入一个整数：,3,,move #1 from A to C,,move #2 from A to B,,move #1 from C to B,,move #3 from A to

20、 C,,move #1 from B to A,,move #2 from B to C,,move #1 from A to C,一次运行结果,8.2.5,,青蛙过河,一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱,L,，面积只容得下一只青蛙落脚，同样右岸也有一石柱,R,，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用,1,，,2,，,…,，,n,编号。规定初始时这队青蛙只能趴在左岸的石头,L,上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有,S,根石柱，有,y,片荷叶，规定溪中的柱子上允许

21、一只青蛙落脚，如有多只同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱,R,，与左岸的石柱,L,一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下，且编号相邻。当青蛙从左岸的,L,上跳走后就不允许再跳回来；同样，从左岸,L,上跳至右岸,R,，或从溪中荷叶或溪中石柱跳至右岸,R,上的青蛙也不允许再离开。问在已知溪中有,S,根石柱和,y,片荷叶的情况下，最多能跳过多少只青蛙？,这题看起来较难，但是如果我们认真分析，理出思路，就可化难为易。,,思路：,,1,、简化问题，探索规律。先从个别再到一般，要善于对多个因素作分解

22、，孤立出一个一个因素来分析，化难为易。,,2.,定义函数,,,Jump ( S ,y ) ——,最多可跳过河的青蛙数,,其中：,S ——,河中柱子数,,,y ——,荷叶数,,,,2,,,说明：河中有一片荷叶，可以过两只青蛙，起始时,L,上有两只青蛙，,1#,在,2#,上面。,,,第一步：,1#,跳到荷叶上；,,第二步：,2#,从,L,直接跳至,R,上；,,第三步：,1#,再从荷叶跳至,R,上。,,如下图：,3.,先看简单情况，河中无柱子：,S = 0,，,Jump ( 0 , y ),当,y = 1,时，,Jump ( 0 , 1 ) =,；,,,3,,,说明：河中有两片荷叶时，可以过,3,只

23、青蛙。起始时：,,,1#,，,2#,，,3# 3,只青蛙落在,L,上，,,第一步：,1#,从,L,跳至叶,1,上，,,第二步：,2#,从,L,跳至叶,2,上，,,第三步：,3#,从,L,直接跳至,R,上，,,第四步：,2#,从叶,2,跳至,R,上，,,第五步：,1#,从叶,1,跳至,R,上，,,,采用归纳法：,Jump ( 0 , y ) =,,当,y = 2,时，,Jump ( 0 , 2 ) =,；,,,,y+1,；,,意思是：在河中没有石柱的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数,+1,。,,再看,Jump( S, y ),先看一个最简单情况：,S = 1,，,y = 1,。

24、,,从图上看出需要 步，跳过 只青蛙。,,,,9 4,,1#,青蛙从,L,－,> Y,；,2#,青蛙从,L,－,> S,；,1#,青蛙从,Y,－,> S,；,3#,青蛙从,L,－,> Y,；,4#,青蛙从,L,－,> R,；,3#,青蛙从,Y,－,> R,；,1#,青蛙从,S,－,> Y,；,2#,青蛙从,S,－,> R,；,1#,青蛙从,Y,－,> R,；,对于,S = 1,，,y = 1,的情形，从另外一个角度来分析,,若没有石柱,S,，最多可过,y+1,,=,,2,只青蛙。,,有了石柱,S,后，最多可过,2*2 = 4,只青蛙。,,步骤,1,：,1#,和,2#,

25、从,L,－,> S,；,,步骤,2,：,3#,和,4#,从,L,－,> R,；,,步骤,3,：,1#,和,2#,从,S,－,> R,；,Y,S,L,R,①,: 1#, 2#,②,: 3#, 4#,③,: 1#, 2#,Y,Y,Y,对于,S = 1,，,y > 1,的情形,,若没有石柱,S,，最多可过,y+1,,只青蛙。,,有了石柱,S,后，最多可过,2*(y+1),只青蛙。,,步骤,1,：前,y+1,只 从,L,－,> S,；,,步骤,2,：后,y+1,只 从,L,－,> R,；,,步骤,3,：前,y+1,只 从,S,－,> R,；,Y,S,L,R,①,:,前,y+1,只,②,:,后,y

26、+1,只,③,:,前,y+1,只,Y,Y,Y,对于,S = 2,，,y > 1,的情形,,若只有石柱,S1,，最多可过,2*(y+1),,只青蛙。,,有了石柱,S2,后，最多可过 只青蛙。,Y,S1,L,R,4*(y+1),S2,步骤,1,：前,2*(y+1),只 从,L,－,> S2,；,,步骤,2,：后,2*(y+1),只 从,L,－,> R,；,,步骤,3,：前,2*(y+1),只 从,S2,－,> R,；,Y,S1,Y,S1,Y,S1,采用归纳法，可得出如下的递归形式：,,Jump(S, y) = 2 * Jump(S-1, y),；,,意思是：先让

27、一半的青蛙利用,y,片荷叶和,S-1,根石柱，落在河中剩下的那根石柱上；然后让另一半的青蛙利用,y,片荷叶和,S-1,根石柱，落在右岸的,R,上面；最后再让先前的一半青蛙，利用,y,片荷叶和,S-1,根石柱，落在右岸的,R,上面。,,递归边界：,Jump(0, y) = y + 1,void main( ),,{,,int S, y;,,printf(",请输入石柱和荷叶的数目：,");,,scanf("%d %d", ,,printf(",最多,有,%d,只青蛙过河,\n", Jump(S, y));,,},,int Jump(int S, int y),,

28、{,,if(S == 0) return( y + 1 );,,return(,2 * Jump(S-1, y),);,,},8.2.6,,快速排序,快速排序的基本思路：,,1,、在数组,a,中，有一段待排序的数据，下标从,l,到,r,。,,2,、取,a[l,],放在变量,value,中，通过由右、左两边对,value,的取值的比较，为,value,选择应该排定的位置。这时要将比,value,大的数放右边，比它小的数放左边。当,value,到达最终位置后（如下标,m,），由它划分了左右两个集合,[l..m-1],、,[m+1..r],。然后转第,1,步，再用,相同的思路,分别去处理

29、左集合和右集合。,令,qsort(l, r),表示将数组元素从下标为,l,到下标为,r,的共,r-l+1,个元素进行从小到大的快速排序。,,目标：,,1,、让,value = a[l],,2,、将,value,放在,a[m],中，,l, m  r,,3,、使,a[l], a[l+1], …, a[m-1] <= a[m],,4,、使,a[m] < a[m+1], a[m+2], …, a[r],例子：数组,a,当中有,7,个元素等待排序。,5,2,6,1,7,3,4,l,r,首先，让,value = a[l] = a[0] = 5,value,5,a,0,1,2,3,4,5,6,下标,

30、5,2,6,1,7,3,4,l,第二步，从,r=6,开始，将,a[r],与,value,进行比较。若,a[r], value,，则,r--,，继续比较。否则，,a[l] = a[r],，,l ++,。,value,5,r,a,0,1,2,3,4,5,6,下标,4,l,4,2,6,1,7,3,4,第三步，从,l=1,开始，将,a[l],与,value,进行比较。若,a[l], value,，则,l++,，继续比较。否则，,a[r] = a[l],，,r --,。,value,5,r,a,0,1,2,3,4,5,6,下标,l,l,6,r,4,2,6,1,7,3,6,又回到第二步，从,r=5

31、,开始，将,a[r],与,value,进行比较。若,a[r], value,，则,r--,，继续比较。否则,a[l] = a[r],，,l ++,。,value,5,a,0,1,2,3,4,5,6,下标,l,r,3,l,4,2,3,1,7,3,6,又回到第三步，从,l=3,开始，将,a[l],与,value,进行比较。若,a[l], value,，则,l++,，继续比较。否则，,a[r] = a[l],，,r --,。,value,5,a,0,1,2,3,4,5,6,下标,r,l,l,7,r,4,2,3,1,7,7,6,现在,l,＝,,r,，已经找到了,value,的正确位置，把,valu

32、e,中的值放回到数组当中。,value,5,a,0,1,2,3,4,5,6,下标,l,r,5,4,2,3,1,5,7,6,下面的任务：用刚才介绍的方法，对,5,左、右两侧的两段数据，分别进行排序。,a,0,1,2,3,4,5,6,下标,×,×,×,1,3,2,4,a,0,1,2,3,4,5,6,下标,l,r,6,7,×,×,×,×,×,a,0,1,2,3,4,5,6,下标,l,r,1,2,3,4,5,6,7,最后的结果：,a,0,1,2,3,4,5,6,下标,具体实现：几重循环语句？,参考程序：略,……,第,八章 递归算法,1,3,2,基本概念,基于回溯策略的递归,基于分治策略的递归,在程序设

33、计当中，有相当一类求一组解、或求,,全部解或求最优解的问题，不是根据某种确定的,,计算法则，而是利用试探和回溯（,Backtracking,）,,的搜索技术求解。回溯法也是设计递归算法的一种,,重要方法，它的求解过程实质上是一个先序遍历一,,棵“状态树”的过程，只不过这棵树不是预先建立的，,,而是隐含在遍历的过程当中。,8.3.1,,分书问题,有五本书，它们的编号分别为,1,，,2,，,3,，,4,，,5,，,现,准备分给,A, B, C, D, E,五个人，每个人的阅读兴趣用一个二维数组来加以描述：,希望编写一个程序，输出所有的分书方案，让人人皆大欢喜。,假定这,5,个人对这,5,本书的

34、阅读兴趣如下表：,,1 2 3 4 5,,A,,B,,C,,D,,E,0,0,1,1,0,1,1,0,0,1,0,1,1,0,1,0,0,0,1,0,0,1,0,0,1,人,书,解题思路：,1,、定义一个整型的二维数组，将上表中的阅读喜好用初始化的方法赋给这个二维数组。可定义：,,int Like[,6,][,6,] = {{0}, {0,,0,0,1,1,0,},,,{0,,1,1,0,0,1,},,,{0,,0,1,1,0,1,},,,{0,,0,0,0,1,0,},  {0,,0,1,0,0,1,}};,2,、定义一个整型一维数组,Book

35、Flag[6],用来记录书是否已被选用。用后五个下标作为五本书的标号，被选用的元素值为,1,,未被选用的值为,0,,初始化皆为,0.,,int BookFlag[6] = {,0,};,3,、定义一个整型一维数组,BookTaken[6],用来记录每一个人选用了哪一本书。用数组元素的下标来作为人的标号，用数组元素的值来表示书号。如果某个人还没有选好书，则相应的元素值为,0,。初始化时，所有的元素值均为,0,。,,int,BookTaken,[6] = {0};,,4,、循环变量,i,表示人，,j,表示书，,i, j, {1, 2, 3, 4, 5},一种方法：,枚举法,。,,把

36、所有可能出现的分书方案都枚举出来，,,然后逐一判断它们是否满足条件，即是否,,使得每个人都能够得到他所喜欢的书。,,缺点：计算量太大。,i=1,,j=1,,j=2,i=2,j=3,,j=5,i=3,j=1,i=3,j=2,,j=4,i=4,j=2,,j=4,i=4,j=5,i=5,j=4,,j=5,,j=5,,j=2,i=5,j=4,,j=2,,j=1,,j=4,i=4,j=5,,j=1,i=5,j=4,,j=1,i=3,j=5,…,i=2,j=4,…,如何抽取出递归形式？,void person( int i );,,int Like[6][6] =

37、 {{0}, {0, 0, 0, 1, 1, 0},,,{0, 1, 1, 0, 0, 1},,,{0, 0, 1, 1, 0, 1},,,{0, 0, 0, 0, 1, 0},,,{0, 0, 1, 0, 0, 1}};,,int BookFlag[6] = {0};,,int BookTaken[6] = {0};,,void main( ),,{,,person( 1 );,,},void,person,(int,i) //,尝试给第,i,个人分书,,{,,int,j, k;,,,for(j,

38、= 1; j <= 5; j++) //,尝试,把,每,本书分给第,i,个人,,,{,,,if((BookFlag[j,] !=,,0) || (,Like[i][j,] == 0)) continue;,//,失败,,,BookTaken[i,] = j;,//,,把第,j,本书分给第,i,个人,,,BookFlag[j,] = 1;,,,if(i,==,5){,//,已找到一种分书方案,,,for(k,= 1; k <= 5; k++),printf("%d,",,BookTaken[k,]);,,,printf("\n,");,,},,,else{,,,,person(i,+ 1

39、); //,给第,i+1,个人分书,,,},,,BookTaken[i,] = 0; //,回溯，把这一次分得的书退回,,,BookFlag[j,] = 0;,,,},,},8.3.2,,下楼,问题,从楼上走到楼下共有,h,个台阶，每一步有三种走法：,,走一个台阶；,,走二个台阶；,,走三个台阶。,,问可以走出多少种方案，希望用,递归,思想来编程。,数据的定义：,,j = 1, 2, 3,——,,表示在每一步可以试着走 的台阶数,,,s,——,,表示步数,,,i,——,,表示当前的高度；,,,pace[s],——,,保存第,s,步走过的台阶数,基本思路：,,让,i,先取,h,值

40、，然后在下楼时，试着一步一步地走，从高到低。每走一步,,i,的值就会减去这一步所走的台阶数,,j,，即,,i = h,（初值），以后,i = i-j,，,( j = 1, 2, 3 ),，当,,i = 0,时，说明已走到楼下。,,每一步都要试,,j,的三种不同取值，即,或者为,1,，或者为,2,，或者为,3,。这时可用,for,循环结构。,,每一步走法都用相同的策略，故可以用递归算法。,i=4,i=3,j=1s=1,i=2,j=2s=1,i=2,j=1s=2,i=1,j=2s=2,i=1,j=3s=1,i=1,j=1s=3,,j=1s=4,i=0,,j=2,,j=3,,j

41、=2s=3,i=0,,j=3,,j=1s=3,i=0,,j=2,,j=3,,j=3s=2,i=0,i=1,j=1s=2,,,j=1s=3,i=0,,j=2,,j=3,,j=2s=2,i=0,,j=3,,,j=1s=2,i=0,,j=2,,j=3,定义,TryStep(i, s) ——,站在第,i,级台阶上往下试 走第,s,步的过程,,如何实现？,,,第一步：,j = 1,；,,第二步：如果,j > i,,表明这一步不可能走,j,级台阶,,,函

42、 数,返回,；否则，转第三步；,,第三步：这一步走,j,级台阶，即,pace[s] = j;,如果,i - j = 0,，说明已经到达地面了，也就是  已经找到一种方案了，把它显示出来；否则 的话，接着走下一步，,TryStep(i-j, s+1),；,,第四步：,j = j +1,，如果,j,,3,，转第二步；否则函数 结束。,能否用分治策略？,8.3.3,,八皇后问题,在,8,×,8,的棋盘上，放置,8,个,皇后,（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个皇后都要满足：,

43、,（,1,）不在棋盘的同一行；（,2,）不在棋盘的同一列；（,3,）不在棋盘的同一对角线上。,,因此可以推论出，棋盘共有,8,行，故至多有,8,个皇后，即每一行有且仅有一个皇后。这,8,个皇后中的每一个应该摆放在哪一列上是解该题的任务。,,,,,,,,,,,,,,,,,…,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,…,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

44、,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,…,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,

45、,,,,,,,,,数据的定义（,1,）：,,i,——,,第,i,行（个）皇后，,1, i  8,；,,,j,——,,第,j,列，,1, j  8,；,,,Q,ueen[i],——,,第,i,行皇后所在的列；,,,Column[j],——,,第,j,列是否,安全,，,{0, 1},；,,1 2 3 4 5 6 7 8,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,,1,2,3,4,

46、5,6,7,8,数据的定义（,2,）：,,Down[-7,..,7 ],——,记录每一条从上到下的对 角线，是否安全，,{0,1},,Up[2..16],——,记录每一条从下到上的对角 角线，是否安全，,{0,1},利用以上的数据定义：,,当我们需要在棋盘的,( i, j ),位置摆放一个皇后的时候，可以通过,Column,数组、,Down,数组和,Up,数组的相应元素，来判断该位置是否安全；,,当我们已经在棋盘的,( i, j ),位置摆放了一个皇后以后，就应该去修改,Column,数组、,Down,数组和,Up,数组的相应

47、元素，把相应的列和对角线设置为不安全。,void TryQueen( int i );,,,int Queen[9] = { 0 };,,int Column[9] = { 0 };,,int Down[15] = { 0 };,,int Up[15] = { 0 };,,,void main( ),,{,,TryQueen( 1 );,,},void,TryQueen,(int i) //,摆放第,i,行的皇后,,{,,int j, k;,,for(j = 1; j <= 8; j++) //,尝试,把,该皇后放在

48、每一列,,,{,,if(,Column[j] || Down[i-j+7] || Up[i+j-2],) continue;,//,失败,,,Queen[i] = j; //,把,该皇后放在,第,j,列上,,,Column[j] = 1; Down[i-j+7] = 1; Up[i+j-2] = 1;,,if(i == 8) //,已找到一种解决方案,,,{,,for(k = 1; k <= 8; k++) printf("%d ", Queen[k]);,,printf("\n");,,},,else TryQueen(i + 1); //,摆放第,i+

49、1,行的皇后,,,Queen[i] = 0; //,回溯，把该皇后从第,j,列拿起,,,Column[j] = 0; Down[i-j+7] = 0; Up[i+j-2] = 0;,,,},,},共,92,组解，部分答案如下：,,方案1：1 5 8 6 3 7 2 4,,方案2：1 6 8 3 7 4 2 5,,方案3：1 7 4 6 8 2 5 3,,方案4：1 7 5 8 2 4 6 3,,方案5：2 4 6 8 3 1 7 5,,方案6：2 5 7 1 3 8 6 4,,方案7：2 5 7 4 1 8 6 3,,方案8：2 6 1 7 4 8 3 5,,方案9：2 6 8 3

50、 1 4 7 5,,方案10：2 7 3 6 8 5 1 4,假设在,棋盘上事先已经摆放了一个国王,，位置为,,，,即,第X行第Y列,，,在摆放八个皇后时，要求皇后间不能互相攻击且不能被国王攻击。,国王的攻击范围如下图所示：,思考题：对题目做如下的修改,先输入某一个皇后所在的位置,，即第X行第Y列，,在此情形下，如何摆放其余的,7,个皇后，要求找到所有解决方案。,8.3.4,,过河,问题,问题描述：,,,M,条狼和,N,条狗（,N,≥,M,）渡船过河，从河西到河东。在每次航行中，该船最多能容纳,2,只动物，且最少需搭载,1,只动物。安全限制：无论在河东、河西还是船上，狗的数量不能小于狼的数量。

51、,,请问：能否找到一种方案，使所有动物都能顺利过河。如果能，移动的步骤是什么？,如何描述系统的当前状态？,位置：河西岸、河东岸、河；,,对象：船、狼、狗。,问题分析,三元组,（,W,、,D,、,B,）,Wolf,Dog,Boat,例如：,(2, 2, W),若,M,＝,2,、,N,＝,2,(2, 2, W),(0, 2, E),(1, 2, W),(0, 0, E),(2, 0, W),(1, 0, E),问题实质：在一个有向图中寻找一条,路径,；,,状态转换：如何从一个结点,跳转,到另一个结点；,,状态树？,问题分析,如何避免访问,重复的,结点？,,如何用,简练的,语句实现状态的转换？,,如

52、何将,5,种情形,归纳,为同一种形式？,技术难点,#include ,,#define MAX_M 20,,#define MAX_N 20,,,int M, N;,,struct Status,,{,,int W, D, B;,,}steps[1000];,,int s = 0, num = 0;,,int flags[MAX_M][MAX_N][2] = {0};,,,void CrossRiver(int W, int D, int B);,,int IsValid(int w, int d, int b);,void main( ),,{,,scanf("%d %d", ,,f

53、lags[M][N][0] = 1;,,steps[0].W = M;,,steps[0].D = N;,,steps[0].B = 0;,,s = 1;,,CrossRiver(M, N, 0);,,},,void CrossRiver(int W, int D, int B),,{,,int i, j, f;,,int w, d, b;,,if(B == 0) f = -1;,,else f = 1;,,,for(j = 1; j <= 5; j++),,{,,switch(j),,{,,case 1: w = W + f*1; d = D; break;,,case 2: w =

54、 W + f*2; d = D; break;,,case 3: d = D + f*1; w = W; break;,,case 4: d = D + f*2; w = W; break;,,case 5: w = W + f*1; d = D + f*1; break;,,},,b = 1 - B;,,if(IsValid(w, d, b)),,,{,,flags[w][d][b] = 1;,,steps[s].W = w;,,steps[s].D = d;,,steps[s].B = b;,,s++;,,if(w == 0 && d == 0 && b == 1),,

55、{,,num ++;,,printf("Solutions %d: \n", num);,,for(i = 0; i < s; i++) printf("%d %d,,%d\n", steps[i].W,,,steps[i].D, steps[i].B);,,},,else CrossRiver(w, d, b);,,flags[w][d][b] = 0;,,s--;,,},,},,},int IsValid(int w, int d, int b),,{,,if(w M) return 0;,,if(d N) return 0;,,if(flags[w][d][b] == 1) ret

56、urn 0;,,if(d > 0 ,,if((N-d > 0) ,,return 1;,,},2 2,,Solutions 1:,,2 2 0,,0 2 1,,1 2 0,,1 0 1,,2 0 0,,0 0 1,,Solutions 2:,,2 2 0,,0 2 1,,1 2 0,,1 0 1,,1 1 0,,0 0 1,Solutions 3:,,2 2 0,,1 1 1,,1 2 0,,1 0 1,,2 0 0,,0 0 1,,Solutions 4:,,2 2 0,,1 1 1,,1 2 0,,1 0 1,,1 1 0,,0 0 1,8.3.5,,排列,问题,n,个对象的一个排列，就是

57、把这,,n,个不同的,,对象放在同一行上的一种安排。例如，对于,,三个对象,,a,,,b,,,c,，总共有,6,个排列：,,,a b c,,a c b,,b a c,,b c a,,c a b,,c b a,,n,个对象的排列个数就是,,n!,。,如何生成排列？,基于分治策略的递归算法：,,假设这,n,,个对象为,1, 2, 3, …,,n,；,,对于前,n-1,个元素的每一个排列,a,1,a,2,…,a,n,-1,，,1,,a,i,,,n,-1,，,通过在所有可能的位置上插入数字,n,，来形成,n,,个所求的排列，即：,n,,a,1,a,

58、2,…,a,n,-1,a,1,n,,a,2,…,a,n,-1,……,a,1,a,2,…,n,,a,n,-1,,a,1,,a,2,…,a,n,-1,n,例如：生成,1,2,3,的所有排列,permutation(3),,permutation(2),,permutation(1),permutation(1),：,1,permutation(2),：,2 1,，,1 2,permutation(3),：,3 2 1,，,2 3 1,，,2 1 3,，,,,3 1 2,，,1 3 2,，,1 2 3,基于回溯策略的递归算法：,,基本思路：每一个排列的长度为,N,，对

59、这,N,个不同的位置，按照顺序逐一地枚举所有可能出现的数字。,,定义一维数组,NumFlag[N+1],用来记录,1-N,之间的每一个数字是否已被使用，,1,表示已使用，,0,表示尚未被使用，初始化皆为,0,；,定义一维数组,NumTaken[N+1],，用来记录每一个位置上使用的是哪一个数字。如果在某个位置上还没有选好数字，则相应的数组元素值为,0,。初始化时，所有元素值均为,0,；,,循环变量,i,表示第,i,个位置，,j,表示整数,j,，,i, j,,{1, 2, …, N},。,i=1,[ ],i=2,j=1,[1 ],,j=1,i=3,j=2,[1 2],j=3,i=3,[1

60、3],,j=1,,j=2,,j=3,[1 2 3],,j=1,,,j=2,[1 3 2],,j=3,i=2,j=2,[2 ],i=3,j=1,[2 1],,j=2,j=3,i=3,[2 3],,j=1,,j=2,,j=3,[2 1 3],,j=1,[2 3 1],,j=2,,j=3,i=2,j=3,[3 ],i=3,j=1,[3 1],,j=3,j=2,i=3,[3 2],,j=1,,j=2,[3 1 2],,j=3,,j=1,[3 2 1],,j=2,3,假定,N=3,#define N 3,,void TryNumber( int i );

61、,,int NumFlag[N+1] = {0};,,int NumTaken[N+1] = {0};,,main( ),,{,,TryNumber( 1 );,,},void TryNumber(int i),,{,,int j, k;,,for(j = 1; j <= N; j++),,{,,if(NumFlag[j] !=,,0) continue;,,NumTaken[i] = j;,,NumFlag[j] = 1;,,if(i == N),,{,,for(k = 1; k <= N; k++) printf("%d ", NumTaken[k])

62、;,,printf("\n");,,},,else TryNumber(i + 1);,,NumTaken[i] = 0;,,NumFlag[j] = 0;,,,},,},问题描述：,编写一个程序，它接受用户输入的一个,,英文单词（长度不超过,20,个字符），然后,,输出由这个单词的各个字母所组成的所有,,排列。有两个条件：第一、这个单词的,,各个字母允许有相同的；第二、不能输出,,重复的排列。,例如：,请输入一个英文单词：,boy,,boy,,byo,,oby,,oyb,,ybo,,yob,请输入一个英文单词：,bob,,bob,,bbo,,obb,讨论,i=1,[ ],i=2,j=1

63、,[b ],,j=1,i=3,j=2,[b o],j=3,i=3,[b b],,j=1,,j=2,,j=3,[b o b],,j=1,,j=2,[b b o],,j=3,i=2,j=2,[o ],i=3,j=1,[o b],,j=2,,j=1,,j=2,,j=3,[o b b],j=3,,假定单词为：,bob,j=3,,#define MAXSIZE,20,,void TryChar(char *word, int i, int length);,,int CharFlag[MAXSIZE] = {0};,,int CharTake

64、n[MAXSIZE] = {0};,,main( ),,{,,char word[MAXSIZE];,,int length;,,printf(",请输入一个单词：,");,,scanf("%s", word);,,length = strlen(word);,,TryChar(word, 1, length);,,},void TryChar(char *word, int i, int length),,{,,int j, k;,,for(j = 1; j <= length; j++),,,{,,,if (CharFlag[j] ==,,1)

65、 continue;,,for(k = 1; k < j; k++),,{,,if(CharFlag[k] == 0),,{,,//,在同一结点不能测试相同的两个字符，,,,//,减,1,是为了对齐下标,。,,,if(word[k - 1] == word[j - 1]) break;,,},,},,if(k < j) continue;,,,,CharTaken[i] = j;,,CharFlag[j] = 1;,,if(i == length),,{,,for(k = 1; k <= length; k++),,{,,printf("%c ", word[CharTaken[k] - 1]);,,},,printf("\n");,,},,else TryChar(word, i + 1, length);,,CharTaken[i] = 0;,,CharFlag[j] = 0;,,,},,},下 课 啦,!,