算法分析与设计答案.pdf

第一章第一章 6 考虑下面算法 回答问题 int Stery int n int S 0 for i 1 i n i S S i i return S 1 该算法求的是什么 从 1 到 N 的平方和 2 该算法基本语句是什么 S S 3 基本语句执行了多少次 N次 4 该算法的效率类型是什么 O n 5 对该算法进行改进 分析改进的算法效率 利用公式法进行求解 int Stery1 int n return n n 1 2n 1 6 O 1 6 如果算法不能在改进了 请证明这一点 因为其时间复杂度已经是常数级 不能再小了 7 使用扩展递推技术求解下列递推关系式 参考P15 假定n 2 k 上式 2 2 2 T n 3 2 n 3 n 2 2 2 T n 3 3 n 32 n 3 n 2 KT 1 2 k 1 n 3k 1 2k 2 n 3k 2 21 n 31 n 2 k n n 3n 1 n 3n 1 当然也可以使用通用分支递推式 可快速确定答案 8 考虑下面的递归算法 回答下面问题 int Q int n n 为正整数 if n 1 return 1 else return Q n 1 2 n 1 1 该算法求的是什么 求一个正整数的平方 2 写出n 3时的执行过程 f 3 f 2 2 3 1 f 2 f 1 2 2 1 f 1 1 回溯 f 2 1 3 4 f 3 4 5 9 3 建立该算法的递推关系式 并求解 f n f n 1 2n 1 f n 2 2 n 1 1 2n 1 f n 3 2 n 2 1 2 n 1 1 2n 1 f 1 3 5 7 2n 1 1 3 5 2n 1 1 2n 1 n 2 n 2 4 将该算法转换为非递归算法 int Q1 int n return n n 补充习题 1 4 设计算法求数组中相差最小的两个元素 称为最接近数 的差 要求给出伪代码描述 设计算法求数组中相差最小的两个元素 称为最接近数 的差 要求给出伪代码描述 并用一组例子进行跟踪验证 写出验证过程 并用一组例子进行跟踪验证 写出验证过程 1 伪代码 伪代码 1 令最小距离令最小距离 min 等于数组头两个元素等于数组头两个元素 R 0 和和 R 1 的差的绝对值 的差的绝对值 2 从从 i 0 循环至循环至 i n 1 对于每个 对于每个 R i 2 1分别求其与分别求其与 j i 1 至至 j n 的数的差的绝对值 的数的差的绝对值 2 2如果此值小于最小距离 则令新的最小距离为此值 如果此值小于最小距离 则令新的最小距离为此值 3 输出最小距离 输出最小距离 2 用实例进行跟踪验证 用实例进行跟踪验证 R 6 10 5 11 16 30 14 n 6 Min 10 5 5 i 0 j 1 R i R j 10 5 5 j 2 R i R j 10 11 1 min min 1 j 3 R i R j 10 16 6 j 4 R i R j 10 30 20 j 5 R i R j 10 14 4 i 1 j 2 R i R j 5 11 6 j 3 R i R j 5 16 11 j 4 R i R j 5 30 15 j 5 R i R j 5 14 9 i 2 j 3 R i R j 11 16 5 j 4 R i R j 11 30 19 j 5 R i R j 11 14 3 i 3 j 4 R i R j 16 30 14 j 5 R i R j 16 14 2 i 4 j 5 R i R j 30 14 16 最后输出最后输出 min 1 第二章第二章 1 求平凡下界 2 n logn 分治法 3 画出 a b c 中秋中值问题的决策树 p27 4 时间复杂度是 O n 可以从 n 到 1 也可以从 1 到 n 从 n 开始就看 k 2 下取整下标的元素 也就是堆中的双亲 是否满 足大根或者小根的条件 从 1 开始就看 2k 和 2k 1 下标的元素 就是堆中的左右孩子 是否满足堆的条件 复杂度 O n 大根堆 bool isHeap int data int n int i j k for i 0 j 1 j n i j 2 i 1 k data j if j 1 data j k data j 1 if data i k return false return true 小根堆 bool isHeap int data int n int i j k for i 0 j 1 j n i j 2 i 1 k data j if j 1 n return true 第三章第三章 3 3 对于 KMP 算法中求 next 数组问题 设计一个蛮力算法 并分析其时间性能 整体思路 1 next 1 next 2 确定的 故不需要求解 2 从 next n 开始计算 依次计算 next n 1 next n 2 next 3 3 在计算 next j 的数值时以最大前后缀进行匹配 voidGetNext char T int next next 1 0 next 2 1 j T 0 k 0 for j 2 j for n j 2 n 1 n n 为要比较的前缀的最后一个字符的下标 m j n m 为要比较的后缀的第一个字符的下标 for i 1 i n i if T i T m i 1 break if i n 1 next j n 1 break if n 0 next j 1 3 4 假设在文本 ababcabccabccacbab 中查找模式 abccac 求分别采用 BF 算法和 KMP 算法进行串匹配过程中的字符比较次数 由此可知 用 BF 算法一共要进行 3 1 4 1 1 6 1 1 1 6 25 次比较方能匹配出 KMP 算法 next 0 1 1 1 1 2 由此可知 用 KMP 算法一共要进行 3 4 6 5 18 次比较方能匹配出 3 8 对于一个平面上对于一个平面上 n 个点的集合个点的集合 S 设计蛮力算法求集合 设计蛮力算法求集合 S 的凸包的一个极点 的凸包的一个极点 点集合中最左边或者最右边的点一定是凸包的一个极点 则求凸包的极点的问题转化为求点集合中最左边或者最右边的点一定是凸包的一个极点 则求凸包的极点的问题转化为求 点的点的 x 坐标最大或最小的点坐标最大或最小的点 int getPole int x int y int n int r 0 for inti 0 ix r r i return r 3 11 设计算法生成在设计算法生成在 n 个元素中包含个元素中包含 k 个元素的所有组合对象 个元素的所有组合对象 两种思路 两种思路 1 生成所有的组合 在组合中找元素个数为生成所有的组合 在组合中找元素个数为 k 个的组合 个的组合 伪代码 伪代码 1 初始化一个长度为 初始化一个长度为 n 的比特串的比特串 s 00 0 并将对应的子集输出 并将对应的子集输出 2 for i 1 i 2n i 注意不能书写成注意不能书写成 i 2n 2 1 s 2 2 判断判断 s 中中 1 的个数 若为的个数 若为 k 则将 则将 s 对应的子集输出 对应的子集输出 2 使用使用 k 层嵌套循环生成元素个数为层嵌套循环生成元素个数为 k 个的组合 个的组合 设设 k 3 n 个元素存储在数组个元素存储在数组 a 中 中 伪代码 伪代码 for i 1 i n 2 i for j i 1 i n 1 i for k j 1 i n i 输出输出 a i a j a k 构成的组合 构成的组合 3 13 美国有个连锁店叫 7 11 这个连锁店以前是每天 7 点开门 晚上 11 点关门 不过现在是全天 24 小时营业 有一天 有个人来到这个连锁店 买了 4 件商品 营业员拿起计算器敲了一下 说 总共是 7 11 顾客开玩笑说 所以你们商店就叫 7 11 营 业员没有理她 说 当然不是 我是把它们的价格相乘之后得到的 顾客说 相乘 你应该把他相加才对 营业员说 我弄错了 接着又算了一遍 结果让两个 人吃惊的是 计算结果也是 7 11 请问 这 4 件商品的价格是多少 参考代码 参考代码 include include int main long i j k m for i 1 i 711 4 i for j i j 711 3 j for k j k 711 2 k m 711 i j k if i j k m 711 1000000 cout i endl j endl k endl m endl return 0 输出结果为 价格分别是输出结果为 价格分别是 1 2 1 25 1 5 3 16 第四章第四章 4 1 分治算法求数组中最大元素4 1 分治算法求数组中最大元素位置位置的算法 的算法 include int Max int a int low int high void main int a 10 m for int i 0 ia max2 max1 max2 return max 4 3 在 n 个元素的一个全排列 用递归的方法找到 n 个不同元素的所有排列方式 Function 用递归的方法找到 n 个不同元素的所有排列方式 递归原理 令 E e1 en 表示 n 个元素的集合 我们的目标是生成该集合的所有排列方式 令 Ei 为 E 中移去元素 i 以后所获得的集合 perm X 表示集合 X 中元素的排列方式 ei perm X 表示在 perm X 中的每个排列方式的前面均加上 ei 以后所得到的排列方式 对于递归的基本部分 采用 n 1 当只有一个元素时 只可能产生一种排列方式 所以 perm E e 其 中e是E中 的 唯 一 元 素 当n 1时 perm E e1 perm E1 e2 perm E2 e3 perm E3 en perm En 这种递归定义形式是采用 n 个 perm X 来定义 perm E 其每个 X 包含 n 1 个元素 至此 一个完整的递归定义所需要的基本部分和递归部分都已完成 程序说明 程序把上述 perm E 的递归定义转变成一个 C 函数 这段代码输出所有前缀为 list 0 k 1 后缀为 list k m 的排列方式 调用 Perm list 0 n 1 将得到 list 0 n 1 的所有 n 个排列方 式 在该调用中 k 0 m n 1 因此排列方式的前缀为空 后缀为 list 0 n 1 产生的所有排列 方式 当 k m 时 仅有一个后缀 l i s t m 因此 list 0 m 即是所要产生的输出 当 k m 时 先 用 list k 与 l i s t k m 中的每个元素进行交换 然后产生 list k 1 m 的所有排列方式 并用它 作为 list 0 k 的后缀 Swap 是一个 inline 函数 它被用来交换两个变量的值 Perm 其定义见程序的正确性可用归纳法来证 明 include template inline void Swap T a b b temp template void Perm T list int k int m list is the array for sorting 生成 list k m 的所有排列方式 int i if k m 输出一个排列方式 for i 0 i m i 因为 list 0 至 list m 1 存储了交换后的数组值 cout list i cout endl else list k m 有多个排列方式 递归地产生这些排列方式 for i k i m i Swap list k list i Perm list k 1 m Swap list k list i 再换回去 void main char a 4 a b c d Perm a 1 3 4 7 S 中的点为平面上的点 坐标为 xi yi 为了将 S 分割为点的个数大致相同的两个子集 选取 x m 其 中 m 为 s 中各点 x 坐标的中位数 然后 m x max x min 2 4 8 打印版书上边有 4 10 众数问题 给定含有 n 个元素的多重集合 S 每个元素在 S 中出现的次数称为该元素的重数 多重集 S 总重数最大的元素称为众数 例如 S 6 1 2 2 2 3 5 多重集 S 的众数是 2 其重数为 3 算法如下 Template void zhongshu T a int n int sort a n 首先对数组 a 进行排序 max 0 curn 1 for i 1 ia i 1 if curn max max curn m a i 1 curn 1 else curn 第五章第五章 1 折半查找的前提必须是有序数组 分别查找 a 与 b 并重新构造 修改 构造一个数组 记录数组之间的所有元素 6 将 120 枚硬币分均分为 A B C 三组 即为 A B C 先将 A B 比较 如果 A B 重量不同 假 如 B 比 A 重 再将 B 与 C 比较 如果 B C 相同 则 A 有假币 如果 B C 不同 再讲 A C 比 较 如果 A C 相同 则 B 有假币 如果 A C 不同则 B 有假币 如果 A B 相同 则 C 有假币 8 1 n 1 2 略 第六章第六章 1 分治法将待求解问题分成若干子问题 先分别求解子问题 然后合并子问题的解得 到原问题的解 动态规划问题也是将待求解问题分成若干子问题 但是子问题往往不 是相互独立的 5 int IsIncluded int x int array n x 是否包含在数组中 for int i 0 i n i if array i x return 0 else return 1 int Left int k int array n int v 2n 1 1 n 实现 V k 的下标检索 int i 0 index 0 Int arraycount i Vcount i For i 0 i n i arraycount i 0 Vcount i 0 for i 0 i n i temp i array i for i 0 i n i if temp i k temp i 0 相当于去掉 k 这个城市 for i 0 i n i if temp i i arraycount i for index 0 index 2n 1 1 index for i 0 i n i if V index i i Vcount i for i 0 i n i if arraycount i Vcount i return index for i 0 i n i Vcount i 0 return 0 void TSP int d 4 8 int c 4 4 int V 8 3 int n int i 0 j 0 k 0 for i 1 i n i V 为空时 给赋值 d i 0 c i 0 for j 1 j 7 j 按列遍历不同集合 1 2 3 1 2 1 3 for i 1 i n i 遍历城市 1 2 3 if IsIncluded i V j i 必须不在集合中 否则就属于经过两次 不符合题意 for k 0 k 3 k 分别试探集合中的每一点 取最小值 if V j k 0 end offor i 1 i n i 遍历城市 1 2 3 end of for j 1 j int pow 2 n 1 j for k 0 k 3 k 分别试探下一步为集合中的任何一点 取最小值 if V 7 k 0 void main int V 8 3 0 0 0 0 0 1 0 0 2 0 0 3 0 1 2 0 1 3 0 2 3 1 2 3 int c 4 4 0 3 6 7 5 0 2 3 6 4 0 2 3 7 5 0 int d 4 8 0 i 0 j 0 for i 0 i 4 i for j 0 j 8 j d i j 1000 假设 1000 为无穷大 TSP d c V 4 printf The least road is d n d 0 7 8 typedef struct int nCoin 使用硬币数量 以下两个成员是为了便于构造出求解过程的展示 int lastSum 上一个状态 int addCoin 从上一个状态达到当前状态所用的硬币种类 state state sum malloc sizeof state total 1 init for i 0 i total i sum i nCoin INF sum 0 nCoin 0 sum 0 lastSum 0 for i 1 i total i for j 0 j 0 sum i nCoin sum i coin j nCoin 1 sum i lastSum j sum i addCoin coin j k k 1 Printf 所需最少的兑换张数为 d 分别为 d k sum i addcoin if sum total nCoin INF printf can t make change n return 0 else output 时间复杂性 最坏为 y n2 最好为 y n 其中 y 表示要兑换的零钱数 9 sum 20 ncoin sum 20 1 ncoin 1 sum 19 1 ncoin 2 20 Sum 20 ncoin sum 20 2 ncoin 1 sum 2 2 10 10 经过一系列运算 可以得出最优解为 Sum 20 ncoin sum 20 5 1 4 10 int ack int int val new int m 1 int ind new int m 1 for i 1 i m i ind i 1 val i 1 ind 0 0 val 0 1 while ind m n val 0 ind 0 printf d val 0 for j 1 j m j if 1 ind j 1 val j val j 1 ind j 0 if val j ind j 1 break ind j val j val j 1 printf n printf iind i val i n for i 0 iC 4 1 x i 1 将第 i 个物品放入背包 4 2 C C w i 4 3 i 5 x i C w i 得出 该背包问题的求解过程为 x 1 1 c 15 1 14v 6x 2 1 c 14 2 12 V 6 10 10 x 3 1 c 12 4 8V 16 18 34x 4 1 c 8 5 3 V 34 15 49 x 5 1 c 3 1 2V 49 3 52 x 6 2 3 c 0 V 52 5 2 3 156 3 最优值为 156 3 最优解为 1 1 1 1 1 2 3 0 7 5 根据会场安排问题的定义 首先将问题简化为 找出两个活动 若 ei 和 ej 满足 si fj 或 sj fi 则称这两个活动相容 即问题转化为 要求找出最多相容会 场集合 A 问题简化为对相容会场 A 的寻找 下面用贪心方法分析过程 根据题意 选取一种量度标准 然后按量度标准对 n 个输入排序 按顺序一次输入一个量 如果这个输入和当前已构成在这种量度意义下的部分最优解加在一起不能产生 一个可行解 则不把此输入加到这部分解中 这种能够得到某种量度意义下的最 优解的分级处理方法就是贪心方法 那么问题转化为对度量标准的寻找 判断各 个数据是否可以包含在解向量中去 然后根据目标函数来选择最优解 综上贪心解法 1 将所有活动按结束时间排序 得到活动集合 E e1 e2 en 2 先将 e1 选入结果集合 A 中 即 A e1 3 依次扫描每一个活动 ei 如果 ei 的开始时间晚于最后一个选入 A 的活动 ej 的结束时间 则将 ei 选入 A 中 否则放弃 ei 最优解证明 若 E e1 e2 en 是按结束时间排序的活动集合 则 e1 具有最早的结束时间 设存在一个最优安排 A 不包含 e1 并以 ei 开始 则易见 A ei e1 也是 最优的活动安排 依此类推 即可推出上述活动都为 A 中的不相容最优活动 7 6书上有 7 7 贪心选择策略 假设原问题为 T 而我们已经知道了某个最优服务系列 即最优解为 A t 1 t 2 t n 其中 t i 为第 i 个用户需要的服务时间 则每个用户等待时间为 T 1 t 1 T 2 t 1 t 2 T n t 1 t 2 t 3 t n 那么总等待时问 即最优值为 TA n t 1 n 1 t 2 n 1 j t i 2 t n 1 t n 由于平均等待时间是 n 个顾客等待时间的总和除以 n 故本题实际上就是求使顾 客等待时间的总和最小的服务次序 本问题采用贪心算法求解 贪心策略如下 对服务时间最短的顾客先服务的贪心 选择策略 首先对需要服务时间最短的顾客进行服务 即做完第一次选择后 原 问题 T 变成了需对 n 1 个顾客服务的新问题 T 新问题和原问题相同 只是问 题规模由 n 减小为 n 1 基于此种选择策略 对新问题 T 选择 n 1 顾客中选择 服务时间最短的先进行服务 如此进行下去 直至所有服务都完成为止 算法实现 由多处最优服务次序问题具有贪心选择性质和最优子结构性质 容易证明算法 greedy 的正确性 本算法采用最短服务时间优先的贪心策略 首先将每个顾客 所需要的服务时间从小到大排序 然后申请 2 个数组 st 是服务数组 st j 为第 j 个队列上的某一个顾客的等待时间 su 是求和数组 su j 的值为第 j 个队列上 所有顾客的等待时间 double greedy vectorx int s vectorst s 1 0 vectorsu s 1 0 int n x size sort x begin x end int i 0 j 0 while i n st j x i su j st j i j if j s j 0 循环分配顾客到每一个服务点上 double t 0 for i 0 i s i t su i t n return t 算法复杂性分析 程序主要是花费在对各顾客所需服务时间的排序和贪心算法 即计算平均服务时 间上面 其中 贪心算法部分只有一重循环影响时间复杂度 其时间复杂度为 O n 而排序算法的时间复杂度为 O nlogn 因此 综合来看算法的时间复杂 度为 O nlogn 第八章第八章 1 图着色问题 m 着色回溯法递归 输入 n 为顶点个数 颜色数 m 图的邻接矩阵 c 输出 n 个顶点的着色 x 递归方法求解 include using namespace std bool c 6 6 int x 6 int m 3 nt n 5 bool ok int k 判断对顶点 k 着色以 后是否合法着色 int i for i 1 i k i if c k i 1 return true void output int x cout The feasible result is endl for int i 1 i n i cout x i cout n output x else for int i 1 i m i x t i if ok t backtrack t 1 x t 0 int main int i j for i 1 i 5 i for j 1 j 5 j c i j false c 1 2 true c 1 3 true c 2 3 true c 2 4 true c 2 5 true c 3 5 true c 4 5 true c 2 1 true c 3 1 true c 3 2 true c 4 2 true c 5 2 true c 5 3 true c 5 4 true backtrack 1 cout endl return 0 2 用递归函数设计八皇后问题的回溯算法 八皇后问题是一个古老而著名的问题 是回溯算法的典型例题 该问题是19世纪著名的数 学家高斯1850年提出 在8 8格的国际象棋盘上摆放8个皇后 使其不能互相攻击 即任意 两个皇后都不能处于同一行 同一列或同一斜线上 问有多少种摆法 英国某著名计算机 图形图像公司面试题 解析 递归实现 n 皇后问题 算法分析 数组 a b c 分别用来标记冲突 a 数组代表列冲突 从 a 0 a 7 代表第0列到第7列 如 果某列上已经有皇后 则为1 否则为0 数组 b 代表主对角线冲突 为 b i j 7 即从 b 0 b 14 如果某条主对角线上已经有皇后 则为1 否则为0 数组 c 代表从对角线冲突 为 c i j 即从 c 0 c 14 如果某条从对角线上已经有皇后 则为1 否则为0 C 代码如下 实现 N 皇后问题 include define QUEENNUM 8 define QCROSSNUM QUEENNUM 2 1 static char QueenArray QUEENNUM QUEENNUM static int a QUEENNUM static int b QCROSSNUM static int c QCROSSNUM static int iQueenNum 0 记录皇后问题总共有多少中摆法 void Queen int i i 为行数 int main int iLine iColumn for iLine 0 iLine QUEENNUM iLine a iLine 0 for iColumn 0 iColumn QUEENNUM iColumn QueenArray iLine iColumn for iLine 0 iLine QCROSSNUM iLine b iLine c iLine 0 Queen 0 return 0 void Queen int i int iColumn for iColumn 0 iColumn QUEENNUM iColumn if a iColumn 0 皇后标志 a iColumn 1 b i iColumn 7 1 c i iColumn 1 if i QUEENNUM 1 Queen i 1 else int iLine iColumn printf The d th state is n iQueenNum for iLine 0 iLine QUEENNUM iLine for iColumn 0 iColumn QUEENNUM iColumn printf c QueenArray iLine iColumn printf n printf n n 后面无论如何也无法放置皇后 则回溯重置 QueenArray i iColumn a iColumn 0 b i iColumn 7 0 c i iColumn 0 5 给定背包容量 W 20 以及 6 个物品 重量为 5 3 2 10 4 2 价值为 11 8 15 18 12 6 有 3 道题不能确定 5 6 8 第九章 第九章 2 如书上 p188 9 2 1 TSP 问题 5 解 应用贪心法求得近似解 1 4 2 3 其路径代价为 3 5 7 6 21 这 可以作为该问题的上界 把每一个任务的最小代价相加 可以得到下界 3 5 3 6 17 所以 目标函数的界为 17 21 限界函数为 n lb v 第 k 行的最小值 k i 1 搜 索空间如下 7 最优解为 4312 最优值为 38 搜索空间树略略 4 a lb 26 4 start lb 17 1 a lb 17 2 a lb 22 3 a lb 18 2 b lb 24 3 b lb 25 4 b lb 17 2 c lb 21 3 d lb 21 表示该结点被丢弃 结点上方的数字表示搜索顺序 2 35 6 7 8 1 9 11 12 10 1 b lb 22 2 b lb 25 4 b lb 18 13 2 c lb 2