分治算法.ppt

分治算法
分治算法
基本思想
当我们求解某些问题时,由于这些问题要处理的数据相当多,或求解过程相当复杂,使得直接求解法在时间上相当长,或者根本无法直接求出。对于这类问题,我们往往先把它分解成几个子问题,找到求出这几个子问题的解法后,再找到合适的方法,把它们组合成求整个问题的解法。如果这些子问题还较大,难以解决,可以再把它们分成几个更小的子问题,以此类推,直至可以直接求出解为止。
分治算法
一般解题步骤
(1)分解,将要解决的问题划分成若干规模较小的同类问题;
(2)求解,当子问题划分得足够小时,用较简单的方法解决;
(3)合并,按原问题的要求,将子问题的解逐层合并构成原问题的解。
分治算法
应用实例

在n个元素中找出最大元素和最小元素
代码_直接查找
代码_二分查找
分治算法
A
-13 13 9 -5 7 23 0 15
low=0 high=7 mid=3
B1 B2
-13 13 9 -5 7 23 0 15
low= 0 high=3 mid=5 low=4 high=7 mid=7
分治算法
B1
-13 13 9 -5
low=0 high=3 MID=2
C1 C2
-13 13 9 -5
low=0 high=1 low=2 high=3
max1=13 max2=9
min1=-13 min2=-5
max=13
min=-13
分治算法
B2
7 23 0 15
low=4 high=7 mid=5
C3 C4
7 23 0 15
low=4 high=5 low=6 high=7
max1=23 max2=15
min1=7 min2=6
max=23
min=7
分治算法
A
-13 13 9 -5 7 23 0 15
low=0 high=7 mid=3 max=23 min=-13
B1 B2
-13 13 9 -5 7 23 0 15
low = 0 high=3 mid=1 low=4 high=7 mid=5
max = 13 max=23
min = -13 min = 7
分治算法
应用实例

给你一个装有1 6个硬币的袋子。1 6个硬币中有一个是伪造的,并且那个伪造的硬币比真的硬币要轻一些。你的任务是找出这个伪造的硬币。为了帮助你完成这一任务,将提供一台可用来比较两组硬币重量的仪器,利用这台仪器,可以知道两组硬币的重量是否相同。
分治算法
应用实例

方案1 两两比较:
比较硬币1与硬币2的重量。假如硬币1比硬币2轻,则硬币1是伪造的;假如硬币2比硬币1轻,则硬币2是伪造的。这样就完成了任务。假如两硬币重量相等,则比较硬币3和硬币4。同样,假如有一个硬币轻一些,则寻找伪币的任务完成。假如两硬币重量相等,则继续比较硬币5和硬币6。按照这种方式,可以最多通过8次比较来判断伪币的存在并找出这一伪币。