2022年动态程序设计 .pdf

例题 1求最大连续子序列的和输入：n(n500)；n 个整数；输出：该序列中最大的连续子序列的和max 。$A+,B-,C+,D+,E-,F-,G+,H+,I+,J+,K-,L+,M-,N+,O+,P+,Q-,R+,S-,T-,U-,V+,W-,X+,Y+,Z1 $MINSTACKSIZE $00004000 $MAXSTACKSIZE $00100000 $IMAGEBASE $00400000 $APPTYPE GUI program ex11_1; $APPTYPE CONSOLE uses SysUtils; const infile=ex11_1.in; outfile=ex11_1.out; var n,i:integer; j,m,max:longint; f,f0:text; begin / Insert user code here assign(f,infile); reset(f); assign(f0,outfile); rewrite(f0); repeat readln(f,n); read(f,m); max:=m; for i:=2 to n do begin read(f,j); if m0 then m:=m+j else m:=j; if mmax then max:=m end; writeln(f0,max) until seekeof(f); close(f); close(f0) end. 例题 22 台处理机A 和 B 承担 n 个作业的任务。设第I 个作业交给机器A 处理时需要ai时间，交给机器B 处理时需要bi时间。由于各作业的特点和机器性能的关系，很可能对于某些 I 有 aibi，而对于某些作业j(j i)有 ai=b then max:=a else max:=b end; procedure search(nw:integer;na,nb:real); begin if max(na,nb)=bt then exit; if nw=n+1 then begin bt:=max(na,nb); exit end; if max(na+anw,nb)=max(na,nb+bnw) then begin search(nw+1,na+anw,nb); search(nw+1,na,nb+bnw) end else begin search(nw+1,na,nb+bnw); search(nw+1,na+anw,nb) end end; begin assign(f,ex11_2.in); reset(f); assign(f0,ex11_2.out); rewrite(f0); while not seekeof(f) do begin readln(f,n); al:=0; bl:=0; for i:=1 to n do begin readln(f,ai,bi); if ai=bi then al:=al+ai else bl:=bl+bi end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 25 页 - - - - - - - - - bt:=max(al,bl); search(1,0,0); writeln(f0,bt:8:2) end; close(f); close(f0) end. 例题 3有 F 束花由左而右插在V 个花瓶内（ 1FV 100） 。花与瓶分别用1F 与 1V的整数标识。 花要按照花的标识数递增排列，不同的花插在不同的瓶子里产生不同的美学价值（ -50 到 50 之间）。求最大的美学价值及其一种摆放方式。program ex11_3; $APPTYPE CONSOLE uses SysUtils; const infile=d:ex11_3.in; outfile=ex11_3.out; max=1000; maxint=10000; type arr=array1.maxof integer; var fn,vn,i,j,k:integer; v:array1.max,1.maxof integer; c0,c1:array0.maxof longint; p0,p1:array0.maxof arr; ansp:arr; ans:longint; f,f0:text; function min(a,b:longint):longint; begin if ac0i-1+vi,k then begin c1i:=c0i; p1i:=p0i end else begin c1i:=c0i-1+vi,k; p1i:=p0i-1; p1i,i:=k end; if c1fnans then begin ans:=c1fn; ansp:=p1fn end; c0:=c1; p0:=p1 end; writeln(f0,ans); for i:=1 to fn do writeln(f0,Flower ,i, : Vase ,anspi) until seekeof(f); close(f); close(f0) end. 例题 4有四个圆柱A，B，C，D。n 个圆盘按照由小至大的顺序摞在A 柱上 (如图 11.3.1)。如何以最少次数将圆盘从A 柱移至 D 柱图 11.3.1 移动必须满足三个条件：能利用 A， B，C，D 四个圆柱；一次只能搬动一个圆盘；小的圆盘只能往大的圆盘上摞；$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R-,S+,T-,V+,X+,Y+ $M 40000,0,655360 program ex11_4; const infile=ex11_4.in; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 25 页 - - - - - - - - - outfile=ex11_4.out; max=50; var n,i,j,k:integer; c3,c4:array1.maxof longint; as:array1.maxof integer; f,f0:text; procedure mv3(a,c,b:char;h,t:integer); var n:integer; begin n:=h-t+1; if t ,c); mv3(b,c,a,h,t-1) end; procedure mv4(a,d,b,c:char;h,t:integer); var n:integer; begin n:=t-h+1; if th then exit; mv4(a,c,b,d,h,h+asn-1); mv3(a,d,b,h+asn,t); mv4(c,d,a,b,h,h+asn-1) end; begin assign(f,infile); reset(f); assign(f0,outfile); rewrite(f0); repeat readln(f,n); c31:=1; for i:=2 to n do c3i:=c3i-1*2+1; for k:=1 to n do begin c4k:=c3k; ask:=0; for i:=1 to k-1 do if 2*c4i+c3k-ic4k then begin c4k:=2*c4i+c3k-i; ask:=i end end; mv4(A,D,B,C,1,n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 25 页 - - - - - - - - - writeln(f0,Total of ,n, plates: ,c4n) until seekeof(f); close(f); close(f0) end. 例题 5关系“ ”和“ =”将 3 个数 A，B和 C依序排列时，有13 种不同的序关系：A=B=C A=BC AB=C ACB ACB A=CB BA=C BAC BCA B=CA CA=B CAB CBA 若要将 n 个数依序进行排列，试设计一个算法，计算出有多少种不同的序关系。$A+,B-,C+,D+,E-,F-,G+,H+,I+,J+,K-,L+,M-,N+,O+,P+,Q-,R+,S-,T-,U-,V+,W-,X+,Y+,Z1 $MINSTACKSIZE $00004000 $MAXSTACKSIZE $00100000 $IMAGEBASE $00400000 $APPTYPE GUI program ex11_5; $APPTYPE CONSOLE uses SysUtils; const infile=d:ex11_5.in; outfile=d:ex11_5.out; max=100; type arrints=record data:array1.100of longint; p:integer end; var n,i,j:integer; cn:array0.maxof arrints; a,b:arrints; c:array0.max,0.maxof arrints; f,f0:text; procedure creat(var a:arrints;n:integer); begin fillchar(a.data,sizeof(a.data),0); a.p:=0; while n0 do begin a.p:=a.p+1; a.dataa.p:=n mod 10000; n:=n div 10000 end end; procedure plus(a,b:arrints;var c:arrints); var 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 6 页，共 25 页 - - - - - - - - - i,m:integer; begin if a.p=b.p then m:=a.p else m:=b.p; creat(c,0); c.p:=m; for i:=1 to m do with c do begin datai:=datai+a.datai+b.datai; datai+1:=datai+1+datai div 10000; datai:=datai mod 10000 end; if c.datac.p+10 then inc(c.p) end; procedure multiply1(a:arrints;n:integer;var c:arrints); var i:integer; begin fillchar(c.data,sizeof(c.data),0); c.p:=a.p; for i:=1 to a.p do with c do begin datai:=datai+a.datai*n; datai+1:=datai div 10000; datai:=datai mod 10000 end; while c.datac.p+10 do inc(c.p) end; procedure multiply2(a,b:arrints;var c:arrints); var i,j:integer; d,e:arrints; begin multiply1(a,b.datab.p,c); for i:=b.p-1 downto 1 do begin inc(c.p); for j:=c.p downto 2 do c.dataj:=c.dataj-1; c.data1:=0; multiply1(a,b.datai,d); plus(c,d,e); c:=e end; end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 25 页 - - - - - - - - - procedure print(a:arrints); var i:integer; s:string; begin write(f0,a.dataa.p); for i:=a.p-1 downto 1 do begin str(a.datai,s); while length(s)4 do s:=0+s; write(f0,s) end; writeln(f0) end; begin / Insert user code here assign(f,infile); reset(f); assign(f0,outfile); rewrite(f0); fillchar(c,sizeof(c),0); creat(c0,0,1); for i:=1 to max do begin creat(ci,0,1); for j:=1 to i do begin plus(ci-1,j,ci-1,j-1,a); ci,j:=a end end; fillchar(cn,sizeof(cn),0); creat(cn0,1); for i:=1 to max do for j:=1 to i do begin multiply2(cni-j,ci,j,a); plus(cni,a,b); cni:=b end; repeat readln(f,n); print(cnn) until seekeof(f); close(f); close(f0); end. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 25 页 - - - - - - - - - 例题 6设给定 n 个变量 x1,x2,xn, 将这些变量依序作底和各层幂，可得出如图11.3.2 的 n重幂：123xxxxn图 11.3.2这里将上述n 重幂看作是不确定的，当在其中加入适当的括号后，才能成为一个确定的n 重幂。通常将n 重幂的理解为图11.3.3 所示的形状：图 11.3.3不同的加括号方式导致不同的n 重幂。例如，当n=4 时， x1,x2,x3,x4的全部 4 重幂有 5个。试设计一个算法，对n 个变量计算出有多少个不同的n 重幂。program ex11_6; $APPTYPE CONSOLE uses SysUtils,arrint; const infile=ex11_6.in; outfile=ex11_6.out; max=100; var n,i,j:integer; c:array1.maxof arrints; f,f0:text; begin / Insert user code here assign(f,infile); reset(f); assign(f0,outfile); rewrite(f0); fillchar(c,sizeof(c),0); creat(c1,1); for i:=2 to max do for j:=1 to i-1 do begin 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 9 页，共 25 页 - - - - - - - - - multiply2(cj,ci-j,a); plus(ci,a,b); ci:=b end; repeat readln(f,n); print(cn,f0,false) until seekeof(f); close(f); close(f0) end. 例题7给定由n 个英文单词组成的的一段文章，每个单词的长度（字符个数）依序为l1,l2, , ， ln。我们要在一台打印机上将这段文章“漂亮地”打印出来。打印机每行最多可打印 M个字符。这时所说的“漂亮”的定义如下。在打印机所打印的每一行中，行首和行尾可不留空格，行中每2 个单词之间留一个空格。这样如果在一行中打印从单词i 到单词j的字符，则按打印规则，应在一行中恰好打印jikkijl个字符（包括字间空格字符），且不允许将单词打破。多余的空格数为jikklijM。除文章的最后一行外，希望每行多余的空格数尽可能少。因此， 我们以各行（最后一行除外）的多余空格数的立方和达到最小作为“漂亮”的标准。请设计一个“漂亮打印”方案。$A+,B-,C+,D+,E-,F-,G+,H+,I+,J+,K-,L+,M-,N+,O+,P+,Q-,R+,S-,T-,U-,V+,W-,X+,Y+,Z1 $MINSTACKSIZE $00004000 $MAXSTACKSIZE $00100000 $IMAGEBASE $00400000 $APPTYPE GUI program ex11_7; $APPTYPE CONSOLE uses SysUtils; const infile=ex11_7.in; outfile=ex11_7.out; max=20; maxint=100000; var n,m,i,j,k,cn,ak,ai:integer; ans:longint; l:array0.maxof integer; c:array0.max,0.maxof longint; lg:array0.max,0.maxof integer; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 10 页，共 25 页 - - - - - - - - - f,f0:text; function power(i:longint):longint; begin power:=i*i*i end; procedure putout(k,i:integer); var j:integer; begin if k=0 then exit; for j:=i-1 downto k-1 do if (lgj+1,im then break; cn:=i; inc(cn); if cnn then begin writeln(f0,Print is impossible.); continue end; if cn=1 then begin writeln(f0,0); writeln(f0,Line 1 : ,n); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 25 页 - - - - - - - - - continue end; readln(f); ans:=maxint; for i:=1 to n do c0,i:=maxint; c0,0:=0; for k:=1 to n-1 do begin for i:=0 to k-1 do ck,i:=maxint; for i:=k to n-1 do begin ck,i:=maxint; for j:=i-1 downto k-1 do if (lgj+1,i=m) and (ck-1,j+power(m-lgj+1,i)ck,i) then ck,i:=ck-1,j+power(m-lgj+1,i) end; for i:=cn-1 to n-1 do if ck,ians then begin ans:=ck,i; ak:=k; ai:=i end end; writeln(f0,ans); putout(ak,ai); writeln(f0,Line ,ak+1, : ,n-ai) until seekeof(f); close(f); close(f0) end. 例题 8设 A 和 B 是 2 个字符串。我们要用最少的字符操作，将字符串A转换为字符串B。这里所说的字符操作包括a. 删除一个字符；b. 插入一个字符；c. 将一个字符改为另一个字符。将字符串 A变换为字符串B所用的最少字符操作数称为字符串A到 B的编辑距离， 记为（A ， B） 。试设计一个有效算法，对任给的2 个字符串A 和 B，计算出它们的编辑距离（A，B） 。$A+,B-,D+,E+,F-,G-,I+,L+,N-,O-,P-,Q-,R+,S+,T-,V+,X+,Y+ $M 16384,0,655360 program ex11_8; const infile=ex11_8.in; outfile=ex11_8.out; var 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 25 页 - - - - - - - - - a,b,s1:string; p,q,i,j,k,t:integer; d0,d1:array0.260of integer; f,f0:text; function one(a:char;s:string):integer; begin if pos(a,s)=0 then one:=length(s) else one:=length(s)-1 end; begin assign(f,infile); reset(f); assign(f0,outfile); rewrite(f0); repeat readln(f,a); readln(f,b); p:=length(a); q:=length(b); d00:=1; for i:=0 to q do begin s1:=copy(b,1,i); d0i:=one(a1,s1) end; for k:=2 to p do begin d10:=k; for i:=1 to q do begin s1:=copy(b,1,i); d1i:=d0i+1; for j:=0 to i-1 do begin s1:=copy(b,j+1,i-j); t:=one(ak,s1); if d0j+td1i then d1i:=d0j+t end end; d0:=d1 end; writeln(f0,d1q) until seekeof(f); close(f); close(f0) end. 例题 9在一个操场上摆放着一行共n 堆石子。现要将石子有序地合并成一堆。规定每次只名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 13 页，共 25 页 - - - - - - - - - 能选相邻的2 堆合并成新的一堆，并将新的一堆的石子数记为该次合并的得分。请计算出将n 堆石子合并成一堆的最小得分和将n 堆石子合并成一堆的最大得分。program ex11_9; const mx=1000; var n,i,j,k:integer; a,b:array1.mxof longint; max,min:longint; f,f0:text; begin assign(f,ex11_9.in); reset(f); assign(f0,ex11_9.out); rewrite(f0); while not seekeof(f) do begin readln(f,n); for i:=1 to n do begin read(f,ai); bi:=ai end; max:=0; min:=0; for k:=n-1 downto 1 do begin j:=1; for i:=2 to k-1 do if ai+ai+1bj+bj+1 then j:=i; max:=max+bj+bj+1; bj:=bj+bj+1; for i:=j+1 to k-1 do bi:=bi+1 end; writeln(f0,min, ,max) end; close(f); close(f0) end. 例题 10在一个圆形操场的四周摆放着n 堆石子。 现要将石子有次序地合并成一堆。规定每次只能选相邻的2 堆石子合并成新的一堆，并将新的一堆石子数记为该次合并的得分。试设计一个算法，计算出将n 堆石子合并成一堆的最小得分和最大得分。program ex11_9; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 25 页 - - - - - - - - - $APPTYPE CONSOLE uses SysUtils; const mx=1000; maxint=1000000; var n,i,j,k,l1,l2,k0:integer; st:array1.mxof longint; c1,c2:array1.mx,1.mxof longint; min,max:longint; f,f0:text; begin assign(f,ex11_9.in); reset(f); assign(f0,ex11_9.out); rewrite(f0); while not seekeof(f) do begin readln(f,n); for i:=1 to n do begin read(f,sti); c1i,i:=0; c2i,i:=0 end; for l1:=2 to n do for i:=1 to n do begin j:=i+l1-1; if jn then dec(j,n); c1i,j:=maxint; c2i,j:=0; for l2:=1 to l1-1 do begin k:=i+l2-1; if kn then dec(k,n); k0:=k mod n+1; if c1i,k+c1k0,jc2i,j then c2i,j:=c2i,k+c2k0,j; end; k:=i; repeat inc(c1i,j,stk); inc(c2i,j,stk); k:=k mod n+1 until k=j mod n+1 end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 25 页 - - - - - - - - - if n=0 then min:=0 else min:=maxint; for i:=1 to n do if c1i mod n+1,imax then max:=c2i mod n+1,i; writeln(f0,min, ,max) end; close(f); close(f0) end. 例题 11输入硬币的n 种不同面值（各种面值的硬币个数不限）和m，输出找出钱数1m元的最少硬币数。$A+,B-,C+,D+,E-,F-,G+,H+,I+,J+,K-,L+,M-,N+,O+,P+,Q-,R+,S-,T-,U-,V+,W-,X+,Y+,Z1 $MINSTACKSIZE $00004000 $MAXSTACKSIZE $00100000 $IMAGEBASE $00400000 $APPTYPE GUI program ex11_11; $APPTYPE CONSOLE uses SysUtils; const maxint=100000000; var n,m,i,j:integer; my,c,p:array0.1000of longint; f,f0:text; begin / Insert user code here assign(f,ex11_11.in); reset(f); assign(f0,ex11_11.out); rewrite(f0); while not seekeof(f) do begin readln(f,n,m); for i:=1 to n do read(f,myi); c0:=0; p0:=0; for i:=1 to m do begin ci:=maxint; for j:=1 to n do if (myj=i) and (i div myj+cmyj-1ci) then begin 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 25 页 - - - - - - - - - ci:=i div myj+cmyj-1; pi:=j end end; if cm=maxint then begin writeln(f0,Impossible.); continue end; writeln(f0,cm); i:=m; while i0 do begin for j:=1 to i div mypi do write(f0,mypi, ); i:=mypi-1 end; writeln(f0) end; close(f); close(f0) end. 例题 12寻宝游戏要求参赛者根据“藏宝图” （n*m 个数的表格） 和不同地点的提示信息（数列） ，在最短时间内找出埋藏在某处的“宝物”。当前位置与“藏宝点”的距离为数列与表格的接近程度。 “接近程度”的定义：假设提示数列为ai，那么“藏宝图”中找出与其最接近的数列 bi( 数列项数为len)，这两个数列的接近程度就是数列与表格的接近程度，其中数列的接近程度D=21)(leniiiba，D 越小表示越接近。除此而外，数列bi还有以下限制：用（xi，yi）表示数列 bi中第 i 项在表格中的位置，则要求)1(111leniyyxxiiii，且同一位置可能在数列中出现多次。输入：n m(“藏宝图”的规模，2n，m50)；n*m 的“藏宝图” （矩阵元素值小于100） ；数列 ai 的项数 len（1 len 150） ；长度为 len 的数列 ai（数列的元素值小于100） ；输出：数列与表格的接近程度。program ex11_12; $APPTYPE CONSOLE uses SysUtils; const ex:array1.4of shortint=(0,0,1,-1); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 25 页 - - - - - - - - - ey:array1.4of shortint=(1,-1,0,0); var n,m,len,i,j,k,l,i0,j0:integer; mp:array1.50,1.50of integer; c0,c1:array1.50,1.50of longint; a:array1.150of integer; ans:longint; f,f0:text; begin / Insert user code here assign(f,ex11_12.in); reset(f); assign(f0,ex11_12.out); rewrite(f0); while not seekeof(f) do begin readln(f,n,m); for i:=1 to n do for j:=1 to m do read(f,mpi,j); readln(f,len); for i:=1 to len do read(f,ai); for i:=1 to n do for j:=1 to m do c0i,j:=sqr(a1-mpi,j); for k:=2 to len do begin for i:=1 to n do for j:=1 to m do begin c1i,j:=maxint; for l:=1 to 4 do begin i0:=i+exl; j0:=j+eyl; if (i0 in 1.n) and (j0 in 1.m) and (c0i0,j0c1i,j) then c1i,j:=c0i0,j0 end; c1i,j:=c1i,j+sqr(mpi,j-ak) end; c0:=c1 end; ans:=maxint; for i:=1 to n do for j:=1 to m do if c1i,jans then ans:=c1i,j; writeln(f0,ans) 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 25 页 - - - - - - - - - end; close(f); close(f0) end. 例题 13 某港口有一批尺寸规格相同的箱子，编号为1,n。现在要将其中某些箱子按照如下规则叠放起来每个箱子上最多只能直接叠放一个箱子；编号小的箱子不能放在编号大的箱子之上；每个箱子给出了自身重量和可承受重量，每个箱子之上的所有箱子重量之和不得超过该箱子的可承受重量；为了节省堆放场地，希望在满足条件的情况下，叠放的箱子数最多。输入：箱子数 n(1 n500) ；以下为 n 行，其中第i 行为箱子i 的自身重量和可承受重量；输出：最多可叠放的箱子数M ；按照由上至下（即编号递减）的叠放顺序，给出M个箱子的编号。program ex11_13; $APPTYPE CONSOLE uses SysUtils; const infile=d:ls.txt; outfile=ex11_13.out; max=500; maxint=1000000; var n,i,j,k,ak,ai,n0:integer; r1:double; w,v:array1.maxof double; c:array0.max,0.maxof double; a:array0.max,0.maxof integer; b:boolean; f,f0:text; begin O(n3)=1.25*108 / Insert user code here assign(f,infile); reset(f); assign(f0,outfile); rewrite(f0); while not seekeof(f) do begin readln(f,n); for i:=1 to n do readln(f,wi,vi); 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 25 页 - - - - - - - - - c0,0:=maxint; for k:=1 to n do begin b:=false; for i:=k to n do begin ck,i:=-maxint; for j:=k-1 to i-1 do begin if vick,i then begin ck,i:=r1; ak,i:=j end end; if ck,i=0 then begin b:=true; ak:=k; ai:=i end end; if not b then break end; writeln(f0,ak); n0:=ak; f