no22.htm

常用经典算法及讲解

10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>次比较。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:20.0pt;
mso-char-indent-count:2.0;mso-char-indent-size:10.0pt;mso-layout-grid-align:
none;text-autospace:none'><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>下面用分而治之方法对这个问题进行求解。当</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>n</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>很小时，比如说， </span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>n</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>≤</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>2</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，识别出最重和最轻的金块，一次比较就足够了。当</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>n </span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>较大时（</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>n</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>＞</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>2</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>），第一步，把这袋金块平分成两个小袋</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>A</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>和</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>B</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>。第二步，分别找出在</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>A</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>和</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>B</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>中最重和最轻的金块。设</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>A</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>中最重和最轻的金块分别为</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>H</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A </span></i><span style='font-size:10.0pt;font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>与</span><i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>L</span></i><i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>A</span></i><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>，以此类推，</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>B</span></i><span style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>中最重和最轻的金块分别为</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>H</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>B </span></i><span style='font-size:10.0pt;font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>和</span><i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>L</span></i><i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>B</span></i><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>。第三步，通过比较</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>H</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A </span></i><span style='font-size:10.0pt;font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>和</span><i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>H</span></i><i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>B</span></i><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>，可以找到所有金块中最重的；通过比较</span><i><span lang=EN-US style='font-size:10.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>L</span></i><i><span
lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A </span></i><span style='font-size:10.0pt;font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>和</span><i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>L</span></i><i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>B</span></i><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>，可以找到所有金块中最轻的。在第二步中，若</span><i><span lang=EN-US style='font-size:10.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>n</span></i><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>＞</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>2</span><span style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>，则递归地应用分而治之方法。<span
lang=EN-US><o:p></o:p></span></span></p>

<p class=MsoNormal align=left style='text-align:left;text-indent:20.0pt;
mso-char-indent-count:2.0;mso-char-indent-size:10.0pt;mso-layout-grid-align:
none;text-autospace:none'><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>假设</span><i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>n</span></i><span lang=EN-US style='font-size:10.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>= 8</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>。这个袋子被平分为各有</span><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>4</span><span style='font-size:
10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>个金块的两个袋子</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>A</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>和</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>B</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>。为了在</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>A</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>中找出最重和最轻的金块，</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>A</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>中的</span><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>4</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>个金块被分成两组</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>A</span></i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>和</span><i><span lang=EN-US style='font-size:
10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>A</span></i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>2</span><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>。每一组有两个金块，可以用一次比较在</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>A</span></i><span style='font-size:10.0pt;
font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>中找出较重的金块</span><i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>H</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A</span></i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>和较轻的金块</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>L</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A</span></i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>。经过另外一次比较，又能找出</span><i><span lang=EN-US style='font-size:10.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>H</span></i><i><span
lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A </span></i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>2</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>和</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>L</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A </span></i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>2</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>。现在通过比较</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>H</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A</span></i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>1</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>和</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>H</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A</span></i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>2</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>，能找出</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>H</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A</span></i><span style='font-size:10.0pt;font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>；通过</span><i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>L</span></i><i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>A </span></i><span
lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>1</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>和</span><i><span lang=EN-US style='font-size:
10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>L</span></i><i><span
lang=EN-US style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A</span></i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>2</span><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>的比较找出</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>L</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A</span></i><span style='font-size:10.0pt;font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>。这样，通过</span><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>4</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>次比较可以找到</span><i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>H</span></i><i><span lang=EN-US style='font-size:5.0pt;
mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>A </span></i><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>和</span><i><span lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>L</span></i><i><span lang=EN-US
style='font-size:5.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>A</span></i><span style='font-size:10.0pt;font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>。同样需要另外</span><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>4</span><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>次比较来确定</span><i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>H</span></i><i><span lang=EN-US style='font-size:5.0pt;