《【2018年整理】c语言递归算法》由会员分享，可在线阅读，更多相关《【2018年整理】c语言递归算法（117页珍藏版）》请在金锄头文库上搜索。
1、1计算机语言与程序设计谌 卫 军清华大学软件学院Introduction to Computer Programming2第八章 递归算法1 13 32 2基本概念基于回溯策略的递归基于分治策略的递归 3从前有座山，山上有座庙，庙里有一个老和尚 和一个小和尚，老和尚正在给小和尚讲故事。 讲的是什么故事呢？他说，从前4Recursion- See “Recursion“. “In order to understand recursion, one must first understand recursion.“ 5C语言允许嵌套地调用函数，也就是说，在调用 一个函数的过程中，又去调用另一个函
2、数。函数的嵌套调用void main( ) study_english ( ); void study_english( ) reading( );listening( );writing( ) void listening( ) 6函数的嵌套调用有一个特例，即递归调用，也就 是说，在调用一个函数的过程中，又出现了直接 或间接地去调用该函数本身。void tell_story( ) int old_monk, young_monk;tell_story ( ); / tell_story 函数的递归调用 函数的递归调用?7void tell_story( ) static int old_mo
3、nk, young_monk;old_monk = old_monk + 1; / 年龄龄大了一岁岁 young_monk = young_monk + 1;if(old_monk R) return(-1);mid = (L + R)/2;if(x = bmid) return mid;else if(x void move(int n, char L, char M, char R);void main( ) int n;printf(“请输请输 入一个整数：“);scanf(“%d“, move(n, A, B, C); 42/ L: Left post, M: Middle post,
4、 R: Right post void move(int n, char L, char M, char R) if(n = 1) printf(“move #1 from %c to %cn“, L, R);elsemove(n-1, L, R, M);printf(“move #%d from %c to %cn“, n, L, R);move(n-1, M, L, R); 43请输请输 入一个整数：3 move #1 from A to C move #2 from A to B move #1 from C to B move #3 from A to C move #1 from B
5、 to A move #2 from B to C move #1 from A to C一次运行结果448.2.5 青蛙过河一条小溪尺寸不大，青蛙可以从左岸跳到右岸，在左岸有一 石柱L，面积只容得下一只青蛙落脚，同样右岸也有一石柱R， 面积也只容得下一只青蛙落脚。有一队青蛙从尺寸上一个比一个 小。我们将青蛙从小到大，用1，2，n编号。规定初始时这 队青蛙只能趴在左岸的石头L上，按编号一个落一个，小的落在 大的上面。不允许大的在小的上面。在小溪中有S根石柱，有y片 荷叶，规定溪中的柱子上允许一只青蛙落脚，如有多只同样要求 按编号一个落一个，大的在下，小的在上，而且必须编号相邻。 对于荷叶只允许
6、一只青蛙落脚，不允许多只在其上。对于右岸的 石柱R，与左岸的石柱L一样允许多个青蛙落脚，但须一个落一 个，小的在上，大的在下，且编号相邻。当青蛙从左岸的L上跳 走后就不允许再跳回来；同样，从左岸L上跳至右岸R，或从溪 中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开。问在已 知溪中有S根石柱和y片荷叶的情况下，最多能跳过多少只青蛙？45这题看起来较难，但是如果我们认真分析，理 出思路，就可化难为易。思路：1、简化问题，探索规律。先从个别再到一般，要善 于对多个因素作分解，孤立出一个一个因素来分 析，化难为易。2. 定义函数Jump ( S ,y ) 最多可跳过河的青蛙数其中：S 河中柱子数y
7、荷叶数462说明：河中有一片荷叶，可以过两只青蛙，起始时 L 上有 两只青蛙，1# 在 2# 上面。第一步：1# 跳到荷叶上；第二步：2# 从 L 直接跳至 R 上；第三步：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 上，第四步：2# 从叶 2 跳至 R 上，第
8、五步：1# 从叶 1 跳至 R 上，采用归纳法：Jump ( 0 , y ) = 当 y = 2 时时，Jump ( 0 , 2 ) = ；y+1；意思是：在河中没有石柱的情况 下，过河的青蛙数仅取决于荷叶 数，数目是荷叶数+1。48再看Jump( S, y ) 先看一个最简单情况： S = 1，y = 1 。从图上看出需要 步，跳过 只青蛙。 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；49对于S = 1，y = 1
9、的情形，从另外一个角度来分析若没有石柱S，最多可过 y+1 = 2 只青蛙。有了石柱S后，最多可过 2*2 = 4 只青蛙。步骤1： 1#和2# 从 L S；步骤2： 3#和4# 从 L R；步骤3： 1#和2# 从 S R；YSLR: 1#, 2#: 3#, 4#: 1#, 2#YYY50对于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；YSLR: 前y+1只: 后y+1只: 前y+1只YYY51对于S = 2，y 1的情形若
10、只有石柱S1，最多可过 2*(y+1) 只青蛙。有了石柱S2后，最多可过 只青蛙。YS1LR4*(y+1)S2步骤1： 前2*(y+1)只 从 L S2；步骤2： 后2*(y+1)只 从 L R；步骤3： 前2*(y+1)只 从 S2 R；Y,S1Y,S1Y,S152采用归纳法，可得出如下的递归形式：Jump(S, y) = 2 * Jump(S-1, y)；意思是：先让一半的青蛙利用y片荷叶和 S-1根石柱，落在河中剩下的那根石柱上 ；然后让另一半的青蛙利用y片荷叶和S-1 根石柱，落在右岸的R上面；最后再让先 前的一半青蛙，利用y片荷叶和S-1根石柱 ，落在右岸的R上面。递归边界：Jump
11、(0, y) = y + 153void main( ) int S, y;printf(“请输请输 入石柱和荷叶的数目：“);scanf(“%d %d“, 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、在数组a中，有一段待排序的数据，下标从l到r。2、取al放在变量value中，通过由右、左两边对 value的取值的比较，为value选择应该排定的位 置。这时要将比va
12、lue大的数放右边，比它小的数 放左边。当value到达最终位置后（如下标m）， 由它划分了左右两个集合lm-1、m+1r。 然后转第1步，再用相同的思路分别去处理左集合 和右集合。55令 qsort(l, r)表示将数组元素从下标为 l 到 下标为 r 的共 r-l+1 个元素进行从小到大的 快速排序。目标：1、让 value = al2、将 value 放在 am中，l m r3、使 al, al+1, , am-1 i, 表明这一步不可能走 j 级台阶, 函数返回；否则，转第三步；第三步：这一步走 j 级台阶，即 paces = j;如果 i - j = 0，说明已经到达地面了，也就是
13、已经找到一种方案了，把它显示出来；否则的话，接着走下一步，TryStep(i-j, s+1)；第四步： j = j +1，如果 j 3，转第二步；否则函数结束。 能否用分治策略？808.3.3 八皇后问题在88的棋盘上，放置8个皇后（棋子），使两两之 间互不攻击。所谓互不攻击是说任何两个皇后都要 满足：（1）不在棋盘的同一行； （2）不在棋盘的同一列； （3）不在棋盘的同一对角线上。因此可以推论出，棋盘共有8行，故至多有8个皇后， 即每一行有且仅有一个皇后。这8个皇后中的每一个 应该摆放在哪一列上是解该题的任务。8182数据的定义（1）： i 第i行（个）皇后，1 i 8； j 第j列， 1
14、j 8； Queeni 第i行皇后所在的列； Columnj 第j列是否安全，0, 1；831 2 3 4 5 6 7 81234567884数据的定义（2）： Down-77 记录每一条从上到下的对角线，是否安全，0,1 Up216记录每一条从下到上的对角角线，是否安全，0,185利用以上的数据定义： 当我们需要在棋盘的( i, j ) 位置摆放一个皇 后的时候，可以通过Column数组、Down 数组和Up数组的相应元素，来判断该位置 是否安全； 当我们已经在棋盘的( i, j ) 位置摆放了一个 皇后以后，就应该去修改Column数组、 Down数组和Up数组的相应元素，把相应的 列和对角线设置为不安全。86void TryQueen( int i );int Queen9 = 0 ; int Column9 = 0 ; int Down15 = 0 ; int Up15 = 0 ;void main( ) TryQueen( 1 ); 87void TryQueen(int i)/ 摆放第 i 行的皇后 int j, k;for(j = 1; j ，即第X行第Y列，在摆放八 个皇后时，要求皇后间不能互相攻击且不能 被国王攻击。国王的攻击范围如下图所示：思考题：对题目做如下的修改902.先输入某一个皇后所在的位置，即 第X行第
