ACM经典算法1
- 格式：pdf
- 大小：219.97 KB
- 文档页数：20
ACM 竞赛经典算法第一课递归一、pascal 特点：1.编写程序结构化；2.支持递归；3.通过使用指针，实现动态存储。
二、函数和过程的作用：1.相对独立功能的一段程序，一般用一个子程序（函数和过程）来编写；2.结构清楚，便于调试、修改和扩充；3.节约程序段和内存；三、递归定义：子程序自己调用自己的程序段叫递归；使用递归的条件1.可以把一个问题转化为一个类似自己的新问题，且问题的规模发生规律性的变化。
2.可以通过转化使问题得到解决。
3.有一个明确的结束条件。
递归实际上是个逆向思维过程，核心是求递归公式。
四、习题：1、用递归求n!.程序如下：program sample1_1;varn:integer;function fac （n:integer ）：real;beginif n=1then 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)因担心超值，所以定义为实型。
加场宽限制小数位数，整数不受场宽限制程序如下：varn:integer;function f(n:integer):integer;beginif (n=1)or(n=0)then begin f:=1;exit;end;f(n):=f(n-1)+f(n-2);end;beginreadln(n);write(f(n));end.总结：（1）递归每执行一次，就要开辟一次局部变量，保护上一次的内容。
递归是逆向出发，先从全局出发，如何将大规模转化为小规模的问题。
（2）fac(4):=fac(3)+fac(2);重复运算多，速度慢。
3、输入一串字符，以’.’结束，倒序输出。
程序如下：varc:char;procedure print(n:char);varch:char;beginif n=’.’then exit;readln(ch);print(ch);writeln(ch);end;beginreadln(c);print(c)end.4、求两个整数的最大公约数（辗转相除法）程序如下：varm ,n :integer;fac(3):=fac(2)+fac(1);Fac(2):=fac(1)+fac(0)Fac(2):=fac(1)+fac(0)倒序输出则在退出时打印，若想正序打印，则在进入时打印。
function fac(I,j:integer):integer;beginif j=0then begin fac:=i;exit;end;fac:=fac(j,i mod j);end;beginreadln(n,m);writeln(fac(n,m));end.5、求给出一个多位整数的第K位。
Fac:=fac(x div10,k-1)(k>1)Fac(x,k)=fac:=x mod10(k=1)程序如下：varx,k:integer;function fac(I,j:integer):integer;beginif j=1then begin fac:=I mod10;exit;end;fac:=fac(I div10,k-1);end;beginreadln(x,k);write(fac(x,k));end.6、梵诺塔VarN:integer;sa,sb,sc:string;Procedure move(n:integer;a,b,c:char;var sa,sb,sc:string;);BeginIf n=1then begin write(A,’:’,sa[1],’-)’,C);Sc:=sa[1]+sc;Sa:=copy(sa,2,length(sa)-1);exit;end;Move(n-1,a,c,b,sa,sc,sb);Write(A,’:’,sa[1],’-)’,C);Sc:=sa[1]+sc;Sa:=copy(sa,2,length(sa)-1);Move(n-1,b,a,c,sb,sa,sc);End;BeginReadln(n);sa:=’12345’;sb:=’’;sc:=’’;Move(5,’A’,’B’,’C’,sa,sb,sc);End.第二课排列（排列）递归跟多重for循环一样，只不过递归可以随机控制循环的层数，可以实现循环次数的可变性，m叫递归的层数，叫深度。
N叫宽度，时间的复杂度为n m次。
控制循环的I一定是局部变量。
１、从n个自然数中取出m个数的排列（允许重复）；程序如下：vara:array[1..100]of integer;n,m,s:integer;procedure print;varI:integer;BeginFor I:=1to m doWrite(a[I]:3);End;procedure play(k:integer)varI:integer;BeginIf k=m+1then beginInc(s);Print;Exit;End;For I:=1to n doBeginA[k]:=I;Play(k+1);End;End;beginreadln(n,m);s:=0;play(1);writeln(s);end.２、n 个自然数中取出m 个数的排列（不允许重复（n>=m ）；vara:array[1..100]of integer;b:array[1..100]of Boolean;n,m,s:integer;procedure print;var I:integer;Begin For I:=1to m do Write(a[I]:3);End;procedure play(k:integer);varI:integer;beginif k=m+1then begin inc(s);print;exit;end;for I:=1to n doif b[I]then begin a[k]:=I;b[I]:=false;play(k+1);b[I]:=true;end;end;beginreadln(n,m);s:=0;fillchar(b,sizeof(b),false);play(1);writeln(s);end.3.限定次数，若干限定次数，即每个数都有限定次数，可用标志数组，B 数组先录入限定的次数，用一次则该数组中的数减1，至到为这是用标志数组的方法来判重，也可以用比较的方法来实现判重。
0为止。
4.若干个不连续的数的排列引入第3个数组C，将不规律映射到规律下标的数组当中。
例：’PASCAL’字符串取3个字母的排列＊本题就是限次，而且不连续数的排列，可以映射到字符串去。
程序如下：vara:array[1..3]of char;b:array[1..26]of integer;p,c:string;I,s:integer;Procedure print;VarI:integer;BeginFor I:=1to3doWrite(a[I]);Writeln;End;Procedure play(k:integer);VarI:integer;BeginIf k=4then begin inc(s);print;exit;end;For I:=1to length(c)doIf b[I]>0then beginA[k]:=c[I];Dec(b[I]);Play(k+1);Inc(b[I]);End;BeginReadln(p);C:=’’;For I:=1to length(p)doIf pos(p[I],c)=0then begin c:=c+p[I];b[pos(p[i],c)]:=1;exit;End else inc(b[pos(p[I],c)];S:=0;Play(1);Writeln(s);End.第三课经典排列1、错排：n封信，n个信封，全装错的情况（I<>j，且不允许重复的情况）vara:array[1..100]of integer;b:array[1..100]of boolean;n,s:integer;procedure print;vari:integer;beginfor i:=1to n dowrite(a[i]:3);writeln;end;procedure play(k:integer);vari:integer;beginif k=n+1then begin print;inc(s);exit;end;for i:=1to n doif(i<>k)and b[i]then begina[k]:=i;b[i]:=false;play(k+1);b[i]:=true;end;end;beginreadln(n);s:=0;fillchar(b,sizeof(b),true);play(1);writeln(s);end.2、8皇后问题（任一皇后不在同一行同一列，同一斜行上）八皇后是一个二维数组，如果用一个一维数组来存放，就可以保证行上不重，在列上再用一个数来判重，就可以保证列上不重。
vara,b:array[1..8]of0..8;s,n:integer;function can(k:integer):boolean;vari:integer;beginnrep:=false;for i:=1to k-1doif abs(i-k)=abs(a[i]-a[k])then exit;nrep:=true;end;procedure print;vari,j:integer;beginfor i:=1to8do beginfor j:=1to8doif a[i]=j then write('*':2)else write(0:2);writeln;end;writeln('----------------------');end;procedure try(k:integer);vari:integer;beginif k>n then begin inc(s);print;exit;end;for i:=1to8doif b[i]=0then begina[k]:=i;b[i]:=1;if can(k)then try(k+1);b[i]:=0;end;end;beginn:=8;s:=0;try(1);writeln(s);end.３、由A、B、C三个字母组成长度为n的没有连续3个相同的子串。
