基本概念题: 6-1什么叫递归? 6-2适宜于用递归算法求解的问题的充分必要条件是什么?什么叫递归出口? 6-3阶乘问题的循环结构算法和递归结构算法哪个的时间效率好,为什么? 6-4非递归函数调用时系统要保存哪些信息?递归函数调用时系统要保存哪些信息?系 统怎样保存递归函数调用时的信息? 6-5什么叫运行时栈?什么叫运行时栈中的活动记录? 6-6叙述递归算法的执行过程。 复杂概念题: 6-7推导求解n阶汉诺塔问题要执行的移动操作(即算法中pint(函数的调用)次数 6-8我们讨论过的折半查找函数设计如下 int BSearch(elemtype a[, elemtype x, int low, int high) It mid: if(low>high) return -1 if(x = a[mid]) return mid if(x< a[mid]) return (BSearch(a, x, low, mid-1)) else return(BSearch(a, x, mid+1, high)) 讨论如果把上述折半查找函数中最后两语句改为如下形式能否实现算法的设计要求,为什 if(x< amid] BSearch(a, x, low, mid-1) BSearch(a, x, mid+1, high 算法设计题 6-9要求: (1)写出求1,2,3,n的n个数累加的递推定义式 (2)编写求1,2,3,,n的n个数累加的递归算法,假设n个数存放在数组a中。 6-10要求 (1)写出求1,2,3, n的n个数连乘的递推定义式 (2)编写求1,2,3 n的n个数连乘的递归算法,假设n个数存放在数组a中 6-11设a是有n个整数类型数据元素的数组,试编写求a中最大值的递归算法 6-12设计输出如下形式数值的算法 要求 (1)把算法设计成递归结构的算法; (2)画出上述递归算法的调用执行过程
基本概念题： 6-1 什么叫递归？ 6-2 适宜于用递归算法求解的问题的充分必要条件是什么？什么叫递归出口？ 6-3 阶乘问题的循环结构算法和递归结构算法哪个的时间效率好，为什么？ 6-4 非递归函数调用时系统要保存哪些信息？递归函数调用时系统要保存哪些信息？系 统怎样保存递归函数调用时的信息？ 6-5 什么叫运行时栈？什么叫运行时栈中的活动记录？ 6-6 叙述递归算法的执行过程。 复杂概念题： 6-7 推导求解 n 阶汉诺塔问题要执行的移动操作（即算法中 printf()函数的调用）次数。 6-8 我们讨论过的折半查找函数设计如下： int BSearch(elemtype a[], elemtype x, int low, int high) { int mid; if(low>high) return -1; mid =(low+high)/2; if(x == a[mid]) return mid; if(x < a[mid]) return (BSearch(a,x,low,mid-1)); else return (BSearch(a,x,mid+1,high)); } 讨论如果把上述折半查找函数中最后两语句改为如下形式能否实现算法的设计要求，为什 么？ if(x < a[mid]) BSearch(a,x,low,mid-1); else BSearch(a,x,mid+1,high); 算法设计题： 6-9 要求： （1）写出求 1,2,3,......,n 的 n 个数累加的递推定义式； （2）编写求 1,2,3,......,n 的 n 个数累加的递归算法，假设 n 个数存放在数组 a 中。 6-10 要求： （1）写出求 1,2,3,......,n 的 n 个数连乘的递推定义式； （2）编写求 1,2,3,......,n 的 n 个数连乘的递归算法，假设 n 个数存放在数组 a 中。 6-11 设 a 是有 n 个整数类型数据元素的数组，试编写求 a 中最大值的递归算法。 6-12 设计输出如下形式数值的算法。 1 2 2 3 3 3 ...... n n n ... n 要求： （1）把算法设计成递归结构的算法； （2）画出上述递归算法的调用执行过程；
(3)把算法设计成循环结构 *6-13背包问题。设有一个背包可以放入物品的重量为s,现有n件物品,重量分别为 w0],w[1]-…,n-1]l问题是能否从这n件物品中选择若干件放入此背包中使得放入的重量之 和正好等于s。如果存在一种符合上述要求的选择,则称此背包问题有解;否则称此背包问 题无解。试用分而治之的算法设计方法设计求解背包问题的函数 提示:此背包问题的递推定义如下(其中True表示有解, False表示无解): True s=0 此时问题有解 False s0且n0且n≥1所选物品不包括{n-1时 KNAP(s-{m-1n-1)s>0且n≥1所选物品包括n-1时 上机实习题 6-14折半査找问题。折半査找问题的描述见61节,折半查找问题的递归算法见例6-2 要求: (1)设计折半査找问题的循环结构算法 (2)设计一个查找成功的例子和一个查找不成功的例子,并设计测试主程序 *(3)设计一个包含10000个数据元素的查找成功的例子,然后分别调用循环结构的查 找算法和递归结构的査找算法,并测试出两种算法在计算机上的实际运行时间。 *6-15八皇后问题。设在初始状态下在国际象棋棋盘上没有任何棋子(这里的棋子指皇 后棋子)。然后顺序在第1行,第2行,…,第8行上布放棋子。在每一行中共有8个可选 择位置,但在任一个时刻棋盘的合法布局都必须满足3个限制条件:1)任意两个棋子不得 放在同一行上:2)任意两个棋子不得放在同一列上:3)任意两个棋子不得放在同一正斜线 和反斜线上 (1)试用回溯法的算法设计方法编写一个函数,求解并输出此问题的一个合法布局 (2)试用回溯法的算法设计方法编写一个函数,求解并输出此问题的所有合法布局 提示:在第ⅰ行布放棋子时,从第1列到第8列逐列考察。当在第ⅰ行第j列布放棋子 时,需要考察布放棋子后在行方向、列方向、正斜线方向和反斜线方向上的布局状态是否合 法,若该棋子布放合法,再递归求解在第计1行布放棋子:若该棋子布放不合法,移去这个 棋子,恢复布放该棋子前的状态,然后再试探在第i行第j+1列布放棋子
（3）把算法设计成循环结构。 *6-13 背包问题。设有一个背包可以放入物品的重量为 s，现有 n 件物品，重量分别为 w[0],w[1],...,[n-1]。问题是能否从这 n 件物品中选择若干件放入此背包中使得放入的重量之 和正好等于 s。如果存在一种符合上述要求的选择，则称此背包问题有解；否则称此背包问 题无解。试用分而治之的算法设计方法设计求解背包问题的函数。 提示：此背包问题的递推定义如下（其中 True 表示有解，False 表示无解）： 上机实习题： 6-14 折半查找问题。折半查找问题的描述见 6.1 节，折半查找问题的递归算法见例 6-2。 要求： （1）设计折半查找问题的循环结构算法； （2）设计一个查找成功的例子和一个查找不成功的例子，并设计测试主程序； *（3）设计一个包含 10000 个数据元素的查找成功的例子，然后分别调用循环结构的查 找算法和递归结构的查找算法，并测试出两种算法在计算机上的实际运行时间。 *6-15 八皇后问题。设在初始状态下在国际象棋棋盘上没有任何棋子（这里的棋子指皇 后棋子）。然后顺序在第 1 行，第 2 行，…，第 8 行上布放棋子。在每一行中共有 8 个可选 择位置，但在任一个时刻棋盘的合法布局都必须满足 3 个限制条件：1）任意两个棋子不得 放在同一行上；2）任意两个棋子不得放在同一列上；3）任意两个棋子不得放在同一正斜线 和反斜线上。 （1）试用回溯法的算法设计方法编写一个函数，求解并输出此问题的一个合法布局； （2）试用回溯法的算法设计方法编写一个函数，求解并输出此问题的所有合法布局。 提示：在第 i 行布放棋子时，从第 1 列到第 8 列逐列考察。当在第 i 行第 j 列布放棋子 时，需要考察布放棋子后在行方向、列方向、正斜线方向和反斜线方向上的布局状态是否合 法，若该棋子布放合法，再递归求解在第 i+1 行布放棋子；若该棋子布放不合法，移去这个 棋子，恢复布放该棋子前的状态，然后再试探在第 i 行第 j+1 列布放棋子。 − − − − − − = = 且 所选物品包括 时 且 所选物品不包括 时 且 物品件数不能为负数 总重量不能为负数 此时问题有解 ( [ 1], 1) 0 1 [ 1] ( , 1) 0 1 [ 1] 0 1 0 0 ( , ) KNAP s w n n s n w n KNAP s n s n w n False s n False s True s KNAP s n