📄 分治策略.htm
字号:
<TABLE cellPadding=0 width=500 align=center border=0>
<TBODY>
<TR>
<TD>
<P>（一次冒泡排序）<BR>m:=a[1];<BR>for i:=2 to n do<BR>if m <
a[i] then m:=a[i];<BR></P></TD>
<TD>(或者一次选择排序)<BR>p:=1;<BR>for i:=2 to n do<BR>if
a[p]<a[i] then p:=i;<BR>m:=a[p];</TD></TR></TBODY></TABLE>
<P>需要n-1次比较得到max，而再经过n-2次比较得到min，共进行2*n-3次比较可以找出极大元和极小元。</P>
<P> 用分治法可以较少比较次数地解决上述问题：<BR>
如果集合中只有1个元素，则它既是最大值也是最小值；<BR> 如果有2个元素，则一次maxnum(i,j)
一次minnum(i,j)就可以得到最大值和最小值；<BR>
如果把集合分成两个子集合，递归的应用这个算法分别求出两个子集合的最大值和最小值，最后让子集合1的最大值跟子集合2的最大值比较得到整个集合的最大值；让子集合1的最小值跟子集合2的最小值比较得到整个集合的最小值。</P>
<P><BR>可得解题思想：</P>
<P>｛maxmin｝<BR> ①if 问题不可分：n=2<BR>
②问题的解求得（两个元素时）：对两元素进行比较;return;<BR> ③for i:=1 to n div 2 do
b[i]:=a[i]<BR> ④maxmin(n div
2,b,max1,min1)，其中max1和min1为解1<BR> ⑤for i:=1 to n div 2 do
b[i]:=a[i+ n div 2]<BR> ⑥maxmin(n div
2,b,max2,min2)，其中max2和min2为解2<BR>
⑦max:=maxnum(max1,max2);<BR>
min:=minnum(min1,min2);<BR>{maxmin}</P>
<P>其中对函数maxnum的求精：<BR>function
maxnum(a,b:integer):integer;<BR> begin<BR> if a>b then
maxnum:=a else maxnum:=b;<BR> end;</P>
<P>分析比较次数：<BR>比较运算均在函数maxnum和minnum中进行，<BR>当n=2时，比较次数T(n)=1<BR>当n>2时，比较次数T(n)=2T(n/2)+2<BR>∵n是2的k次幂<BR>∴设n=2^k<BR> <BR> </P>
<P><IMG height=410 src="分治策略.files/Image59.gif" width=186></P>
<P>?</P>
<P> 2、快速排序</P>
<P> 快速排序是基于分治策略的一个排序算法。按照分治法的思想分析快速排序：<BR>（1）分解(Divide)
以元素a[p]为基准元素将a[p：q-1]划分为三段a[p：q-1]，a[q]和a[q+1：r]，使得a[p：q-1]中任何一个元素都小于a[q]，a[q+1：r]中任何一个元素大于等于a[q]，下标q在划分中确定。<BR>（2）递归求解(Conquer)
通过递归调用快速排序算法分别对a[p:q-1] 和a[q+1:r]进行排序。<BR>（3）合并(Merge)
由于a[p:q-1] 和a[q+1:r]的排序都是在原位置进行的，所以不必进行任何合并操作就已经排好序了。</P>
<P>在上面三个步骤中，第一步：分解是关键。一次快速排序确定划分元素的位置，具体参见排序算法----快速排序</P>
<P> 3、归并排序</P>
<P> </P>
<P> 归并排序也是基于分治策略的另一个算法。归并的思路是把两个已经排好序的数组合并为一个。<BR>２－路归并排序示例：</P>
<TABLE cellPadding=0 width=507 align=center border=1>
<TBODY>
<TR>
<TD>
<DIV align=center>初始值 </DIV></TD>
<TD>
<DIV align=center>E </DIV></TD>
<TD>
<DIV align=center>Y </DIV></TD>
<TD>
<DIV align=center>U </DIV></TD>
<TD>
<DIV align=center>K </DIV></TD>
<TD>
<DIV align=center>S </DIV></TD>
<TD>
<DIV align=center>L </DIV></TD>
<TD>
<DIV align=center>B </DIV></TD></TR>
<TR>
<TD>
<DIV align=center>一趟归并排序 </DIV></TD>
<TD bgColor=#99ffff colSpan=2>
<DIV align=center>E Y </DIV></TD>
<TD bgColor=#ffff99 colSpan=2>
<DIV align=center>K U </DIV></TD>
<TD bgColor=#ff99cc colSpan=2>
<DIV align=center>L S </DIV></TD>
<TD bgColor=#99ccff>
<DIV align=center>B </DIV></TD></TR>
<TR>
<TD>
<DIV align=center>两趟归并排序 </DIV></TD>
<TD bgColor=#ccffcc colSpan=4>
<DIV align=center>E K U Y </DIV></TD>
<TD bgColor=#eb9bff colSpan=3>
<DIV align=center>B L S </DIV></TD></TR>
<TR>
<TD height=23>
<DIV align=center>三趟归并排序 </DIV></TD>
<TD bgColor=#e1e1e1 colSpan=7 height=23>
<DIV align=center>B E K L S U Y
</DIV></TD></TR></TBODY></TABLE>习题:对数字49 38 40 97 76 13
27进行归并排序<BR>
<P>procedure mergesort(var r,r1:listtype;s,t:integer);</P>
<P>{r,r1：均为链表，存储排序数据；过程mergesort(r,r1,s,t)完成把链表r中的关键字进行归并排序、并存放到链表r1中，其中s是下界t是上界}<BR>{过程merge(r2,s,m,t,r1)把链表r2中排好序的子链r2[s..m]和子链r2[m+1..t]合并到r1中}</P>
<TABLE cellPadding=0 width=639 align=center border=0>
<TBODY>
<TR bgColor=#eeeeee>
<TD width=362>
<P>if 问题不可分 then</P>
<P> 求解</P></TD>
<TD width=271>
<P>if s=t then</P>
<P>r1[s]:=r[s]</P></TD></TR>
<TR bgColor=#eeeeee>
<TD width=362>else</TD>
<TD width=271>else</TD></TR>
<TR bgColor=#eeeeee>
<TD width=362 height=30> （1）分出问题的一个子问题1，并求解子问题1</TD>
<TD width=271 height=30>mergesort(r,r2,s,(s+t)div
2);</TD></TR>
<TR bgColor=#eeeeee>
<TD width=362 height=31> （2）分出问题的一个子问题2，求解子问题2</TD>
<TD width=271 height=31>mergesort(r,r2,(s+t)div
2,t);</TD></TR>
<TR bgColor=#eeeeee>
<TD width=362 height=31> （3）合并子问题1和子问题2</TD>
<TD width=271 height=31>merge(r2,s,(s+t)div
2,t,r1);</TD></TR></TBODY></TABLE>
<P> 4、[循环赛问题]（1999年广东省青少年信息学奥林匹克竞赛
第三题：棒球联赛）<BR>问题描述：广州市体委将举行一次由N支队伍（队伍编号为1..N）参加的少年棒球联赛。联赛总共不能多于N轮（同一时间内若干支队进行一次比赛为一轮），并且每两支队之间必须而且仅必须进行一次比赛。请编程为这次比赛设计一个赛程表。<BR>循环赛问题可以用分治法解决。下面是先假定n=2^k</P>
<P><BR>procedure table(k:integer;a:array[1..u1,1..u2] of
integer);<BR>var n,i,j,m,s,t:integer;<BR>begin<BR>
n:=1;<BR> for i:=1 to k do n:=n*2;<BR> for i:=1 to n do
a[1,i]:=i;<BR> m:=1;<BR> for s:=1 to k do<BR>
begin<BR> n:=n / 2;<BR> for t:=1 to n do<BR> for
i:=m+1 to 2*m do<BR> for j:=m+1 to 2*m do<BR>
begin<BR>
a[i,j+(t-1)*m*2]:=a[i-m,j+(t-1)*m*2-m];<BR>
a[i,j+(t-1)*m*2-m]:=a[i-m,j+(t-1)*m*2];<BR>
end;<BR> m:=m*2;<BR> end;{for s}</P>
<P>end;</P>
<P><FONT color=#cc0000>三、练习题</FONT></P>
<P>[二分检索]假定在A[1..9]中顺序存放这九个数：-7,-2,0,5,16,43,57,102,291
要求检索291,16,101是否在数组中。</P>
<P> 给定已排好序的n个元素A1,A2,A3,…，An,
找出元素x是否在A中，如果x在A中，指出它在A中的位置。</P></TD></TR></TBODY></TABLE></TD></TR></TBODY></TABLE>
<TABLE>
<TBODY>
<TR>
<TD vAlign=bottom height=81>
<TABLE cellSpacing=0 cellPadding=0 width="100%" border=0>
<TBODY>
<TR bgColor=#cccccc>
<TD width=800 height=1><IMG height=1 width=800></TD>
<TD width=459 height=1></TD></TR>
<TR vAlign=top>
<TD width=800>
<TABLE cellSpacing=0 cellPadding=0 width=800>
<TBODY>
<TR>
<TD width=210 height=10></TD>
<TD width=590 colSpan=2 height=10></TD></TR>
<TR>
<TD width=210 height=14>
<P align=center><A onfocus=this.blur()
href="http://www.muduhs.com/" target=_blank><FONT
face=Verdana color=#999999 size=1>GO Muduhs
WebSite!</FONT></A> </P></TD>
<TD width=536 height=14>
<P><FONT face=Verdana size=1>Copyright ⓒ Mudu - Internet
HighSchool. Some right reserved.</FONT></P></TD>
<TD width=54 height=14>
<P align=right><A onfocus=this.blur()
href="http://www.muduhs.com/~yanxm/pds10.htm#"><FONT
face=Verdana size=1><B>-TOP</B></FONT></A> </P></TD></TR>
<TR>
<TD width=210 height=10></TD>
<TD width=590 colSpan=2
height=10></TD></TR></TBODY></TABLE></TD>
<TD width=459></TD></TR></TBODY></TABLE></TD></TR><MAP
name=ImageMap1><AREA shape=RECT coords=81,1,161,33
href="http://www.muduhs.com/~yanxm/pds.htm"><AREA shape=RECT
coords=161,1,240,33
href="http://www.muduhs.com/~yanxm/contest.htm"><AREA shape=RECT
coords=240,1,320,34
href="http://www.muduhs.com/~yanxm/circle.htm"><AREA shape=RECT
coords=319,1,401,35
href="http://www.muduhs.com/~yanxm/gellery.htm"><AREA shape=RECT
coords=401,2,479,35
href="http://www.muduhs.com/~yanxm/board.htm"><AREA shape=RECT
coords=1,1,82,33
href="http://www.muduhs.com/~yanxm/about.htm"></MAP></TBODY></TABLE></TR></TBODY></TABLE></BODY></HTML>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -