Archive for the ‘数据结构与算法’ Category.

循环赛日程安排分治法分析

问题描述:

  • 设有n(n = 2^k)位选手参加网球循环赛,循环赛共进行n-1天,每位选手要与其他n-1位选手比赛一场,且每位选手每天必须比赛一场,不能轮空。试按此要求为比赛安排日程。

编程思想:

假设n位选手被顺序编号为1,2,3,…,n,比赛的日程表是一个n行n-1列的表格,i行j列的表格内容是第i号选手在第j天的比赛对手。根据分而治之的原则,可从其中一半选手(2^(n-1位)的比赛日程,导出全体n位选手的日程,最终细分到只有两位选手的比赛日程出发。可假设只有8位选手参赛,若1至4号选手之间的比赛日程填在日程表的左上角(4行3列),5至8号选手之间的比赛日程填在日程表的左下角(4行3列);那么左下角的内容可由左上角的对应项加上数字4得到。至此,剩余的右上角(4行4列)是为编号小的1至4号选手与编号大的5至8号选手之间的比赛日程安排。例如,在第4天,让1至4号选手分别与5至8号选手比赛,以后各天,依次由前一天的日程安排,让5至8号选手“循环轮转”即可。最后,比赛日程表的右下角的比赛日程表可由,右上角的对应项减去数字4得到。

具体实现:
Continue reading ‘循环赛日程安排分治法分析’ »

最大子段和算法分析

问题:

给定n个整数(可能为负数)组成的序列a[1],a[2],a[3],…,a[n],求该序列如a[i]+a[i+1]+…+a[j]的子段和的最大值。当所给的整均为负数时定义子段和为0,依此定义,所求的最优值为:

Max{0,a[i]+a[i+1]+…+a[j]},1< =i<=j<=n 例如,当(a1,a2,a3,a4,a4,a6)=(-2,11,-4,13,-5,-2)时,最大子段和为20 下面列出了四种计算方式,时间复杂度各逐渐变小,其中动态规划法时间复杂度最小。 Continue reading ‘最大子段和算法分析’ »

分治法排序

在计算机科学中,分治法是一种很重要的算法。字面上的解释是“分而治之”,就是把一个复杂的问题分成两个或更多的相同或相似的子问题,再把子问题分成更小的子问题……直到最后子问题可以简单的直接求解,原问题的解即子问题的解的合并。

分治法所能解决的问题一般具有以下几个特征:
1) 该问题的规模缩小到一定的程度就可以容易地解决
2) 该问题可以分解为若干个规模较小的相同问题,即该问题具有最优子结构性质。
3) 利用该问题分解出的子问题的解可以合并为该问题的解;
4) 该问题所分解出的各个子问题是相互独立的,即子问题之间不包含公共的子问题。
Continue reading ‘分治法排序’ »