c语言递归算法实用教案

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

1、第八章第八章 递归算法递归算法(sun f)(sun f)基本概念基本概念基于基于(jy)回溯策略的递归回溯策略的递归基于分治基于分治(fn zh)策略的递归策略的递归 第1页/共117页第一页，共118页。从前从前(cngqin)(cngqin)有座山，山上有座庙，庙里有一个老和尚有座山，山上有座庙，庙里有一个老和尚和一个小和尚，老和尚正在给小和尚讲故事。和一个小和尚，老和尚正在给小和尚讲故事。讲的是什么故事呢？他说，从前讲的是什么故事呢？他说，从前(cngqin)(cngqin)第2页/共117页第二页，共118页。Recursion- See Recursion. In order to

2、 understand recursion, one must first understand recursion. 第3页/共117页第三页，共118页。C语言允许语言允许(ynx)嵌套地调用函数，也就是说，在调嵌套地调用函数，也就是说，在调用用一个函数的过程中，又去调用另一个函数。一个函数的过程中，又去调用另一个函数。函数函数(hnsh)的嵌套调用的嵌套调用void main( ) study_english ( ); void study_english( ) reading( ); listening( ); writing( )void listening( ) 第4页/共117页

3、第四页，共118页。函数的嵌套调用有一个特例函数的嵌套调用有一个特例(tl)，即递归调用，即递归调用，也就也就是说，在调用一个函数的过程中，又出现了直接是说，在调用一个函数的过程中，又出现了直接或间接地去调用该函数本身。或间接地去调用该函数本身。void tell_story( ) int old_monk, young_monk; tell_story ( ); / tell_story 函数(hnsh)的递归调用函数函数(hnsh)的递归调用的递归调用? ?第5页/共117页第五页，共118页。void tell_story( ) static int old_monk, young_mo

4、nk; old_monk = old_monk + 1; / 年龄大了一岁 young_monk = young_monk + 1; if(old_monk = 60) / 递归形式(xngsh) tell_story ( ); else printf(对不起，已退休！); / 递归边界第6页/共117页第六页，共118页。在语法上（简单在语法上（简单(jindn)(jindn)）递归即为普通的函数调用。递归即为普通的函数调用。在算法上（难）在算法上（难）如何找到递归形式？如何找到递归形式？如何找到递归边界？如何找到递归边界？如何编写如何编写(binxi)递归程序？递归程序？ 第7页/共117

5、页第七页，共118页。递归算法递归算法(sun f)的类型的类型递归算法可以分为递归算法可以分为(fn wi)两种类型：两种类型：基于分治策略的递归算法；基于分治策略的递归算法；基于回溯策略的递归算法。基于回溯策略的递归算法。第8页/共117页第八页，共118页。第八章第八章 递归算法递归算法(sun f)(sun f)基本概念基本概念基于基于(jy)回溯策略的递归回溯策略的递归基于分治基于分治(fn zh)策略的递归策略的递归 第9页/共117页第九页，共118页。分而治之（分而治之（divide-and-conquer）的算法）的算法设计思想：设计思想：Divide：把问题划分为若干个子问

6、题；：把问题划分为若干个子问题；Conquer：以同样的方式分别：以同样的方式分别(fnbi)去处理各个子问题；去处理各个子问题；Combine：把各个子问题的处理结果综合起来，形成最终的处理结果。：把各个子问题的处理结果综合起来，形成最终的处理结果。8.2.1 分而治之分而治之(fn r zh zh)第10页/共117页第十页，共118页。玛特露什卡玛特露什卡第11页/共117页第十一页，共118页。调用调用(dioyng)调用调用(dioyng)调用调用(dioyng)调用调用调用调用调用调用第12页/共117页第十二页，共118页。如何编写基于分治策略的递归程序？如何编写基于分治策略的递

7、归程序？在算法分析上，要建立分治递归的思维方式。在算法分析上，要建立分治递归的思维方式。在编程实现在编程实现(shxin)(shxin)上，要建立递归信心（上，要建立递归信心（To turst the recursion, Jerry Cain, To turst the recursion, Jerry Cain, stanfordstanford）。）。第13页/共117页第十三页，共118页。如何建立分治递归的思维方式？如何建立分治递归的思维方式？基本原则：目标驱动基本原则：目标驱动(q dn)！计算计算n!：n! = n * (n-1)!，且，且1! = 1。递归形式递归形式递归边界递

8、归边界第14页/共117页第十四页，共118页。调用调用调用调用fact(3)fact(2)fact(1)第15页/共117页第十五页，共118页。void main( ) int n; printf(请输入(shr)一个整数：); 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);请输入(shr)一个整数：33! = 6第16页/共117页第十六页，共118页。 Bfact(2)fact(2)=2*fact(1)=2*fact(

9、1)=2*1=2*1=2=2返回返回 DAfact(3)fact(3)=3*fact(2)=3*fact(2)=3*2=3*2=6=6E E返回返回 Cfact(1)=1调用调用调用调用调用调用(dioyng)和返回的递归示意图和返回的递归示意图第17页/共117页第十七页，共118页。如何建立递归信心？如何建立递归信心？函数的递归调用到底是如何进行的呢？在递归调用时，执行的是不是相同的代函数的递归调用到底是如何进行的呢？在递归调用时，执行的是不是相同的代码？访问的是不是相同的数据？如果是的话，那么大家码？访问的是不是相同的数据？如果是的话，那么大家(dji)会不会相互会不会相互干扰、相互妨碍

10、？干扰、相互妨碍？第18页/共117页第十八页，共118页。main的栈帧的栈帧m3void main( ) int m; printf(请输入(shr)一个整数：); 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的栈帧的栈帧第19页/共117页第十九页，共118页。8.2.2 寻找寻找(xnzho)最大值最大值问题问题(wnt)描述：描述：给定一个整型数组给定一个整

11、型数组a，找出其中的最大，找出其中的最大值。值。如何设计相应的递归算法？如何设计相应的递归算法？第20页/共117页第二十页，共118页。如何来设计相应的递归算法？如何来设计相应的递归算法？目标：目标：maxa0, a1, an-1可分解为：可分解为：maxa0, maxa1, an-1另外已知另外已知maxx x这就是递归算法的递归形式这就是递归算法的递归形式(xngsh)和递归边界，据和递归边界，据此可以编写出相应的递归函数。此可以编写出相应的递归函数。第21页/共117页第二十一页，共118页。int Max(int a, int first, int n) int max; if(fi

12、rst = n-1) return afirst; max = Max(a, first+1, n); if(max R) return(-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);第32页/共117页第三十二页，共118页。8.2.4 汉诺汉诺(Hanoi)塔问题塔问题(wnt)相传在古印度相传在古印度Bramah庙中，有位僧人整天把三根柱子上的庙中，有位僧人整天把三根柱子上的

13、金盘倒来倒去，原来他是想把金盘倒来倒去，原来他是想把64个一个个一个(y )比一个比一个(y )小的金盘从一根柱子上移到另一根柱子上去。移动过程中遵小的金盘从一根柱子上移到另一根柱子上去。移动过程中遵守以下规则：每次只允许移动一只盘，且大盘不得落在小盘守以下规则：每次只允许移动一只盘，且大盘不得落在小盘上（简单吗？若每秒移动一只盘子，需上（简单吗？若每秒移动一只盘子，需5800亿年）亿年）ABC第33页/共117页第三十三页，共118页。怎样编写这种程序？思路上还是先从最简单的情况分析怎样编写这种程序？思路上还是先从最简单的情况分析(fnx)起，搬一搬看，慢慢理出思路。起，搬一搬看，慢慢理出思

14、路。1、在、在A柱上只有一只盘子，假定柱上只有一只盘子，假定(jidng)盘号盘号为为1， 这时只需将该盘直接从这时只需将该盘直接从A搬至搬至C，记，记为为 move from A to CABC1第34页/共117页第三十四页，共118页。2、在、在A柱上有二只盘子，柱上有二只盘子，1为小盘为小盘2为大盘为大盘(d pn)。分三步进行：分三步进行：ABC21move from A to B;move from A to C;move form B to C;第35页/共117页第三十五页，共118页。3、在、在A柱上有柱上有3只盘子只盘子(pn zi)，从小到大分别，从小到大分别为为1号，号

15、，2号，号，3号。怎么移？号。怎么移？ABC213分七步分七步(q b)！第36页/共117页第三十六页，共118页。 分三步进行分三步进行(jnxng)： move 2 discs from A to B using C； move from A to C； move 2 discs from B to C using A ；ABC213第37页/共117页第三十七页，共118页。4、在、在A柱上有柱上有 n 个盘子个盘子(pn zi), 从小到大分别为从小到大分别为1号、号、2号、号、3 号、号、n号。号。 第第 1 步：将步：将1号、号、2号、号、n-1号盘作为一个整体，号盘作为一个整体

16、， 在在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 ；递归形式(xngsh)！第38页/共117页第三十八页，共118页。定义函数定义函数move(int n, char L, char M,

17、char R);表示表示(biosh)move n discs from L to R using M；如果如果 n = 1，即表示，即表示(biosh)move from L to R；移动的是谁？第39页/共117页第三十九页，共118页。#include void move(int n, char L, char M, char R);void main( ) int n; printf(请输入(shr)一个整数：); scanf(%d, &n); move(n, A, B, C);第40页/共117页第四十页，共118页。/ L: Left post, M: Middle post,

18、R: Right 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); 第41页/共117页第四十一页，共118页。请输入(shr)一个整数：3move #1 from A to Cmove #2 from A to Bmove #1 from C to Bmove #3 from A to

19、Cmove #1 from B to Amove #2 from B to Cmove #1 from A to C一次运行一次运行(ynxng)结果结果第42页/共117页第四十二页，共118页。8.2.5 青蛙青蛙(qngw)过河过河 一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一石柱L，面，面积只容得下一只青蛙落脚，同样右岸也有一石柱积只容得下一只青蛙落脚，同样右岸也有一石柱R，面积也只容得下一只青，面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将青蛙从小到大，用蛙落脚。有一队青蛙从尺寸上一个比一个小。我们将

20、青蛙从小到大，用1，2，n编号。规定初始编号。规定初始(ch sh)时这队青蛙只能趴在左岸的石头时这队青蛙只能趴在左岸的石头L上，按上，按编号一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中编号一个落一个，小的落在大的上面。不允许大的在小的上面。在小溪中有有S根石柱，有根石柱，有y片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只片荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。同样要求按编号一个落一个，大的在下，小的在上，而且必须编号相邻。对于荷叶只允许一只青蛙落脚，不允许多只在其上。对于右岸的石柱对于荷叶只允许一只

21、青蛙落脚，不允许多只在其上。对于右岸的石柱R，与，与左岸的石柱左岸的石柱L一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在一样允许多个青蛙落脚，但须一个落一个，小的在上，大的在下，且编号相邻。当青蛙从左岸的下，且编号相邻。当青蛙从左岸的L上跳走后就不允许再跳回来；同样，从上跳走后就不允许再跳回来；同样，从左岸左岸L上跳至右岸上跳至右岸R，或从溪中荷叶或溪中石柱跳至右岸，或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允上的青蛙也不允许再离开。问在已知溪中有许再离开。问在已知溪中有S根石柱和根石柱和y片荷叶的情况下，最多能跳过多少片荷叶的情况下，最多能跳过多少只青蛙？只青蛙？第43页/共117

22、页第四十三页，共118页。这题看起来较难，但是如果我们认真分析，理这题看起来较难，但是如果我们认真分析，理出思路，就可化难为易。出思路，就可化难为易。思路：思路：1、简化问题，探索规律。先从个别再到一般，要善、简化问题，探索规律。先从个别再到一般，要善于对多个因素于对多个因素(yn s)作分解，孤立出一个一个因作分解，孤立出一个一个因素素(yn s)来分析，化难为易。来分析，化难为易。2. 定义函数定义函数 Jump ( S ,y ) 最多可跳过河的青蛙数最多可跳过河的青蛙数 其中：其中： S 河中柱子数河中柱子数 y 荷叶数荷叶数第44页/共117页第四十四页，共118页。 2 说明：河中有

23、一片荷叶，可以过两只青蛙，起始时说明：河中有一片荷叶，可以过两只青蛙，起始时 L 上有两上有两只青蛙，只青蛙，1# 在在 2# 上面。上面。 第一步：第一步：1# 跳到荷叶上；跳到荷叶上； 第二步：第二步：2# 从从 L 直接跳至直接跳至 R 上；上； 第三步：第三步：1# 再从荷叶跳至再从荷叶跳至 R 上。上。 如下图：如下图：2#2#1#1#2 21 13 3L L左岸左岸R R右岸右岸3. 先看简单(jindn)情况，河中无柱子：S = 0 ，Jump ( 0 , y ) 当 y = 1 时，Jump ( 0 , 1 ) = ；第45页/共117页第四十五页，共118页。3 说明：河中有

24、两片荷叶时，可以过说明：河中有两片荷叶时，可以过 3 只青蛙。起始时：只青蛙。起始时： 1#，2#，3# 3只青蛙落在只青蛙落在 L 上，上， 第一步：第一步：1# 从从 L 跳至叶跳至叶 1上，上， 第二步：第二步：2# 从从 L 跳至叶跳至叶 2上，上， 第三步：第三步：3# 从从 L 直接跳至直接跳至 R 上，上， 第四步：第四步：2# 从叶从叶 2 跳至跳至 R 上，上， 第五步：第五步：1# 从叶从叶 1 跳至跳至 R 上，上，叶1叶13 31 15 5L LR R叶2叶22 24 4采用采用(ciyng)归纳法：归纳法：Jump ( 0 , y ) = 当 y = 2 时， Jum

25、p ( 0 , 2 ) = ； y+1； 意思是：在河中没有石柱意思是：在河中没有石柱(sh zh)的情况下，过河的青蛙数仅取决于的情况下，过河的青蛙数仅取决于荷叶数，数目是荷叶数荷叶数，数目是荷叶数+1。第46页/共117页第四十六页，共118页。再看再看Jump( S, y )Jump( S, y )先看一个最简单情况：先看一个最简单情况： S = 1 S = 1，y = 1 y = 1 。从图上看出需要从图上看出需要(xyo) (xyo) 步，跳过步，跳过 只青蛙。只青蛙。S SY Y5 54 46 6L LR R1 12 23 37 78 89 91#2#4#3#3#1#2#1#1#

26、9 4 9 4 1# 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；第47页/共117页第四十七页，共118页。对于对于S = 1S = 1，y = 1y = 1的情形，从另外一个角度来分析的情形，从另外一个角度来分析(fnx)(fnx)若没有石柱若没有石柱S S，最多可过

27、，最多可过 y+1 = 2 y+1 = 2 只青蛙。只青蛙。有了石柱有了石柱S S后，最多可过后，最多可过 2 2* *2 = 4 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#YYY第48页/共117页第四十八页，共118页。对于对于S = 1S = 1，y 1y 1的情形的情形若没有若没有(mi yu)(mi yu)石柱石柱S S，最多可过，最多可过 y+1 y+1 只

28、青蛙。只青蛙。有了石柱有了石柱S S后，最多可过后，最多可过 2 2* *(y+1) (y+1) 只青蛙。只青蛙。步骤步骤1 1：前前y+1y+1只只 从从 L L S S；步骤步骤2 2：后后y+1y+1只只 从从 L L R R；步骤步骤3 3：前前y+1y+1只只 从从 S S R R；YSLR: 前前y+1只只: 后后y+1只只: 前前y+1只只YYY第49页/共117页第四十九页，共118页。对于对于S = 2S = 2，y 1y 1的情形的情形若只有石柱若只有石柱(sh zh)S1(sh zh)S1，最多可过，最多可过 2 2* *(y+1) (y+1) 只青蛙。只青蛙。有了石柱有

29、了石柱(sh zh)S2(sh zh)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,S1第50页/共117页第五十页，共118页。采用归纳法，可得出如下的递归形式：采用归纳法，可得出如下的递归形式：Jump(S, y) = 2 * Jump(S-1, y)；意思是：先让一半的青蛙利用意思是：先让一半的青蛙利用y片荷叶和片荷叶和S-1根根石柱，落在河中剩下石

30、柱，落在河中剩下(shn xi)的那根石柱上；的那根石柱上；然后让另一半的青蛙利用然后让另一半的青蛙利用y片荷叶和片荷叶和S-1根石柱，根石柱，落在右岸的落在右岸的R上面；最后再让先前的一半青蛙，上面；最后再让先前的一半青蛙，利用利用y片荷叶和片荷叶和S-1根石柱，落在右岸的根石柱，落在右岸的R上面。上面。递归边界：递归边界：Jump(0, y) = y + 1第51页/共117页第五十一页，共118页。void main( ) int S, y; printf(请输入石柱(sh zh)和荷叶的数目：); scanf(%d %d, &S, &y); printf(最多有 %d 只青蛙过河n,

31、Jump(S, y);int Jump(int S, int y) if(S = 0) return( y + 1 ); return( 2 * Jump(S-1, y);第52页/共117页第五十二页，共118页。8.2.6 快速快速(kui s)排序排序快速排序的基本思路：快速排序的基本思路：1 1、在数组、在数组a a中，有一段待排序的数据，下标中，有一段待排序的数据，下标从从l l到到r r。2 2、取、取alal放在变量放在变量valuevalue中，通过由右、左中，通过由右、左两边对两边对valuevalue的取值的比较，为的取值的比较，为valuevalue选择选择应该排定的位置

32、。这时要将比应该排定的位置。这时要将比valuevalue大的数大的数放右边，比它小的数放左边。当放右边，比它小的数放左边。当valuevalue到达到达(dod)(dod)最终位置后（如下标最终位置后（如下标m m），由它划），由它划分了左右两个集合分了左右两个集合l.m-1l.m-1、m+1.rm+1.r。然后转第然后转第1 1步，再用相同的思路分别去处理步，再用相同的思路分别去处理左集合和右集合。左集合和右集合。第53页/共117页第五十三页，共118页。令令 qsort(l, r)表示表示(biosh)将数组元素从下标为将数组元素从下标为 l 到到下标为下标为 r 的共的共 r-l+1

33、 个元素进行从小到大的个元素进行从小到大的快速排序。快速排序。目标：目标：1、让、让 value = al2、将、将 value 放在放在 am中，中，l m r3、使、使 al, al+1, , am-1 = am4、使、使 am am+1, am+2, , ar第54页/共117页第五十四页，共118页。例子：数组例子：数组a当中有当中有7个元素等待个元素等待(dngdi)排序。排序。5261734lr首先首先(shuxin)，让，让value = al = a0 = 5value5a0123456下标下标(xi bio)第55页/共117页第五十五页，共118页。5261734l第二步，

34、从第二步，从r=6开始，将开始，将ar与与value进行进行(jnxng)比较。比较。若若ar value，则，则 r-，继续比较。否则，继续比较。否则，al = ar，l +。value5ra0123456下标下标(xi bio)4l第56页/共117页第五十六页，共118页。4261734第三步，从第三步，从l=1开始，将开始，将al与与value进行比较进行比较(bjio)。若若al value，则，则 l+，继续比较，继续比较(bjio)。否则，。否则，ar = al，r -。value5ra0123456下标下标(xi bio)ll6r第57页/共117页第五十七页，共118页。42

35、61736又回到第二步，从又回到第二步，从r=5开始，将开始，将ar与与value进行进行(jnxng)比较。若比较。若ar value，则，则 r-，继续比较。否则，继续比较。否则al = ar，l +。 value5a0123456下标下标(xi bio)lr3l第58页/共117页第五十八页，共118页。4231736又回到第三步，从又回到第三步，从l=3开始，将开始，将al与与value进行进行(jnxng)比较。若比较。若al value，则，则 l+，继续比较。否则，继续比较。否则，ar = al，r -。 value5a0123456下标下标(xi bio)rll7r第59页/共

36、117页第五十九页，共118页。4231776现在现在 l r，已经找到了，已经找到了value的正确的正确(zhngqu)位置，把位置，把value中的值放回到数组当中。中的值放回到数组当中。value5a0123456下标下标(xi bio)lr5第60页/共117页第六十页，共118页。4231576下面的任务：用刚才介绍的方法，对下面的任务：用刚才介绍的方法，对 5 左、右两侧左、右两侧(lin c)的两段数据，分别进行排序。的两段数据，分别进行排序。a0123456下标下标(xi bio)1324a0123456下标下标lr67a0123456下标下标lr第61页/共117页第六十一

37、页，共118页。1234567最后最后(zuhu)的结果：的结果：a0123456下标下标(xi bio)具体具体(jt)实现：几重循环语句？实现：几重循环语句？参考程序：略参考程序：略第62页/共117页第六十二页，共118页。第八章第八章 递归算法递归算法(sun f)(sun f)基本概念基本概念基于基于(jy)回溯策略的递归回溯策略的递归基于基于(jy)分治策略的递归分治策略的递归 第63页/共117页第六十三页，共118页。 在程序设计当中，有相当一类求一组解、或求在程序设计当中，有相当一类求一组解、或求全部解或求最优解的问题，不是根据某种确定的全部解或求最优解的问题，不是根据某种确

38、定的计算法则，而是利用试探和回溯（计算法则，而是利用试探和回溯（Backtracking）的搜索技术求解的搜索技术求解(qi ji)。回溯法也是设计递归算法的。回溯法也是设计递归算法的一种一种重要方法，它的求解重要方法，它的求解(qi ji)过程实质上是一个先序遍过程实质上是一个先序遍历一历一棵棵“状态树状态树”的过程，只不过这棵树不是预先建立的，的过程，只不过这棵树不是预先建立的，而是隐含在遍历的过程当中。而是隐含在遍历的过程当中。第64页/共117页第六十四页，共118页。8.3.1 分书问题分书问题(wnt)有五本书，它们的编号分别为1，2，3，4，5，现准备(zhnbi)分给 A, B

39、, C, D, E五个人，每个人的阅读兴趣用一个二维数组来加以描述：10 ijijlike ij 喜欢 书不喜欢 书希望编写一个希望编写一个(y )程序，输出所有的分书方案，程序，输出所有的分书方案，让人人皆大欢喜。让人人皆大欢喜。第65页/共117页第六十五页，共118页。假定这假定这5个人对这个人对这5本书的阅读本书的阅读(yud)兴趣如下表：兴趣如下表： 1 2 3 4 5ABCDE0011011001011010001001001人人书书第66页/共117页第六十六页，共118页。解题解题(ji t)思路：思路：1、定义一个整型的二维数组，将上表中的阅读喜好、定义一个整型的二维数组，将

40、上表中的阅读喜好用初始化的方法用初始化的方法(fngf)赋给这个二维数组。赋给这个二维数组。可定义：可定义：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;第67页/共117页第六十七页，共118页。2、定义、定义(dngy)一个整型一维数组一个整型一维数组BookFlag6用来记录书用来记录书是否已被选用。用后五个下标作为五本书的标号，是否已被选用。用后五个下标作为五本书的标号，被选用的元素值为被选用的元素值为1, 未被选用的值为未被选用的值为0, 初始化皆为初始化皆为0

41、.int BookFlag6 = 0;第68页/共117页第六十八页，共118页。3、定义、定义(dngy)一个整型一维数组一个整型一维数组BookTaken6用来记录用来记录每一个人选用了哪一本书。用数组元素的下标来作每一个人选用了哪一本书。用数组元素的下标来作为人的标号，用数组元素的值来表示书号。如果某为人的标号，用数组元素的值来表示书号。如果某个人还没有选好书，则相应的元素值为个人还没有选好书，则相应的元素值为0。初始化。初始化时，所有的元素值均为时，所有的元素值均为0。int BookTaken6 = 0;4、循环变量、循环变量 i 表示人，表示人，j 表示书，表示书，i, j 1,

42、2, 3, 4, 5第69页/共117页第六十九页，共118页。一种方法：枚举一种方法：枚举(mi j)法。法。把所有可能出现的分书方案都枚举把所有可能出现的分书方案都枚举(mi j)出来，出来，然后逐一判断它们是否满足条件，即是否然后逐一判断它们是否满足条件，即是否使得每个人都能够得到他所喜欢的书。使得每个人都能够得到他所喜欢的书。缺点：计算量太大。缺点：计算量太大。第70页/共117页第七十页，共118页。i=1 j=1 j=2i=2j=3 j=5i=3j=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

43、=5 j=1i=5j=4 j=1i=3j=5i=2j=4如何抽取(chu q)出递归形式？第71页/共117页第七十一页，共118页。void 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 );第72页/共117页第七十二页，共118页。void person(int i) / 尝试

44、给第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, 表明表明(biomng)这一步不可能走这一步不可能走 j 级台阶级台阶, 函函 数返回；否则，转第三步；数返回；否则，转第三步；第三步：这一步走第三步：这一步走 j 级台阶，即级台阶，即 paces = j; 如果如果 i - j

45、 = 0，说明已经到达地面了，也就是，说明已经到达地面了，也就是 已经找到一种方案了，把它显示出来；否则已经找到一种方案了，把它显示出来；否则 的话，接着走下一步，的话，接着走下一步，TryStep(i-j, s+1)；第四步：第四步： j = j +1，如果，如果 j 3，转第二步；否则函数，转第二步；否则函数 结束。结束。能否用分治策略？第78页/共117页第七十八页，共118页。8.3.3 八皇后八皇后(hunghu)问题问题在在8 88 8的棋盘上，放置的棋盘上，放置8 8个皇后（棋子），使两两之个皇后（棋子），使两两之间互不攻击。所谓互不攻击是说任何两个皇后都要间互不攻击。所谓互不攻

46、击是说任何两个皇后都要满足：满足：（1 1）不在棋盘的同一行）不在棋盘的同一行(yxng)(yxng)；（2 2）不在棋盘的同一列；）不在棋盘的同一列；（3 3）不在棋盘的同一对角线上。）不在棋盘的同一对角线上。因此可以推论出，棋盘共有因此可以推论出，棋盘共有8 8行，故至多有行，故至多有8 8个皇后，个皇后，即每一行即每一行(yxng)(yxng)有且仅有一个皇后。这有且仅有一个皇后。这8 8个皇后中的每一个个皇后中的每一个应该摆放在哪一列上是解该题的任务。应该摆放在哪一列上是解该题的任务。第79页/共117页第七十九页，共118页。第80页/共117页第八十页，共118页。数据数据(shj

47、)的定义（的定义（1）：）： i 第第i行（个）皇后，行（个）皇后，1 i 8； j 第第j列，列， 1 j 8； Queeni 第第i行皇后所在的列；行皇后所在的列； Columnj 第第j列是否列是否(sh fu)安全，安全，0, 1；第81页/共117页第八十一页，共118页。 1 2 3 4 5 6 7 812345678第82页/共117页第八十二页，共118页。数据数据(shj)的定义（的定义（2）：）： Down-7.7 记录每一条从上到下的对记录每一条从上到下的对 角线，是否安全角线，是否安全(nqun)，0,1 Up2.16记录每一条从下到上的对角记录每一条从下到上的对角 角

48、线，是否安全角线，是否安全(nqun)，0,1第83页/共117页第八十三页，共118页。利用以上的数据定义：利用以上的数据定义：当我们需要在棋盘的当我们需要在棋盘的( i, j ) 位置摆放一个皇后的位置摆放一个皇后的时候，可以通过时候，可以通过Column数组、数组、Down数组和数组和Up数组的相应元素，来判断该位置是数组的相应元素，来判断该位置是否安全；否安全；当我们已经在棋盘的当我们已经在棋盘的( i, j ) 位置摆放了一个皇后位置摆放了一个皇后以后，就应该去修改以后，就应该去修改(xigi)Column数组、数组、Down数组和数组和Up数组的相应元素，把相应的列数组的相应元素，

49、把相应的列和对角线设置为不安全。和对角线设置为不安全。第84页/共117页第八十四页，共118页。void TryQueen( int i );int Queen9 = 0 ;int Column9 = 0 ;int Down15 = 0 ;int Up15 = 0 ;void main( ) TryQueen( 1 );第85页/共117页第八十五页，共118页。void TryQueen(int i)/ 摆放(bi fn)第 i 行的皇后 int j, k; for(j = 1; j = 8; j+) / 尝试把该皇后放在每一列 if(Columnj | Downi-j+7 | Upi+j

50、-2) continue; / 失败 Queeni = j; / 把该皇后放在第j列上 Columnj = 1; Downi-j+7 = 1; Upi+j-2 = 1; if(i = 8)/ 已找到一种解决方案 for(k = 1; k = 8; k+) printf(%d , Queenk); printf(n); else TryQueen(i + 1);/ 摆放(bi fn)第i+1行的皇后 Queeni = 0; / 回溯，把该皇后从第j列拿起 Columnj = 0; Downi-j+7 = 0; Upi+j-2 = 0; 第86页/共117页第八十六页，共118页。共共92组解，部

51、分组解，部分(b fen)答案如下：答案如下：方案方案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 1 4 7 5方案方案10：2 7 3 6 8 5 1 4第87页/共117页第八十七页，共118页。假设在棋盘上事先已经摆放了一个国王，位置假设在棋盘上事先已经摆放了一个国王，位置(wi

52、zhi)(wi zhi)为为，即第，即第X X行第行第Y Y列，列，在摆放八个皇后时，要求皇后间不能互相攻击且不能被国王攻击。国王的攻击范围在摆放八个皇后时，要求皇后间不能互相攻击且不能被国王攻击。国王的攻击范围如下图所示：如下图所示：思考题：对题目思考题：对题目(tm)做如下的修改做如下的修改第88页/共117页第八十八页，共118页。先输入某一个皇后所在的位置先输入某一个皇后所在的位置(wi zhi)(wi zhi)，即第，即第X X行第行第Y Y列，在此情形下，如何摆放其余的列，在此情形下，如何摆放其余的7 7个皇后，要求找到所有解决方案。个皇后，要求找到所有解决方案。第89页/共117

53、页第八十九页，共118页。8.3.4 过河问题过河问题(wnt)问题描述：问题描述：M条狼和条狼和N条狗（条狗（NM）渡船过河，从）渡船过河，从河西到河东。在每次航行中，该船最多能容河西到河东。在每次航行中，该船最多能容纳纳2只动物，且最少需搭载只动物，且最少需搭载1只动物。安全只动物。安全限制：无论在河东、河西还是船上，狗的数限制：无论在河东、河西还是船上，狗的数量不能小于狼的数量。量不能小于狼的数量。请问：能否找到一种方案，使所有动物都能请问：能否找到一种方案，使所有动物都能顺利顺利(shnl)过河。如果能，移动的步骤是过河。如果能，移动的步骤是什么？什么？第90页/共117页第九十页，共

54、118页。如何描述如何描述(mio sh)(mio sh)系统的当前状态？系统的当前状态？位置位置(wi zhi)(wi zhi)：河西岸、河东岸、河；：河西岸、河东岸、河；对象：船、狼、狗。对象：船、狼、狗。问题问题(wnt)分析分析第91页/共117页第九十一页，共118页。三元组三元组（W、 D、 B）WolfDogBoat例如例如(lr)：(2, 2, W)第92页/共117页第九十二页，共118页。若若M2、N2(2, 2, W)(0, 2, E)(1, 2, W)(0, 0, E)(2, 0, W)(1, 0, E)第93页/共117页第九十三页，共118页。问题实质：在一个有向图

55、中寻找一条路径；问题实质：在一个有向图中寻找一条路径；状态转换状态转换(zhunhun)：如何从一个结点跳转到另一个结点；：如何从一个结点跳转到另一个结点；状态树？状态树？问题问题(wnt)分析分析第94页/共117页第九十四页，共118页。如何避免访问重复的结点？如何避免访问重复的结点？如何用简练的语句实现状态如何用简练的语句实现状态(zhungti)的转换？的转换？如何将如何将5种情形归纳为同一种形式？种情形归纳为同一种形式？技术技术(jsh)难点难点第95页/共117页第九十五页，共118页。#include #define MAX_M 20#define MAX_N 20int M,

56、N;struct Status int W, D, B;steps1000;int s = 0, num = 0;int flagsMAX_MMAX_N2 = 0;void CrossRiver(int W, int D, int B);int IsValid(int w, int d, int b);第96页/共117页第九十六页，共118页。void main( ) scanf(%d %d, &M, &N); flagsMN0 = 1; steps0.W = M; steps0.D = N; steps0.B = 0; s = 1; CrossRiver(M, N, 0);void Cro

57、ssRiver(int W, int D, int B) int i, j, f; int w, d, b;第97页/共117页第九十七页，共118页。 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 = 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;

58、d = D + f*1; break; b = 1 - B;第98页/共117页第九十八页，共118页。 if(IsValid(w, d, b) flagswdb = 1; stepss.W = w; stepss.D = d; stepss.B = b; s+; if(w = 0 & 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

59、= 0; s-; 第99页/共117页第九十九页，共118页。int 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) & (M-w N-d) return 0; return 1;第100页/共117页第一百页，共118页。2 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

60、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 1第101页/共117页第一百零一页，共118页。8.3.5 排列排列(pili)问题问题n个对象的一个排列，就是把这个对象的一个排列，就是把这 n 个不同的个不同的对象放在同一行上的一种安排。例如，对于对象放在同一行上的一种安排。例如，对于(duy)三个对象三个对象 a,b,c，总共有，总共有6个排列：个排列：a b ca c bb a cb c ac a bc b an 个对象的排列个数就是个对象的排列个数就是 n!。第10

61、2页/共117页第一百零二页，共118页。如何如何(rh)生成排列？生成排列？基于分治策略的递归算法：基于分治策略的递归算法：假设这假设这 n 个对象为个对象为 1, 2, 3, , n；对于前对于前n-1个元素的每一个排列个元素的每一个排列(pili) a1 a2 an-1，1ai n-1，通过在所有可能的位置上插入，通过在所有可能的位置上插入数字数字 n，来形成，来形成 n 个所求的排列个所求的排列(pili)，即：，即：n a1 a2 an-1a1 n a2 an-1a1 a2 n an-1 a1 a2 an-1 n第103页/共117页第一百零三页，共118页。例如例如(lr)：生成：

62、生成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 3第104页/共117页第一百零四页，共118页。基于回溯策略的递归算法：基于回溯策略的递归算法：基本思路：每一个排列的长度为基本思路：每一个排列的长度为 N，对这，对这N个不同个不同的位置的位置(wi zhi)，按照顺序逐一地枚举所有，按照顺序逐一地枚举所有可能出现的数字。可能出现的数字。定义一维数

63、组定义一维数组NumFlagN+1用来记录用来记录1-N之间的每之间的每一个数字是否已被使用，一个数字是否已被使用，1表示已使用，表示已使用，0表示尚表示尚未被使用，初始化皆为未被使用，初始化皆为0；第105页/共117页第一百零五页，共118页。 定义一维数组定义一维数组NumTakenN+1，用来记录每一个，用来记录每一个位置上使用的是哪一个数字位置上使用的是哪一个数字(shz)。如果在某个。如果在某个位置上还没有选好数字位置上还没有选好数字(shz)，则相应的数组元，则相应的数组元素值为素值为0。初始化时，所有元素值均为。初始化时，所有元素值均为0； 循环变量循环变量 i 表示第表示第

64、i 个位置，个位置，j 表示整数表示整数 j，i, j 1, 2, , N。第106页/共117页第一百零六页，共118页。i=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=2j=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假定假定(jidng)N=3第107页/共117页第一百零七页，共118页。#defin

65、e N 3void TryNumber( int i );int NumFlagN+1 = 0;int NumTakenN+1 = 0;main( ) TryNumber( 1 );第108页/共117页第一百零八页，共118页。void 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 Tr

66、yNumber(i + 1); NumTakeni = 0; NumFlagj = 0; 第109页/共117页第一百零九页，共118页。问题问题(wnt)描述：描述：编写一个程序，它接受用户输入的一个编写一个程序，它接受用户输入的一个英文单词（长度不超过英文单词（长度不超过20个字符），然后个字符），然后输出由这个单词的各个字母所组成输出由这个单词的各个字母所组成(z chn)的所有的所有排列。有两个条件：第一、这个单词的排列。有两个条件：第一、这个单词的各个字母允许有相同的；第二、不能输出各个字母允许有相同的；第二、不能输出重复的排列。重复的排列。第110页/共117页第一百一十页，共118页。例如例如(lr)：请输入(shr)一个英文单词：boyboybyoobyoybyboyob请输入(shr)一个英文单词：bobbobbboobb讨论第111页/共117页第一百一十一页，共118页。i=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=3j=1o b j=2 j=1 j=2