第四章 算法策略

第四章基本的算法策略 4 1迭代算法4 2蛮力算法4 3分而治之算法4 4贪婪算法4 5动态规划4 6算法策略间的比较 4 1迭代算法 4 1 1递推法4 1 2倒推法4 1 3迭代法解方程 4 1 1递推法 例1 兔子繁殖问题问题描述 一对兔子从出生后第三个月开始 每月生一对小兔子 小兔子到第三个月又开始生下一代小兔子 假若兔子只生不死 一月份抱来一对刚出生的小兔子 问一年中每个月各有多少只兔子 问题分析 因一对兔子从出生后第三个月开始每月生一对小兔子 则每月新下小兔子的对儿数 用斜体数字表示 显然由前两个月的小兔子的对儿数决定 则繁殖过程如下 一月二月三月四月五月六月 111 1 22 1 33 2 55 3 8 算法1 main inti a 1 b 1 print a b for i 1 i 10 i c a b print c a b b c 数学建模 y1 y2 1 yn yn 1 yn 2 n 3 4 5 算法2 表4 1递推迭代表达式123456789abc a ba b cb a cc a ba b cb a c 由此归纳出可以用 c a b a b c b c a 做循环 不变式 算法2如下 main inti a 1 b 1 print a b for i 1 i 4 i c a b a b c b c a print a b c 算法2 最后输出的并不是12项 而是2 3 4共14项 表4 2递推迭代表达式123456789aba a bb a ba a bb a b 由此归纳出可以用 a a b b a b 做循环 不变式 从而得到以下算法3 main inti a 1 b 1 print a b for i 1 i 5 i a a b b a b print a b 算法3 例2 求两个整数的最大公约数 数学建模 辗转相除法是根据递推策略设计的 不妨设两个整数a b且a除以b商x余c 则a bx c 不难看出a b的最大公约数也是c的约数 一个数能整除等式左边就一定能整除等式的右边 则a b的最大公约数与b c的最大公约数相同 同样方法推出b c的最大公约数与 直到余数为0时 除数即为所求的最大公约数 算法设计 循环 不变式 第一次是求a b相除的余数c 第二次还是求 a b 相除的余数 经a b b c操作 就实现了第二次还是求 a b 相除的余数 这就找到了循环不变式 循环在余数c为0时结束 算法如下 main inta b input a b if b 0 print dataerror return else c amodb whilec0 a b b c c amodb print b 4 1 2倒推法 所谓倒推法 是对某些特殊问题所采用的违反通常习惯的 从后向前推解问题的方法 如下面的例题 因不同方面的需求而采用了倒推策略 例1在不知前提条件的情况下 经过从后向前递推 从而求解问题 即由结果倒过来推解它的前提条件 又如例2由于存储的要求 而必须从后向前进行推算 另外 在对一些问题进行分析或建立数学模型时 从前向后分析问题感到比较棘手 而采用倒推法 如例3 则问题容易理解和解决 下面分别看这几个例子 例1 猴子吃桃问题一只小猴子摘了若干桃子 每天吃现有桃的一半多一个 到第10天时就只有一个桃子了 求原有多少个桃 数学模型 每天的桃子数为 a10 1 a9 1 a10 2 a8 1 a9 2 a10 1 递推公式为 ai 1 ai 1 2I 9 8 7 6 1算法如下 main inti s s 1 for i 9 i 1 i i 1 s s 1 2print s 例2 输出如图4 1的杨辉三角形 限定用一个一维数组完成 数学模型 上下层规律较明显 中间的数等于上行左上 右上两数之和 问题分析 题目中要求用一个一维数组即完成 数组空间一定是由下标从小到大利用的 这样其实杨辉三角形是按下图4 2形式存储的 若求n层 则数组最多存储n个数据 111121133114641 图4 1杨辉三角形 111121133114641 图4 2杨辉三角形存储格式 算法设计 A 1 A i 1A j A j A j 1 j i 1 i 2 2i行i 1行i 1行 算法如下 main intn i j a 100 input n print 1 print 换行符 a 1 a 2 1 print a 1 a 2 print 换行符 for i 3 i1 j j 1 a j a j a j 1 for j 1 j i j j 1 print a j print 换行符 例3 穿越沙漠问题用一辆吉普车穿越1000公里的沙漠 吉普车的总装油量为500加仑 耗油率为1加仑 公里 由于沙漠中没有油库 必须先用这辆车在沙漠中建立临时油库 该吉普车以最少的耗油量穿越沙漠 应在什么地方建油库 以及各处的贮油量 问题分析 1 先看一简单问题 有一位探险家用5天的时间徒步横穿A B两村 两村间是荒无人烟的沙漠 如果一个人只能担负3天的食物和水 那么这个探险家至少雇几个人才能顺利通过沙漠 A城雇用一人与探险家同带3天食物同行一天 然后被雇人带一天食物返回 并留一天食物给探险家 这样探险家正好有3天的食物继续前行 并于第三天打电话雇B城人带3天食物出发 第四天会面他们会面 探险家得到一天的食物赴B城 如图4 3主要表示了被雇用二人的行程 AB图4 3被雇用二人的行程 2 贮油点问题要求要以最少的耗油量穿越沙漠 即到达终点时 沙漠中的各临时油库和车的装油量均为0 这样只能从终点开始向前倒着推解贮油点和贮油量 数学模型 根据耗油量最少目标的分析 下面从后向前分段讨论 第一段长度为500公里且第一个加油点贮油为500加仑 第二段中为了贮备油 吉普车在这段的行程必须有往返 下面讨论怎样走效率高 1 首先不计方向这段应走奇数次 保证最后向前走 2 每次向前行进时吉普车是满载 3 要能贮存够下一加油点的贮油量 路上耗油又最少 下图是满足以上条件的最佳方案 此段共走3次 第一 二次来回耗油2 3贮油1 3 第三次耗油1 3贮油2 3 所以第二个加油点贮油为1000加仑 由于每公里耗油率为1加仑 则此段长度为500 3公里 第三段与第二段思路相同 下图是一最佳方案此段共走5次 第一 二次来回耗油2 5贮油3 5 第三 四次来回耗油2 5贮油3 5 第五次耗油1 5贮油4 5 第三个加油点贮油为1500加仑 此段长度为500 5 500 5公里第二 第三终点 贮油点 500 贮油点 1000 贮油点 1500 图4 4贮油点及贮油量示意 综上分析 从终点开始分别间隔500 500 3 500 5 500 7 公里 设立贮油点 直到总距离超过1000公里 每个贮油点的油量为500 1000 1500 算法设计 由模型知道此问题并不必用倒推算法解决 只是分析过程用的是倒推法 只需通过累加算法就能解决 变量说明 dis表示距终点的距离 1000 dis则表示距起点的距离 k表示贮油点从后到前的序号 desert intdis k oil k dis 500 k 1 oil 500 do print storepoint k distance 1000 dis oilquantity oil k k 1 dis dis 500 2 k 1 oil 500 k while dis 1000 oil 500 k 1 1000 dis 2 k 1 print storepoint k distance 0 oilquantity oil 4 1 3迭代法解方程 迭代法解方程的实质是按照下列步骤构造一个序列x0 x1 xn 来逐步逼近方程f x 0的解 1 选取适当的初值x0 2 确定迭代格式 即建立迭代关系 需要将方程f x 0改写为x x 的等价形式 构造序列x0 x1 xn 即先求得x1 x0 再求x2 x1 如此反复迭代 就得到一个数列x0 x1 xn 若这个数列收敛 即存在极值 且函数 x 连续 则很容易得到这个极限值x 就是方程f x 0的根 例1 迭代法求方程组根算法说明 方程组解的初值X x0 x1 xn 1 迭代关系方程组为 xi gi X i 0 1 n 1 w为解的精度 则算法如下 for i 0 iwandk maxn for i 0 i n i print i 变量的近似根是 x i 例2 牛顿迭代法牛顿迭代法又称为切线法 它比一般的迭代法有更高的收敛速度 如图4 5所示 首先 选择一个接近函数f x 零点的x0 计算相应的f x0 和切线斜率f x0 这里f 表示函数f的导数 然后我们计算穿过点 x0 f x0 且斜率为f x0 的直线方程为 和x轴的交点的x坐标 也就是求如下方程的解 将新求得交点的x坐标命名为x1 如图4 5所示 通常x1会比x0更接近方程f x 0的解 接下来用x1开始下一轮迭代 图4 5牛顿迭代法示意图 迭代公式可化简为 此公式就是有名的牛顿迭代公式 已经证明 如果f 是连续的 并且待求的零点x是孤立的 那么在零点x周围存在一个区域 只要初始值x0位于这个邻近区域内 那么牛顿法必定收敛 下面给出用牛顿迭代法 求形如ax3 bx2 cx d 0方程根的算法 系数a b c d的值依次为1 2 3 4 由主函数输入 求x在1附近的一个实根 求出根后由主函数输出 main floata b c d fx print 输入系数a b c d input a b c d fx f a b c d printf 方程的根为 fx floatf a b c d floata b c d floatx1 1 x0 f0 f1 do x0 x1 f0 a x0 b x0 c x0 d f1 3 a x0 2 b x0 c x1 x0 f0 f1 while fabs x1 x0 1e 4 return x1 令 a0 b0 a b c0 a0 b0 2 若f c0 0 则c0为方程f x 0的根 否则 若f a0 与f c0 异号 即f a0 f c0 0 则令 a1 b1 a0 c0 若f b0 与f c0 异号 即f b0 f c0 0 则令 a1 b1 c0 b0 依此做下去 当发现f cn 0时 或区间 an bn 足够小 比如 an bn 0 0001时 就认为找到了方程的根 用二分法求一元非线性方程f x x 3 2 2x 2 8 0 其中 表示幂运算 在区间 0 2 上的近似实根r 精确到0 0001 算法如下 图4 6二分法求解方程示意 例3 二分法求解方程f x 0根用二分法求解方程f x 0根的前提条件是 f x 在求解的区间 a b 上是连续的 且已知f a 与f b 异号 即f a f b 0 main floatx x1 0 x2 2 f1 f2 f print inputa b f a f b 0 printf Noroot return do x x1 x2 2 f x x x 2 2 x x 8 if f 0 break if f1 f 0 0 x1 x f1 x1 x1 x1 2 2 x1 x1 8 elsex2 x while fabs f 1e 4 print root x 4 2蛮力法 4 2 1枚举法4 2 2其它范例 蛮力法是基于计算机运算速度快这一特性 在解决问题时采取的一种 懒惰 的策略 这种策略不经过 或者说是经过很少的 思考 把问题的所有情况或所有过程交给计算机去一一尝试 从中找出问题的解 蛮力策略的应用很广 具体表现形式各异 数据结构课程中学习的 选择排序 冒泡排序 插入排序 顺序查找 朴素的字符串匹配等 都是蛮力策略具体应用 比较常用还有枚举法 盲目搜索算法等 本节介绍枚举法和其它一些小的范例 第五章介绍盲目搜索算法 4 2 1枚举法 枚举 enumerate 法 穷举法 是蛮力策略的一种表现形式 也是一种使用非常普遍的思维方法 它是根据问题中的条件将可能的情况一一列举出来 逐一尝试从中找出满足问题条件的解 但有时一一列举出的情况数目很大 如果超过了我们所能忍受的范围 则需要进一步考虑 排除一些明显不合理的情况 尽可能减少问题可能解的列举数目 用枚举法解决问题 通常可以从两个方面进行算法设计 1 找出枚举范围 分析问题所涉及的各种情况 2 找出约束条件 分析问题的解需要满足的条件 并用逻辑表达式表示 例1 百钱百鸡问题 中国古代数学家张丘建在他的 算经 中提出了著名的 百钱百鸡问题 鸡翁一 值钱五 鸡母一 值钱三 鸡雏三 值钱一 百钱买百鸡 翁 母 雏各几何 算法设计1 通过对问题的理解 读者可能会想到列出两个三元一次方程 去解这个不定解方程 就能找出问题的解 这确实是一种办法 但这里我们要用 懒惰 的枚举策略进行算法设计 设x y z分别为公鸡 母鸡 小鸡的数量 尝试范围 由题意给定共100钱要买百鸡 若全买公鸡最多买100 5 20只 显然x的取值范围1 20之间 同理 y的取值范围在1 33之间 z的取值范围在1 100之间 约束条件 x y z 100且5 x 3 y z 3 100 算法1如下 main intx y z for x 1 x 20 x x 1 for y 1 y 34 y y 1 for z 1 z 100 z z 1 if 100 x y zand100 5 x 3 y z 3 print thecocknumberis x print thehennumberis y print thechicknumberis z 算法分析 以上算法需要枚举尝试20 34 100 68000次 算法的效率显然太低算法设计2 在公鸡 x 母鸡 y 的数量确定后 小鸡的数量z就固定为100 x y 无需再进行枚举了此时约束条件只有一个 5 x 3 y z 3 100算法2如下 main intx y z for x 1 x 20 x x 1 for y 1 y 33 y y 1 z 100 x y if zmod3 0and5 x 3 y z 3 100 print thecocknumberis x print thehennumberis y print thechicknumberis z 算法分析 以上算法只需要枚举尝试20 33 660次 实现时约束条件又限定Z能被3整除时 才会判断 5 x 3 y z 3 100 这样省去了z不整除3时的算术计算和条件判断 进一步提高了算法的效率 例2 解数字迷 ABCAB ADDDDDD算法设计1 按乘法枚举1 枚举范围为 A 3 9 A 1 2时积不会得到六位数 B 0 9 C 0 9六位数表示为A 10000 B 1000 C 100 A 10 B 共尝试800次 2 约束条件为 每次尝试 先求六位数与A的积 再测试积的各位是否相同 若相同则找到了问题的解 测试积的各位是否相同比较简单的方法是 从低位开始 每次都取数据的个位 然后整除10 使高位的数字不断变成个位 并逐一比较 算法1如下 main intA B C D E E1 F G1 G2 i for A 3 AG2 break if i 6 print F A E 算法说明1 算法中对枚举出的每一个五位数与A相乘 结果存储在变量E中 然后 测试得到的六位数E是否各个位的数字都相同 鉴于要输出结果 所以不要改变计算结果 而另设变量E1 用于测试运算 算法分析1 以上算法的尝试范围是A 3 9 B 0 9 C 0 9 共尝试800次 每次 不是一个好的算法 算法设计2 将算式变形为除法 DDDDDD A ABCAB 此时只需枚举A 3 9D 1 9 共尝试7 9 63次 每次尝试 测试商的万位 十位与除数是否相同 千位与个位是否相同 都相同时为解 算法2如下 main intA B C D E F for A 3 A 9 A for D 1 D 9 D E D 100000 D 10000 D 1000 D 100 D 10 D if EmodA 0 F E A if F 10000 Aand Fmod100 10 A if F 1000 Fmod10 print F A E 蛮力法的表现形式非常多 如第三章3 2 4例题 3 2 5例1及本章下一节4 3 3例4的算法1等 本节将通过蛮力策略 用算法模拟问题中所描述的全部过程和全部状态 来找出问题的解 并与经过数学建模后的算法进行效率上的比较 4 2 2其它范例 例3 狱吏问题某国王对囚犯进行大赦 让一狱吏n次通过一排锁着的n间牢房 每通过一次 按所定规则转动n间牢房中的某些门锁 每转动一次 原来锁着的被打开 原来打开的被锁上 通过n次后 门锁开着的 牢房中的犯人放出 否则犯人不得获释 转动门锁的规则是这样的 第一次通过牢房 要转动每一把门锁 即把全部锁打开 第二次通过牢房时 从第二间开始转动 每隔一间转动一次 第k次通过牢房 从第k间开始转动 每隔k 1间转动一次 问通过n次后 那些牢房的锁仍然是打开的 算法设计1 1 用n个空间的一维数组a n 每个元素记录一个锁的状态 1为被锁上 0为被打开 2 用数学运算方便模拟开关锁的技巧 对i号锁的一次开关锁可以转化为算术运算 a i 1 a i 3 第一次转动的是1 2 3 n号牢房 第二次转动的是2 4 6 号牢房 第三次转动的是3 6 9 号牢房 第i次转动的是i 2i 3i 4i 号牢房 是起点为i 公差为i的等差数列 4 不做其它的优化 用蛮力法通过循环模拟狱吏的开关锁过程 最后当第i号牢房对应的数组元素a i 为0时 该牢房的囚犯得到大赦 算法1如下 main1 int a i j n input n a calloc n 1 sizeof int for i 1 i n i a i 1 for i 1 i n i for j i j n j j i a i 1 a i for i 1 i n i if a i 0 print i isfree 算法分析 以一次开关锁计算 算法的时间复杂度为n 1 1 2 1 3 1 n O nlogn 问题分析 转动门锁的规则可以有另一种理解 第一次转动的是编号为1的倍数的牢房 第二次转动的是编号为2的倍数的牢房 第三次转动的是编号为3的倍数的牢房 则狱吏问题是一个关于因子个数的问题 令d n 为自然数n的因子个数 这里不计重复的因子 如4的因子为1 2 4共三个因子 而非1 2 2 4 则d n 有的为奇数 有的为偶数 见下表 表4 3编号与因数个数的关系n12345678910111213141516 d n 1223242434262445 数学模型1 上表中的d n 有的为奇数 有的为偶数 由于牢房的门开始是关着的 这样编号为i的牢房 所含1 i之间的不重复因子个数为奇数时 牢房最后是打开的 反之 牢房最后是关闭的 算法设计2 1 算法应该是求出每个牢房编号的不重复的因子个数 当它为奇数时 这里边的囚犯得到大赦 2 一个数的因子是没有规律的 只能从1 n枚举尝试 算法2如下 main2 ints i j n input n for i 1 i n i s 1 for j 2 j i j j if imodj 0 s s 1 if smod2 1 print i isfree 算法分析 狱吏开关锁的主要操作是a i 1 a i 共执行了n 1 1 2 1 3 1 n 次 时间近似为复杂度为O nlogn 使用了n个空间的一维数组 算法2没有使用辅助空间 但由于求一个编号的因子个数也很复杂 其主要操作是判断imodj是否为0 共执行了n 1 2 3 n 次 时间复杂度为O n2 数学模型2 仔细观察表4 3 发现当且仅当n为完全平方数时 d n 为奇数 这是因为n的因子是成对出现的 也即当n a b且a b时 必有两个因子a b 只有n为完全平方数 也即当n a2时 才会出现d n 为奇数的情形 算法设计3 这时只需要找出小于n的平方数即可 算法3如下 main3 ints i j n input n for i 1 i n i if i i n print i isfree elsebreak 由此算法我们应当注意 在对运行效率要求较高的大规模的数据处理问题时 必须多动脑筋找出效率较高的数学模型及其对应的算法 4 3分而治之算法 4 3 1分治算法框架4 3 2二分法4 3 3二分法变异4 3 4其它分治方法 4 3 1分治算法框架 1 算法设计思想分治法求解问题的过程是 将整个问题分解成若干个小问题后分而治之 如果分解得到的子问题相对来说还太大 则可反复使用分治策略将这些子问题分成更小的同类型子问题 直至产生出方便求解的子问题 必要时逐步合并这些子问题的解 从而得到问题的解 分治法的基本步骤在每一层递归上都有三个步骤 1 分解 将原问题分解为若干个规模较小 相互独立 与原问题形式相同的子问题 2 解决 若子问题规模较小而容易被解决则直接解 否则再继续分解为更小的子问题 直到容易解决 3 合并 将已求解的各个子问题的解 逐步合并为原问题的解 有时问题分解后 不必求解所有的子问题 也就不必作第三步的操作 比如折半查找 在判别出问题的解在某一个子问题中后 其它的子问题就不必求解了 问题的解就是最后 最小 的子问题的解 分治法的这类应用 又称为 减治法 多数问题需要所有子问题的解 并由子问题的解 使用恰当的方法合并成为整个问题的解 比如合并排序 就是不断将子问题中已排好序的解合并成较大规模的有序子集 2 适合用分治法策略的问题当求解一个输入规模为n且取值又相当大的问题时 用蛮力策略效率一般得不到保证 若问题能满足以下几个条件 就能用分治法来提高解决问题的效率 1 能将这n个数据分解成k个不同子集合 且得到k个子集合是可以独立求解的子问题 其中1 k n 2 分解所得到的子问题与原问题具有相似的结构 便于利用递归或循环机制 在求出这些子问题的解之后 就可以推解出原问题的解 分治法的一般的算法设计模式如下 Divide and Conquer intn n为问题规模 if n n0 n0为可解子问题的规模 解子问题 return 子问题的解 for i 1 i k i 分解为较小子问题p1 p2 pk yi Divide and Conquer Pi 递归解决Pi T MERGE y1 y2 yk 合并子问题 return T 其中 P 表示问题P的规模 n0为一阈值 表示当问题P的规模不超过n0时 问题已容易直接解出 不必再继续分解 算法MERGE y1 y2 yk 是该分治法中的合并子算法 用于将P的子问题P1 P2 Pk的相应的解y1 y2 yk合并为P的解 在一些问题中不需要这一步 如析半查找 4 3 2中的例1 例2等 4 3 2二分法 不同于现实中对问题 或工作 的分解 可能会考虑问题 或工作 的重点 难点 承担人员的能力等来进行问题的分解和分配 在算法设计中每次一个问题分解成的子问题个数一般是固定的 每个子问题的规模也是平均分配的 当每次都将问题分解为原问题规模的一半时 称为二分法 二分法是分治法较常用的分解策略 数据结构课程中的折半查找 归并排序等算法都是采用此策略实现的 例1 金块问题 老板有一袋金块 共n块 最优秀的雇员得到其中最重的一块 最差的雇员得到其中最轻的一块 假设有一台比较重量的仪器 我们希望用最少的比较次数找出最重的金块 算法设计1 比较简单的方法是逐个的进行比较查找 先拿两块比较重量 留下重的一个与下一块比较 直到全部比较完毕 就找到了最重的金子 算法类似于一趟选择排序 算法如下 maxmin floata intn max min a 1 for i 2ia i min a i 算法分析1 算法中需要n 1次比较得到max 最好的情况是金块是由小到大取出的 不需要进行与min的比较 共进行n 1次比较 最坏的情况是金块是由大到小取出的 需要再经过n 1次比较得到min 共进行2 n 2次比较 至于在平均情况下 A i 将有一半的时间比max大 因此平均比较数是3 n 1 2 算法设计2 问题可以简化为 在含n n是2的幂 n 2 个元素的集合中寻找极大元和极小元 用分治法 二分法 可以用较少比较次数地解决上述问题 1 将数据等分为两组 两组数据可能差1 目的是分别选取其中的最大 小 值 2 递归分解直到每组元素的个数 2 可简单地找到最大 小 值 3 回溯时将分解的两组解大者取大 小者取小 合并为当前问题的解 算法2递归求取最大和最小元素floata n maxmin inti intj float 算法分析 MAXMIN需要的元素比较数是多少呢 如果用T n 表示这个数 则所导出的递归关系式是 当n是2的幂时 即对于这个某个正整数k n 2k 有 可以证明 任何以元素比较为基础的找最大和最小元素的算法 其元素比较下界均为次 因此 过程MAXMIN在这种意义上是最优的 例2 残缺棋盘残缺棋盘是一个有2k 2k k 1 个方格的棋盘 其中恰有一个方格残缺 图4 7给出k 1时各种可能的残缺棋盘 其中残缺的方格用阴影表示 号 号 号 号图4 7四种三格板这样的棋盘我们称作 三格板 残缺棋盘问题就是要用这四种三格板覆盖更大的残缺棋盘 在此覆盖中要求 1 两个三格板不能重叠2 三格板不能覆盖残缺方格 但必须覆盖其他所有的方格在这种限制条件下 所需要的三格板总数为 2k 2k 1 3 算法设计1 下面用分而治之方法解决残缺棋盘问题 1 问题分解过程如下 以k 2时的问题为例 用二分法进行分解 得到的是如下图4 8 用双线划分的四个k 1的棋盘 但要注意这四个棋盘 并不都是与原问题相似且独立的子问题 因为当如图4 8中的残缺方格在左上部时 第1个子问题与原问题相似 而右上角 左下角和右下角三个子棋盘 也就是图中标识为2 3 4号子棋盘 并不是原问题的相似子问题 自然也就不能独立求解了 当使用一个 号三格板 图中阴影 覆盖2 3 4号三个子棋盘的各一个方格后 如4 8右图所示 我们把覆盖后的方格 也看作是残缺方格 称为 伪 残缺方格 这时的2 3 4号子问题就是独立且与原问题相似的子问题了 图4 8一个4 4的残缺棋盘 从以上例子还可以发现 当残缺方格在第1个子棋盘 用 号三格板覆盖其余三个子棋盘的交界方格 可以使另外三个子棋盘转化为独立子问题 同样地 如下图4 9所示 当残缺方格在第2个子棋盘时 则首先用 号三格板进行棋盘覆盖 当残缺方格在第3个子棋盘时 则首先用 号三格板进行棋盘覆盖 当残缺方格在第4个子棋盘时 则首先用 号三格板进行棋盘覆盖 这样就使另外三个子棋盘转化为独立子问题 如下图4 9 同样地k 1 2 3 4 都是如此 k 1为停止条件 图4 9其它4 4的残缺棋盘 2 棋盘的识别棋盘的规模是一个必要的信息 有了这个信息 只要知道其左上角的左上角方格所在行 列就可以唯一确定一个棋盘了 残缺方格或 伪 残缺方格直接用行 列号记录 tr棋盘中左上角方格所在行 tc棋盘中左上角方格所在列 dr残缺方块所在行 dl残缺方块所在列 size棋盘的行数或列数 数据结构设计 用二维数组board 模拟棋盘 覆盖残缺棋盘所需要的三格板数目为 size2 1 3将这些三格板编号为1到 size2 1 3 则将残缺棋盘三格板编号的存储在数组board 的对应位置中 这样输出数组内容就是问题的解 结合图4 9 理解算法 算法如下 intamount 0 main intsize 1 x y input k for i 1 i k i size size 2 print inputincompletepane input x y Cover 0 0 x y size 图4 9一个4 4的残缺棋盘及其解 Cover inttr inttc intdr intdc intsize if size 2 return intt amount 所使用的三格板的数目s size 2 子问题棋盘大小if dr tr s elseif dr tc s 残缺方格位于右上象限 Cover tr tc s dr dc s Board tr s 1 tc s 1 t 覆盖 号三格板Board tr s tc s 1 t Board tr s tc s t Cover tr tc tr s 1 tc s 1 s 覆盖其余部分Cover tr s tc tr s tc s 1 s Cover tr s tc s tr s tc s s elseif dr tr s elseif dr tr s 算法分析 因为要覆盖 size2 1 3个三格板 所以算法的时间复杂性为 size2 4 3 3二分法变异 例 求最长连续不升数列有一组数据找出其中最长的连续不升数列算法设计 此问题用二分法分解后的两个子序列 子问题 并不独立 因为有可能最长的连续不升数列正好存在于两个子序列的连接位置 如果将所给的序列a 1 n 分为长度相等的2段a 1 n 2 和a n 2 1 n 则a 1 n 的最长连续不升数列有3种情况 问题分析 若用二分法将实例中的数据分解为两组 2 11 4 13 5 2 第一个子问题的解是11 第二个子问题的解是13 两个子问题的解不能简单地得到原问题的解 由此看出这个问题不能分解用二分法成解为独立的两个子问题 子问题中间还有公共的子问题 这类问题称为子问题重叠类的问题 那么 怎样解决这类问题呢 虽没有通用的方法 但本章4 5节的介绍的动态规划算法是一种较好的解决方法 下面我们仍用二分法解决这类问题中的一些简单问题 学习一下如何处理不独立的子问题 算法设计 分解方法和上面的例题一样采用二分法 虽然分解后的子问题并不独立 但通过对重叠的子问题进行专门处理 并对所有子问题合并进行设计 就可以用二分策略解决此题 如果将所给的序列a 1 n 分为长度相等的2段a 1 n 2 和a n 2 1 n 分别求出这2段的最大子段和 则a 1 n 的最大子段和有3种情形 1 a 1 n 的最长连续不升数列与a 1 n 2 的最长连续不升数列相同 2 a 1 n 的最长连续不升数列与a n 2 1 n 的最长连续不升数列相同 3 a 1 n 的最长连续不升数列为 a k 且1 i n 2 n 2 n 2 1 j n 情况1 和情况2 可分别递归求得 对于情况3 a n 2 与a n 2 1 一定在最优子序列中 因此 我们可以计算出a i n 2 的最大值s1 并计算出a n 2 1 j 中的最大值s2 则s1 s2即为出现情况3 时的最优值 算法如下 intmax sum3 inta intn return max sub sum a 1 n max sub sum inta intleft intright intcenter i j sum left sum right sum s1 s2 lefts rights if left right if a left 0 return a left elsereturn 0 else center left right 2 left sum max sub sum a left center right sum max sub sum a center 1 right s1 0 处理情形3 lefts 0 for i center i left i lefts lefts a i if lefts s1 s1 lefts s2 0 rights 0 for i center 1 is2 s2 rights if s1 s2 left sumandright sum left sum rturn left sum if s1 s2 right sum return right sum return s1 s2 例4 大整数乘法在某些情况下 我们需要处理很大的整数 它无法在计算机硬件能直接允许的范围内进行表示和处理 若用浮点数来存储它 只能近似地参与计算 计算结果的有效数字会受到限制 若要精确地表示大整数 并在计算结果中要求精确地得到所有位数上的数字 就必须用软件的方法来实现大整数的算术运算 请设计一个有效的算法 可以进行两个n位大整数的乘法运算 数据结构设计 首先用数组存储大整数数据 再将两个乘数和积都按由低位到高位逐位存储到数组元素中 算法设计1 存储好两个高精度数据后 模拟竖式乘法 让两个高精度数据的按位交叉相乘 并逐步累加即可得到精确的结果 用二重循环就可实现 算法设计1 存储好两个高精度数据后 我们模拟竖式乘法 让两个高精度数据的按位交叉相乘 并逐步累加 即可得到精确的计算结果 用二重循环就可控制两个数不同位相乘的过程 只考虑正整数的乘法 算法细节设计如下 1 对于大整数比较方便的输入方法是 按字符型处理 存储在字符串数组s1 s2中 计算结果存储在整型数组a中 2 通过字符的ASCII码 数字字符可以直接参与运算 k位数字与j位数字相乘的表达式为 s1 k 48 s2 j 48 这是C语言的处理方法 其它程序设计语言有对应的函可以实现数字字符与数字的转换 这里不详细介绍了 3 每一次数字相乘的结果位数是不固定的 而结果数组中每个元素只存储一位数字 所以用变量b暂存结果 若超过1位数则进位 用变量d存储 这样每次计算的表达式为 b a i s1 k 48 s2 j 48 d main longb c d inti i1 i2 j k n n1 n2 a 256 chars1 256 s2 256 input s1 input s2 for i 0 i0 i i 1 a i a i dmod10 d d 10 n i for i n i 0 i print a i 算法说明 循环变量j k分别是两个乘数字符串的下标 i1表示字符串str1由低位到高位的位数 范围0 n1 1 与k相同 i2表示字符串str2由低位到高位的位数 范围0 n2 1 与j相同 i表示乘法正在运算的位 也是计算结果存储的位置 算法分析1 算法是以n1 n2代表两个乘数的位数 由算法中的循环嵌套知 算法的主要操作是乘法 算法的时间复杂度是O n1 n2 算法设计2 下面们用分治法来设计一个更有效的大整数乘积算法 设计的重点是要提高乘法算法的效率 设计如下 设X和Y都是n位的二进制整数 现在要计算它们的乘积X Y 图4 10大整数X和Y的分段 将n位的二进制整数X和Y各分为2段 每段的长为n 2位 为简单起见 假设n是2的幂 如图4 10所示 显然问题的答案并不是A C K1 C D K2 K1 K2与A B C D无关 也就是说 这样做并没有将问题分解成两个独立的子问题 按照乘法分配律 分解后的计算过程如下 记 X A 2n 2 B Y C 2n 2 D 这样 X和Y的乘积为 X Y A 2n 2 B C 2n 2 D A C 2n AD CB 2n 2 B D 1 模型分析 如果按式 1 计算X Y 则我们必须进行4次n 2位整数的乘法 AC AD BC和BD 以及3次不超过n位的整数加法 此外还要做2次移位 分别对应于式 1 中乘2n和乘2n 2 所有这些加法和移位共用O n 步运算 设T n 是2个n位整数相乘所需的运算总数 则由式 1 我们有以下 2 式 T 1 1T n 4T n 2 O n 2 由此递归式迭代过程如下 T n 4T n 2 cn 4 4T n 4 cn 2 cn 16 T n 8 cn 4 3cn 2 cn 4k 1 2c 4k 2 4c 4c2k 1 c2k O 4k O nlog4 O n2 所以可得算法的时间复杂度为T n O n2 模型改进 可以把X Y写成另一种形式 X Y A C 2n A B D C AC BD 2n 2 B D 3 式 3 看起来比式 1 复杂 但它仅需做3次n 2位整数的乘法 AC BD和 A B D C 6次加 减法和2次移位 由此可得 4 用解递归方程的迭代公式法 不妨设n 2k T n 3T n 2 cn 3 3T n 4 cn 2 cn 9 T n 8 cn 4 3cn 2 cn 3k 3k 1 2c 3k 2 4c 3c2k 1 c2k O nlog3 则得到T n O nlog3 O n1 59 MULT X Y n X和Y为2个小于2n的整数 返回结果为X和Y的乘积XY S SIGN X SIGN Y S为X和Y的符号乘积X ABS X Y ABS Y X和Y分别取绝对值if n 1 if X 1andY 1 return S elsereturn 0 else A X的左边n 2位 B X的右边n 2位 C Y的左边n 2位 D Y的右边n 2位 ml MULT A C n 2 m2 MULT A B D C n 2 m3 MULT B D n 2 S S m1 2n m1 m2 m3 2n 2 m3 return S 4 3 4其它分治方法 以上的例子都是用二分策略把问题分解为与原问题相似 相等 的子问题 下面看几个用 非等分二分法 解决问题的例子 选择问题就是 从一组数中选择的第k小的数据 这个问题的一个应用就是寻找中值元素 此时k n 2 中值是一个很有用的统计量 例如中间工资 中间年龄 中间重量等 k取其他值也是有意义的 例如 通过寻找第k n 2 k n 3和k n 4的年龄 可将人口进行划分 了解人口的分布情况 这个问题可以通过排序来解决 但根据 数据结构 课程的经验 最好的排序算法的复杂性也是O n log n 下面我们要利用