电脑桌面
添加小米粒文库到电脑桌面
安装后可以在桌面快捷访问

C++经典算法

C++经典算法_第1页
1/53
C++经典算法_第2页
2/53
C++经典算法_第3页
3/53
分治算法的基本思想 是将一个规模为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];{构造左下...

1、当您付费下载文档后,您只拥有了使用权限,并不意味着购买了版权,文档只能用于自身使用,不得用于其他商业用途(如 [转卖]进行直接盈利或[编辑后售卖]进行间接盈利)。
2、本站所有内容均由合作方或网友上传,本站不对文档的完整性、权威性及其观点立场正确性做任何保证或承诺!文档内容仅供研究参考,付费前请自行鉴别。
3、如文档内容存在违规,或者侵犯商业秘密、侵犯著作权等,请点击“违规举报”。

碎片内容

确认删除?
VIP
微信客服
  • 扫码咨询
会员Q群
  • 会员专属群点击这里加入QQ群
客服邮箱
回到顶部