82111668版Pascal算法高级视频教程附带例题与答案.docx
《82111668版Pascal算法高级视频教程附带例题与答案.docx》由会员分享，可在线阅读，更多相关《82111668版Pascal算法高级视频教程附带例题与答案.docx（18页珍藏版）》请在冰点文库上搜索。
82111668版Pascal算法高级视频教程附带例题与答案
82111668_2012版Pascal高级算法视频教程附带例题与答案
例：
2.1.1高精度加法
programex（input,output）;
typearr=array[1..256]ofinteger;
varst1,st2,st3:
string;
sz1,sz2,sz3:
arr;
i:
integer;
proceduresum（st:
string;varsz:
arr）;
vari,code:
integer;
begin
fori:
=1tolength（st）do
val（st[length（st）+1-i],sz[i],code）;
end;
functionfac:
boolean;
varj:
integer;
begin
fac:
=true;
forj:
=256downtoi+1do
ifsz3[j]<>0then
begin
fac:
=false;
exit;
end;
end;
procedurestart;
begin
fori:
=1to256do
begin
sz1[i]:
=0;
sz2[i]:
=0;
sz3[i]:
=0;
end;
end;
begin
start;
readln（st1）;
readln（st2）;
sum（st1,sz1）;
sum（st2,sz2）;{字符串→数组}
st3:
='';
fori:
=1to255do
begin
sz3[i+1]:
=（sz3[i]+sz1[i]+sz2[i]）div10;
sz3[i]:
=（sz3[i]+sz1[i]+sz2[i]）mod10;
end;{加法}
fori:
=1to256do
begin
st3:
=chr（sz3[i]+48）+st3;
iffacthenbreak;
end;{数组→字符串}
writeln（st1,'+',st2,'=',st3）;
readln;
end.
例2.1.2.1高精度减法_1
programex（input,output）;
typearr=array[1..65536]ofinteger;
varst1,st2,st3:
ansistring;
sz1,sz2,sz3:
arr;
i:
integer;
proceduresum（st:
string;varsz:
arr）;
vari,code:
integer;
begin
fori:
=1tolength（st）do
val（st[length（st）+1-i],sz[i],code）;
end;
functionfac:
boolean;
varj:
integer;
begin
fac:
=true;
forj:
=256downtoi+1do
ifsz3[j]<>0then
begin
fac:
=false;
exit;
end;
end;
procedurestart;
begin
fori:
=1to256do
begin
sz1[i]:
=0;
sz2[i]:
=0;
sz3[i]:
=0;
end;
end;
begin
start;
readln（st1）;
readln（st2）;
sum（st1,sz1）;
sum（st2,sz2）;{字符串→数组}
st3:
='';
fori:
=1to255do
begin
sz3[i]:
=sz3[i]+sz1[i]-sz2[i];
ifsz3[i]<0then
begin
sz3[i]:
=sz3[i]+10;
sz3[i+1]:
=sz3[i+1]-1;
end;
end;{减法}
fori:
=1to256do
begin
st3:
=chr（sz3[i]+48）+st3;
iffacthenbreak;
end;{数组→字符串}
writeln（st1,'-',st2,'=',st3）;
readln;
end.
例2.1.2.2高精度减法_2
programex（input,output）;
typearr1=array[1..65536]ofshortint;
arr2=array[1..65536]ofchar;
varsz1,sz2,sz3:
arr1;
s1,s2:
arr2;
n,m,i:
longint;
begin
fori:
=1to65536dobeginsz1[i]:
=0;sz2[i]:
=0;sz3[i]:
=0;end;
n:
=0;
whilenot（eoln（））do
begin
inc（n）;
read（s1[n]）;
end;
fori:
=1tondosz1[i]:
=integer（s1[n+1-i]）-48;
readln（）;
m:
=0;
whilenot（eoln（））do
begin
inc（m）;
read（s2[m]）;
end;
readln（）;
fori:
=1tomdosz2[i]:
=integer（s2[m+1-i]）-48;
fori:
=1tondo
begin
sz3[i]:
=sz3[i]+sz1[i]-sz2[i];
ifsz3[i]<0then
begin
sz3[i]:
=sz3[i]+10;
sz3[i+1]:
=-1;
end;
end;
i:
=n;
while（i>0）and（sz3[i]=0）dodec（i）;
ifi=0thenwriteln（0）
else
begin
fori:
=idownto1dowrite（sz3[i]）;
writeln（）;
end;
readln;
end.
例2.3.1：
插入排序
programinsert_sort（input,output）;
vari,j,n,k:
integer;a:
array[1..100]ofinteger;
begin
readln（n）;
fori:
=1tondoread（a[i]）;
readln;
fori:
=2tondo
begin
k:
=a[i];
j:
=i;
while（j>=2）and（a[j-1]>k）do
begin
a[j]:
=a[j-1];
dec（j）;
end;
a[j]:
=k;
end;
fori:
=1tondowrite（a[i]）;
writeln;
readln;
end.
例3.3.1：
先序遍历
procedurefirst（p:
point）;
begin
ifp=nilthenexit;
writeln（p^.data）;
first（p^.left）;
first（p^.right）;
end;
例3.3.2：
中序遍历
proceduremiddle（p:
point）;
begin
ifp=nilthenexit;
middle（p^.left）;
writeln（p^.data）;
middle（p^.right）;
end;
例3.3.3：
后序遍历
procedurelast（p:
point）;
begin
ifp=nilthenexit;
last（p^.left）;
last（p^.right）;
writeln（p^.data）;
end;
例3.3.4：
树的宽度搜索
programBFS（input,output）;
typepoint=^node;
node=record
data:
integer;
left,right:
point;
end;
queue=object
constmaxn=1000;
data:
array[1..maxn]ofpoint;
front,rear:
integer;
functionempty（）:
boolean;
procedureadd（n:
point）;
end;
functionqueue.empty（）:
boolean;
begin
exit（front=rear）;
end;
procedurequeue.add（n:
point）;
begin
inc（rear）;
data[rear]:
=n;
end;
varhead,p:
point;q:
queue;
begin
{输入二叉树。
}
q[1]:
=head;
q.front:
=0;
repeat
inc（q.front）;
ifq.data[q.front]^.left<>nilthenq.add（q[q.front]^.left）;
ifq.data[q.front]^.right<>nilthenq.add（q[q.front]^.right）;
writeln（q.data[q.front]^.data）;
untilq.empty（）;
end.
例4.1.1：
求100以内所有素数
programex（input,output）;
vari:
integer;
functionfac（n:
integer）:
boolean;
vari:
integer;
begin
fori:
=2totrunc（sqrt（n））do
ifnmodI=0then
exit（false）;
exit（true）;
end;
begin
fori:
=2to100do
iffac（i）then
write（I,’’）;
writeln（）;
readln（）;
end.
例4.2.1：
不定级数穷举代码段
a:
arrayofinteger;n:
integer;
fillchar（a,sizeof（a）,1）;
repeat
i:
=1;
whilea[i]=11do
begin
a[i]:
=1;
inc（a[i+1]）;
inc（i）;
end;
{执行的语句}
inc（a[1]）;
untila[n+1]=2;
例4.3.1：
N皇后
programex（input,output）;
varn,i:
integer;a:
array[1..100]ofinteger;
functionfac:
boolean;
vari,j:
integer;
begin
fori:
=1ton-1do
forj:
=i+1tondo
if（a[i]=a[j]）or（abs（a[i]-a[j]）=abs（i-j））then
begin
fac:
=false;
exit;
end;
fac:
=true;
end;
procedureprintf;
vari:
integer;j:
integer;
begin
fori:
=1tondo
begin
forj:
=1toa[i]-1do
write（''）;
write（'*'）;
writeln（）;
end;
writeln（）;
end;
begin
readln（n）;
fori:
=1ton+1doa[i]:
=1;
repeat
i:
=1;
whilea[i]=n+1do
begin
a[i]:
=1;
inc（a[i+1]）;
inc（i）;
end;
iffac（）thenprintf;
inc（a[1]）;
untila[n+1]=2;
readln;
end.
例4.4.1：
部分背包问题
program部分背包（input,output）;
{定义区}
typenode=record
w:
integer;
v:
integer;
end;
arr=array[1..100]ofnode;
varsz:
arr;n,m:
integer;
{主程序}
begin
读入;
按v/w排序sz;
i:
=0;
whilem<>0do
begin
inc（i）;
ifsz[i].wbegin
m:
=m-sz[i].v;
write（sz[i].w,'',sz[i].v）;
end
else
begin
write（sz[i].w,'',m）;
break;
end;
end;
readln;
end.
例5.2.1：
线性动规——砍价问题（步步高升
programStepByStep（input,output）;
typearr=array[1..1000]oflongint;
varw,z,a,b,i:
integer;sz:
arr;
begin
assign（input,'1.in'）;
reset（input）;
readln（w,z）;
readln（a,b）;
close（input）;
fillchar（sz,sizeof（sz）,0）;
sz[w]:
=1;
fori:
=w-1downtozdo
sz[i]:
=sz[i+a]+sz[i+b];
assign（output,'1.out'）;
rewrite（output）;
writeln（sz[z]）;
close（output）;
end.
例5.3.1：
区域动规——统计单词个数
programTotalOfWords（input,output）;
vartotal,i:
integer;ch:
char;
begin
assign（input,'1.in'）;
reset（input）;
total:
=0;
whilenot（eof）do
begin
read（ch）;
ifchin['a'..'z','A'..'Z']then
begin
inc（total）;
while（chin['a'..'z','A'..'Z']）do
read（ch）;
end;
end;
close（input）;
assign（output,'1.out'）;
rewrite（output）;
writeln（total）;
close（output）;
end.
例5.4.1：
树形动规——数字三角形
programNumberTriangle_high（input,output）;
varsz:
array[1..4,1..4]ofinteger=（（1,0,0,0）,（2,3,0,0）,（4,5,6,0）,（7,8,9,10））;i,j:
integer;
functionmax（a,b:
integer）:
integer;
begin
ifa>bthenmax:
=a
elsemax:
=b;
end;
begin
fori:
=3downto1do
forj:
=idownto1do
sz[i,j]:
=max（sz[i+1,j],sz[i+1,j+1]）+sz[i,j];
writeln（sz[1,1]）;
write（'Theroot:
'）;
whilei<>4do
begin
write（sz[i,j]-max（sz[i+1,j],sz[i+1,j+1]）,'-->'）;
ifsz[i+1,j]inc（i）;
end;
writeln（sz[i,j]）;
end.
例5.5.1：
背包动规——0/1背包问题（完全背包问题）
programbag（input,output）;
constmaxm=200;maxn=30;
varm,n,i,j,k:
integer;
w,c,x:
array[0..maxn]ofinteger;
f:
array[0..maxn,0..maxm]ofinteger;
begin
readln（m,n）;
fori:
=1tondoreadln（w[i],c[i]）;
fori:
=1tomdof[0,i]:
=0;
fori:
=1tondof[i,0]:
=0;
fori:
=1tondo
forj:
=1tomdo
ifj>=w[i]theniff[i-1,j-w[i]]+c[i]>f[i-1,j]thenf[i,j]:
=f[i-1,j-w[i]]+c[i]
elsef[i,j]:
=f[i-1,j]
elsef[i,j]:
=f[i-1,j];
k:
=m;
fori:
=ndownto1do
iff[i,k]>f[i-1,k]thenbeginx[i]:
=1;k:
=k-w[i];end
elsex[i]:
=0;
writeln（f[n,m]）;
fori:
=1tondo
ifx[i]=1then
write（i,''）;
readln（）;
fori:
=0tondo
begin
forj:
=0tomdo
write（f[i,j],''）;
writeln（）;
end;
end.
例5.6.1.1：
斐波那契数列求第n项值.递归公式
functionfac（n:
integer）:
integer;
begin
ifn<=1thenfac:
=1;
elsefac:
=fac（n-1）+fac（n-2）;
end;
例5.6.1.2：
斐波那契数列求第n项值.递推公式
sz[0]:
=1;
sz[1]:
=1;
fori:
=2tondosz[i]:
=sz[i-1]+sz[i-2];
例5.7.1：
过河卒问题地推公式
fori:
=1to8do
forj:
=1to4do
ifsz[i,j]<>-1thensz[i,j]:
=sz[i-1,j]+sz[i,j-1]
elsesz[i,j]:
=0;
升级会员 