2022年ACM经典算法 .pdf

《2022年ACM经典算法 .pdf》由会员分享，可在线阅读，更多相关《2022年ACM经典算法 .pdf（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、ACM 竞赛经典算法第一课递归一、 pascal 特点：1.编写程序结构化；2.支持递归；3.通过使用指针，实现动态存储。二、函数和过程的作用：1.相对独立功能的一段程序，一般用一个子程序（函数和过程）来编写；2.结构清楚，便于调试、修改和扩充；3.节约程序段和内存；三、递归定义：子程序自己调用自己的程序段叫递归；使用递归的条件1.可以把一个问题转化为一个类似自己的新问题，且问题的规模发生规律性的变化。2.可以通过转化使问题得到解决。3.有一个明确的结束条件。递归实际上是个逆向思维过程，核心是求递归公式。四、习题：1、用递归求 n!. 程序如下：program sample1_1; var n

2、:integer; function fac （n:integer） ：real; begin if n=1 then begin fac:=1;exit;end; fac:=n*fac(n-1); end; begin readln(n); writeln(fac(n):3:0); end. 总结：1、 递归一般用函数或过程来实现，主程序没有办法来实现递归；2、 递归要有空间想象能力；3、 需要保护的变量一定要开成局部变量。像 function fac( n:integer ) 中的 n.就是局部变量。2、斐波那契数列f(n)=f(n-1)+f(n-2) 因 担 心 超值，所以定义为实型。加

3、 场 宽 限 制 小 数 位数，整数不受场宽限制名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 1 页，共 20 页 - - - - - - - - - 程序如下：var n:integer; function f(n:integer):integer; begin if (n=1) or(n=0) then begin f:=1;exit;end; f(n):=f(n-1)+f(n-2); end; begin readln(n); write(f(n); end.总结：（1）递归

4、每执行一次，就要开辟一次局部变量，保护上一次的内容。递归是逆向出发，先从全局出发，如何将大规模转化为小规模的问题。（2）fac(4):= fac(3) + fac(2); 重复运算多，速度慢。3、输入一串字符，以 . 结束，倒序输出。程序如下：var c:char; procedure print(n: char); var ch:char; begin if n= . then exit; readln(ch); print(ch); writeln(ch); end; begin readln( c); print( c) end. 4、求两个整数的最大公约数（辗转相除法）程序如下：var

5、 m , n : integer; fac(3):=fac(2)+fac(1); Fac(2):=fac(1)+fac(0) Fac(2):=fac(1)+fac(0) 倒 序 输 出 则在 退 出时 打印，若想正序打印，则在进入时打印。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 2 页，共 20 页 - - - - - - - - - function fac(I, j:integer):integer; begin if j=0 then begin fac:=i;exit;

6、end; fac:=fac(j ,i mod j); end; begin readln(n, m); writeln(fac(n,m); end. 5、求给出一个多位整数的第K 位。Fac:=fac(x div 10, k-1)(k1) Fac(x, k)= fac:=x mod 10 (k=1) 程序如下：var x , k : integer ; function fac(I , j : integer):integer; begin if j=1 then begin fac:=I mod 10;exit;end; fac:=fac(I div 10,k-1); end; begin

7、readln(x, k); write(fac(x,k); end. 6、梵诺塔Var N:integer; sa, sb, sc:string; Procedure move (n:integer; a, b, c:char; var sa, sb, sc:string;); Begin If n=1 then begin write( A, : ,sa1, -) ,C); Sc:=sa1+sc; Sa:=copy(sa,2,length(sa)-1); exit;end; Move(n-1,a,c,b,sa,sc,sb); Write(A, : ,sa1, -) , C); Sc:=sa1

8、+sc; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 3 页，共 20 页 - - - - - - - - - Sa:=copy(sa, 2, length(sa)-1); Move(n-1,b,a,c,sb,sa,sc); End; Begin Readln(n); sa:= 12345 ; sb:=; sc:=; Move(5, A , B , C ,sa,sb,sc); End. 第二课排列（排列）递归跟多重 for 循环一样，只不过递归可以随机控制循环的层数，可以实现循环

9、次数的可变性，m 叫递归的层数，叫深度。N 叫宽度，时间的复杂度为nm次。控制循环的I 一定是局部变量。、从 n 个自然数中取出m 个数的排列（允许重复） ；程序如下：var a:array1.100of integer; n,m,s:integer; procedure print; var I:integer; Begin For I:=1 to m do Write(aI:3); End; procedure play(k:integer) var I:integer; Begin If k=m+1 then begin Inc(s); Print; Exit; End; For I:=

10、1 to n do 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 4 页，共 20 页 - - - - - - - - - Begin Ak:=I; Play(k+1); End; End; begin readln(n,m); s:=0; play(1); writeln(s); end. 、n 个自然数中取出m 个数的排列（不允许重复（n=m） ；var a:array1.100of integer; b:array1.100of Boolean; n,m,s:integer;

11、 procedure print; var I:integer; Begin For I:=1 to m do Write(aI:3); End; procedure play(k:integer); var I:integer; begin if k=m+1 then begin inc(s);print;exit;end; for I:=1 to n do if bI then begin ak:=I; bI:=false; play(k+1); bI:=true; end; end; begin readln(n,m); s:=0; fillchar(b,sizeof(b),false)

12、; play(1); writeln(s); end. 3. 限定次数，若干限定次数，即每个数都有限定次数，可用标志数组，B 数组先录入限定的次数，用一次则该数组中的数减1，至到为这是用标志数组的方法来判重，也可以用比较的方法来实现判重。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 5 页，共 20 页 - - - - - - - - - 0 为止。4. 若干个不连续的数的排列引入第 3 个数组 C，将不规律映射到规律下标的数组当中。例： PASCAL 字符串取 3 个字母的排列本

13、题就是限次，而且不连续数的排列，可以映射到字符串去。程序如下：var a: array1.3of char; b: array1.26of integer; p,c:string; I, s:integer; Procedure print; Var I:integer; Begin For I:=1 to 3 do Write(aI); Writeln; End; Procedure play(k: integer); Var I: integer; Begin If k=4 then begin inc(s);print; exit; end; For I:=1 to length( c)

14、 do If bI0 then begin Ak:=cI; Dec(bI); Play(k+1); Inc(bI); End; Begin Readln(p); C:=; For I:=1 to length(p) do If pos(pI,c)=0 then begin c:=c+pI; bpos(pi,c):=1;exit; End else inc(bpos(pI,c); S:=0; Play(1); Writeln(s); End. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - -

15、 第 6 页，共 20 页 - - - - - - - - - 第三课经典排列1、错排：n 封信， n 个信封，全装错的情况（Ij ，且不允许重复的情况）var a:array1.100of integer; b:array1.100of boolean; n,s:integer; procedure print; var i:integer; begin for i:=1 to n do write(ai:3); writeln; end; procedure play(k:integer); var i:integer; begin if k=n+1 then begin print;in

16、c(s);exit;end; for i:=1 to n do if (ik) and bi then begin ak:=i;bi:=false; play(k+1); bi:=true; end; end; begin readln(n); s:=0; fillchar(b,sizeof(b),true); play(1); writeln(s); end. 2、8 皇后问题（任一皇后不在同一行同一列，同一斜行上）八皇后是一个二维数组，如果用一个一维数组来存放，就可以保证行上不重，在列上再用一个数来判重，就可以保证列上不重。var a,b:array1.8of 0.8; s,n:integ

17、er; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 7 页，共 20 页 - - - - - - - - - function can(k:integer):boolean; var i:integer; begin nrep:=false; for i:=1 to k-1 do if abs(i-k)=abs(ai-ak) then exit; nrep:=true; end; procedure print; var i,j:integer; begin for i:=1 t

18、o 8 do begin for j:=1 to 8 do if ai=j then write(*:2)else write(0:2); writeln; end; writeln(-); end; procedure try(k:integer); var i:integer; begin if kn then begin inc(s);print;exit;end; for i:=1 to 8 do if bi=0 then begin ak:=i; bi:=1; if can(k) then try(k+1); bi:=0; end; end; begin n:=8; s:=0; tr

19、y(1); writeln(s); end. 、由 A、B、C 三个字母组成长度为n 的没有连续 3 个相同的子串。 (只讨论第 k 个字母加上去后是否影响到产生三个相同的子串) type 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 8 页，共 20 页 - - - - - - - - - str=string10; var n,s:integer; function nrep(p:string):boolean; var i:integer; begin nrep:=false

20、; for i:=1 to length(p)div 3 do if (copy(p,length(p)-i+1,i)=copy(p,length(p)-2*i+1,i)and ( copy(p,length(p)-2*i+1,i)=copy(p,length(p)-3*i+1,i) then exit; nrep:=true; end; procedure try(p:str); var i:char; begin if length(p)n then begin inc(s);writeln(p);exit;end; for i:=a to c do begin if nrep(p+i)

21、then try(p+i); end; end; begin readln(n); s:=0; try(); writeln(s); end. 4、九连环（九连环的移动规则： 1、第 1 位可以随意变； 2、第 i 位改变时，只要 i-1 位为 0，前面各位都为1，则本位可变。）var a,b:string; i:integer; procedure play(k:integer;c:char); var i:integer; begin if ak=c then exit; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师

22、精心整理 - - - - - - - 第 9 页，共 20 页 - - - - - - - - - if k=1 then ak:=c else begin play(k-1,0); for i:=k-2 downto 1 do play(i,1); ak:=c; end; writeln(a); end; begin readln(a); readln(b); for i:=length(a) downto 1 do play(i,bi); end. 组合问题（ 1）1、从 n 个自然数中取 m 个数的组合；var a:array0.100of integer; n,m,s:integer;

23、 procedure print; var i:integer; begin for i:=1 to m do write(ai:4); writeln; end; procedure try(k:integer); var i:integer; begin if km then begin inc(s);print;exit;end; for i:=ak-1+1 to n do begin ak:=i; try(k+1); end; end; begin readln(n,m); s:=0; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - -

24、 - - - 名师精心整理 - - - - - - - 第 10 页，共 20 页 - - - - - - - - - a0:=0; try(1); writeln(s); end. 2.输入一个正整数，拆分成正整数的和，求所有的情况。（是组合问题，但允许重复）程序如下：var a:array0.100of integer; n,s:integer; procedure print(k:integer); var i:integer; begin write(n,=,a1); for i:=2 to k do write(+,ai); writeln; end; procedure try(k

25、,p:integer); var i:integer; begin if p=0 then begin print(k-1);inc(s);exit;end; ak:=p; try(k+1,0); for i:=ak-1 to p div 2 do begin ak:=i; try(k+1,p-i);end; end; begin s:=0; readln(n); a0:=1; try(1,n); writeln(s); end. 3.分解质因数程序如下：var a:array0.100of integer; n:integer; procedure print(k:integer); 由于加

26、法的交换率使分解因式是组合问题，但允许数字重复， 因此选择排列的一个递增序列，但一个数如果大于取的一半，则后面不能再分， 所以如果一个数大于一半，则全取。名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 11 页，共 20 页 - - - - - - - - - var i:integer; begin write(n,=,a1); for i:=2 to k do write(*,ai); writeln; end; function yes(p:integer):boolean;

27、var i:integer; begin yes:=false; for i:=2 to trunc(sqrt(p) do if p mod i=0 then exit; yes:=true; end; procedure play(k,p:integer); var i:integer; begin if p=1 then begin print(k-1);exit;end; if yes(p) then begin ak:=p;play(k+1,1);end; for i:=ak-1 to trunc(sqrt(p) do if(i1)and(p mod i=0) then begin a

28、k:=i;play(k+1,p div i);end; end; begin readln(n); a0:=2; play(1,n); end. 第四次课深度搜索在我们遇到的一些问题当中，有些问题我们不能够确切的找出数学模型，即找不出一种直接求解的方法，解决这一类问题，我们一般采用搜索的方法解决。搜索就是用问题的所有可能去试探，按照一定的顺序、规则，不断去试探，直到找到问题的解，试完了也没有找到解，那就是无解，试探时一定要试探完所有的情况（实际上就是穷举）；对于问题的第一个状态，叫初始状态，要求的状态叫目标状态。搜索就是把规则应用于实始状态，在其产生的状态中，直到得到一个目标状态为止。产生新的

29、状态的过程叫扩展（由一个状态，应用规则，产生新状态的过程）搜索的要点： （1）初始状态；（2）重复产生新状态；（3）检查新状态是否为目标，是结束，否转（2） ；判 p 是否是质数， 是质数就结束名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 12 页，共 20 页 - - - - - - - - - 如果搜索是以接近起始状态的程序依次扩展状态的，叫宽度优先搜索。如果扩展是首先扩展新产生的状态，则叫深度优先搜索。深度优先搜索深度优先搜索用一个数组存放产生的所有状态。（1）把初始状态放入

30、数组中，设为当前状态；（2）扩展当前的状态，产生一个新的状态放入数组中，同时把新产生的状态设为当前状态；（3）判断当前状态是否和前面的重复，如果重复则回到上一个状态，产生它的另一状态；（4）判断当前状态是否为目标状态，如果是目标，则找到一个解答，结束算法。（5）如果数组为空，说明无解。（6）转到（）对于pascal 语言来讲，它支持递归，在递归时可以自动实现回溯（利用局部变量）所以使用递归编写深度优先搜索程序相对简单，当然也有非递归实现的算法。1、迷宫程序如下：const d:array1.4,1.4of integer=(1,1,0,0),(0,1,1,1),(1,1,0,1),(0,1,1

31、,1); c:array1.4,1.2of -1.1=(0,1),(0,-1),(1,0),(-1,0); var a:array1.16,1.2of integer; i,j:integer; procedure play(k:integer); var i:integer; begin if (ak,1=4)and(ak,2=4) then begin for i:=1 to k do write(,ai,1,ai,2,); writeln; 11 10 101 1 1 1 1 0 0 0 1 1 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - -

32、 - - - - - 名师精心整理 - - - - - - - 第 13 页，共 20 页 - - - - - - - - - readln; exit; end; for i:=1 to 4 do if (ak,1+ci,10)and(ak,1+ci,10)and(ak,2+ci,25) then if dak,1,ak,2=1 then begin dak,1,ak,2:=2; ak+1,1:=ak,1+ci,1; ak+1,2:=ak,2+ci,2; play(k+1); dak,1,ak,2:=1; end; end; begin fillchar(a,sizeof(a),0); a1

33、,1:=1;a1,2:=1; play(1); end. 2、8 数码程序如下：type node=array1.3,1.3of 0.8; const st:node=(2,8,3),(1,6,4),(7,0,5); gl:node=(1,2,3),(8,0,4),(7,6,5); rl:array1.4,1.2of-1.1=(0,1),(0,-1),(1,0),(-1,0); var a:array1.20of node; function result(k:integer):boolean; var i,x,y:integer; begin result:=false; for x:=1

34、to 3 do 5 6 7 4 0 8 3 2 1 5 0 7 4 6 1 3 8 2 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 14 页，共 20 页 - - - - - - - - - for y:=1 to 3 do if ak,x,yglx,y then exit; result:=true; end; procedure look(k:integer;var x,y:integer); var i,j:integer; begin for i:=1 to 3 do f

35、or j:=1 to 3 do if ak,i,j=0 then begin x:=i;y:=j;end; end; procedure print(k:integer); var i,x,y:integer; begin for i:=1 to k do begin writeln(step:,i); for x:=1 to 3 do begin for y:=1 to 3 do write(ai,x,y:3); writeln; end; writeln(-); end; end; function nrep(k:integer):boolean; var i,x,y:integer; f

36、:boolean; begin nrep:=false; for i:=1 to k-1 do begin f:=true; for x:=1 to 3 do for y:=1 to 3 do if ai,x,yak,x,y then begin f:=false;break;break;end; if f then exit; end; nrep:=true; end; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 15 页，共 20 页 - - - - - - - - - pr

37、ocedure step(k:integer); var i,x,y:integer; begin if k=20 then exit; if result(k) then begin print(k);exit;end; look(k,x,y); for i:=1 to 4 do begin if (x+rli,1=1)and(x+rli,1=3)and(y+rli,2=1)then begin ak+1:=ak; ak+1,x+rli,1,y+rli,2:=ak,x,y; ak+1,x,y:=ak,x+rli,1,y+rli,2; if nrep(k+1) then step(k+1);

38、end; end; end; begin a1:=st; step(1); end. 3、跳马（ 5*5）程序如下：const d:array1.8,1.2of -2.2=(-2,1),(-2,-1),(1,2),(1,-2),(2,-1),(2,1),(-1,-2),(-1,2); var a:array1.5,1.5of 0.1; procedure print; var i,j:integer; begin for i:=1 to 5 do begin for j:=1 to 5 do write(ai,j:3); writeln; end; 名师资料总结 - - -精品资料欢迎下载 -

39、 - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 16 页，共 20 页 - - - - - - - - - readln; end; procedure play(x,y:integer); var i:integer; begin if (x=5)and(y=5) then begin print;exit;end; for i:=1 to 8 do if (x+di,10)and(x+di,10)and(y+di,2目标(40,40.0) 程序如下：const v:array1.3of integer=(80,50,30)

40、; var a:array1.30,1.3of integer; procedure print(k:integer); var i:integer; begin for i:=1 to k do writeln(step:,i,ai,1:3,ai,2:3,ai,3:3); readln; end; function nrep(k:integer):boolean; var i:integer; begin nrep:=false; for i:=1 to k-1 do if (ai,1=ak,1)and(ai,2=ak,2)then exit; 名师资料总结 - - -精品资料欢迎下载 -

41、- - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 17 页，共 20 页 - - - - - - - - - nrep:=true; end; procedure step(k:integer); var i,j:integer; begin if (ak,1=40)and(ak,2=40) then begin print(k);exit;end; for i:=1 to 3 do for j:=1 to 3 do if (ij)and(ak,i0)and(ak,jvj )then begin ak+1,i:=ak,i+ak,j

42、-vj; ak+1,j:=vj;end else begin ak+1,i:=0;ak+1,j:=ak,i+ak,j;end;if nrep(k+1) then step(k+1); end; end; begin a1,1:=80; a1,2:=0; a1,3:=0; step(1); end. 5、狼、羊、菜过河规则是：猎人每次只能带一样过河，而狼吃羊，羊吃菜， 不能没有猎人在时在一起。算出过河的方案。程序如下：var a:array1.30,1.4of integer; procedure print(k:integer); var i:integer; begin for i:=1 t

43、o k do writeln(step:,i,ai,1:3,ai,2:3,ai,3:3,ai,4:3); readln; end; function can(k:integer):boolean; var i:integer; begin 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 18 页，共 20 页 - - - - - - - - - can:=false; if (ak,2=ak,3)and(ak,2ak,1)or(ak,3=ak,4)and(ak,3ak,1) then

44、 exit; i:=k-2; while i0 do begin if (ai,1=ak,1)and(ai,2=ak,2)and(ai,3=ak,3)and(ai,4=ak,4) then exit; i:=i-2; end; can:=true; end; procedure step(k:integer); var i:integer; begin if ak,1+ak,2+ak,3+ak,4=0 then begin print(k);exit;end; for i:=1 to 4 do begin if i1 then begin ak+1:=ak; ak+1,i:=1-ak,i; a

45、k+1,1:=1-ak,1; end else begin ak+1:=ak; ak+1,1:=1-ak,1; end; if can(k+1) then step(k+1); end; end; begin a1,1:=1; a1,2:=1; a1,3:=1; a1,4:=1; step(1); end. 6、野人和传教士过河?野人和传教士各三人，小船只能载两人，要求野人的人数不能多于传教士。算出过河的方案总数。程序如下： const c:array1.5,1.2of 0.2=(1,0),(0,1),(2,0),(0,2),(1,1); var a:array1.30,1.2of integ

46、er; 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 19 页，共 20 页 - - - - - - - - - procedure print(k:integer); var i,j:integer; begin for i:=1 to k do begin writeln(step:,i,ai,1:3,ai,2:3); end; end; function can(k:integer):boolean; var i:integer; begin can:=false; if (

47、ak,13)or(ak,13)or(ak,2ak,2)and(ak,20)or(ak,1ak,2)and(ak,20 do begin if (ai,1=ak,1) and(ai,2=ak,2) then exit; i:=i-2; end; can:=true; end; procedure step(k,p:integer); var i:integer; begin if ak,1+ak,2=0 then begin print(k);exit;end; for i:=1 to 5 do begin ak+1,1:=ak,1+p*ci,1; ak+1,2:=ak,2+p*ci,2; if can(k+1) then step(k+1,-p); end; end; begin a1,1:=3; a1,2:=3; step(1,-1); end. 名师资料总结 - - -精品资料欢迎下载 - - - - - - - - - - - - - - - - - - 名师精心整理 - - - - - - - 第 20 页，共 20 页 - - - - - - - - -