实用算法的分析与程序设计 吴文虎 王建德 一九九六年六月三日 目 录 憙拕 第一章 基础算法憖………………………………………………………………(4) §1.1 递推法…………………………………………………………………(4) §1.2 贪心法…………………………………………………………………(11) §1.3 递归法…………………………………………………………………(23) §1.4 分治法…………………………………………………………………(27) §1.5 枚举法 ……………………………………

作者:吴文虎 王建德 本书总结了历届国际奥林匹克竞赛（IOI）的试题特点及我国参赛选手的培训经验。书中许多例题取自历届大赛的试题及中国队选手的训练题目，针对问题讲解了解题的关键思路及如何灵活运用有关的算法知识。 第一章基础算法 1．1 递推法 一、倒推法 二、顺推法 1．2 贪心法 1．3 递归法 1．4 分治法 1．5 枚举法 1．6 摸拟法 第二章 顺序统计算法和中位数 2．1 顺序统计的算法 一、划分方法 二、二分法求解 2．2 中位数的应用 第三章 有关数论的算法 3．1 求最大公约数

模型改进： 可以把X*Y写成另一种形式： X*Y=A*C*2^n+[(A-B)(D-C)+AC+BD]*2^(n/2)+B*D (3) 式(3)看起来比式(1)复杂，但它仅需做3次n/2位整数的乘法：AC，BD和(A-B)(D-C)，6次加、减法和2次移位。由此可得:用解递归方程的迭代公式法，不妨设n=2^k： T(n)=3T(n/2)+cn =3(3T(n/4)+cn/2)+cn =9(T(n/8)+ cn/4)+3cn/2+cn =…… =3^k +3^(k-1) *2c+3^(k-2)