计算机算法设计与分析基础第五章减治法.ppt

5.5.2减常因子法俄式乘法 减常因子法算例 俄式乘法俄国农夫法 问题两个正整数相乘十九世纪俄国农民广泛采用该算法不需 使用九九乘法表文献介绍埃及数学家早在公元前 1650 年 就使用了该算法思想 算法策略 n 和 m 为两个正整数计算它们的乘积问题规模选择 n 采用减治 策略可得递推式规模减半常因子 = 2 n为偶数 n为奇数 算法停止 n = 1 时停止1m = m 算法实现递归法非递归法