apsimon 的造币厂问题.htm

一个简单的小程序

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for j:=1 to
rj do<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>if e[j]=mn1 then<span style="mso-spacerun: yes">&nbsp; </span>显示&quot;没通过检验&quot;,结束;<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>inc(rj);
e[rj]:=rs1;<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>】;<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>A-3 通过检验,打印结果.<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp; </span>算法 B.利用递归生成所有可能的(a[1],a[2],...,a[n]),(b[1],b[2],...,b[n]).<o:p></o:p></span></p>

<p class=MsoPlainText><span style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>从中搜索满足条件的解<span
lang=EN-US>.记第i1次递归过程为next(i1).<o:p></o:p></span></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp; </span>B-1 if i1=n then {递归结束控制}<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>【b[i1]:=samp-ss;<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if
bb[i1]&gt;0<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>then<span style="mso-spacerun: yes">&nbsp; </span>for k:=0 to b[i1] do 【
a[i1]:=k; 执行算法A】<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>else 返回上层过程<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>】<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp; </span>B-2 i2:=mint-i1+1;<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>c[i1]:=(samp-ss+i2-1) div i2;<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>maxt:=c[i1]*2; {c[i1],maxt为对a[i1]或b[i1]搜索的下界,上界}<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>if i1&gt;1 then<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>【maxt:=a[i1-1];<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if
b[i1-1]&gt;a[i1-1] then maxt:=b[i1-1]】;<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp; </span>B-3 if i1&lt;=(mint
div 2) then<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for a[i1]:=c[i1]
to maxt do<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>【ss:=ss+a[i1];<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>if ss&lt;samp then<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>for b[i1]:=0 to a[i1] do next(i1+1);<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>ss:=ss-aa[i1];<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>】<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>else<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for b[i1]:=cc[i1]
to maxt do<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;</span><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>【ss:=ss+bb[i1];<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>if ss&lt;samp then<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>for a[i1]:=0 to b[i1] do next(i1+1)<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>ss:=ss-bb[i1];<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>】<span
style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span><o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp; </span>主算法:<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>(1) 输入 n,
samp, 令 ss:=0.<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>(2) i1=1, 执行算法
B.(next(i1))<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp; </span>第 1 段中的结果 L.1
就是利用该算法得到的.计算机程序是用Turbo Pascal 7.0编写的.实际计算表明,当n=6,7时,对固定的样本数,若有解,则解不唯一.容易分析,该算法的时间复杂性是指数型的.为了找到更好的结果(满足min(p<sub>n</sub>)&lt;2<sup>n-1</sup>),作者曾在一台奔腾200MHz的微机上运行数小时,鉴于时间太长，没有完成搜索.<o:p></o:p></span></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

<p class=MsoPlainText><b style='mso-bidi-font-weight:normal'><span lang=EN-US
style='font-size:12.0pt;mso-bidi-font-size:10.0pt'>4 结束语<o:p></o:p></span></b></p>

<p class=MsoPlainText><b style='mso-bidi-font-weight:normal'><span lang=EN-US
style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></b></p>

<p class=MsoPlainText><span lang=EN-US style='font-size:12.0pt;mso-bidi-font-size:
10.0pt'><span style="mso-spacerun: yes">&nbsp;&nbsp; </span>关于艾波西蒙问题还有许多工作可做.今后力图找出某些内在的规律,进而简化算法,从而可对更大的n进行搜索或得到更小的p<sub>n</sub>.作者深刻体会到,一些难题在数学理论上的研究,一旦与计算机算法联系起来,与实际的上机计算联系起来,必将有所突破,有所进展.<o:p></o:p></span></p>

<p class=MsoPlainText style='line-height:12.0pt'><span lang=EN-US
style='font-size:12.0pt;mso-bidi-font-size:10.0pt'><o:p></o:p></span></p>

<p class=MsoNormal><span lang=EN-US><![if !supportEmptyParas]>&nbsp;<![endif]><o:p></o:p></span></p>

</div>

</body>

</html>