学中枢前的准备理论之二
(2009-09-05 19:49:13)
标签:
递归杂谈 |
分类: 缠论股票课程 |
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;
repeat
while (b[j]>=x)
and (j>i) do
j:=j-1;
if j>i then begin t1:=b;
b:=b[j];b[j]:=t1;end;
while (b<=x) and
(i<j) do
i:=i+1;
if i<j then begin
t1:=b[j];b[j]:=b;b:=t1;
end
until
i=j;
b:=x;
i:=i+1;j:=j-1;
if s<j then
quicksort(b,s,j);
if i<t then
quicksort(b,i,t);
end;
begin
write('input
data:');
for i:=1 to n do
read(a);
writeln;
quicksort(a,1,n);
write('output
data:');
for i:=1 to n do
write(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)
最大值最小值定理
介值定理