信息学竞赛常用算法与策略:递归
查字典合肥奥数网讯:信息学竞赛常用算法与策略:递归。
递归是计算机科学的一个重要概念,递归的方法是程序设计中有效的方法,采用递归编写
程序能是程序变得简洁和清晰.
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<j) do i:=i+1;
if i<j then begin t1:=b[j];b[j]:=b[i];b[i]:=t1; end
until i=j;
b[i]:=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[i]);
writeln;
quicksort(a,1,n);
write('output data:');
for i:=1 to n do write(a[i]: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)
关于合肥市青少年信息学竞赛更多的信息,请关注查字典合肥奥数网“青少年信息学竞赛”频道。
信息学竞赛常用算法与策略:算法的概念
青少年信息学竞赛Pascal语言:程序调试(十一)
青少年信息学竞赛Pascal语言:指针(十)
信息学竞赛Pascal语言:记录与文件类型(九)
更多精彩内容推荐>>
【信息学竞赛常用算法与策略:递归】相关文章:
相关文章
网友关注
网友关注视频
精品推荐
分类导航
- 太原小学奥数第二讲—有余除法
- 太原小学奥数第一讲—找规律
- 武汉楚才作文登报作品《一件“伟大”事》
- 武汉楚才作文登报作品《又是一年银耳飘香》
- 武汉楚才作文登报作品《芬芳何处寻》
- 武汉楚才作文登报作品《我总想着这些事》
- 合肥市28届青少年信息学(计算机)竞赛获奖名单(小学组)
- 屯小13名选手参加包河区第四届青少年信息学计算机竞赛
- NOIP2013普及组初赛答案
- 2013全国青少年信息学奥林匹克竞赛时间日程
- 合肥中小学生参加信息学奥赛有哪些好处?
- 信息学竞赛Pascal语言 数组与字符串(五)
- 合肥市“讯飞”杯信息学竞赛(小学组)考试大纲
- 青少年信息学竞赛对小升初的作用?
- 合肥市讯飞杯青少年信息学竞赛规则(小学组)
- 全国青少年信息学(计算机)奥林匹克联赛初赛内容
- 全国青少年信息学(计算机)奥林匹克联赛题型
- 青少年信息学竞赛33个初级篇试题