no12.htm

常用经典算法及讲解

</span>');</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>writeln;</span></p>

<p class=MsoPlainText><span lang=EN-US>end.</span></p>

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>2. 发行一套四种不同面值的邮票,限定使用时不超过3枚,为了能连续贴出</span></p>

<p class=MsoPlainText><span lang=EN-US>1,2,...,r的面值, 如何确定四种面值,使 r 最大?</span></p>

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

<p class=MsoPlainText><span lang=EN-US>program lxw002;</span></p>

<p class=MsoPlainText><span lang=EN-US>var</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>s1,s2,s3,s4: integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>r,r0,r1,r2,r3,r4: integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>stamp: set of 1..100;</span></p>

<p class=MsoPlainText><span lang=EN-US>function
workr(s1,s2,s3,s4:integer):integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var n1,n2,n3,n4,f:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>stamp:=[];</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>for n1:=0 to 3 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for n2:=0 to 3-n1 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for n3 :=0 to 3-n1-n2 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for n4:=0 to
3-n1-n2-n3 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>f:=n1*s1+n2*s2+n3*s3+n4*s4;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>stamp:=stamp+[f]</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>f:=1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>while f in stamp do f:=f+1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>workr:=f-1</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US>begin{main};</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>s1:=1;<span style="mso-spacerun: yes">&nbsp; </span><span
style="mso-spacerun: yes">&nbsp;</span>r0:=0;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>for s2:=s1+1 to 3*s1+1 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>for s3:=s2+1 to 3*s2+1 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>for s4:=s3+1 to 3*s3+1 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>r:=workr(s1,s2,s3,s4);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>if r&gt;r0
then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>r0:=r;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;
</span>r1:=s1; r2:=s2; r3:=s3; r4:=s4</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;</span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>writeln('s1=',r1,',<span style="mso-spacerun: yes">&nbsp;
</span>s2=',r2,',<span style="mso-spacerun: yes">&nbsp; </span>s3=',r3,',<span
style="mso-spacerun: yes">&nbsp; </span>s4=',r4);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>writeln('The max Value is: ',r0)</span></p>

<p class=MsoPlainText><span lang=EN-US>end.</span></p>

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>3. n个A与n个B(n≥4)排成一排, 开始时, 字符B全排在A的后面,然后将它移成</span></p>

<p class=MsoPlainText><span lang=EN-US>A,B 相间的情形: AAAABBBB → ABABABAB. 要求如下:</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;</span>(1) 每次同时移动两相邻字符, 不得调换顺序.</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;</span>(2) 总步数应尽量少.</span></p>

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

<p class=MsoPlainText><span lang=EN-US>program lxw003;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var i,n,step:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>s:array [1..100] of char;</span></p>

<p class=MsoPlainText><span lang=EN-US>procedure display;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var i:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>write('No.',step:2,'<span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>');</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>for i:=1 to 2*n+2 do write(s[i]);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>writeln</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US>procedure move(i,k:integer);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var j:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>step:=step+1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>for j:=0 to 1 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin<span style="mso-spacerun:
yes">&nbsp; </span>s[k+j]:=s[i+j];<span style="mso-spacerun: yes">&nbsp;
</span>s[i+j]:=' '<span style="mso-spacerun: yes">&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>display</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US>begin{main}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>repeat<span style="mso-spacerun: yes">&nbsp;&nbsp;&nbsp;
</span>writeln('input n:');<span style="mso-spacerun: yes">&nbsp;
</span>readln(n)<span style="mso-spacerun: yes">&nbsp;&nbsp; </span>until
n&gt;3;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>step:=0;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>for i:=1 to n do s[i]:='A';</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>for i:=n+1 to 2*n do s[i]:='B';</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>s[2*n+1]:=' ';<span style="mso-spacerun: yes">&nbsp;&nbsp;
</span>s[2*n+2]:=' ';</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>display;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>if n&gt;4 then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>for i:=n downto 5 do</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin<span style="mso-spacerun:
yes">&nbsp; </span>move(i,2*i+1);<span style="mso-spacerun: yes">&nbsp;&nbsp;
</span>move(2*i-1,i)<span style="mso-spacerun: yes">&nbsp;&nbsp; </span>end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>move(4,9);<span style="mso-spacerun: yes">&nbsp; </span>move(8,4);<span
style="mso-spacerun: yes">&nbsp; </span>move(2,8);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>move(7,2);<span style="mso-spacerun: yes">&nbsp; </span>move(1,7)</span></p>

<p class=MsoPlainText><span lang=EN-US>end.</span></p>

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

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>4. 由键盘输入N, B={1,2,...,N}为连续N个整数的集合, 取B中若干不同的整</span></p>

<p class=MsoPlainText>数<span lang=EN-US>, 使这些整数之和为给定的M, 共有多少种不同的取法?</span></p>

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

<p class=MsoPlainText><span lang=EN-US>program lxw004;</span></p>

<p class=MsoPlainText><span lang=EN-US>var<span style="mso-spacerun:
yes">&nbsp; </span>m,n,i:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp; </span>s:longint;</span></p>

<p class=MsoPlainText><span lang=EN-US>function aa(k,m:integer):longint;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>var i,t1,kz:integer;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>temp:longint;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>begin</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if (k&gt;m) or (k=1)and(m&gt;1) or
(k=0)and(m&gt;0) then</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp;&nbsp;&nbsp; </span>begin aa:=0; exit end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if k=m then begin aa:=1; exit end;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>temp:=0; {处理 k&lt;m的情形}</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>t1:=m-k; kz:=k-1;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>if kz&gt;m-k then kz:=m-k;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>for i:=1 to kz do<span style="mso-spacerun:
yes">&nbsp; </span>temp:=temp+aa(i,t1);</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun:
yes">&nbsp;&nbsp;&nbsp; </span>aa:=temp;</span></p>

<p class=MsoPlainText><span lang=EN-US><span style="mso-spacerun: yes">&nbsp;
</span>end;</span></p>