算法第五章课件.ppt

第5章 减治法 什么是减治法 减治技术利用了一种关系一个问题给定实例的解和同样问题较小实例的解之间的关系一旦建立了这样一种关系我们既可以从顶至下递归地也可以从底至上非递归地来运用这种关系 三种主要的类型 减去一个常量 减去一个常量因子 减去的规模是可变的 1.减常量 每次算法迭代时总是从实例规模中减去一个规模相同的常量的值 见图 5.1 P119 例计算an的值 f(n-1*a if n>1 f(