c语言_递归算法.ppt

计算机语言与程序设计 谌卫军 清华大学软件学院 IntroductiontoComputerProgramming 第八章递归算法 1 3 2 基本概念 基于回溯策略的递归 基于分治策略的递归 从前有座山 山上有座庙 庙里有一个老和尚和一个小和尚 老和尚正在给小和尚讲故事 讲的是什么故事呢 他说 从前 Recursion See Recursion Inordertounderstandrecursion onemustfirstunderstandrecursion C语言允许嵌套地调用函数 也就是说 在调用一个函数的过程中 又去调用另一个函数 函数的嵌套调用 voidmain study english voidstudy english reading listening writing voidlistening 函数的嵌套调用有一个特例 即递归调用 也就是说 在调用一个函数的过程中 又出现了直接或间接地去调用该函数本身 voidtell story intold monk young monk tell story tell story函数的递归调用 函数的递归调用 voidtell story staticintold monk young monk old monk old monk 1 年龄大了一岁young monk young monk 1 if old monk 60 递归形式tell story elseprintf 对不起 已退休 递归边界 在语法上 简单 递归即为普通的函数调用 在算法上 难 如何找到递归形式 如何找到递归边界 如何编写递归程序 递归算法的类型 递归算法可以分为两种类型 基于分治策略的递归算法 基于回溯策略的递归算法 第八章递归算法 1 3 2 基本概念 基于回溯策略的递归 基于分治策略的递归 分而治之 divide and conquer 的算法设计思想 Divide 把问题划分为若干个子问题 Conquer 以同样的方式分别去处理各个子问题 Combine 把各个子问题的处理结果综合起来 形成最终的处理结果 8 2 1分而治之 玛特露什卡 调用 调用 调用 调用 调用 调用 如何编写基于分治策略的递归程序 在算法分析上 要建立分治递归的思维方式 在编程实现上 要建立递归信心 Totursttherecursion JerryCain stanford 如何建立分治递归的思维方式 基本原则 目标驱动 计算n n n n 1 且1 1 fact 3 fact 2 fact 1 voidmain intn printf 请输入一个整数 scanf d 请输入一个整数 33 6 调用和返回的递归示意图 如何建立递归信心 函数的递归调用到底是如何进行的呢 在递归调用时 执行的是不是相同的代码 访问的是不是相同的数据 如果是的话 那么大家会不会相互干扰 相互妨碍 voidmain intm printf 请输入一个整数 scanf d 8 2 2寻找最大值 问题描述 给定一个整型数组a 找出其中的最大值 如何设计相应的递归算法 如何来设计相应的递归算法 目标 max a 0 a 1 a n 1 可分解为 max a 0 max a 1 a n 1 另外已知max x x这就是递归算法的递归形式和递归边界 据此可以编写出相应的递归函数 intMax inta intfirst intn intmax if first n 1 returna first max Max a first 1 n if max a first returna first elsereturnmax Max a 0 n 8 2 3折半查找法 问题描述 查找 Searching 根据给定的某个值 在一组数据 尤其是一个数组 当中 确定有没有出现相同取值的数据元素 顺序查找 折半查找 前提 数据是有序排列的 基本思路 将目标值与数组的中间元素进行比较 若相等 查找成功 否则根据比较的结果将查找范围缩小一半 然后重复此过程 请问 4565926是否在此列表当中 请问 4565926是否在此列表当中 数组正中间的元素 请问 4565926是否在此列表当中 不予考虑 请问 4565926是否在此列表当中 正中间的元素 请问 4565926是否在此列表当中 正中间的元素 不予考虑 4565925 voidmain intb 05 13 19 21 37 56 64 75 80 88 92 intx 21 printf x位于数组的第 d个元素 n bsearch b x 0 10 如何用递归来实现 函数原型 intbsearch intb intx intL intR 递归的形式 递归的边界 问题分析 intbsearch intb intx intL intR intmid if L R return 1 mid L R 2 if x b mid returnmid elseif x b mid returnbsearch b x L mid 1 elsereturnbsearch b x mid 1 R 8 2 4汉诺 Hanoi 塔问题 相传在古印度Bramah庙中 有位僧人整天把三根柱子上的金盘倒来倒去 原来他是想把64个一个比一个小的金盘从一根柱子上移到另一根柱子上去 移动过程中遵守以下规则 每次只允许移动一只盘 且大盘不得落在小盘上 简单吗 若每秒移动一只盘子 需5800亿年 A B C 怎样编写这种程序 思路上还是先从最简单的情况分析起 搬一搬看 慢慢理出思路 1 在A柱上只有一只盘子 假定盘号为1 这时只需将该盘直接从A搬至C 记为movefromAtoC A B C 1 2 在A柱上有二只盘子 1为小盘2为大盘 分三步进行 A B C 2 1 movefromAtoB movefromAtoC moveformBtoC 3 在A柱上有3只盘子 从小到大分别为1号 2号 3号 怎么移 2 1 3 分七步 分三步进行 move2discsfromAtoBusingC movefromAtoC move2discsfromBtoCusingA 3 4 在A柱上有n个盘子 从小到大分别为1号 2号 3号 n号 第1步 将1号 2号 n 1号盘作为一个整体 在C的帮助下 从A移至B 第2步 将n号盘从A移至C 第3步 再将1号 2号 n 1号盘作为一个整体 在A的帮助下 从B移至C 这三步记为 moven 1discsfromAtoBusingC move1discsfromAtoC moven 1discsfromBtoCusingA 递归形式 定义函数move intn charL charM charR 表示movendiscsfromLtoRusingM 如果n 1 即表示movefromLtoR includevoidmove intn charL charM charR voidmain intn printf 请输入一个整数 scanf d L Leftpost M Middlepost R Rightpostvoidmove intn charL charM charR if n 1 printf move 1from cto c n L R else move n 1 L R M printf move dfrom cto c n n L R move n 1 M L R 请输入一个整数 3move 1fromAtoCmove 2fromAtoBmove 1fromCtoBmove 3fromAtoCmove 1fromBtoAmove 2fromBtoCmove 1fromAtoC 一次运行结果 8 2 5青蛙过河 一条小溪尺寸不大 青蛙可以从左岸跳到右岸 在左岸有一石柱L 面积只容得下一只青蛙落脚 同样右岸也有一石柱R 面积也只容得下一只青蛙落脚 有一队青蛙从尺寸上一个比一个小 我们将青蛙从小到大 用1 2 n编号 规定初始时这队青蛙只能趴在左岸的石头L上 按编号一个落一个 小的落在大的上面 不允许大的在小的上面 在小溪中有S根石柱 有y片荷叶 规定溪中的柱子上允许一只青蛙落脚 如有多只同样要求按编号一个落一个 大的在下 小的在上 而且必须编号相邻 对于荷叶只允许一只青蛙落脚 不允许多只在其上 对于右岸的石柱R 与左岸的石柱L一样允许多个青蛙落脚 但须一个落一个 小的在上 大的在下 且编号相邻 当青蛙从左岸的L上跳走后就不允许再跳回来 同样 从左岸L上跳至右岸R 或从溪中荷叶或溪中石柱跳至右岸R上的青蛙也不允许再离开 问在已知溪中有S根石柱和y片荷叶的情况下 最多能跳过多少只青蛙 这题看起来较难 但是如果我们认真分析 理出思路 就可化难为易 思路 1 简化问题 探索规律 先从个别再到一般 要善于对多个因素作分解 孤立出一个一个因素来分析 化难为易 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只青蛙 起始时 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 从图上看出需要步 跳过只青蛙 941 青蛙从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 从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 1只 前y 1只 Y Y Y 对于S 2 y 1的情形若只有石柱S1 最多可过2 y 1 只青蛙 有了石柱S2后 最多可过只青蛙 Y S1 L R 4 y 1 S2 采用归纳法 可得出如下的递归形式 Jump S y 2 Jump S 1 y 意思是 先让一半的青蛙利用y片荷叶和S 1根石柱 落在河中剩下的那根石柱上 然后让另一半的青蛙利用y片荷叶和S 1根石柱 落在右岸的R上面 最后再让先前的一半青蛙 利用y片荷叶和S 1根石柱 落在右岸的R上面 递归边界 Jump 0 y y 1 voidmain intS y printf 请输入石柱和荷叶的数目 scanf d d 8 2 6快速排序 快速排序的基本思路 1 在数组a中 有一段待排序的数据 下标从l到r 2 取a l 放在变量value中 通过由右 左两边对value的取值的比较 为value选择应该排定的位置 这时要将比value大的数放右边 比它小的数放左边 当value到达最终位置后 如下标m 由它划分了左右两个集合 l m 1 m 1 r 然后转第1步 再用相同的思路分别去处理左集合和右集合 令qsort l r 表示将数组元素从下标为l到下标为r的共r l 1个元素进行从小到大的快速排序 目标 1 让value a l 2 将value放在a m 中 l m r3 使a l a l 1 a m 1 a m 4 使a m a m 1 a m 2 a r 例子 数组a当中有7个元素等待排序 l r 首先 让value a l a 0 5 value 5 a 0 1 2 3 4 5 6 下标 第二步 从r 6开始 将a r 与value进行比较 若a r value 则r 继续比较 否则 a l a r l value 5 a 0 1 2 3 4 5 6 下标 4 第三步 从l 1开始 将a l 与value进行比较 若a l value 则l 继续比较 否则 a r a l r value 5 a 0 1 2 3 4 5 6 下标 6 又回到第二步 从r 5开始 将a r 与value进行比较 若a r value 则r 继续比较 否则a l a r l value 5 a 0 1 2 3 4 5 6 下标 3 又回到第三步 从l 3开始 将a l 与value进行比较 若a l value 则l 继续比较 否则 a r a l r value 5 a 0 1 2 3 4 5 6 下标 7 现在l r 已经找到了value的正确位置 把value中的值放回到数组当中 value 5 a 0 1 2 3 4 5 6 下标 5 下面的任务 用刚才介绍的方法 对5左 右两侧的两段数据 分别进行排序 a 0 1 2 3 4 5 6 下标 最后的结果 a 0 1 2 3 4 5 6 下标 具体实现 几重循环语句 参考程序 略 第八章递归算法 1 3 2 基本概念 基于回溯策略的递归 基于分治策略的递归 在程序设计当中 有相当一类求一组解 或求全部解或求最优解的问题 不是根据某种确定的计算法则 而是利用试探和回溯 Backtracking 的搜索技术求解 回溯法也是设计递归算法的一种重要方法 它的求解过程实质上是一个先序遍历一棵 状态树 的过程 只不过这棵树不是预先建立的 而是隐含在遍历的过程当中 8 3 1分书问题 有五本书 它们的编号分别为1 2 3 4 5 现准备分给A B C D E五个人 每个人的阅读兴趣用一个二维数组来加以描述 希望编写一个程序 输出所有的分书方案 让人人皆大欢喜 假定这5个人对这5本书的阅读兴趣如下表 12345ABCDE 人 书 解题思路 1 定义一个整型的二维数组 将上表中的阅读喜好用初始化的方法赋给这个二维数组 可定义 intLike 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 定义一个整型一维数组BookFlag 6 用来记录书是否已被选用 用后五个下标作为五本书的标号 被选用的元素值为1 未被选用的值为0 初始化皆为0 intBookFlag 6 0 3 定义一个整型一维数组BookTaken 6 用来记录每一个人选用了哪一本书 用数组元素的下标来作为人的标号 用数组元素的值来表示书号 如果某个人还没有选好书 则相应的元素值为0 初始化时 所有的元素值均为0 intBookTaken 6 0 4 循环变量i表示人 j表示书 i j 1 2 3 4 5 一种方法 枚举法 把所有可能出现的分书方案都枚举出来 然后逐一判断它们是否满足条件 即是否使得每个人都能够得到他所喜欢的书 缺点 计算量太大 如何抽取出递归形式 voidperson inti intLike 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 intBookFlag 6 0 intBookTaken 6 0 voidmain person 1 voidperson inti 尝试给第i个人分书 intj k for j 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 给第i 1个人分书 BookTaken i 0 回溯 把这一次分得的书退回BookFlag j 0 8 3 2下楼问题 从楼上走到楼下共有h个台阶 每一步有三种走法 走一个台阶 走二个台阶 走三个台阶 问可以走出多少种方案 希望用递归思想来编程 数据的定义 j 1 2 3 表示在每一步可以试着走的台阶数s 表示步数i 表示当前的高度 pace s 保存第s步走过的台阶数 基本思路 让i先取h值 然后在下楼时 试着一步一步地走 从高到低 每走一步i的值就会减去这一步所走的台阶数j 即i h 初值 以后i i j j 1 2 3 当i 0时 说明已走到楼下 每一步都要试j的三种不同取值 即或者为1 或者为2 或者为3 这时可用for循环结构 每一步走法都用相同的策略 故可以用递归算法 定义TryStep i s 站在第i级台阶上往下试走第s步的过程 如何实现 第一步 j 1 第二步 如果j i 表明这一步不可能走j级台阶 函数返回 否则 转第三步 第三步 这一步走j级台阶 即pace s j 如果i j 0 说明已经到达地面了 也就是已经找到一种方案了 把它显示出来 否则的话 接着走下一步 TryStep i j s 1 第四步 j j 1 如果j 3 转第二步 否则函数结束 能否用分治策略 8 3 3八皇后问题 在8 8的棋盘上 放置8个皇后 棋子 使两两之间互不攻击 所谓互不攻击是说任何两个皇后都要满足 1 不在棋盘的同一行 2 不在棋盘的同一列 3 不在棋盘的同一对角线上 因此可以推论出 棋盘共有8行 故至多有8个皇后 即每一行有且仅有一个皇后 这8个皇后中的每一个应该摆放在哪一列上是解该题的任务 数据的定义 1 i 第i行 个 皇后 1 i 8 j 第j列 1 j 8 Queen i 第i行皇后所在的列 Column j 第j列是否安全 0 1 12345678 1 2 3 4 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数组的相应元素 把相应的列和对角线设置为不安全 voidTryQueen inti intQueen 9 0 intColumn 9 0 intDown 15 0 intUp 15 0 voidmain TryQueen 1 voidTryQueen inti 摆放第i行的皇后 intj k for j 1 j 8 j 尝试把该皇后放在每一列 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 elseTryQueen i 1 摆放第i 1行的皇后Queen i 0 回溯 把该皇后从第j列拿起Column j 0 Down i j 7 0 Up i j 2 0 共92组解 部分答案如下 方案1 15863724方案2 16837425方案3 17468253方案4 17582463方案5 24683175方案6 25713864方案7 25741863方案8 26174835方案9 26831475方案10 27368514 假设在棋盘上事先已经摆放了一个国王 位置为 即第X行第Y列 在摆放八个皇后时 要求皇后间不能互相攻击且不能被国王攻击 国王的攻击范围如下图所示 思考题 对题目做如下的修改 先输入某一个皇后所在的位置 即第X行第Y列 在此情形下 如何摆放其余的7个皇后 要求找到所有解决方案 8 3 4过河问题 问题描述 M条狼和N条狗 N M 渡船过河 从河西到河东 在每次航行中 该船最多能容纳2只动物 且最少需搭载1只动物 安全限制 无论在河东 河西还是船上 狗的数量不能小于狼的数量 请问 能否找到一种方案 使所有动物都能顺利过河 如果能 移动的步骤是什么 如何描述系统的当前状态 位置 河西岸 河东岸 河 对象 船 狼 狗 问题分析 三元组 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 问题实质 在一个有向图中寻找一条路径 状态转换 如何从一个结点跳转到另一个结点 状态树 问题分析 如何避免访问重复的结点 如何用简练的语句实现状态的转换 如何将5种情形归纳为同一种形式 技术难点 include defineMAX M20 defineMAX N20intM N structStatus intW D B steps 1000 ints 0 num 0 intflags MAX M MAX N 2 0 voidCrossRiver intW intD intB intIsValid intw intd intb voidmain scanf d d if B 0 f 1 elsef 1 for j 1 j 5 j switch j case1 w W f 1 d D break case2 w W f 2 d D break case3 d D f 1 w W break case4 d D f 2 w W break case5 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 intIsValid intw intd intb if wM return0 if dN return0 if flags w d b 1 return0 if d 0 22Solutions1 220021120101200001Solutions2 220021120101110001 Solutions3 220111120101200001Solutions4 220111120101110001 8 3 5排列问题 n个对象的一个排列 就是把这n个不同的对象放在同一行上的一种安排 例如 对于三个对象a b c 总共有6个排列 abcacbbacbcacabcban个对象的排列个数就是n 如何生成排列 基于分治策略的递归算法 假设这n个对象为1 2 3 n 对于前n 1个元素的每一个排列a1a2 an 1 1 ai n 1 通过在所有可能的位置上插入数字n 来形成n个所求的排列 即 na1a2 an 1a1na2 an 1 a1a2 nan 1a1a2 an 1n 例如 生成1 2 3的所有排列 permutation 3 permutation 2 permutation 1 permutation 1 1 permutation 2 21 12 permutation 3 321 231 213 312 132 123 基于回溯策略的递归算法 基本思路 每一个排列的长度为N 对这N个不同的位置 按照顺序逐一地枚举所有可能出现的数字 定义一维数组NumFlag N 1 用来记录1 N之间的每一个数字是否已被使用 1表示已使用