凡治众如治寡,分数是也”,这里的”分数”,是指分到各层次的部分,”数”是指每部分人的人数,意思就是将帅只需要通过管理少数几个人即可实现管理全部队的各个组织,这样,人数众多的军队,就如同管理几个人一样容易.在算法设计中...,我们也引入分而治之的策略,称为分治算法,其本质其实就是将一个问题分解为若干个规模较小的相同子问题,分而治之....分治算法秘籍:
分治法解题的基本步骤如下:
1:分解问题:
将要解决的问题分解为若干个规模较小,相互独立,与原问题形式相同的子问题
2:问题治理:
求解各个子问题,由于各个子问题和原问题的形式相同,只是规模较小...在使用分治法时,使用递归算法是解决问题的利器.下面我们用二分搜索,这个最典型的分治问题来举例,看看分治算法是如何进行工作的....算法设计:
使用一维数组S[]放置该有序序列,设置变量low和high表示查找的上下界,middle表示中间的位置,x为特定的查找元素.
1:初始化.令low=0(S[]中的第一位数),high=n-1