信息学竞赛常用算法与策略：递归 标签：信息学

优学合肥奥数网讯：信息学竞赛常用算法与策略：递归。

递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写

程序能是程序变得简洁和清晰.

2.1 递归的概念

1.概念

一个过程(或函数)直接或间接调用自己本身,这种过程(或函数)叫递归过程(或函数).

如:

procedure a;

begin

.

.

.

a;

.

.

.

end;

这种方式是直接调用.

又如:

procedure b;procedure c;

begin begin

. .

. .

. .

c; b;

. .

. .

. .

end; end;

这种方式是间接调用.

例1计算n!可用递归公式如下:

1 当 n=0 时

fac(n)={n*fac(n-1) 当n>0时

可编写程序如下:

program fac2;

var

n:integer;

function fac(n:integer):real;

begin

if n=0 then fac:=1 else fac:=n*fac(n-1)

end;

begin

write('n=');readln(n);

writeln('fac(',n,')=',fac(n):6:0);

end.

例2 楼梯有n阶台阶,上楼可以一步上1阶,也可以一步上2阶,编一程序计算共有多少种不同的走法.

设n阶台阶的走法数为f(n)

显然有

1 n=1

f(n)={2 n=2

f(n-1)+f(n-2) n>2

可编程序如下：

program louti;

var n:integer;

function f(x:integer):integer;

begin

if x=1 then f:=1 else

if x=2 then f:=2 else f:=f(x-1)+f(x-2);

end;

begin

write('n=');read(n);

writeln('f(',n,')=',f(n))

end.

2.2 如何设计递归算法

1.确定递归公式

2.确定边界(终了)条件

练习:

用递归的方法完成下列问题

1.求数组中的最大数

2.1+2+3+...+n

3.求n个整数的积

4.求n个整数的平均值

5.求n个自然数的最大公约数与最小公倍数

6.有一对雌雄兔,每两个月就繁殖雌雄各一对兔子.问n个月后共有多少对兔子?

7.已知:数列1,1,2,4,7,13,24,44,...求数列的第 n项.

2.3 典型例题

例3 梵塔问题

如图:已知有三根针分别用1,2,3表示,在一号针中从小放n个盘子,现要求把所有的盘子

从1针全部移到3针,移动规则是:使用2针作为过度针,每次只移动一块盘子,且每根针上

不能出现大盘压小盘.找出移动次数最小的方案.

程序如下:

program fanta;

var

n:integer;

procedure move(n,a,b,c:integer);

begin

if n=1 then writeln(a,'--->',c)

else begin

move(n-1,a,c,b);

writeln(a,'--->',c);

move(n-1,b,a,c);

end;

end;

begin

write('Enter n=');

read(n);

move(n,1,2,3);

end.

例4 快速排序

快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1, 处理结束.

程序如下:

program kspv;

const n=7;

type

arr=array[1..n] of integer;

var

a:arr;

i:integer;

procedure quicksort(var b:arr; s,t:integer);

var i,j,x,t1:integer;

begin

i:=s;j:=t;x:=b[i];

repeat

while (b[j]>=x) and (j>i) do j:=j-1;

if j>i then begin t1:=b[i]; b[i]:=b[j];b[j]:=t1;end;

while (b[i]<=x) and (i

if i

until i=j;

b[i]:=x;

i:=i+1;j:=j-1;

if s

if i

end;

begin

write('input data:');

for i:=1 to n do read(a[i]);

writeln;

quicksort(a,1,n);

write('output data:');

for i:=1 to n do write(a[i]:6);

writeln;

end.

练习:

1.计算ackerman函数值:

n+1m=0

ack(m,n)={ ack(m-1,1) m<>0 ,n=0

ack(m-1,ack(m,n-1)) m<>0,n<>0

求ack(5,4)

关于合肥市青少年信息学竞赛更多的信息，请关注优学合肥奥数网“青少年信息学竞赛”频道。

信息学竞赛常用算法与策略：算法的概念

青少年信息学竞赛Pascal语言：程序调试（十一）

青少年信息学竞赛Pascal语言：指针（十）

信息学竞赛Pascal语言：记录与文件类型（九）

更多精彩内容推荐>>