|
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)
三、区间套
闭区间是包括区间两端点值，用中括号表示，如[-3，6]就包括-3和6点，（-3，6]不包括-3，而包括6。等等。
闭区间上的连续函数则是在其连续区间的左端点右连续，右端点左连续.对于闭区间上的连续函数有几条重要的性质，
下面我们来学习一下：
最大值最小值定理
在闭区间上连续的函数一定有最大值和最小值。(在此不作证明)
例：函数y=sinx在闭区间[0，2π]上连续，
则在点x=π/2处，它的函数值为1，且大于闭区间[0，2π]上其它各点出的函数值；
则在点x=3π/2处，它的函数值为-1，且小于闭区间[0，2π]上其它各点出的函数值
介值定理
在闭区间上连续的函数一定取得介于区间两端点的函数值间的任何值。
即：，μ在α、β之间，则在[a，b]间一定有一个ξ，使
推论：
在闭区间连续的函数必取得介于最大值最小值之间的任何值。
后面的课程要用数学的思维理解股市，先复习数学，才能找到问题的关键。缠说过对股市要庖丁解牛，缠论也是如此。
|
