分治递归算法.ppt

文档介绍：IntroductiontoAlgorithmsDivideandConquer*递归与分治策略07网络工程郝毅敏QQ344959789Tel**********本讲代码多为伪码,需要大家理解后自己实现。本讲出现的所有代码均没有进行测试,如有疑问,欢迎提出。将一个难以直接解决的大问题,分割成一些规模较小的相同问题,以便各个击破,分而治之*T(N)NN/KN/KN/K分治(divide-and-conquer)***在印度,有这么一个古老的传说:在世界中心贝拿勒斯(在印度北部)的圣庙里,一块黄铜板上插着三根宝石针。印度教的主神梵天在创造世界的时候,在其中一根针上从下到上地穿好了由大到小的64片金片,这就是所谓的汉诺塔。不论白天黑夜,总有一个僧侣在按照下面的法则移动这些金片,一次只移动一片,不管在哪根针上,小片必在大片上面。当所有的金片都从梵天穿好的那根针上移到另外一概针上时,世界就将在一声霹雳中消灭,梵塔、庙宇和众生都将同归于尽。例2:Hanoi塔传说ABC*思考:递归可以用于解决哪些问题?*递归算法一般用于解决三类问题: (1)数据的定义是按递归定义的。(阶乘) (2)问题解法按递归算法实现。(回溯) (3)数据的结构形式是按递归定义的。(树的遍历,图的搜索)*Hanoi塔传说中的世界末日!