C++经典算法

分治算法的基本思想 是将一个规模为N 的问题分解为K 个规模较小的子问题，这些子问题相互独立且与原问，性质相同。求出子问题的解，就可得到原问题的解。 分治法解题的一般步骤： （1）分解，将要解决的问题划分成若干规模较小的同类问题； （2）求解，当子问题划分得足够小时，用较简单的方法解决； （3）合并，按原问题的要求，将子问题的解逐层合并构成原问题的解。 例1、比赛安排(noip1996) 设有 2^n(n<=6)个球队进行单循环比赛,计划在 2^n-1 天内完成,每个队每天进行一场比赛。设计一个比赛的安排,使在 2^n-1 天内每个队都与不同的对手比赛。例如 n=2 时的比赛安排为: 队 1 2 3 4 比赛 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 的方阵： 1 2 3 4 2 1 4 3 3 4 1 2 4 3 2 1 同理可由 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 这样就构成了整个比赛的安排表。 在算法设计中，用数组 a 记录 2^n 个球队的循环比赛表，整个循环比赛表从最初的1*1 方阵按上述规则生成2*2 的方阵，再生成4*4 的方阵，„„直到生成出整个循环比赛表为止。变量 h 表示当前方阵的大小,也就是要生成的下一个方阵的一半。 源程序： var i,j,h,m,n:integer; a:array[1..32,1..32]of integer; begin readln(n); m:=1;a[1,1]:=1;h:=1; for i:=1 to n do m:=m*2; repeat 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];{构造左下...