📄 分治策略.htm
字号:
<!DOCTYPE HTML PUBLIC "-//W3C//DTD HTML 4.0 Transitional//EN">
<!-- saved from url=(0038)http://www.muduhs.com/~yanxm/pds10.htm -->
<HTML><HEAD>
<META http-equiv=Content-Type content="text/html; charset=gb2312"><LINK
href="分治策略.files/style.css" type=text/css rel=stylesheet>
<META content="MSHTML 6.00.2800.1400" name=GENERATOR></HEAD>
<BODY text=#8d8d8d bgColor=#ffffff leftMargin=0 topMargin=0 marginwidth="0"
marginheight="0">
<TABLE height=701 cellSpacing=0 cellPadding=0 width=895 border=0>
<TBODY>
<TR>
<TD vAlign=top width=958 height=109>
<TABLE cellSpacing=0 cellPadding=0 width="100%" bgColor=#ffffff
border=0><TBODY>
<TR>
<TD width=800 height=56>
<TABLE cellSpacing=0 borderColorDark=black cellPadding=0 width=800
borderColorLight=black>
<TBODY>
<TR>
<TD width=10 height=67>
<P> </P></TD>
<TD width=235 height=67>
<P><A href="http://www.muduhs.com/~yanxm/index1.htm"><IMG
height=79 src="分治策略.files/plogo1.jpg" width=155
align=absMiddle border=0></A></P></TD>
<TD width=480 height=67>
<P><IMG height=79 src="分治策略.files/pds.gif" width=480
useMap=#ImageMap1 border=0></P></TD></TR></TBODY></TABLE></TD>
<TD vAlign=top width=459 height=56><IMG height=1 width=1></TD></TR>
<TR bgColor=#333333>
<TD width=800 height=25>
<TABLE cellSpacing=0 cellPadding=0 width=784>
<TBODY>
<TR>
<TD width=20>
<P> </P></TD>
<TD width=764>
<P><IMG height=20 src="分治策略.files/m9.jpg" width=157
border=0></P></TD></TR></TBODY></TABLE></TD>
<TD width=459 height=25></TD></TR>
<TR bgColor=#cccccc>
<TD width=800 height=1><IMG height=1 width=800></TD>
<TD width=459 height=1><IMG height=1 width=1><IMG height=1
width=150></TD></TR></TBODY></TABLE></TD></TR>
<TR vAlign=top>
<TD vAlign=top width=958 bgColor=#ffffff height=511>
<TABLE cellSpacing=0 cellPadding=0 width=858>
<TBODY>
<TR vAlign=top>
<TD width=48> </TD>
<TD width=156>
<TABLE cellSpacing=0 cellPadding=0 width=150>
<TBODY>
<TR>
<TD width=141 height=12>
<P><A href="http://www.muduhs.com/~yanxm/pds.htm"><IMG
height=50 src="分治策略.files/s_02.gif" width=150
border=0></A></P></TD></TR>
<TR>
<TD width=141 bgColor=#eeeeee height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds0.htm"><FONT
color=navy>+ 数据结构</FONT></A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD width=141 bgColor=#eeeeee height=20>
<P><FONT color=navy>+ 常用算法</FONT></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD width=141 height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds01.htm">-
排序</A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds02.htm">-
列举法</A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds03.htm">-
归纳解析</A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds04.htm">-
递推与递归</A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds05.htm">-
回溯</A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds06.htm">-
搜索</A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds08.htm">-
动态规划</A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds10.htm">-
分治策略</A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds12.htm">- 贪心算法
</A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1 width=150></TD></TR>
<TR>
<TD height=20>
<P><A href="http://www.muduhs.com/~yanxm/pds13.htm">-
分支限界</A></P></TD></TR>
<TR>
<TD bgColor=#cccccc height=1><IMG height=1
width=150></TD></TR></TBODY></TABLE></TD>
<TD width=110></TD>
<TD width=559>
<TABLE cellSpacing=0 cellPadding=0 width=424>
<TBODY>
<TR>
<TD width=639 colSpan=2>
<P align=right> </P></TD></TR>
<TR>
<TD width=270>
<P><IMG height=20 src="分治策略.files/s2.gif" width=20
align=absMiddle border=0> <B>分治策略</B></P></TD>
<TD width=367>
<P align=right><A
href="http://www.muduhs.com/~yanxm/index1.htm">Index</A> >
<A href="http://www.muduhs.com/~yanxm/pds.htm">Alogri+Data
str</A> > <A
href="http://www.muduhs.com/~yanxm/pds00.htm">常用算法</A> >
分治策略</P></TD></TR>
<TR>
<TD width=639 background=分治策略.files/bg.gif colSpan=2
height=1></TD></TR>
<TR>
<TD width=639 colSpan=2>
<P><BR><SPAN class=title>分治策略</SPAN></P>
<P><FONT color=#cc0000>一、算法思想</FONT></P>
<P> 任何一个可以用计算机求解的问题所需的计算时间都与其规模有关。问题规模越小，解题所需的计算时间往往也越少，从而也越容易计算。想解决一个较大的问题，有时是相当困难的。分治法的思想就是，将一个难以直接解决的大问题，分割成一些规模较小的相同问题，以便各个击破，分而治之。</P>
<P> 分治的基本思想是将一个规模为n的问题分解为k个规模较小的子问题，这些子问题互相独立且与原问题相同。找出各部分的解，然后把各部分的解组合成整个问题的解。</P>
<P> 1、解决算法实现的同时，需要估算算法实现所需时间。分治算法时间是这样确定的：<BR> <BR>
解决子问题所需的工作总量（由 <FONT color=#0066cc>子问题的个数</FONT>、<FONT
color=#0066cc>解决每个子问题的工作量</FONT> 决定）<BR> 合并所有子问题所需的工作量</P>
<P> 2、分治法是把任意大小问题尽可能地等分成两个子问题的递归算法</P>
<P> 3、分治的具体过程：<BR> begin ｛开始｝<BR> if ①问题不可分 then ②返回问题解
<BR> else begin<BR>
③从原问题中划出含一半运算对象的子问题1；<BR> ④递归调用分治法过程，求出解1；<BR>
⑤从原问题中划出含另一半运算对象的子问题2；<BR>
⑥递归调用分治法过程，求出解2；<BR> ⑦将解1、解2组合成整修问题的解； <BR>
end;<BR> end; {结束}</P>
<P><FONT color=#cc0000>二、例题分析</FONT></P>
<P>
1、[金块问题]老板有一袋金块(共n块，n是2的幂（n>=2）），将有两名最优秀的雇员每人得到其中的一块，排名第一的得到最重的那块，排名第二的雇员得到袋子中最轻的金块。假设有一台比较重量的仪器，我们希望用最少的比较次数找出最重的金块。</P>
<P>分析:问题可以简化为：在含n（n是2的幂（n>=2））个元素的集合中寻找极大元和极小元。</P>
<P>明显的方法是逐个的进行比较查找。</P>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -