《c语言-递归算法》由会员分享，可在线阅读，更多相关《c语言-递归算法（117页珍藏版）》请在金锄头文库上搜索。
1、1计算机语言与程序设计计算机语言与程序设计谌谌 卫卫 军军清华大学软件学院清华大学软件学院Introduction to Computer Programming2第第八章八章 递归算法递归算法1 13 32 2基本概念基本概念基于回溯策略的递归基于回溯策略的递归基于分治策略的递归基于分治策略的递归 3从前有座山，山上有座庙，庙里有一个老和尚从前有座山，山上有座庙，庙里有一个老和尚和一个小和尚，老和尚正在给小和尚讲故事。和一个小和尚，老和尚正在给小和尚讲故事。讲的是什么故事呢？他说，从前讲的是什么故事呢？他说，从前4Recursion- See Recursion. In order to u
2、nderstand recursion, one must first understand recursion. 5C语言允许嵌套地调用函数，也就是说，在调用语言允许嵌套地调用函数，也就是说，在调用一个函数的过程中，又去调用另一个函数一个函数的过程中，又去调用另一个函数。函数的嵌套调用函数的嵌套调用void main( ) study_english ( ); void study_english( ) reading( ); listening( ); writing( )void listening( ) 6函数的嵌套调用有一个特例，即递归调用，也就函数的嵌套调用有一个特例，即递归调用，
3、也就是说，在调用一个函数的过程中，又出现了直接是说，在调用一个函数的过程中，又出现了直接或间接地去调用该函数本身或间接地去调用该函数本身。void tell_story( ) int old_monk, young_monk; tell_story ( ); / tell_story 函数的递归调用函数的递归调用函数的递归调用函数的递归调用? ?7void tell_story( ) static int old_monk, young_monk; old_monk = old_monk + 1; / 年年龄大了一大了一岁 young_monk = young_monk + 1; if(old
4、_monk = 60) / 递归形式形式 tell_story ( ); else printf(对不起，已退休！不起，已退休！); / 递归边界界8在语法上（简单）在语法上（简单）J递归即为普通的函数调用。递归即为普通的函数调用。在算法上（难）在算法上（难）J如何找到递归形式？如何找到递归形式？J如何找到递归边界？如何找到递归边界？如何编写递归程序？如何编写递归程序？ 9递归算法的类型递归算法的类型递归算法可以分为两种类型：递归算法可以分为两种类型：基于分治策略的递归算法；基于分治策略的递归算法；基于回溯策略的递归算法。基于回溯策略的递归算法。10第第八章八章 递归算法递归算法1 13 32
5、 2基本概念基本概念基于回溯策略的递归基于回溯策略的递归基于分治策略的递归基于分治策略的递归 11分而治之（分而治之（divide-and-conquer）的算法）的算法设计思想：设计思想：1.Divide：把问题划分为若干个子问题；：把问题划分为若干个子问题；2.Conquer：以：以同样的方式同样的方式分别去处理各分别去处理各个子问题；个子问题；3.Combine：把各个子问题的处理结果综：把各个子问题的处理结果综合起来，形成最终的处理结果。合起来，形成最终的处理结果。8.2.1 分而治之分而治之12玛特露什卡玛特露什卡13调用调用调用调用调用调用调用调用调用调用调用调用14如何编写基于分
6、治策略的递归程序？如何编写基于分治策略的递归程序？J在算法分析上，要建立分治递归的思维在算法分析上，要建立分治递归的思维方式。方式。J在编程实现上，要建立在编程实现上，要建立递归信心递归信心（To turst the recursion, Jerry Cain, stanford）。）。15如何建立分治递归的思维方式？如何建立分治递归的思维方式？J基本原则：基本原则：目标驱动目标驱动！J计算计算n!：n! = n * (n-1)!，且，且1! = 1。递归形式递归形式递归边界递归边界16调用调用调用调用fact(3)fact(2)fact(1)17void main( ) int n; pri
7、ntf(请输入一个整数：入一个整数：); scanf(%d, &n); printf(%d! = %d n, n, fact(n);int fact(int n) if(n = 1) return(1); else return(n * fact(n-1);请输入一个整数：入一个整数：33! = 618调用和返回的递归示意图调用和返回的递归示意图19如何建立递归信心？如何建立递归信心？J函数的递归调用到底是如何进行的呢？函数的递归调用到底是如何进行的呢？在递归调用时，执行的是不是相同的代在递归调用时，执行的是不是相同的代码？访问的是不是相同的数据？如果是码？访问的是不是相同的数据？如果是的话，
8、那么大家会不会相互干扰、相互的话，那么大家会不会相互干扰、相互妨碍？妨碍？20main的栈帧的栈帧m3void main( ) int m; printf(请输入一个整数：入一个整数：); scanf(%d, &m); printf(%d! = %dn, m, fact(m);int fact(int n) if(n = 1) return(1); else return(n * fact(n-1);3nfact的栈帧的栈帧2nfact的栈帧的栈帧1nfact的栈帧的栈帧218.2.2 寻找最大值寻找最大值问题描述：问题描述：给定一个整型数组给定一个整型数组a，找出其中的最大，找出其中的最大值
9、。值。如何设计相应的如何设计相应的递归算法递归算法？22如何来设计相应的递归算法？如何来设计相应的递归算法？目标：目标：maxa0, a1, an-1可分解为：可分解为：maxa0, maxa1, an-1另外已知另外已知maxx x这就是递归算法的这就是递归算法的递归形式递归形式和和递归边界递归边界，据，据此可以编写出相应的递归函数。此可以编写出相应的递归函数。23int Max(int a, int first, int n) int max; if(first = n-1) return afirst; max = Max(a, first+1, n); if(max R) return
10、(-1); mid = (L + R)/2; if(x = bmid) return mid; else if(x bmid) return bsearch(b, x, L, mid-1); else return bsearch(b, x, mid+1, R);348.2.4 汉诺汉诺(Hanoi)(Hanoi)塔问题塔问题相传在古印度相传在古印度Bramah庙中，有位僧人整天把三根柱子庙中，有位僧人整天把三根柱子上的金盘倒来倒去，原来他是想把上的金盘倒来倒去，原来他是想把64个一个比一个小的个一个比一个小的金盘从一根柱子上移到另一根柱子上去。移动过程中遵金盘从一根柱子上移到另一根柱子上去。
11、移动过程中遵守以下规则：每次只允许移动一只盘，且大盘不得落在守以下规则：每次只允许移动一只盘，且大盘不得落在小盘上（简单吗？若每秒移动一只盘子，需小盘上（简单吗？若每秒移动一只盘子，需5800亿年亿年）ABC35怎样编写这种程序？思路上还是先从最简单的情况分析怎样编写这种程序？思路上还是先从最简单的情况分析起，搬一搬看，慢慢理出思路。起，搬一搬看，慢慢理出思路。1、在、在A柱上只有一只盘子，假定盘号为柱上只有一只盘子，假定盘号为1， 这时只需将该盘直接从这时只需将该盘直接从A搬至搬至C，记为，记为 move from A to CABC1362、在、在A柱上有二只盘子，柱上有二只盘子，1为小盘
12、为小盘2为大盘。为大盘。分三步进行：分三步进行：ABC21move from A to B;move from A to C;move form B to C;373、在、在A柱上有柱上有3只盘子，从小到大分别为只盘子，从小到大分别为1号，号，2号，号，3号。号。怎么移？怎么移？ABC213分七步！分七步！38 分三步进行：分三步进行： move 2 discs from A to B using C； move from A to C； move 2 discs from B to C using A ；ABC213394、在、在A柱上有柱上有 n 个盘子个盘子, 从小到大分别为从小到大分别
13、为1号、号、2号、号、3 号、号、n号。号。 第第 1 步：将步：将1号、号、2号、号、n-1号盘作为一个整体，号盘作为一个整体， 在在C的帮助下，从的帮助下，从A移至移至B； 第第 2 步：将步：将n号盘从号盘从A移至移至C； 第第 3 步：再将步：再将1号、号、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 ；递归形式！形
14、式！40定义函数定义函数move(int n, char L, char M, char R);表示表示move n discs from L to R using M；如果如果 n = 1，即表示，即表示move from L to R；移移动的是的是谁？41#include void move(int n, char L, char M, char R);void main( ) int n; printf(请输入一个整数：入一个整数：); scanf(%d, &n); move(n, A, B, C);42/ L: Left post, M: Middle post, R: Right
15、postvoid move(int n, char L, char M, char R) if(n = 1) printf(move #1 from %c to %cn, L, R); else move(n-1, L, R, M); printf(move #%d from %c to %cn, n, L, R); move(n-1, M, L, R); 43请输入一个整数：入一个整数：3move #1 from A to Cmove #2 from A to Bmove #1 from C to Bmove #3 from A to Cmove #1 from B to Amove #2
16、from B to Cmove #1 from A to C一次运行结果一次运行结果448.2.5 青蛙过河青蛙过河 一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱，面积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用小。我们将青蛙从小到大，用1，2，n编号。规定初始时这编号。规定初始时这队青蛙只能趴在左岸的石头队青蛙只能趴在左岸的石头L上，按编号一
17、个落一个，小的落在上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有大的上面。不允许大的在小的上面。在小溪中有S根石柱，有根石柱，有y片片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。按编号一个落一个，大的在下，小的在上，而且必须编号相邻。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱石柱R，与左岸的石柱，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一一样允许多个青蛙落脚，但须一个
18、落一个，小的在上，大的在下，且编号相邻。当青蛙从左岸的个，小的在上，大的在下，且编号相邻。当青蛙从左岸的L上跳上跳走后就不允许再跳回来；同样，从左岸走后就不允许再跳回来；同样，从左岸L上跳至右岸上跳至右岸R，或从溪，或从溪中荷叶或溪中石柱跳至右岸中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已上的青蛙也不允许再离开。问在已知溪中有知溪中有S根石柱和根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？片荷叶的情况下，最多能跳过多少只青蛙？45这题看起来较难，但是如果我们认真分析，理这题看起来较难，但是如果我们认真分析，理出思路，就可化难为易。出思路，就可化难为易。思路：思路：1、简化问题，探
19、索规律。先从个别再到一般，要善、简化问题，探索规律。先从个别再到一般，要善于对多个因素作分解，孤立出一个一个因素来分析于对多个因素作分解，孤立出一个一个因素来分析，化难为易。，化难为易。2. 定义函数定义函数 Jump ( S ,y ) 最多可跳过河的青蛙数最多可跳过河的青蛙数 其中：其中：S 河中柱子数河中柱子数 y 荷叶数荷叶数46 2 说明：河中有一片荷叶，可以过两只青蛙，起始时说明：河中有一片荷叶，可以过两只青蛙，起始时 L 上有上有两只青蛙，两只青蛙，1# 在在 2# 上面。上面。 第一步：第一步：1# 跳到荷叶上；跳到荷叶上； 第二步：第二步：2# 从从 L 直接跳至直接跳至 R
20、上；上； 第三步：第三步：1# 再从荷叶跳至再从荷叶跳至 R 上。上。 如下图：如下图：3. 先看先看简单情况，河中无柱子：情况，河中无柱子：S = 0 ，Jump ( 0 , y ) 当当 y = 1 时，Jump ( 0 , 1 ) = ；473 说明：河中有两片荷叶时，可以过说明：河中有两片荷叶时，可以过 3 只青蛙。起始时：只青蛙。起始时： 1#，2#，3# 3只青蛙落在只青蛙落在 L 上，上， 第一步：第一步：1# 从从 L 跳至叶跳至叶 1上，上， 第二步：第二步：2# 从从 L 跳至叶跳至叶 2上，上， 第三步：第三步：3# 从从 L 直接跳至直接跳至 R 上，上， 第四步：第四
21、步：2# 从叶从叶 2 跳至跳至 R 上，上， 第五步：第五步：1# 从叶从叶 1 跳至跳至 R 上，上，采用归纳法：采用归纳法：Jump ( 0 , y ) = 当当 y = 2 时， Jump ( 0 , 2 ) = ； y+1； 意思是：在河中没有石柱的情况意思是：在河中没有石柱的情况下，过河的青蛙数仅取决于荷叶下，过河的青蛙数仅取决于荷叶数，数目是荷叶数数，数目是荷叶数+1。48再看再看Jump( S, y )Jump( S, y )先看一个最简单情况：先看一个最简单情况： S = 1，y = 1 。从图上看出需要从图上看出需要 步，跳过步，跳过 只青蛙。只青蛙。 9 4 9 4 1#
22、 1# 青蛙从青蛙从 L L Y Y；2# 2# 青蛙从青蛙从 L L S S；1# 1# 青蛙从青蛙从 Y Y S S；3# 3# 青蛙从青蛙从 L L Y Y；4# 4# 青蛙从青蛙从 L L R R；3# 3# 青蛙从青蛙从 Y Y R R；1# 1# 青蛙从青蛙从 S S Y Y；2# 2# 青蛙从青蛙从 S S R R；1# 1# 青蛙从青蛙从 Y Y R R；49对于对于S = 1，y = 1的情形，从另外一个角度来分析的情形，从另外一个角度来分析若没有石柱若没有石柱S S，最多可过，最多可过 y+1y+1 = = 2 2 只青蛙。只青蛙。有了石柱有了石柱S后，最多可过后，最多可过
23、 2*2 = 4 只青蛙。只青蛙。步骤步骤1 1：1#1#和和2# 2# 从从 L L S S；步骤步骤2 2：3#3#和和4# 4# 从从 L L R R；步骤步骤3 3：1#1#和和2# 2# 从从 S S R R；YSLR: 1#, 2#: 3#, 4#: 1#, 2#YYY50对于对于S = 1，y 1的情形的情形若没有石柱若没有石柱S S，最多可过，最多可过 y+1y+1 只青蛙。只青蛙。有了石柱有了石柱S后，最多可过后，最多可过 2*(y+1) 只青蛙。只青蛙。步骤步骤1 1：前前y+1y+1只只 从从 L L S S；步骤步骤2 2：后后y+1y+1只只 从从 L L R R；步
24、骤步骤3 3：前前y+1y+1只只 从从 S S R R；YSLR: 前前y+1只只: 后后y+1只只: 前前y+1只只YYY51对于对于S = 2，y 1的情形的情形若只有石柱若只有石柱S1，最多可过，最多可过 2*(y+1)2*(y+1) 只青蛙。只青蛙。有了石柱有了石柱S2后，最多可过后，最多可过 只青蛙。只青蛙。YS1LR4*(y+1)S2步骤步骤1 1：前前2*(y+1)只只 从从 L L S2 S2；步骤步骤2 2：后后2*(y+1)只只 从从 L L R R；步骤步骤3 3：前前2*(y+1)只只 从从 S2 S2 R R；Y,S1Y,S1Y,S152采用归纳法，可得出如下的递归
25、形式：采用归纳法，可得出如下的递归形式：Jump(S, y) = 2 * Jump(S-1, y)；意思是：先让一半的青蛙利用意思是：先让一半的青蛙利用y片荷叶和片荷叶和S-1根石柱，落在河中剩下的那根石柱上；根石柱，落在河中剩下的那根石柱上；然后让另一半的青蛙利用然后让另一半的青蛙利用y片荷叶和片荷叶和S-1根根石柱，落在右岸的石柱，落在右岸的R上面；最后再让先前上面；最后再让先前的一半青蛙，利用的一半青蛙，利用y片荷叶和片荷叶和S-1根石柱，根石柱，落在右岸的落在右岸的R上面。上面。递归边界：递归边界：Jump(0, y) = y + 153void main( ) int S, y; p
26、rintf(请输入石柱和荷叶的数目：入石柱和荷叶的数目：); scanf(%d %d, &S, &y); printf(最多最多有有 %d 只青蛙只青蛙过河河n, Jump(S, y);int Jump(int S, int y) if(S = 0) return( y + 1 ); return( 2 * Jump(S-1, y);548.2.6 快速排序快速排序快速排序的基本思路：快速排序的基本思路：1 1、在数组、在数组a a中，有一段待排序的数据，下标从中，有一段待排序的数据，下标从l l到到r r。2 2、取、取alal 放在变量放在变量valuevalue中，通过由右、左两边对中，
27、通过由右、左两边对valuevalue的取值的比较，为的取值的比较，为valuevalue选择应该排定的位置选择应该排定的位置。这时要将比。这时要将比valuevalue大的数放右边，比它小的数放大的数放右边，比它小的数放左边。当左边。当valuevalue到达最终位置后（如下标到达最终位置后（如下标m m），由它），由它划分了左右两个集合划分了左右两个集合l.m-1l.m-1、m+1.rm+1.r。然后转。然后转第第1 1步，再用步，再用相同的思路相同的思路分别去处理左集合和右集分别去处理左集合和右集合。合。55令令 qsort(l, r)表示将数组元素从下标为表示将数组元素从下标为 l 到
28、到下标为下标为 r 的共的共 r-l+1 个元素进行从小到大的个元素进行从小到大的快速排序。快速排序。目标：目标：1、让、让 value = al2、将、将 value 放在放在 am中，中，l m r3、使、使 al, al+1, , am-1 = am4、使、使 am am+1, am+2, , ar56例子：数组例子：数组a当中有当中有7个元素等待排序。个元素等待排序。5261734lr首先，让首先，让value = al = a0 = 5value5a0123456下标下标575261734l第二步，从第二步，从r=6开始，将开始，将ar与与value进行比较。进行比较。若若ar va
29、lue，则，则 r-，继续比较。否则，继续比较。否则，al = ar，l +。value5ra0123456下标下标4l584261734第三步，从第三步，从l=1开始，将开始，将al与与value进行比较。进行比较。若若al value，则，则 l+，继续比较。否则，继续比较。否则，ar = al，r -。value5ra0123456下标下标ll6r594261736又回到第二步，从又回到第二步，从r=5开始，将开始，将ar与与value进行进行比较。若比较。若ar value，则，则 r-，继续比较。否则，继续比较。否则al = ar，l +。 value5a0123456下标下标lr3
30、l604231736又回到第三步，从又回到第三步，从l=3开始，将开始，将al与与value进行进行比较。若比较。若al value，则，则 l+，继续比较。否则，继续比较。否则，ar = al，r -。 value5a0123456下标下标rll7r614231776现在现在 l r，已经找到了，已经找到了value的正确位置，把的正确位置，把value中的值放回到数组当中。中的值放回到数组当中。value5a0123456下标下标lr5624231576下面的任务：用刚才介绍的方法，对下面的任务：用刚才介绍的方法，对 5 左、右左、右两侧的两段数据，分别进行排序。两侧的两段数据，分别进行排
31、序。a0123456下标下标1324a0123456下标下标lr67a0123456下标下标lr631234567最后的结果：最后的结果：a0123456下标下标具体实现：几重循环语句？具体实现：几重循环语句？参考程序：略参考程序：略64第第八章八章 递归算法递归算法1 13 32 2基本概念基本概念基于回溯策略的递归基于回溯策略的递归基于分治策略的递归基于分治策略的递归 65 在程序设计当中，有相当一类求一组解、或求在程序设计当中，有相当一类求一组解、或求全部解或求最优解的问题，不是根据某种确定的全部解或求最优解的问题，不是根据某种确定的计算法则，而是利用试探和回溯（计算法则，而是利用试探和
32、回溯（Backtracking）的搜索技术求解。回溯法也是设计递归算法的一种的搜索技术求解。回溯法也是设计递归算法的一种重要方法，它的求解过程实质上是一个先序遍历一重要方法，它的求解过程实质上是一个先序遍历一棵棵“状态树状态树”的过程，只不过这棵树不是预先建立的，的过程，只不过这棵树不是预先建立的，而是隐含在遍历的过程当中。而是隐含在遍历的过程当中。668.3.1 分书问题分书问题有五本有五本书，它，它们的的编号分号分别为1，2，3，4，5，现现准准备分分给 A, B, C, D, E五个人，每个五个人，每个人的人的阅读兴趣用一个二趣用一个二维数数组来加以描述：来加以描述：希望编写一个程序，输
33、出所有的分书方案，希望编写一个程序，输出所有的分书方案，让人人皆大欢喜。让人人皆大欢喜。67假定这假定这5个人对这个人对这5本书的阅读兴趣如下表：本书的阅读兴趣如下表： 1 2 3 4 5ABCDE0011011001011010001001001人人书书68解题思路：解题思路：1、定义一个整型的二维数组，将上表中的阅读喜好、定义一个整型的二维数组，将上表中的阅读喜好用初始化的方法赋给这个二维数组。用初始化的方法赋给这个二维数组。可定义：可定义：int Like66 = 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,
34、0,1,0,0,1;692、定义一个整型一维数组、定义一个整型一维数组BookFlag6用来记录书用来记录书是否已被选用。用后五个下标作为五本书的标号，是否已被选用。用后五个下标作为五本书的标号，被选用的元素值为被选用的元素值为1, 未被选用的值为未被选用的值为0, 初始化皆为初始化皆为0.int BookFlag6 = 0;703、定义一个整型一维数组、定义一个整型一维数组BookTaken6用来记录用来记录每一个人选用了哪一本书。用数组元素的下标来作每一个人选用了哪一本书。用数组元素的下标来作为人的标号，用数组元素的值来表示书号。如果某为人的标号，用数组元素的值来表示书号。如果某个人还没有
35、选好书，则相应的元素值为个人还没有选好书，则相应的元素值为0。初始化。初始化时，所有的元素值均为时，所有的元素值均为0。int BookTaken6 = 0;4、循环变量、循环变量 i 表示人，表示人，j 表示书，表示书，i, j 1, 2, 3, 4, 571一种方法：一种方法：枚举法枚举法。把所有可能出现的分书方案都枚举出来，把所有可能出现的分书方案都枚举出来，然后逐一判断它们是否满足条件，即是否然后逐一判断它们是否满足条件，即是否使得每个人都能够得到他所喜欢的书。使得每个人都能够得到他所喜欢的书。缺点：计算量太大。缺点：计算量太大。72i=1 j=1 j=2i=2j=3 j=5i=3j=
36、1i=3j=2 j=4i=4j=2 j=4i=4j=5i=5j=4 j=5 j=5 j=2i=5j=4 j=2 j=1 j=4i=4j=5 j=1i=5j=4 j=1i=3j=5i=2j=4如何抽取出如何抽取出递归形式？形式？73void person( int i );int Like66 = 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 BookFlag6 = 0;int BookTaken6 = 0;void main( ) person( 1
37、 );74void person(int i)/ 尝试给第尝试给第i个人分书个人分书 int j, k; for(j = 1; j = 5; j+)/ 尝试尝试把把每每本本书分分给第第i个人个人 if(BookFlagj != 0) | (Likeij = 0) continue; / 失败失败 BookTakeni = j; / 把第把第j本本书分分给第第i个人个人 BookFlagj = 1; if(i = 5)/ 已找到一种分书方案已找到一种分书方案 for(k = 1; k i, 表明这一步不可能走表明这一步不可能走 j 级台阶级台阶, 函函 数数返回返回；否则，转第三步；否则，转第三
38、步；第三步：这一步走第三步：这一步走 j 级台阶，即级台阶，即 paces = j; 如果如果 i - j = 0，说明已经到达地面了，也就是，说明已经到达地面了，也就是 已经找到一种方案了，把它显示出来；否则已经找到一种方案了，把它显示出来；否则 的话，接着走下一步，的话，接着走下一步，TryStep(i-j, s+1)；第四步：第四步： j = j +1，如果，如果 j 3，转第二步；否则函数，转第二步；否则函数 结束。结束。能否用分治策略？能否用分治策略？808.3.3 八皇后问题八皇后问题在在8 88 8的棋盘上，放置的棋盘上，放置8 8个个皇后皇后（棋子），使两两之（棋子），使两两之
39、间互不攻击。所谓互不攻击是说任何两个皇后都要间互不攻击。所谓互不攻击是说任何两个皇后都要满足：满足：（1 1）不在棋盘的同一行；）不在棋盘的同一行；（2 2）不在棋盘的同一列；）不在棋盘的同一列；（3 3）不在棋盘的同一对角线上。）不在棋盘的同一对角线上。因此可以推论出，棋盘共有因此可以推论出，棋盘共有8 8行，故至多有行，故至多有8 8个皇后，个皇后，即每一行有且仅有一个皇后。这即每一行有且仅有一个皇后。这8 8个皇后中的每一个个皇后中的每一个应该摆放在哪一列上是解该题的任务。应该摆放在哪一列上是解该题的任务。8182数据的定义（数据的定义（1）：）： i 第第i i行（个）皇后，行（个）皇
40、后，1 1 i i 8 8； j 第第j列，列， 1 1 j j 8 8； Queeni 第第i i行皇后所在的列；行皇后所在的列； ColumnjColumnj 第第j j列是否列是否安全安全，0, 10, 1；83 1 2 3 4 5 6 7 81234567884数据的定义（数据的定义（2）：）： Down-7.7 记录每一条从上到下的对记录每一条从上到下的对 角线，是否安全，角线，是否安全，0,10,1 Up2.16 Up2.16记录每一条从下到上的对角记录每一条从下到上的对角 角线，是否安全，角线，是否安全，0,10,185利用以上的数据定义：利用以上的数据定义：当我们需要在棋盘的当
41、我们需要在棋盘的( i, j ) 位置摆放一个皇位置摆放一个皇后的时候，可以通过后的时候，可以通过Column数组、数组、Down数组和数组和Up数组的相应元素，来判断该位置数组的相应元素，来判断该位置是否安全；是否安全；当我们已经在棋盘的当我们已经在棋盘的( i, j ) 位置摆放了一个位置摆放了一个皇后以后，就应该去修改皇后以后，就应该去修改Column数组、数组、Down数组和数组和Up数组的相应元素，把相应的数组的相应元素，把相应的列和对角线设置为不安全。列和对角线设置为不安全。86void TryQueen( int i );int Queen9 = 0 ;int Column9 =
42、 0 ;int Down15 = 0 ;int Up15 = 0 ;void main( ) TryQueen( 1 );87void TryQueen(int i)/ 摆放第摆放第 i 行的皇后行的皇后 int j, k; for(j = 1; j = 8; j+)/ 尝试尝试把把该皇后放在每一列该皇后放在每一列 if(Columnj | Downi-j+7 | Upi+j-2) continue; / 失败失败 Queeni = j; / 把把该皇后放在该皇后放在第第j列上列上 Columnj = 1; Downi-j+7 = 1; Upi+j-2 = 1; if(i = 8)/ 已找到一
43、种解决方案已找到一种解决方案 for(k = 1; k = 8; k+) printf(%d , Queenk); printf(n); else TryQueen(i + 1); / 摆放第摆放第i+1行的皇后行的皇后 Queeni = 0;/ 回溯，把该皇后从第回溯，把该皇后从第j列拿起列拿起 Columnj = 0; Downi-j+7 = 0; Upi+j-2 = 0; 88共共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
44、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 1 4 7 5方案方案10：2 7 3 6 8 5 1 4891.1.假设在假设在棋盘上事先已经摆放了一个国王棋盘上事先已经摆放了一个国王，位，位置为置为，即即第第X X行第行第Y Y列列，在摆放八个皇在摆放八个皇后时，要求皇后间不能互相攻击且不能被国后时，要求皇后间不能互相攻击且不能被国王攻击。王攻击。国王的攻击范围如下图所示：国王的攻击范围如下图所示：思考题：对题目做如下的修改思考题：对题目做如
45、下的修改902.2.先输入某一个皇后所在的位置先输入某一个皇后所在的位置，即第，即第X X行第行第Y Y列，列，在此情形下，如何摆放其余的在此情形下，如何摆放其余的7 7个个皇后，要求找到所有解决方案。皇后，要求找到所有解决方案。918.3.4 过河过河问题问题问题描述：问题描述：M条狼和条狼和N条狗（条狗（NM）渡船过河，从河西）渡船过河，从河西到河东。在每次航行中，该船最多能容纳到河东。在每次航行中，该船最多能容纳2只动物，只动物，且最少需搭载且最少需搭载1只动物。安全限制：无论在河东、只动物。安全限制：无论在河东、河西还是船上，狗的数量不能小于狼的数量。河西还是船上，狗的数量不能小于狼的
46、数量。请问：能否找到一种方案，使所有动物都能顺利过请问：能否找到一种方案，使所有动物都能顺利过河。如果能，移动的步骤是什么？河。如果能，移动的步骤是什么？92如何描述系统的当前状态？如何描述系统的当前状态？位置：河西岸、河东岸、河；位置：河西岸、河东岸、河；对象：船、狼、狗。对象：船、狼、狗。问题分析问题分析93三元组三元组（W、 D、 B）WolfDogBoat例如：例如：(2, 2, W)94若若M2、N2(2, 2, W)(0, 2, E)(1, 2, W)(0, 0, E)(2, 0, W)(1, 0, E)951.问题实质：在一个有向图中寻找一条问题实质：在一个有向图中寻找一条路径路
47、径；2.状态转换：如何从一个结点状态转换：如何从一个结点跳转跳转到另一个到另一个结点；结点；3.状态树？状态树？问题分析问题分析961.如何避免访问如何避免访问重复的重复的结点？结点？2.如何用如何用简练的简练的语句实现状态的转换？语句实现状态的转换？3.如何将如何将5种情形种情形归纳归纳为同一种形式？为同一种形式？技术难点技术难点97#include #define MAX_M 20#define MAX_N 20int M, N;struct Status int W, D, B;steps1000;int s = 0, num = 0;int flagsMAX_MMAX_N2 = 0;v
48、oid CrossRiver(int W, int D, int B);int IsValid(int w, int d, int b);98void main( ) scanf(%d %d, &M, &N); flagsMN0 = 1; steps0.W = M; steps0.D = N; steps0.B = 0; s = 1; CrossRiver(M, N, 0);void CrossRiver(int W, int D, int B) int i, j, f; int w, d, b;99 if(B = 0) f = -1; else f = 1; for(j = 1; j = 5
49、; j+) switch(j) case 1: w = W + f*1; d = D; break; case 2: w = 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;100 if(IsValid(w, d, b) flagswdb = 1; stepss.W = w; stepss.D = d; stepss.B = b; s+; if(w = 0
50、& d = 0 & b = 1) num +; printf(Solutions %d: n, num); for(i = 0; i s; i+) printf(%d %d %dn, stepsi.W, stepsi.D, stepsi.B); else CrossRiver(w, d, b); flagswdb = 0; s-; 101int IsValid(int w, int d, int b) if(w M) return 0; if(d N) return 0; if(flagswdb = 1) return 0; if(d 0 & w d) return 0; if(N-d 0)
51、& (M-w N-d) return 0; return 1;1022 2Solutions 1:2 2 00 2 11 2 01 0 12 0 00 0 1Solutions 2:2 2 00 2 11 2 01 0 11 1 00 0 1Solutions 3:2 2 01 1 11 2 01 0 12 0 00 0 1Solutions 4:2 2 01 1 11 2 01 0 11 1 00 0 11038.3.5 排列排列问题问题n个对象的一个排列，就是把这个对象的一个排列，就是把这 n 个不同的个不同的对象放在同一行上的一种安排。例如，对于对象放在同一行上的一种安排。例如，对于三个
52、对象三个对象 a, ,b, ,c，总共有，总共有6个排列：个排列：a b ca c bb a cb c ac a bc b an 个对象的排列个数就是个对象的排列个数就是 n!。104如何生成排列？如何生成排列？基于分治策略的递归算法：基于分治策略的递归算法：假设这假设这 n 个对象为个对象为 1, 2, 3, , n；对于前对于前n-1个元素的每一个排列个元素的每一个排列 a1 a2 an-1，1 ai n-1，通过在所有可能的位置上插入通过在所有可能的位置上插入数字数字 n，来形成，来形成 n 个所求的排列，即：个所求的排列，即：n a1 a2 an-1a1 n a2 an-1a1 a2
53、n an-1 a1 a2 an-1 n105例如：生成例如：生成1,2,3的所有排列的所有排列permutation(3) permutation(2) permutation(1)permutation(1)：1permutation(2)：2 1，1 2permutation(3)：3 2 1，2 3 1，2 1 3， 3 1 2，1 3 2，1 2 3106基于回溯策略的递归算法：基于回溯策略的递归算法：基本思路：每一个排列的长度为基本思路：每一个排列的长度为 N，对这，对这N个不同的位置，按照顺序逐一地枚举所有个不同的位置，按照顺序逐一地枚举所有可能出现的数字。可能出现的数字。定义一维
54、数组定义一维数组NumFlagN+1用来记录用来记录1-N之之间的每一个数字是否已被使用，间的每一个数字是否已被使用，1表示已使表示已使用，用，0表示尚未被使用，初始化皆为表示尚未被使用，初始化皆为0；107定义一维数组定义一维数组NumTakenN+1，用来记录每，用来记录每一个位置上使用的是哪一个数字。如果在某一个位置上使用的是哪一个数字。如果在某个位置上还没有选好数字，则相应的数组元个位置上还没有选好数字，则相应的数组元素值为素值为0。初始化时，所有元素值均为。初始化时，所有元素值均为0；循环变量循环变量 i 表示第表示第 i 个位置，个位置，j 表示整数表示整数 j，i, j 1, 2
55、, , N。108i=1 i=2j=11 j=1i=3j=21 2j=3i=3 1 3 j=1 j=2 j=31 2 3 j=1 j=21 3 2 j=3i=2j=22 i=3j=12 1 j=2 j=3i=32 3 j=1 j=2 j=32 1 3 j=12 3 1 j=2 j=3i=2j=33 i=3j=13 1 j=3j=2i=33 2 j=1 j=23 1 2 j=3 j=13 2 1 j=2,3假定假定N=3109#define N 3void TryNumber( int i );int NumFlagN+1 = 0;int NumTakenN+1 = 0;main( ) TryN
56、umber( 1 );110void TryNumber(int i) int j, k; for(j = 1; j = N; j+) if(NumFlagj != 0) continue; NumTakeni = j; NumFlagj = 1; if(i = N) for(k = 1; k = N; k+) printf(%d , NumTakenk); printf(n); else TryNumber(i + 1); NumTakeni = 0; NumFlagj = 0; 111问题描述：问题描述：编写一个程序，它接受用户输入的一个编写一个程序，它接受用户输入的一个英文单词（长度不超
57、过英文单词（长度不超过20个字符），然后个字符），然后输出由这个单词的各个字母所组成的所有输出由这个单词的各个字母所组成的所有排列。有两个条件：第一、这个单词的排列。有两个条件：第一、这个单词的各个字母允许有相同的；第二、不能输出各个字母允许有相同的；第二、不能输出重复的排列。重复的排列。112例如：例如：请输入一个英文入一个英文单词：boyboybyoobyoybyboyob请输入一个英文入一个英文单词：bobbobbboobb讨论113i=1 i=2j=1b j=1i=3j=2b oj=3i=3 b b j=1 j=2 j=3b o b j=1 j=2b b o j=3i=2j=2o i=
58、3j=1o b j=2 j=1 j=2 j=3o b bj=3 假定单词为：假定单词为：bobj=3 114#define MAXSIZE 20void TryChar(char *word, int i, int length);int CharFlagMAXSIZE = 0;int CharTakenMAXSIZE = 0;main( ) char wordMAXSIZE; int length; printf(请输入一个入一个单词：); scanf(%s, word); length = strlen(word); TryChar(word, 1, length);115void Try
59、Char(char *word, int i, int length) int j, k; for(j = 1; j = length; j+) if (CharFlagj = 1) continue; for(k = 1; k j; k+) if(CharFlagk = 0) / 在同一在同一结点不能点不能测试相同的两个字符，相同的两个字符， / 减减1是是为了了对齐下下标。 if(wordk - 1 = wordj - 1) break; if(k j) continue;116 CharTakeni = j; CharFlagj = 1; if(i = length) for(k = 1; k = length; k+) printf(%c , wordCharTakenk - 1); printf(n); else TryChar(word, i + 1, length); CharTakeni = 0; CharFlagj = 0; 117下下 课课 啦啦 !
