俄式乘法
n n * m= — * 2 * m 2
• 两个大整数m和n乘法
n为偶数
n -1 n * m= —— * 2 * m + m 2
n为奇数
an=(a(n-1)/2)2 *a n是奇数
an =a
子问题的解
n=1
原始问题的解Leabharlann 7减常因子法 减治法的第 2 种变化。折半查找 —— 常因子 = 2 ， 注意与分治法区别 这类算法效率常常是对数型，速度非常快，不要指望 有很多此类算法，常因子 ≠ 2 的情况更是少之又少。 常因子 = 3，每次规模减 2 / 3 . 假币问题 有n 枚外观相同的硬币，其中有一枚假币。设假币较 轻，用一架天平将这枚假币检测出来 减常因子策略 （多种方法，这里仅用减治策略） 把 n 枚硬币等分为两堆 —— n 为奇数：留下一枚硬币，把两堆放天平上。若两 堆硬币重量相同，留下这枚即为假币 n 为偶数：较轻的一堆含假币，继续分解它，丢弃 较重的那一堆 —— 常因子 = 2 ，减半法
解此递推式，得 本算法并非最高效的算法！更高效的策略是： 每次把 n 个硬币分为 3 堆，常因子 = 3，每次减去问题 规模的2/3 . 称重次数约为 log3n, 比 log2n 更小。
减常因子法算例 —— 俄式乘法（俄国农夫法） 问题：两个正整数相乘。十九世纪，俄国农 民广泛采用该算法，不需使用九九乘法表。 算法策略 n 和 m 为两个正整数，计算它们的乘积。 问题规模选择 n ，采用减治 策略，可得递推式：（规模减半，常因子 = 2） n为偶数： n为奇数： 算法停止： n = 1 时停止：1×m = m 算法实现：递归法、非递归法
分治法和减治法区别
分治法是对分解的子问题分别求解，需要 对子问题的解进行合并，而减治法只对一个子问 题求解，并且不需要进行解的合并。应用减治法 （例如减半法）得到的算法通常具有如下递推式：
0 T (n) T (n / 2) 1
n 1 n 1
算法的三个变形
减常量法：常量通常为1（每此迭代规模减小n→n-1 ） 减常因子法：常因子通常为 2（每此迭代规模减半 n→ n/2 ） 减可变规模法：每次减去的规模不同
减治算法
Decrease and Conquer减治算法
☆基本思想 ☆三个变形及实现 ☆几个实例
减治法的基本思想
将规模为n的问题递减为规模为 n-1或n/2的子问题,反复递减后对子问 题分别求解,再建立子问题的解与原问 题的解的关系。 减治法：利用给定规模与较小规 模问题解之间的关系求解问题的方法。
当n>1时，W(n)=W([n/2])+1
, W(1)=0
时间效率分析 输入规模：硬币数 n 基本操作：称重（比较操作） 效率类别：有最佳、最差、平均效率情况 增长函数：称重次数与硬币数 n 的函数关系 T(n) = ? 1. 最佳效率 T(n) = 1 ( n 为奇数 ) 需要作 1 次称重 2. 最差效率 将问题规模减半
实现 —— 从顶向下：规模减小（递归） 从底向上：规模增大（非 递归）
减（一）治技术
规模为n 的问题
规模为n-1 的子问题
例如： f(n)=an
f(n)=f(n-1)*a
n>1
n=1
子问题的解
f(n)=a
原始问题的解
减（半）治技术
规模为n的问题 规模为n/2 的子问题
an=(an/2)2
n是偶数