分成2组: [49,38,65,97] [76,13,27] 再分组: [49,38] [65,97] [76,13] [27]
每一组找大数: 49
97
归并成2组:
[49,97]
76
27
[76,27]
每一组找大数: 归并成1组
97
76
[97,76]
找出最大数:
97
第6讲 软件开发与软件工程 11
分治法的基本思想
2. 在未排序数的左面设置1个标志,
4 937 8 2 5
以区分已排序部分和未排序部分 1c
2 937 8 4 5
3. 重复步骤4~步骤7,直到未排序
部分只剩下1个数为止:
2 937 8 4 5
2c
4. 对未排序部分的数进行比较
2 397 8 4 5
5. 从中选择最小的1个数
2 397 8 4 5
3c
z=100-ห้องสมุดไป่ตู้-y
5x+3y+z/3=100? Y
N
x+1
输出x,y,z
N
x+y=100?
Y
x=0, y+1
N
x+y=100?
Y
枚举法也 叫做“穷 举法”或 Bruteforce
结束 第6讲 软件开发与软件工程 7
例2:货郎担问题
(TSP-Traveling Salesman Problem)
售货员从城市A出发,到B、 C、D等若干城市销售货物。 已知各城市之间的距离,要 求选择一条旅行路线,使总 路程最短。条件:每个城市 只能经过一次,最后仍回到 出发城市A。
假设: 公鸡数目为x,母鸡数目为y,则小鸡数目为(100-x-y)