算法设计与分析(第2版)-王红梅-胡明-习题答案

第 1 页 共 41 页 算法设计与分析算法设计与分析 第第 2 2 版版 王红梅王红梅 胡明胡明 习题习题 答案答案 习题习题 1 1 图论诞生于七桥问题 出生于瑞士的伟大数学家欧拉 图论诞生于七桥问题 出生于瑞士的伟大数学家欧拉 Leonhard Euler 1707 1783 提出并解决了该问题 七桥问题是这样 提出并解决了该问题 七桥问题是这样 描述的 一个人是否能在一次步行中穿越哥尼描述的 一个人是否能在一次步行中穿越哥尼 斯堡 现在叫加里宁格勒 在波罗的海南岸 斯堡 现在叫加里宁格勒 在波罗的海南岸 城中全部的七座桥后回到起点 且每座桥只经城中全部的七座桥后回到起点 且每座桥只经 过一次 图过一次 图 1 7 是这条河以及河上的两个岛和是这条河以及河上的两个岛和 七座桥的草图 请将该问题的数据模型抽象出七座桥的草图 请将该问题的数据模型抽象出 来 并判断此问题是否有解 来 并判断此问题是否有解 七桥问题属于一笔画问题 输入 一个起点 输出 相同的点 1 一次步行 2 经过七座桥 且每次只经历过一次 3 回到起点 该问题无解 能一笔画的图形只有两类 一类是所有的点都是偶点 另一类是只有二个 奇点的图形 2 在欧几里德提出的欧几里德算法中 即 在欧几里德提出的欧几里德算法中 即最初的欧几里德算法最初的欧几里德算法 用的不是除法而是减 用的不是除法而是减 法 请用伪代码描述这个版本的欧几里德算法法 请用伪代码描述这个版本的欧几里德算法 1 r m n 2 循环直到 r 0 2 1 m n 2 2 n r 2 3 r m n 3 输出 m 3 设计算法求数组中相差最小的两个元素 称为最接近数 的差 要求分别给出伪代 设计算法求数组中相差最小的两个元素 称为最接近数 的差 要求分别给出伪代 码和码和 C 描述 描述 采用分治法 对数组先进行快速排序 在依次比较相邻的差 图 1 7 七桥问题 北区 东区 岛区 南区 第 2 页 共 41 页 include using namespace std int partions int b int low int high int prvotkey b low b 0 b low while low high while low prvotkey high b low b high while low high b high b low b low b 0 return low void qsort int l int low int high int prvotloc if low high prvotloc partions l low high 将第一次排序的结果作为枢轴 qsort l low prvotloc 1 递归调用排序 由 low 到 prvotloc 1 qsort l prvotloc 1 high 递归调用排序 由 prvotloc 1 到 high void quicksort int l int n qsort l 1 n 第一个作为枢轴 从第一个排到第 n 个 int main int a 11 0 2 32 43 23 45 36 57 14 27 39 int value 0 将最小差的值赋值给 value for int b 1 b 11 b cout a b 第 3 页 共 41 页 cout endl quicksort a 11 for int i 0 i 9 i if a i 1 a i a i 2 a i 1 value a i 1 a i else value a i 2 a i 1 cout value endl return 0 4 设数组设数组 a n 中的元素均不相等 设计算法找出中的元素均不相等 设计算法找出 a n 中一个既不是最大也不是最小中一个既不是最大也不是最小 的元素 并说明最坏情况下的比较次数 要求分别给出伪代码和的元素 并说明最坏情况下的比较次数 要求分别给出伪代码和 C 描述 描述 include using namespace std int main int a 1 2 3 6 4 9 0 int mid value 0 将 既不是最大也不是最小的元素 的值赋值给它 for int i 0 i 4 i if a i 1 a i cout mid value endl break else if a i 1 a i 2 mid value a i 1 cout mid value endl break for 第 4 页 共 41 页 return 0 5 编写程序 求编写程序 求 n 至少为多大时 至少为多大时 n 个个 1 组成的整数能被组成的整数能被 2013 整除 整除 include using namespace std int main double value 0 for int n 1 n 10000 n value value 10 1 if value 2013 0 cout n 至少为 n endl break for return 0 6 计算计算 值的问题能精确求解吗 编写程序 求解满足给定精度要求的值的问题能精确求解吗 编写程序 求解满足给定精度要求的 值值 include using namespace std int main double a b double arctan double x 声明 a 16 0 arctan 1 5 0 b 4 0 arctan 1 239 cout PI a b 1e 15 定义精度范围 f e i f 是每次 r 需要叠加的方程 r i 4 1 r f r f e e sqr e 每次乘于 x 的平方 i 2 i 每次加 2 while return r 7 圣经上说 神圣经上说 神 6 天创造天地万有 第天创造天地万有 第 7 日安歇 为什么是日安歇 为什么是 6 天呢 任何一个自然数天呢 任何一个自然数 的因数中都有的因数中都有 1 和它本身 所有小于它本身的因数称为这个数的真因数 如果一个自然数和它本身 所有小于它本身的因数称为这个数的真因数 如果一个自然数 的真因数之和等于它本身 这个自然数称为完美数 例如 的真因数之和等于它本身 这个自然数称为完美数 例如 6 1 2 3 因此 因此 6 是完美数 神是完美数 神 6 天创造世界 暗示着该创造是完美的 设计算法 判断给定的自然数是否是完美数天创造世界 暗示着该创造是完美的 设计算法 判断给定的自然数是否是完美数 include using namespace std int main int value k 1 cin value for int i 2 i value i while value i 0 k i k 为该自然数所有因子之和 value value i for if k value cout 该自然数是完美数 endl else cout 该自然数不是完美数 endl return 0 8 有有 4 个人打算过桥 这个桥每次最多只能有两个人同时通过 他们都在桥的某一端 个人打算过桥 这个桥每次最多只能有两个人同时通过 他们都在桥的某一端 第 6 页 共 41 页 并且是在晚上 过桥需要一只手电筒 而他们只有一只手电筒 这就意味着两个人过桥后并且是在晚上 过桥需要一只手电筒 而他们只有一只手电筒 这就意味着两个人过桥后 必须有一个人将手电筒带回来 每个人走路的速度是不同的 甲过桥要用必须有一个人将手电筒带回来 每个人走路的速度是不同的 甲过桥要用 1 分钟 乙过桥分钟 乙过桥 要用要用 2 分钟 丙过桥要用分钟 丙过桥要用 5 分钟 丁过桥要用分钟 丁过桥要用 10 分钟 显然 两个人走路的速度等于其中分钟 显然 两个人走路的速度等于其中 较慢那个人的速度 问题是他们全部过桥最少要用多长时间 较慢那个人的速度 问题是他们全部过桥最少要用多长时间 由于甲过桥时间最短 那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如 第一趟 甲 乙过桥且甲回来 第二趟 甲 丙过桥且甲回来 第一趟 甲 丁过桥 一共用时 19 小时 9 欧几里德游戏 开始的时候 白板上有两个不相等的正整数 两个玩家交替行动 欧几里德游戏 开始的时候 白板上有两个不相等的正整数 两个玩家交替行动 每次行动时 当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差 而且这每次行动时 当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差 而且这 个数字必须是新的 也就是说 和白板上的任何一个已有的数字都不相同 当一方再也写个数字必须是新的 也就是说 和白板上的任何一个已有的数字都不相同 当一方再也写 不出新数字时 他就输了 请问 你是选择先行动还是后行动 为什么 不出新数字时 他就输了 请问 你是选择先行动还是后行动 为什么 设最初两个数较大的为 a 较小的为 b 两个数的最大公约数为 factor 则最终能出现的数包括 factor factor 2 factor 3 factor a factor a 一 共 a factor 个 如果 a factor 是奇数 就选择先行动 否则就后行动 习题习题 2 1 如果 如果 T1 n O f n T2 n O g n 解答下列问题 解答下列问题 1 证明加法定理 证明加法定理 T1 n T2 n max O f n O g n 2 证明乘法定理 证明乘法定理 T1 n T2 n O f n O g n 3 举例说明在什么情况下应用加法定理和乘法定理 举例说明在什么情况下应用加法定理和乘法定理 1 2 3 比如在 for f n for g n 中应该用乘法定理 如果在 讲两个数组合并成一个数组时 应当用加法定理 2 考虑下面的算法 回答下列问题 算法完成什么功能 算法的基本语句是什么 基本 考虑下面的算法 回答下列问题 算法完成什么功能 算法的基本语句是什么 基本 1 int Stery int n int S 0 for int i 1 i n i S S i i return S 2 int Q int n if n 1 return 1 else return Q n 1 2 n 1 第 7 页 共 41 页 语句执行了多少次 算法的时间复杂性是多少 语句执行了多少次 算法的时间复杂性是多少 1 完成的是 1 n 的平方和 基本语句 s i i 执行了 n 次 时间复杂度 O n 2 2 完成的是 n 的平方 基本语句 return Q n 1 2 n 1 执行了 n 次 时间复杂度 O n 3 分析以下程序段中基本语句的执行次数是多少 要求列出计算公式 分析以下程序段中基本语句的执行次数是多少 要求列出计算公式 1 基本语句 2 i1 return 3 T n 1 2 int T int n if n 1 return 1 else if n 1 return 2 T n 3 n 1 for i 1 i n i if 2 i n for j 2 i j n j y y i j 2 m 0 for i 1 i n i for j 1 j 2 i j m m 1 第 8 页 共 41 页 5 求下列问题的平凡下界 并指出其下界是否紧密 求下列问题的平凡下界 并指出其下界是否紧密 1 求数组中的最大元素 求数组中的最大元素 2 判断邻接矩阵表示的无向图是不是完全图 判断邻接矩阵表示的无向图是不是完全图 3 确定数组中的元素是否都是惟一的 确定数组中的元素是否都是惟一的 4 生成一个具有 生成一个具有 n 个元素集合的所有子集个元素集合的所有子集 1 n 紧密 2 n n 3 logn n 先进行快排 然后进行比较查找 4 2 n 7 画出在三个数 画出在三个数 a b c 中求中值问题的判定树 中求中值问题的判定树 8 国际象棋是很久以前由一个印度人 国际象棋是很久以前由一个印度人 Shashi 发明的 当他把该发明献给国王时 国发明的 当他把该发明献给国王时 国 王很高兴 就许诺可以给这个发明人任何他想要的奖赏 王很高兴 就许诺可以给这个发明人任何他想要的奖赏 Shashi 要求以这种方式给他一些要求以这种方式给他一些 粮食 棋盘的第粮食 棋盘的第 1 个方格内只放个方格内只放 1 粒麦粒 第粒麦粒 第 2 格格 2 粒 第粒 第 3 格格 4 粒 第粒 第 4 格格 8 粒 粒 以此类推 直到 以此类推 直到 64 个方格全部放满 这个奖赏的最终结果会是什么样呢 个方格全部放满 这个奖赏的最终结果会是什么样呢 include using namespace std int main long double result 1 double j 1 for int i 1 i 64 i j j 2 result j j a b a b c 是 是是 否 否 否 a c b c b a cb c C b ab c a a c C a b a c b 否否是是 第 9 页 共 41 页 cout result endl return 0 习题习题 3 1 假设在文本假设在文本 ababcabccabccacbab 中查找模式中查找模式 abccac 写出分别采用 写出分别采用 BF 算法和算法和 KMP 算法的串匹配过算法的串匹配过 BF 算法 include using namespace std int BF char S char T int index 0 int i 0 j 0 while S i 0 j else index i index j 0 if T j 0 return index 1 else 第 10 页 共 41 页 return 0 int main char s1 19 ababcabccabccacbab char s2 7 abccac cout BF s1 s2 endl return 0 KMP 算法 include using namespace std void GetNext char T int next 求模式 T 的 next 值 int i j len next 0 1 for j 1 T j 0 j 依次求 next j for len j 1 len 1 len 相等子串的最大长度为 j 1 for i 0 i len i 依次比较 T 0 T len 1 与 T j len T j 1 if T i T j len i break if i len next j len break for if len 1 next j 0 其他情况 无相等子串 for int KMP char S char T 求 T 在 S 中的序号 int i 0 j 0 int next 80 假定模式最长为 80 个字符 GetNext T next while S i 0 j else j next j if j 1 i j if T j 0 return i strlen T 1 返回本趟匹配的开始位置 else return 0 int main char s1 ababcabccabccacbab char s2 abccac cout KMP s1 s2 endl return 0 2 分式化简 设计算法 将一个给定的真分数化简为最简分数形式 例如 将分式化简 设计算法 将一个给定的真分数化简为最简分数形式 例如 将 6 8 化简为化简为 3 4 include using namespace std int main int n 分子 int m 分母 int factor 最大公因子 int factor1 cout 输入一个真分数的分子与分母 n m int r m n 因为是真分数 所以分母一定大于分子 factor1 m factor n while r 0 第 12 页 共 41 页 factor1 factor factor r r factor1 factor cout 输出该真分数的最简分数 n factor m factor endl return 0 3 设计算法 判断一个大整数能否被设计算法 判断一个大整数能否被 11 整除 可以通过以下方法 将该数的十进制表示整除 可以通过以下方法 将该数的十进制表示 从右端开始 每两位一组构成一个整数 然后将这些数相加 判断其和能否被从右端开始 每两位一组构成一个整数 然后将这些数相加 判断其和能否被 11 整除 整除 例如 将例如 将 562843748 分割成分割成 5 62 84 37 48 然后判断 然后判断 5 62 84 37 48 能否被能否被 11 整除整除 将一个大整数看成一个数组 数组的奇数位对应数的 10 倍加上数组偶数对应数的本身 验证结果能否被 11 整除 include using namespace std int main int a 9 5 6 2 8 4 3 7 4 8 int result 0 result 为题目要求的各位之和 for int i 0 i 9 i if i 2 0 result a i i 为偶数位时 结果加上其对应数组数的本身 else result a i 10 i 为奇数位时 结果加上对应数组数的 10 倍 if result 11 0 cout 该整数能被 11 整除 endl else cout 该整数不能被 11 整除 endl return 0 4 数字游戏数字游戏 把数字 把数字 1 2 9 这这 9 个数字填入以下含有加 减 乘 除的四则运算式个数字填入以下含有加 减 乘 除的四则运算式 中 使得该等式成立 要求中 使得该等式成立 要求 9 个数字均出现一次且仅出现一次 且数字个数字均出现一次且仅出现一次 且数字 1 不能出现在乘和不能出现在乘和 除的一位数中 即排除运算式中一位数为除的一位数中 即排除运算式中一位数为 1 的平凡情形 的平凡情形 0 第 13 页 共 41 页 5 设计算法求解设计算法求解 an mod m 其中其中 a n 和和 m 均为大于均为大于 1 的整数的整数 提示 为了避免 提示 为了避免 an 超出超出 int 型的表示范围 应该每做一次乘法之后对型的表示范围 应该每做一次乘法之后对 n 取模 取模 include using namespace std int square int x return x x 用递归思想 int resultmod int a int n if n 0 return 1 if n 2 0 return square resultmod a n 2 n 为偶数的时 取 n 的一半防止溢出 else return a resultmod a n 1 n 为奇数时 取 n 1 int main int a n m cout 请输入 a n m a n m cout endl int result resultmod a n cout a n mod m 的结果为 result m endl return 0 第 14 页 共 41 页 6 设计算法 在数组设计算法 在数组 r n 中删除所有元素值为中删除所有元素值为 x 的元素 要求时间复杂性为的元素 要求时间复杂性为 O n 空间 空间 复杂性为复杂性为 O 1 7 设计算法 在数组设计算法 在数组 r n 中删除重复的元素 要求移动元素的次数较少并使剩余元素间中删除重复的元素 要求移动元素的次数较少并使剩余元素间 的相对次序保持不变 的相对次序保持不变 include using namespace std void deletere int a int N int b 100 0 int i k k 0 static int j 0 for i 0 i N i b a i for i 0 i 100 i if b i 0 if b i 2 k a j i j for i 0 i N k i cout a i endl int main int a 1 2 1 3 2 4 deletere a 6 return 0 第 15 页 共 41 页 在数组查找相同的元素 把其中一个相同的数值的元素位置设成一个 特殊数值 输出所求函数 include using namespace std int main int a 1 2 1 5 3 2 9 4 5 5 3 5 int i j for i 0 i 12 i for j 0 j i j if a j a i a i 64787250 设一个数组不存在的数值 for for i 0 i 12 i if a i 64787250 cout a i cout endl return 0 8 设表设表 A a1 a2 an 将 将 A 拆成拆成 B 和和 C 两个表 使两个表 使 A 中值大于等于中值大于等于 0 的元素存入的元素存入 表表 B 值小于 值小于 0 的元素存入表的元素存入表 C 要求表 要求表 B 和和 C 不另外设置存储空间而利用表不另外设置存储空间而利用表 A 的空间 的空间 先对 A 进行快排 将大于 0 的元素给 B 小于 0 的元素给 C include using namespace std int partions int l int low int high int prvotkey l low l 0 l low while low high 第 16 页 共 41 页 while low prvotkey high l low l high while low high l high l low l low l 0 return low void qsort int l int low int high int prvotloc if low high prvotloc partions l low high 将第一次排序的结果作为枢轴 qsort l low prvotloc 1 递归调用排序 由 low 到 prvotloc 1 qsort l prvotloc 1 high 递归调用排序 由 prvotloc 1 到 high void quicksort int l int n qsort l 1 n 第一个作为枢轴 从第一个排到第 n 个 int main int a 11 2 2 32 43 23 45 36 57 14 27 39 quicksort a 11 for int i 1 i 11 i if a i 0 cout C a i else cout B a i 第 17 页 共 41 页 cout endl return 0 9 荷兰国旗问题 要求重新排列一个由字符荷兰国旗问题 要求重新排列一个由字符 R W B R 代表红色 代表红色 W 代表白色 代表白色 B 代代 表兰色 这都是荷兰国旗的颜色 构成的数组 使得所有的表兰色 这都是荷兰国旗的颜色 构成的数组 使得所有的 R 都排在最前面 都排在最前面 W 排在其次 排在其次 B 排在最后 为荷兰国旗问题设计一个算法 其时间性能是排在最后 为荷兰国旗问题设计一个算法 其时间性能是 O n 0 代表红 1 代表白 2 代表蓝 include using namespace std const int N 20 void swap ab int p int q int tmp p p q q tmp void process int a int n int p q p q a while p a n 1 p 向前遍历 直到便利完毕 if p 1 p q p 1 while q q 1 swap ab q q 1 q q 指针后移 if 第 18 页 共 41 页 p while int main int a N 0 2 1 2 0 1 0 2 2 1 0 1 2 1 1 0 0 1 1 2 待处理的数组 cout 处理后的数组序列 endl process a N for int i 0 i N i cout a i cout endl return 0 10 设最近对问题以设最近对问题以 k 维空间的形式出现 维空间的形式出现 k 维空间的两个点维空间的两个点 p1 x1 x2 xk 和和 p2 y1 y2 yk 的欧几里德距离定义为 的欧几里德距离定义为 对 对 k 维空间的最近对问题设计维空间的最近对问题设计 k i ii x yppd 1 2 21 蛮力算法 并分析其时间性能 蛮力算法 并分析其时间性能 11 设计蛮力算法求解小规模的线性规划问题 假设约束条件为 设计蛮力算法求解小规模的线性规划问题 假设约束条件为 1 x y 4 2 x 3y 6 3 x 0 且且 y 0 使目标函数 使目标函数 3x 5y 取得极大值 取得极大值 include using namespace std int main int x y x0 y0 int summax 0 temp 0 for x0 0 x0 4 x0 for y0 0 x0 y0 4 x x0 符合 sum 最大值的 x 第 19 页 共 41 页 y y0 符合 sum 最大值得 y for cout x x y y summax summax 0 的元素进行判断 1 1 循环变量 i 从 1 n 重复进行下述操作 1 1 1 计算矩阵 i 次方 如果矩阵对角线上有 0 的元素 则跳转到 1 2 1 1 2 否则 i 1 2 如果矩阵对角线有 0 的元素 则输出该回路 2 输出无解信息 13 找词游戏 要求游戏者从一张填满字符的正方形表中 找出包含在一个给定集合中的找词游戏 要求游戏者从一张填满字符的正方形表中 找出包含在一个给定集合中的 所有单词 这些词在正方形表中可以横着读 竖着读 或者斜着读 为这个游戏设计一个所有单词 这些词在正方形表中可以横着读 竖着读 或者斜着读 为这个游戏设计一个 蛮力算法蛮力算法 14 变位词 给定两个单词 判断这两个单词是否是变位词 如果两个单词的字母完变位词 给定两个单词 判断这两个单词是否是变位词 如果两个单词的字母完 全相同 只是位置有所不同 则这两个单词称为变位词 例如 全相同 只是位置有所不同 则这两个单词称为变位词 例如 eat 和和 tea 是变位词 是变位词 判断 qwer 和 rewq 是否是变位词 include include using namespace std int main char s 5 qwer char t 5 rewq for int i 0 i 4 i if s i t 3 i 第 20 页 共 41 页 cout qwer 和 rewq 不是变位词 endl return 0 break cout qwer 和 rewq 是变位词 endl return 0 15 在美国有一个连锁店叫 在美国有一个连锁店叫 7 11 店 因为这个商店以前是早晨店 因为这个商店以前是早晨 7 点开门 晚上点开门 晚上 11 点关门 有一天 一个顾客在这个店挑选了四样东西 然后到付款处去交钱 营点关门 有一天 一个顾客在这个店挑选了四样东西 然后到付款处去交钱 营 业员拿起计算器 按了一些键 然后说 业员拿起计算器 按了一些键 然后说 总共是总共是 7 11 这个顾客开了个玩笑说 这个顾客开了个玩笑说 哦 难道因为你们的店名叫哦 难道因为你们的店名叫 7 11 所以我就要付 所以我就要付 7 11 吗 吗 营业员没有听出这是营业员没有听出这是 个玩笑 回答说 个玩笑 回答说 当然不是 我已经把这四样东西的价格相乘才得出这个结果的 当然不是 我已经把这四样东西的价格相乘才得出这个结果的 顾客一听非常吃惊 顾客一听非常吃惊 你怎么把他们相乘呢 你应该把他们相加才对 你怎么把他们相乘呢 你应该把他们相加才对 营业员答营业员答 道 道 噢 对不起 我今天非常头疼 所以把键按错了 噢 对不起 我今天非常头疼 所以把键按错了 然后 营业员将结果重算然后 营业员将结果重算 了一遍 将这四样东西的价格加在一起 然而 令他俩更为吃惊的是总和也是了一遍 将这四样东西的价格加在一起 然而 令他俩更为吃惊的是总和也是 7 11 设计蛮力算法找出这四样东西的价格各是多少 设计蛮力算法找出这四样东西的价格各是多少 该算法为 int 7 11 float a float b float c float d int n for int i 0 i n i for int j 0 j n j for int k 0 k n k for int m 0 m n m if a i b j c k d m 7 11 return 0 return 0 习题习题 4 1 分治法的时间性能与直接计算最小问题的时间 合并子问题解的时间以及子问题的分治法的时间性能与直接计算最小问题的时间 合并子问题解的时间以及子问题的 第 21 页 共 41 页 个数有关 试说明这几个参数与分治法时间复杂性之间的关系个数有关 试说明这几个参数与分治法时间复杂性之间的关系 2 证明 如果分治法的合并可以在线性时间内完成 则当子问题的规模之和小于原问证明 如果分治法的合并可以在线性时间内完成 则当子问题的规模之和小于原问 题的规模时 算法的时间复杂性可达到题的规模时 算法的时间复杂性可达到 O n O N 2 O N 2 x O N x 2 O N 2 2 x a O N x a 2 O N 2 x x 2 a O N 2 a 1 x 由此可知 时间复杂度可达到 O n 3 分治策略一定导致递归吗 如果是 请解释原因 如果不是 给出一个不包含递归的分治策略一定导致递归吗 如果是 请解释原因 如果不是 给出一个不包含递归的 分治例子 并阐述这种分治和包含递归的分治的主要不同 分治例子 并阐述这种分治和包含递归的分治的主要不同 不一定导致递归 如非递归的二叉树中序遍历 这种分治方法与递归的二叉树中序遍历主要区别是 应用了栈这个数据结构 4 对于待排序序列对于待排序序列 5 3 1 9 分别画出归并排序和快速排序的递归运行轨迹 分别画出归并排序和快速排序的递归运行轨迹 归并排序 第一趟 5 3 1 9 第二趟 3 5 1 9 第三趟 1 3 5 9 快速排序 第一趟 5 3 1 9 5 为哨兵 比较 9 和 5 第二趟 5 1 3 9 比较 1 和 5 将 1 挪到相应位置 第三趟 5 1 3 9 比较 3 和 5 第四趟 1 3 5 9 5 设计分治算法求一个数组中的最大元素 并分析时间性能 设计分治算法求一个数组中的最大元素 并分析时间性能 简单的分治问题 将数组均衡的分为 前 后 两部分 分别求出这两部分最大值 然后再比较这两个最大值 include using namespace std extern const int n 6 声明 int main int a n 0 6 1 2 3 5 初始化 第 22 页 共 41 页 int mid n int num max1 0 num max2 0 for int i 0 inum max1 num max1 a i for int j n 1 jnum max2 num max2 a j if num max1 num max2 cout 数组中的最大元素 num max1 endl else cout 数组中的最大元素 num max2 endl return 0 时间复杂度 O n 6 设计分治算法 实现将数组设计分治算法 实现将数组 A n 中所有元素循环左移中所有元素循环左移 k 个位置个位置 要求时间复杂性为要求时间复杂性为 O n 空间复杂性为 空间复杂性为 O 1 例如 对 例如 对 abcdefgh 循环左移循环左移 3 位得到位得到 defghabc 采用分治法 将数组分为 0 k 1 和 k n 1 两块 将这两块分别左移 然后再合并左移 include using namespace std void LeftReverse char a int begin int end for int i 0 i end begin 1 2 i 交换移动 int temp a begin i a begin i a end i a end i temp 第 23 页 共 41 页 void Converse char a int n int k LeftReverse a 0 k 1 LeftReverse a k n 1 LeftReverse a 0 n 1 for int i 0 i n i cout a i cout endl int main char a 7 a b c d e f g Converse a 7 3 return 0 7 设计递归算法生成设计递归算法生成 n 个元素的所有排列对象 个元素的所有排列对象 include using namespace std int data 100 在 m 个数中输出 n 个排列数 n m void DPpl int num int m int n int depth if depth n for int i 0 i n i cout data i cout endl for int j 0 j m j if num DPpl num 1 j m n depth 1 第 24 页 共 41 页 for int main DPpl 0 5 1 0 DPpl 0 5 2 0 DPpl 0 5 3 0 DPpl 0 5 4 0 DPpl 0 5 5 0 return 0 8 设计分治算法求解一维空间上设计分治算法求解一维空间上 n 个点的最近对问题 个点的最近对问题 参见 4 4 1 最近对问题的算法分析及算法实现 9 在有序序列在有序序列 r1 r2 rn 中 存在序号中 存在序号 i 1 i n 使得 使得 ri i 请设计一个分治算法 请设计一个分治算法 找到这个元素 要求算法在最坏情况下的时间性能为找到这个元素 要求算法在最坏情况下的时间性能为 O log2n 在有序数组中 采用二分法查找符合条件的元素 include using namespace std void Findnum int a int n int low 0 int high n 1 while low high int mid low high 2 if a mid mid cout 这个数是 a mid mid 第 25 页 共 41 页 high mid 1 else low mid 1 int main int a 7 1 0 2 5 6 7 9 Findnum a 7 return 0 时间复杂度为 O log2n 10 在一个序列中出现次数最多的元素称为众数 请设计算法寻找众数并分析算法的在一个序列中出现次数最多的元素称为众数 请设计算法寻找众数并分析算法的 时间复杂性 时间复杂性 先对序列进行快速排序 再进行一次遍历 输出众数的重复次数 include using namespace std int partions int b int low int high int prvotkey b low b 0 b low while low high while low prvotkey high b low b high while low high b high b low 第 26 页 共 41 页 b low b 0 return low void qsort int l int low int high int prvotloc if low high prvotloc partions l low high 将第一次排序的结果作为枢轴 qsort l low prvotloc 1 递归调用排序 由 low 到 prvotloc 1 qsort l prvotloc 1 high 递归调用排序 由 prvotloc 1 到 high void quicksort int l int n qsort l 1 n 第一个作为枢轴 从第一个排到第 n 个 int main int a 10 1 2 3 5 3 3 3 2 5 1 int i 0 int count 0 int max 0 max 表示出现的次数 qsort a 0 10 while i 10 int j j i 1 if a i a j count 0 第 27 页 共 41 页 while cout 重复次数 max endl return 0 时间复杂度 nlog n 11 设设 M 是一个是一个 n n 的整数矩阵 其中每一行 从左到右 和每一列 从上到下 的整数矩阵 其中每一行 从左到右 和每一列 从上到下 的元素都按升序排列 设计分治算法确定一个给定的整数的元素都按升序排列 设计分治算法确定一个给定的整数 x 是否在是否在 M 中 并分析算法的时中 并分析算法的时 间复杂性 间复杂性 12 设设 S 是是 n n 为偶数 个不等的正整数的集合 要求将集合为偶数 个不等的正整数的集合 要求将集合 S 划分为子集划分为子集 S1和和 S2 使得使得 S1 S2 n 2 且两个子集元素之和的差达到最大 且两个子集元素之和的差达到最大 先用快速排序进行一趟排序 如果 s1 大的数集 的的个数大于 n 2 将 i n 2 low 1 个最小的数排到后面 如果 s1 大的数集 的的个数小于 n 2 将 s2 小的数集 n 2 low 1 排到前面 将排好的数组的前 n 2 个数赋值给 s1 将排好的数组的后 n 2 个数赋值给 s2 include using namespace std const int n 8 void partions int a int low int high 进行一趟快排进行一趟快排 int prvotkey a low a 0 a low while low high while low high a low a high while low prvotkey low a high a low a low prvotkey 第 28 页 共 41 页 如果如果 s1 大的数集 的的个数大于 大的数集 的的个数大于 n 2 if low n 2 for int i 0 i n 2 low 1 i for int j 0 j n i j if a j a j 1 int temp a j a j a j 1 a j 1 temp for if 如果如果 s1 大的数集 的的个数小于 大的数集 的的个数小于 n 2 else for int i 0 i n 2 low 1 i for int k n 1 ka k 1 int temp1 a k a k a k 1 a k 1 temp1 for int main int a n 1 3 5 9 6 0 11 8 partions a 0 n 1 for int i 0 i n i if i 4 cout 属于子集属于子集 s1 的 的 endl 第 29 页 共 41 页 cout a i endl else cout 属于子集属于子集 s2 的 的 endl cout a i endl return 0 13 设设 a1 a2 an是集合是集合 1 2 n 的一个排列 如果的一个排列 如果 iaj 则序偶 则序偶 ai aj 称为称为 该排列的一个逆序 例如 该排列的一个逆序 例如 2 3 1 有两个逆序 有两个逆序 3 1 和和 2 1 设计算法统计给定排列中含 设计算法统计给定排列中含 有逆序的个数 有逆序的个数 用归并进行排序 当一个子集的一个数大于第二个子集的一个数 为逆序 即 a i a j 则逆序数为 end j 1 include using namespace std int count void Merge int a int a1 int begin int mid int end 合并子序列 int i begin j mid 1 k end while i mid 取 a i 和 a j 中较小者放入 r1 k else a1 k a j count end j 1 while i mid a1 k a i while j end a1 k a j 第 30 页 共 41 页 void MergeSort int a int begin int end int mid a1 1000 if begin end return else mid begin end 2 MergeSort a begin mid MergeSort a mid 1 end Merge a a1 begin mid end int main int a 6 6 5 4 3 2 1 count 0 MergeSort a 0 6 cout count endl return 0 14 循环赛日程安排问题 设有循环赛日程安排问题 设有 n 2k个选手要进行网球循环赛 要求设计一个满足以下个选手要进行网球循环赛 要求设计一个满足以下 要求的比赛日程表 要求的比赛日程表 1 每个选手必须与其他 每个选手必须与其他 n 1 个选手各赛一次 个选手各赛一次 2 每个选手一天只能赛一次 每个选手一天只能赛一次 采用分治方法 将 2 k 选手分为 2 k 1 两组 采用递归方法 继续进行分组 直到只剩下 2 个选手时 然后进行比赛 回溯就可以指定比赛日程表了 15 格雷码是一个长度为格雷码是一个长度为 2n的序列 序列中无相同元素 且每个元素都是长度为的序列 序列中无相同元素 且每个元素都是长度为 n 的的 二进制位串 相邻元素恰好只有二进制位串 相邻元素恰好只有 1 位不同 例如长度为位不同 例如长度为 23的格雷码为的格雷码为 000 001 011 010 110 111 101 100 设计分治算法对任意的 设计分治算法对任意的 n 值构造相应的格雷码 值构造相应的格雷码 构造格雷码 include using namespace std int n char a 100 第 31 页 共 41 页 void gelei int k if k n cout a n 初始化 全部置零 a n 0 gelei 0 cout endl return 0 16 矩阵乘法 两个 n n 的矩阵 X 和 Y 的乘积得到另外一个 n n 的矩阵 Z 且 Zij 满足 1 i j n 这个公式给出了运行时间为 O n3 的算法 可以用分 治法解决矩阵乘法问题 将矩阵 X 和 Y 都划分成四个 n 2 n 2 的子块 从而 X 和 Y 的乘积 可以用这些子块进行表达 即 A BE FAEBG AFBH XY C DG HCEDG CFDH 从而得到分治算法 先递归地计算 8 个规模为 n 2 的矩阵乘积 AE BG AF BH CE DG CF DH 然后再花费 O n2 的时间完成加法