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针作为过度针,每次只移动一块盘子,且每根针上
不能出现大盘压小盘.找出移动次数最小的方案.
程序如下:
programfanta;
var
n:integer;
proceduremove(n,a,b,c:integer);
begin
if n=1 thenwriteln(a,'--->',c)
elsebegin
move(n-1,a,c,b);
writeln(a,'--->',c);
move(n-1,b,a,c);
end;
end;
begin
write('Entern=');
read(n);
move(n,1,2,3);
end.
例4快速排序
快速排序的思想是:先从数据序列中选一个元素,并将序列中所有比该元素小的元素都放到它的右边或左边,再对左右两边分别用同样的方法处之直到每一个待处理的序列的长度为1,处理结束.
程序如下:
programkspv;
constn=7;
type
arr=array[1..n] ofinteger;
var
a:arr;
i:integer;
procedure quicksort(var b:arr;s,t:integer);
vari,j,x,t1:integer;
begin
i:=s;j:=t;x:=b;
repeat
while (b[j]>=x)and (j>i) doj:=j-1;
if j>i then begin t1:=b;b:=b[j];b[j]:=t1;end;
while (b<=x) and(i<j) doi:=i+1;
if i<j then begint1:=b[j];b[j]:=b;b:=t1;end
untili=j;
b:=x;
i:=i+1;j:=j-1;
if s<j thenquicksort(b,s,j);
if i<t thenquicksort(b,i,t);
end;
begin
write('inputdata:');
for i:=1 to n doread(a);
writeln;
quicksort(a,1,n);
write('outputdata:');
for i:=1 to n dowrite(a:6);
writeln;
end.
练习:
1.计算ackerman函数值:
n+1 m=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)
最大值最小值定理
介值定理
联系客服