基础算法5-分治法2.ppt

循环日程表问题 在算法设计中，用数组a记录2^n个球队的循环比赛表，整个循环比赛表从最初的1*1方阵按上述规则生成2*2的方阵，再生成4*4的方阵，……直到生成出整个循环比赛表为止。变量h表示当前方阵的大小,也就是要生成的下一个方阵的一半。 总结归纳 分治是一种解题的策略，它的基本思想是：“如果整个问题比较复杂，可以将问题分化，各个击破。” 分治包含“分”和“治”两层含义，如何分，分后如何“治”成为解决问题的关键所在 不是所有的问题都可以采用分治，只有那些能将问题分成与原问题类似的子问题，并且归并后符合原问题的性质的问题，才能进行分治 分治可进行二分，三分等等，具体怎么分，需看问题的性质和分治后的效果。 只有深刻地领会分治的思想，认真分析分治后可能产生的预期效率，才能灵活地运用分治思想解决实际问题。 * 【例题】比赛安排 【问题描述】设有2n(n=6)个球队进行单循环比赛,计划在2n -1天内完成，每个队每天进行一场比赛。设计一个比赛的安排，使在2n -1天内每个队都与不同的对手比赛。例如n=2时的比赛安排为： 队 1 2 3 4  比赛 1-2 3-4 第一天  1-3 2-4 第二天  1-4 2-3 第三天 【文件输入】一个整数n。 【文件输出】输出比赛安排表。 【样例输入】2 【样例输出】 1-2 3-4  1-3 2-4  1-4 2-3 算法分析：此题很难直接给出结果，我们先将问题进行分解，设m=2^n，将规模减半，如果n=3(即m=8),8个球队的比赛，减半后变成4个球队的比赛（m=4），4个球队的比赛的安排方式还不是很明显，再减半到两个球队的比赛(m=2)，两个球队的比赛安排方式很简单，只要让两个球队直接进行一场比赛即可： 1 2 2 1 分析两个球队的比赛的情况不难发现，这是一个对称的方阵，我们把这个方阵分成4部分（即左上，右上，左下，右下），右上部分可由左上部分加1（即加m/2）得到，而右上与左下部分、左上与右下部分别相等。因此我们也可以把这个方阵看作是由M=1的方阵所成生的，同理可得M=4的方阵： 3 4 4 3 1 2 2 1 1 2 2 1 3 4 4 3 同理可由M=4方阵生成M=8的方阵： 1 2 3 4 5 6 7 8 2 1 4 3 6 5 8 7 3 4 1 2 7 8 5 6 4 3 2 1 8 7 6 5 5 6 7 8 1 2 3 4 6 5 8 7 2 1 4 3 7 8 5 6 3 4 1 2 8 7 6 5 4 3 2 1 Program saicheng; var i,j,h,m,n:integer; a:array[1..32,1..32]of integer; begin read(n); m:=1;a[1,1]:=1;h:=1; for i:=1 to n do m:=2*m; {比赛总队数} while(h=m)do {从一个球队开始构造} begin for i:=1 to h do{构造其余三个方阵} for j:=1 to h do begin a[i,j+h]:=a[i,j]+h; {构造右上角方阵} a[i+h,j]:=a[i,j+h]; {构造左下角方阵} a[i+h,j+h]:=a[i,j]; {构造右下角方阵} end; h:=h*2; end; for i:=1 to m do begin for j:=1 to m do write(a[i,j]:4); writeln; end; end. 分析2：递归形式实现 由于N个运动员要进行单循环比赛，且在N-1天内要结束全部比赛，经过分析，当且仅当N为2的整次幂时，问题才有解，当然解是不唯一的。这样可以将运动员分成两组： 1,2,…,N/2 和 N/2+1,N/2+2,…,N。给第一组运动员安排一个比赛日程，得到一个N/2阶的方阵A1；同时给第二组的运动员安排一个比赛日程，同样会得到一个N/2阶的一个方阵A2。考虑到比赛的性质，设定第I个运动员在某一天的比赛对手为第K个运动员，则第K个运动员在同一天的比赛对手必然是第I个运动员，即若有A[I,J]=K，则A[K,J]=I。因此原问题的解(一个N阶方阵)可以由分解后的两个子问题的解，合并起来。同时每一个子问题又可以按