微信号:grzlwx

介绍:光荣之路官方资讯

算法洗洗脑——第五篇 分治思想

2015-07-14 23:10 光荣之路


由于最近工作比较忙,好长时间都没有更新博客了,今天就分享下分治思想。


一: 思想

有时候我们处理一个复杂的问题,可能此问题求解步骤非常杂,也可能是数据非常多,导致我们当时很难求出或者无法求出,古语有云:

步步为营,各个击破,这个思想在算法中称为分治思想,就是我们可以将该问题分解成若干个子问题,然后我们逐一解决子问题,最后将子问题的答案组合成整个问题的答案。


二: 条件

当然各个思想都有它的使用领域,所以玩这场分治游戏就要遵守它的游戏规则。

① 求解问题确实能够分解成若干个规模较小的子问题,并且这些子问题最后能够实现接近或者是O(1)时间求解。

② 各个子问题之间不能有依赖关系,并且这些子问题确实能够通过组合得到整个问题的解。


三:步骤

通过上面对分治的说明,可以看到分治分三步走:

① 分解: 将问题分解成若干了小问题。

② 求解: O(1)的时间解决该子问题。

③ 合并: 子问题逐一合并构成整个问题的解。


四:举例

有n位选手参加羽毛球赛,比赛要进行n-1天,每位选手都要与其他每一个选手比赛一场并且每位选手每天都要比赛一场,请根据比赛要求排出选手的比赛日程表。


思路:首先我们拿到问题要给自己打气,哈哈,因为日常的基本问题都跑不出我们所知道算法思想的范畴,此问题也包括在内。

当n是8,16,32时,面对这么一个庞大的问题我们可能就崩溃了,因为我们实在无法求出来,此时我们就要想想是否可以分治一下。

① 就拿16个选手的比赛安排来说,需要比赛15天。

② 分成2个8位选手7天的比赛安排。

③ 分为4个4位选手3天的比赛安排。

④ 分为8个2位选手1天的比赛安排。

相信2位选手1天的比赛安排大家都会吧,如图:

然后退化到第三步即4位选手3天的比赛安排,如图:

在图中可以看出:

第一天:将1,2位和3,4位选手的日程合并。

第二天,第三天:这两天的比赛安排其实可以发现规律的,整个表格可以划分四格,对角赋值。

程序代码如下:


(作者:一线码农 来源:http://www.cnblogs.com/huangxincheng/archive/2012/02/07/2340797.html)

 
            
 
            
 
            
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           
 
           

一字一句当思来之不易,感谢作者,传播测试知识、技能与正能量!

光荣之路软件测试培训

官网:http://www.gloryroad.cn/

微信公众号:gloryroadtrain

性能测试QQ群:415987441
软件测试招聘QQ群: 203715128
自动化3群QQ: 371211499


 
光荣之路 更多文章 今天晚上的 linux 公开课- Awk 编程 7月28日(今天)晚上的 linux 公开课- shell编程 8月4日(今天)晚上的 linux 公开课- shell编程 9月1日(本周一)晚8点半,光荣之路Web自动化系列基础课—javascript第二讲 推荐本好书《与机器赛跑》
猜您喜欢 (资源)SWAP的罪与罚 浅谈服务器性能测试的全生命周期——从测试、结果分析到优化策略 PHP5.6新特性介绍 Python破解ZIP或RAR文件密码 深度学习及其在淘宝图像应用探讨