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

精品文档 第 1 页 共 42 页 1欢迎下载 算法设计与分析算法设计与分析 第第 2 2 版版 王红梅王红梅 胡明胡明 习习 题答案题答案 习题习题 1 1 1 图论诞生于七桥问题 出生于瑞士的伟大数学家欧拉 图论诞生于七桥问题 出生于瑞士的伟大数学家欧拉 LeonhardLeonhard EulerEuler 17071707 17831783 提出并解决了该问题 七桥问题是这样 提出并解决了该问题 七桥问题是这样 描述的 一个人是否能在一次步行中穿越哥尼描述的 一个人是否能在一次步行中穿越哥尼 斯堡 现在叫加里宁格勒 在波罗的海南岸 斯堡 现在叫加里宁格勒 在波罗的海南岸 城中全部的七座桥后回到起点 且每座桥只经城中全部的七座桥后回到起点 且每座桥只经 过一次 图过一次 图 1 71 7 是这条河以及河上的两个岛和是这条河以及河上的两个岛和 七座桥的草图 请将该问题的数据模型抽象出七座桥的草图 请将该问题的数据模型抽象出 来 并判断此问题是否有解 来 并判断此问题是否有解 七桥问题属于一笔画问题 输入 一个起点 输出 相同的点 1 一次步行 2 经过七座桥 且每次只经历过一次 3 回到起点 该问题无解 能一笔画的图形只有两类 一类是所有的点都是偶点 另一类是只有二个 奇点的图形 2 2 在欧几里德提出的欧几里德算法中 即最初的欧几里德算法 用的不是除法而是减 在欧几里德提出的欧几里德算法中 即最初的欧几里德算法 用的不是除法而是减 法 请用伪代码描述这个版本的欧几里德算法法 请用伪代码描述这个版本的欧几里德算法 1 r m n 2 循环直到 r 0 2 1 m n 2 2 n r 2 3 r m n 3 输出 m 3 3 设计算法求数组中相差最小的两个元素 称为最接近数 的差 要求分别给出伪代 设计算法求数组中相差最小的两个元素 称为最接近数 的差 要求分别给出伪代 码和码和 C C 描述 描述 采用分治法 对数组先进行快速排序 在依次比较相邻的差 图 1 7 七桥问题 北区 东区 岛区 南区 精品文档 第 2 页 共 42 页 2欢迎下载 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 页 共 42 页 3欢迎下载 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 4 设数组设数组 a n a n 中的元素均不相等 设计算法找出中的元素均不相等 设计算法找出 a n a n 中一个既不是最大也不是最小中一个既不是最大也不是最小 的元素 并说明最坏情况下的比较次数 要求分别给出伪代码和的元素 并说明最坏情况下的比较次数 要求分别给出伪代码和 C 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 页 共 42 页 4欢迎下载 return 0 5 5 编写程序 求编写程序 求n n至少为多大时 至少为多大时 n n个个 1 1 组成的整数能被组成的整数能被 20132013 整除 整除 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 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 7 圣经上说 神圣经上说 神 6 6 天创造天地万有 第天创造天地万有 第 7 7 日安歇 为什么是日安歇 为什么是 6 6 天呢 任何一个自然数天呢 任何一个自然数 的因数中都有的因数中都有 1 1 和它本身 所有小于它本身的因数称为这个数的真因数 如果一个自然数和它本身 所有小于它本身的因数称为这个数的真因数 如果一个自然数 的真因数之和等于它本身 这个自然数称为完美数 例如 的真因数之和等于它本身 这个自然数称为完美数 例如 6 1 2 36 1 2 3 因此 因此 6 6 是完美数 神是完美数 神 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 8 有有 4 4 个人打算过桥 这个桥每次最多只能有两个人同时通过 他们都在桥的某一端 个人打算过桥 这个桥每次最多只能有两个人同时通过 他们都在桥的某一端 精品文档 第 6 页 共 42 页 6欢迎下载 并且是在晚上 过桥需要一只手电筒 而他们只有一只手电筒 这就意味着两个人过桥后并且是在晚上 过桥需要一只手电筒 而他们只有一只手电筒 这就意味着两个人过桥后 必须有一个人将手电筒带回来 每个人走路的速度是不同的 甲过桥要用必须有一个人将手电筒带回来 每个人走路的速度是不同的 甲过桥要用 1 1 分钟 乙过桥分钟 乙过桥 要用要用 2 2 分钟 丙过桥要用分钟 丙过桥要用 5 5 分钟 丁过桥要用分钟 丁过桥要用 1010 分钟 显然 两个人走路的速度等于其中分钟 显然 两个人走路的速度等于其中 较慢那个人的速度 问题是他们全部过桥最少要用多长时间 较慢那个人的速度 问题是他们全部过桥最少要用多长时间 由于甲过桥时间最短 那么每次传递手电的工作应有甲完成 甲每次分别带着乙丙丁过桥 例如 第一趟 甲 乙过桥且甲回来 第二趟 甲 丙过桥且甲回来 第一趟 甲 丁过桥 一共用时 19 小时 9 9 欧几里德游戏 开始的时候 白板上有两个不相等的正整数 两个玩家交替行动 欧几里德游戏 开始的时候 白板上有两个不相等的正整数 两个玩家交替行动 每次行动时 当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差 而且这每次行动时 当前玩家都必须在白板上写出任意两个已经出现在板上的数字的差 而且这 个数字必须是新的 也就是说 和白板上的任何一个已有的数字都不相同 当一方再也写个数字必须是新的 也就是说 和白板上的任何一个已有的数字都不相同 当一方再也写 不出新数字时 他就输了 请问 你是选择先行动还是后行动 为什么 不出新数字时 他就输了 请问 你是选择先行动还是后行动 为什么 设最初两个数较大的为 a 较小的为 b 两个数的最大公约数为 factor 则最终能出现的数包括 factor factor 2 factor 3 factor a factor a 一 共 a factor 个 如果 a factor 是奇数 就选择先行动 否则就后行动 习题习题 2 2 1 1 如果 如果T T1 1 n n O O f f n n T T2 2 n n O O g g n n 解答下列问题 解答下列问题 1 1 证明加法定理 证明加法定理 T T1 1 n n T T2 2 n n max max O O f f n n O O g g n n 2 2 证明乘法定理 证明乘法定理 T T1 1 n n T T2 2 n n O O f f n n O O g g n n 3 3 举例说明在什么情况下应用加法定理和乘法定理 举例说明在什么情况下应用加法定理和乘法定理 1 2 3 比如在 for f n for g n 中应该用乘法定理 如果在 讲两个数组合并成一个数组时 应当用加法定理 2 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 页 共 42 页 7欢迎下载 语句执行了多少次 算法的时间复杂性是多少 语句执行了多少次 算法的时间复杂性是多少 1 完成的是 1 n 的平方和 基本语句 s i i 执行了 n 次 时间复杂度 O n 2 2 完成的是 n 的平方 基本语句 return Q n 1 2 n 1 执行了 n 次 时间复杂度 O n 3 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 页 共 42 页 8欢迎下载 5 5 求下列问题的平凡下界 并指出其下界是否紧密 求下列问题的平凡下界 并指出其下界是否紧密 1 1 求数组中的最大元素 求数组中的最大元素 2 2 判断邻接矩阵表示的无向图是不是完全图 判断邻接矩阵表示的无向图是不是完全图 3 3 确定数组中的元素是否都是惟一的 确定数组中的元素是否都是惟一的 4 4 生成一个具有 生成一个具有n n个元素集合的所有子集个元素集合的所有子集 1 n 紧密 2 n n 3 logn n 先进行快排 然后进行比较查找 4 2 n 7 7 画出在三个数 画出在三个数a a b b c c中求中值问题的判定树 中求中值问题的判定树 8 8 国际象棋是很久以前由一个印度人 国际象棋是很久以前由一个印度人 ShashiShashi 发明的 当他把该发明献给国王时 国发明的 当他把该发明献给国王时 国 王很高兴 就许诺可以给这个发明人任何他想要的奖赏 王很高兴 就许诺可以给这个发明人任何他想要的奖赏 ShashiShashi 要求以这种方式给他一些要求以这种方式给他一些 粮食 棋盘的第粮食 棋盘的第 1 1 个方格内只放个方格内只放 1 1 粒麦粒 第粒麦粒 第 2 2 格格 2 2 粒 第粒 第 3 3 格格 4 4 粒 第粒 第 4 4 格格 8 8 粒 粒 以此类推 直到 以此类推 直到 6464 个方格全部放满 这个奖赏的最终结果会是什么样呢 个方格全部放满 这个奖赏的最终结果会是什么样呢 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 页 共 42 页 9欢迎下载 cout result endl return 0 习题习题 3 3 1 1 假设在文本假设在文本 ababcabccabccacbab ababcabccabccacbab 中查找模式中查找模式 abccac abccac 写出分别采用 写出分别采用 BFBF 算法和算法和 KMPKMP 算法的串匹配过算法的串匹配过 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 页 共 42 页 10欢迎下载 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 2 分式化简 设计算法 将一个给定的真分数化简为最简分数形式 例如 将分式化简 设计算法 将一个给定的真分数化简为最简分数形式 例如 将 6 86 8 化简为化简为 3 43 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 页 共 42 页 12欢迎下载 factor1 factor factor r r factor1 factor cout 输出该真分数的最简分数 n factor m factor endl return 0 3 3 设计算法 判断一个大整数能否被设计算法 判断一个大整数能否被 1111 整除 可以通过以下方法 将该数的十进制表示整除 可以通过以下方法 将该数的十进制表示 从右端开始 每两位一组构成一个整数 然后将这些数相加 判断其和能否被从右端开始 每两位一组构成一个整数 然后将这些数相加 判断其和能否被 1111 整除 整除 例如 将例如 将 562843748562843748 分割成分割成 5 62 84 37 485 62 84 37 48 然后判断 然后判断 5 62 84 37 48 5 62 84 37 48 能否被能否被 1111 整除整除 将一个大整数看成一个数组 数组的奇数位对应数的 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 4 数字游戏 把数字数字游戏 把数字 1 2 91 2 9 这这 9 9 个数字填入以下含有加 减 乘 除的四则运算个数字填入以下含有加 减 乘 除的四则运算 式中 使得该等式成立 要求式中 使得该等式成立 要求 9 9 个数字均出现一次且仅出现一次 且数字个数字均出现一次且仅出现一次 且数字 1 1 不能出现在乘不能出现在乘 和除的一位数中 即排除运算式中一位数为和除的一位数中 即排除运算式中一位数为 1 1 的平凡情形 的平凡情形 0 0 精品文档 第 13 页 共 42 页 13欢迎下载 5 5 设计算法求解设计算法求解a an n modmod m m 其中 其中a a n n和和m m均为大于均为大于 1 1 的整数 的整数 提示 为了避免 提示 为了避免a an n 超出超出 intint 型的表示范围 应该每做一次乘法之后对型的表示范围 应该每做一次乘法之后对n 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 页 共 42 页 14欢迎下载 6 6 设计算法 在数组设计算法 在数组r r n n 中删除所有元素值为中删除所有元素值为x x的元素 要求时间复杂性为的元素 要求时间复杂性为O O n n 空 空 间复杂性为间复杂性为O O 1 1 7 7 设计算法 在数组设计算法 在数组r r n n 中删除重复的元素 要求移动元素的次数较少并使剩余元素中删除重复的元素 要求移动元素的次数较少并使剩余元素 间的相对次序保持不变 间的相对次序保持不变 include include usingusing namespacenamespace std std voidvoid deletere intdeletere int a inta int N N intint b 100 0 b 100 0 intint i k i k k 0 k 0 staticstatic intint j 0 j 0 for i 0 i N i for i 0 i N i b a i b a i for i 0 i 100 i for i 0 i 100 i if b i 0 if b i 0 if b i 2 if b i 2 k k a j i a j i j j for i 0 i N k i for i 0 i N k i cout a i endl cout a i endl intint main main intint a 1 2 1 3 2 4 a 1 2 1 3 2 4 deletere a 6 deletere a 6 returnreturn 0 0 精品文档 第 15 页 共 42 页 15欢迎下载 在数组查找相同的元素 把其中一个相同的数值的元素位置设成一个 特殊数值 输出所求函数 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 8 设表设表A A a a1 1 a a2 2 a an n 将 将A A拆成拆成B B和和C C两个表 使两个表 使A A中值大于等于中值大于等于 0 0 的元素存的元素存 入表入表B B 值小于 值小于 0 0 的元素存入表的元素存入表C C 要求表 要求表B B和和C C不另外设置存储空间而利用表不另外设置存储空间而利用表A 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 页 共 42 页 16欢迎下载 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 页 共 42 页 17欢迎下载 cout endl return 0 9 9 荷兰国旗问题 要求重新排列一个由字符荷兰国旗问题 要求重新排列一个由字符R R W W B B R R代表红色 代表红色 W W代表白色 代表白色 B B代代 表兰色 这都是荷兰国旗的颜色 构成的数组 使得所有的表兰色 这都是荷兰国旗的颜色 构成的数组 使得所有的R R都排在最前面 都排在最前面 W W排在其次 排在其次 B B排在最后 为荷兰国旗问题设计一个算法 其时间性能是排在最后 为荷兰国旗问题设计一个算法 其时间性能是O O n 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 页 共 42 页 18欢迎下载 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 10 设最近对问题以设最近对问题以k k维空间的形式出现 维空间的形式出现 k k维空间的两个点维空间的两个点p p1 1 x x1 1 x x2 2 x xk k 和和 p p2 2 y y1 1 y y2 2 y yk k 的欧几里德距离定义为 的欧几里德距离定义为 对 对k k维空间的最近维空间的最近 k i ii x yppd 1 2 21 对问题设计蛮力算法 并分析其时间性能 对问题设计蛮力算法 并分析其时间性能 1111 设计蛮力算法求解小规模的线性规划问题 假设约束条件为 设计蛮力算法求解小规模的线性规划问题 假设约束条件为 1 1 x x y y 4 4 2 2 x x 3 3y y 6 6 3 3 x x 0 0 且且y y 0 0 使目标函数 使目标函数 3 3x x 5 5y y取得极大值 取得极大值 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 页 共 42 页 19欢迎下载 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 输出无解信息 1313 找词游戏 要求游戏者从一张填满字符的正方形表中 找出包含在一个给定集合中的找词游戏 要求游戏者从一张填满字符的正方形表中 找出包含在一个给定集合中的 所有单词 这些词在正方形表中可以横着读 竖着读 或者斜着读 为这个游戏设计一个所有单词 这些词在正方形表中可以横着读 竖着读 或者斜着读 为这个游戏设计一个 蛮力算法蛮力算法 14 14 变位词 给定两个单词 判断这两个单词是否是变位词 如果两个单词的字母完变位词 给定两个单词 判断这两个单词是否是变位词 如果两个单词的字母完 全相同 只是位置有所不同 则这两个单词称为变位词 例如 全相同 只是位置有所不同 则这两个单词称为变位词 例如 eateat 和和 teatea 是变位词 是变位词 判断 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 页 共 42 页 20欢迎下载 cout qwer 和 rewq 不是变位词 endl return 0 break cout qwer 和 rewq 是变位词 endl return 0 1515 在美国有一个连锁店叫 在美国有一个连锁店叫 7 117 11 店 因为这个商店以前是早晨店 因为这个商店以前是早晨 7 7 点开门 晚上点开门 晚上 1111 点关门 有一天 一个顾客在这个店挑选了四样东西 然后到付款处去交钱 营点关门 有一天 一个顾客在这个店挑选了四样东西 然后到付款处去交钱 营 业员拿起计算器 按了一些键 然后说 业员拿起计算器 按了一些键 然后说 总共是总共是 7 11 7 11 这个顾客开了个玩笑说 这个顾客开了个玩笑说 哦 难道因为你们的店名叫哦 难道因为你们的店名叫 7 117 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 4 精品文档 第 21 页 共 42 页 21欢迎下载 1 1 分治法的时间性能与直接计算最小问题的时间 合并子问题解的时间以及子问题的分治法的时间性能与直接计算最小问题的时间 合并子问题解的时间以及子问题的 个数有关 试说明这几个参数与分治法时间复杂性之间的关系个数有关 试说明这几个参数与分治法时间复杂性之间的关系 2 2 证明 如果分治法的合并可以在线性时间内完成 则当子问题的规模之和小于原问证明 如果分治法的合并可以在线性时间内完成 则当子问题的规模之和小于原问 题的规模时 算法的时间复杂性可达到题的规模时 算法的时间复杂性可达到O O n 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 3 分治策略一定导致递归吗 如果是 请解释原因 如果不是 给出一个不包含递归的分治策略一定导致递归吗 如果是 请解释原因 如果不是 给出一个不包含递归的 分治例子 并阐述这种分治和包含递归的分治的主要不同 分治例子 并阐述这种分治和包含递归的分治的主要不同 不一定导致递归 如非递归的二叉树中序遍历 这种分治方法与递归的二叉树中序遍历主要区别是 应用了栈这个数据结构 4 4 对于待排序序列对于待排序序列 5 5 3 3 1 1 9 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 5 设计分治算法求一个数组中的最大元素 并分析时间性能 设计分治算法求一个数组中的最大元素 并分析时间性能 简单的分治问题 将数组均衡的分为 前 后 两部分 分别求出这两部分最大值 然后再比较这两个最大值 include using namespace std extern const int n 6 声明 int main 精品文档 第 22 页 共 42 页 22欢迎下载 int a n 0 6 1 2 3 5 初始化 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 6 设计分治算法 实现将数组设计分治算法 实现将数组A A n n 中所有元素循环左移中所有元素循环左移k k个位置个位置 要求时间复杂性要求时间复杂性 为为O O n n 空间复杂性为 空间复杂性为O O 1 1 例如 对 例如 对abcdefghabcdefgh循环左移循环左移 3 3 位得到位得到defghabcdefghabc 采用分治法 将数组分为 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 页 共 42 页 23欢迎下载 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 7 设计递归算法生成设计递归算法生成n 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 精品文档 第 24 页 共 42 页 24欢迎下载 DPpl num 1 j m n depth 1 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 8 设计分治算法求解一维空间上设计分治算法求解一维空间上n n个点的最近对问题 个点的最近对问题 参见 4 4 1 最近对问题的算法分析及算法实现 9 9 在有序序列在有序序列 r r1 1 r r2 2 r rn n 中 存在序号中 存在序号i i 1 1 i i n n 使得 使得r ri i i i 请设计一个 请设计一个 分治算法找到这个元素 要求算法在最坏情况下的时间性能为分治算法找到这个元素 要求算法在最坏情况下的时间性能为O O log log2 2n n 在有序数组中 采用二分法查找符合条件的元素 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 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 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 页 共 42 页 26欢迎下载 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 页 共 42 页 27欢迎下载 while cout 重复次数 max endl return 0 时间复杂度 nlog n 11 11 设设M M是一个是一个n n n n的整数矩阵 其中每一行 从左到右 和每一列 从上到下 的的整数矩阵 其中每一行 从左到右 和每一列 从上到下 的 元素都按升序排列 设计分治算法确定一个给定的整数元素都按升序排列 设计分治算法确定一个给定的整数x x是否在是否在M M中 并分析算法的时间中 并分析算法的时间 复杂性 复杂性 12 12 设设S S是是n n n n为偶数 个不等的正整数的集合 要求将集合为偶数 个不等的正整数的集合 要求将集合S S划分为子集划分为子集S S1 1和和 S S2 2 使得 使得 S S1 1 S S2 2 n n 2 2 且两个子集元素之和的差达到最大 且两个子集元素之和的差达到最大 先用快速排序进行一趟排序 如果 s1 大的数集 的的个数大于 n 2 将 i n 2 low 1 个最小的数排到后面 如果 s1 大的数集 的的个数小于 n 2 将 s2 小的数集 n 2 low 1 排到前面 将排好的数组的前 n 2 个数赋值给 s1 将排好的数组的后 n 2 个数赋值给 s2 include include usingusing namespacenamespace std std constconst intint n 8 n 8 voidvoid partions intpartions int a inta int low intlow int high high 进行一趟快排进行一趟快排 intint prvotkey a low prvotkey a low a 0 a low a 0 a low whilewhile low high low high whilewhile low high high a low a high a low a high whilewhile low prvotkey low prvotkey low low a high a low a high a low a low prvotkey a low prvotkey 精品文档 第 28 页 共 42 页 28欢迎下载 如果如果 s1s1 大的数集 的的个数大于 大的数集 的的个数大于 n 2n 2 if low n 2 if low n 2 for intfor int i 0 i n 2 low 1 i i 0 i n 2 low 1 i for intfor int j 0 j n i j j 0 j n i j if a j a j 1 if a j a j 1 intint temp a j temp a j a j a j 1 a j a j 1 a j 1 temp a j 1 temp for for if if 如果如果 s1s1 大的数集 的的个数小于 大的数集 的的个数小于 n 2n 2 elseelse for intfor int i 0 i n 2 low 1 i i 0 i n 2 low 1 i for intfor int k n 1 k n i k k n 1 ka k 1 if a k a k 1 intint temp1 a k temp1 a k a k a k 1 a k a k 1 a k 1 temp1 a k 1 temp1 for for intint main main intint a n 1 3 5 9 6 0 11 8 a n 1 3 5 9 6 0 11 8 partions a 0 n 1 partions a 0 n 1 for intfor int i 0 i n i i 0 i n i if i 4 if i 4 精品文档 第 29 页 共 42 页 29欢迎下载 cout cout 属于子集属于子集 s1