no22.htm

常用经典算法及讲解

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'>1</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'>2</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'>3</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><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>5</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'>6</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'>8</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><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>1 6</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'>8</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><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><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><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1 6</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'>8</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><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1 6</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><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1 6</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><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1 6</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'>8</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'>B</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'>B</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'>B</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'>B</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'>B</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'>B</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'>B</span></i><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>1<i>a</i></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'>B</span></i><span lang=EN-US
style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;color:black;
mso-font-kerning:0pt'>1<i>b</i></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.1pt;
mso-char-indent-count:2.0;mso-char-indent-size:10.05pt;mso-layout-grid-align:
none;text-autospace:none'><b><span style='font-size:10.0pt;font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>例<span lang=EN-US>2</span></span></b><b><span
lang=EN-US style='font-size:10.0pt;font-family:Arial;mso-fareast-font-family:
仿宋_GB2312;color:black;mso-font-kerning:0pt'>-2 [</span></b><b><span
style='font-size:10.0pt;font-family:仿宋_GB2312;color:black;mso-font-kerning:
0pt'>金块问题</span></b><b><span lang=EN-US style='font-size:10.0pt;font-family:
Arial;mso-fareast-font-family:仿宋_GB2312;color:black;mso-font-kerning:0pt'>] </span></b><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 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'>M a x</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'>1 - 3 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'>n</span></i><span lang=EN-US 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'>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'>n</span></i><span lang=EN-US
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'>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'>n</span></i><span lang=EN-US
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><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>2<i>n</i></span><span lang=EN-US
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'>3</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'>2 - 2 6</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'>2 - 2 7</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'>2<i>n</i></span><span lang=EN-US
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><span
lang=EN-US style='font-size:10.0pt;mso-fareast-font-family:仿宋_GB2312;
color:black;mso-font-kerning:0pt'>2<i>n</i></span><span lang=EN-US
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: