高中信息技术 全国青少年奥林匹克联赛教案 递推法.docx
- 文档编号:15413989
- 上传时间:2023-07-04
- 格式:DOCX
- 页数:17
- 大小:65.37KB
高中信息技术 全国青少年奥林匹克联赛教案 递推法.docx
《高中信息技术 全国青少年奥林匹克联赛教案 递推法.docx》由会员分享,可在线阅读,更多相关《高中信息技术 全国青少年奥林匹克联赛教案 递推法.docx(17页珍藏版)》请在冰点文库上搜索。
高中信息技术全国青少年奥林匹克联赛教案递推法
2019-2020年高中信息技术全国青少年奥林匹克联赛教案递推法
所谓递推,是指从已知的初始条件出发,依据某种递推关系,逐次推出所要求的各中间结果及最后结果。
其中初始条件或是问题本身已经给定,或是通过对问题的分析与化简后确定。
可用递推算法求解的题目一般有以下二个特点:
(1)问题可以划分成多个状态;
(2)除初始状态外,其它各个状态都可以用固定的递推关系式来表示。
在我们实际解题中,题目不会直接给出递推关系式,而是需要通过分析各种状态,找出递推关系式。
递推法应用
例1骑士游历:
(noip1997tg)
设有一个n*m的棋盘(2<=n<=50,2<=m<=50),如下图,在棋盘上任一点有一个中国象棋马,
马走的规则为:
1.马走日字2.马只能向右走,即如下图所示:
任务1:
当N,M输入之后,找出一条从左下角到右上角的路径。
例如:
输入N=4,M=4
输出:
路径的格式:
(1,1)->(2,3)->(4,4)
若不存在路径,则输出"no"
任务2:
当N,M给出之后,同时给出马起始的位置和终点的位置,试找出从起点到终点的所有路径的数目。
例如:
(N=10,M=10),(1,5)(起点),(3,5)(终点)
输出:
2(即由(1,5)到(3,5)共有2条路径)
输入格式:
n,m,x1,y1,x2,y2(分别表示n,m,起点坐标,终点坐标)
输出格式:
路径数目(若不存在从起点到终点的路径,输出0)
算法分析:
为了研究的方便,我们先将棋盘的横坐标规定为i,纵坐标规定为j,对于一个n×m的棋盘,i的值从1到n,j的值从1到m。
棋盘上的任意点都可以用坐标(i,j)表示。
对于马的移动方法,我们用K来表示四种移动方向(1,2,3,4);而每种移动方法用偏移值来表示,并将这些偏移值分别保存在数组dx和dy中,如下表
K
Dx[k]
Dy[k]
1
2
1
2
2
-1
3
1
2
4
1
-2
根据马走的规则,马可以由(i-dx[k],j-dy[k])走到(i,j)。
只要马能从(1,1)走到(i-dx[k],j-dy[k]),就一定能走到(i,j),马走的坐标必须保证在棋盘上。
我们以(n,m)为起点向左递推,当递推到(i-dx[k],j-dy[k])的位置是(1,1)时,就找到了一条从(1,1)到(n,m)的路径。
我们用一个二维数组a表示棋盘,对于任务一,使用倒推法,从终点(n,m)往左递推,设初始值a[n,m]为(-1,-1),如果从(i,j)一步能走到(n,m),就将(n,m)存放在a[i,j]中。
如下表,a[3,2]和a[2,3]的值是(4,4),表示从这两个点都可以到达坐标(4,4)。
从(1,1)可到达(2,3)、(3,2)两个点,所以a[1,1]存放两个点中的任意一个即可。
递推结束以后,如果a[1,1]值为(0,0)说明不存在路径,否则a[1,1]值就是马走下一步的坐标,以此递推输出路径。
-1,-1
4,4
4,4
2,3
任务一的源程序:
const
dx:
array[1..4]ofinteger=(2,2,1,1);
dy:
array[1..4]ofinteger=(1,-1,2,-2);
type
map=record
x,y:
integer;
end;
var
i,j,n,m,k:
integer;
a:
array[0..50,0..50]ofmap;
begin
read(n,m);
fillchar(a,sizeof(a),0);
a[n,m].x:
=-1;a[n,m].y:
=-1;{标记为终点}
fori:
=ndownto2do{倒推}
forj:
=1tomdo
ifa[i,j].x<>0then
fork:
=1to4do
begin
a[i-dx[k],j-dy[k]].x:
=i;
a[i-dx[k],j-dy[k]].y:
=j;
end;
ifa[1,1].x=0thenwriteln('no')
elsebegin{存在路径}
i:
=1;j:
=1;
write('(',i,',',j,')');
whilea[i,j].x<>-1do
begin
k:
=i;
i:
=a[i,j].x;j:
=a[k,j].y;
write('->(',i,',',j,')');
end;
end;
end.
对于任务二,也可以使用递推法,用数组A[i,j]存放从起点(x1,y1)到(i,j)的路径总数,按同样的方法从左向右递推,一直递推到(x2,y2),a[x2,y2]即为所求的解。
源程序(略)
在上面的例题中,递推过程中的某个状态只与前面的一个状态有关,递推关系并不复杂,如果在递推中的某个状态与前面的所有状态都有关,就不容易找出递推关系式,这就需要我们对实际问题进行分析与归纳,从中找到突破口,总结出递推关系式。
我们可以按以下四个步骤去分析:
(1)细心的观察;
(2)丰富的联想;(3)不断地尝试;(4)总结出递推关系式。
下面我们再看一个复杂点的例子。
例2、栈(noipxxpj)
题目大意:
求n个数通过栈后的排列总数。
(1≤n≤18)
如输入3输出5
算法分析:
先模拟入栈、出栈操作,看看能否找出规律,我们用f(n)表示n个数通过栈操作后的排列总数,当n很小时,很容易模拟出f
(1)=1;f
(2)=2;f(3)=5,通过观察,看不出它们之间的递推关系,我们再分析N=4的情况,假设入栈前的排列为“4321”,按第一个数“4”在出栈后的位置进行分情况讨论:
(1)若“4”最先输出,刚好与N=3相同,总数为f(3);
(2)若“4”第二个输出,则在“4”的前只能是“1”,“23”在“4”的后面,这时可以分别看作是N=1和N=2时的二种情况,排列数分别为f
(1)和f
(2),所以此时的总数为f
(1)*f
(2);
(3)若“4”第三个输出,则“4”的前面二个数为“12”,后面一个数为“3”,组成的排列总数为f
(2)*f
(1);
(4)若“4”第四个输出,与情况
(1)相同,总数为f(3);
所以有:
f(4)=f(3)+f
(1)*f
(2)+f
(2)*f
(1)+f(3);
若设0个数通过栈后的排列总数为:
f(0)=1;
上式可变为:
f(4)=f(0)*f(3)+f
(1)*f
(2)+f
(2)*f
(1)+f(3)*f(0);
再进一步推导,不难推出递推式:
f(n)=f(0)*f(n-1)+f
(1)*f(n-2)+…+f(n-1)*f(0);
即f(n)=(n>=1)
初始值:
f(0)=1;
有了以上递推式,就很容易用递推法写出程序。
var
a:
array[0..18]oflongint;
n,i,j:
integer;
begin
readln(n);
fillchar(a,sizeof(a),0);
a[0]:
=1;
fori:
=1tondo
forj:
=0toi-1doa[i]:
=a[i]+a[j]*a[i-j-1];
writeln(a[n]);
end.
递推算法最主要的优点是算法结构简单,程序易于实现,难点是从问题的分析中找出解决问题的递推关系式。
对于以上两个例子,如果在比赛中找不出递推关系式,也可以用回溯法求解。
2019-2020年高中信息技术全国青少年奥林匹克联赛教案递推法二
课题:
递推法
目标:
知识目标:
递推概念与利用递推解决实际问题
能力目标:
递推方程
重点:
递推方程
难点:
递推方程写出
板书示意:
1)递推的理解(例20)
2)倒推法(例21)
3)顺推法(例22、例23)
授课过程:
递推就是逐步推导的过程。
我们先看一个简单的问题。
例20:
一个数列的第0项为0,第1项为1,以后每一项都是前两项的和,这个数列就是著名的裴波那契数列,求裴波那契数列的第N项。
分析:
我们可以根据裴波那契数列的定义:
从第2项开始,逐项推算,直到第N项。
因此可以设计出如下算法:
F[0]:
=1;F[1]:
=2;
FORI:
=2TONDO
F[I]:
=F[I–1]+F[I–2];
从这个问题可以看出,在计算裴波那契数列的每一项目时,都可以由前两项推出。
这样,相邻两项之间的变化有一定的规律性,我们可以将这种规律归纳成如下简捷的递推关系式:
Fn=g(Fn-1),这就在数的序列中,建立起后项和前项之间的关系。
然后从初始条件(或是最终结果)入手,按递推关系式递推,直至求出最终结果(或初始值)。
很多问题就是这样逐步求解的。
对一个试题,我们要是能找到后一项与前一项的关系并清楚其起始条件(或最终结果),问题就可以递推了,接下来便是让计算机一步步了。
让高速的计算机从事这种重复运算,真正起到“物尽其用”的效果。
满足求解
Y{顺推}
初始条件F1
N{倒推}
由题意(或递推关系)定初始值F1(边界条件)求出顺推关系式Fi=g(Fi-1);
由题意(或递推关系)确定最终结果Fn;求出倒推关系式Fi-1=g’(Fi);
I=1;{由边界条件F1出发进行顺推}
I=n;{从最终结果Fn出发进行倒推}
While当前结果Fi非最终结果Fndo
While当前结果Fi非初始值F1do
由Fi=g(Fi-1)顺推后项;
由Fi-1=g(Fi)倒推前项;
输出顺推结果Fn和顺推过程;
输出倒推结果F1和倒推过程;
递推分倒推法和顺推法两种形式。
算法流程如下:
一、倒推法
所谓倒推法,就是在问题的解或目标是由初始值递推得到的问题中,已知解或目标,根据递推关系,采用倒推手段,一步步的倒推直至求得这个问题的初始陈述的方法。
因为这类问题的运算过程是一一映射的,故可分析其递推公式。
看看下面的例题。
例21:
贮油点
一辆重型卡车欲穿过1000公里的沙漠,卡车耗汽油为1升/公里,卡车总载油能力为500公升。
显然卡车装一次油是过不了沙漠的。
因此司机必须设法在沿途建立若干个贮油点,使卡车能顺利穿过沙漠。
试问司机如怎样建立这些贮油点?
每一贮油点应存储多少汽油,才能使卡车以消耗最少汽油的代价通过沙漠?
编程计算及打印建立的贮油点序号,各贮油点距沙漠边沿出发的距离以及存油量。
格式如下:
No.
Distance(k.m.)
Oil(litre)
1
××
××
2
××
××
…
……
……
分析:
设Way[I]——第I个贮油点到终点(I=0)的距离;
oil[I]——第I个贮油点的贮油量;
我们可以用倒推法来解决这个问题。
从终点向始点倒推,逐一求出每个贮油点的位置及存油量。
图19表示倒推时的返回点。
从贮油点I向贮油点I+1倒推的方法是:
卡车在贮油点I和贮油点I+1间往返若干次。
卡车每次返回I+1点时应该正好耗尽500公升汽油,而每次从I+1点出发时又必须装足500公升汽油。
两点之间的距离必须满足在耗油最少的条件下,使I点贮足I*500公升汽油的要求(0≦I≦n-1)。
具体来说,第一个贮油点I=1应距终点I=0处500km,且在该点贮藏500公升汽油,这样才能保证卡车能由I=1处到达终点I=0处,这就是说
Way[I]=500;oil[I]=500;
为了在I=1处贮藏500公升汽油,卡车至少从I=2处开两趟满载油的车至I=1处,所以I=2处至少贮有2*500公升汽油,即oil[2]=500*2=1000;另外,再加上从I=1返回至I=2处的一趟空载,合计往返3次。
三次往返路程的耗油量按最省要求只能为500公升,即d12=500/3km,Way[2]=Way[1]+d12=Way[I]+500/3
此时的状况如图20所示。
为了在I=2处贮藏1000公升汽油,卡车至少从I=3处开三趟满载油的车至I=2处。
所以I=3处至少贮有3*500公升汽油,即oil[3]=500*3=1500。
加上I=2至I=3处的二趟返程空车,合计5次。
路途耗油亦应500公升,即d23=500/5,
Way[3]=Way[2]+d23=Way[2]+500/5;
此时的状况如图21所示。
依次类推,为了在I=k处贮藏k*500公升汽油,卡车至少从I=k+1处开k趟满载车至I=k处,即oil[k+1]=(k+1)*500=oil[k]+500,加上从I=k返回I=k+1的k-1趟返程空间,合计2k-1次。
这2k-1次总耗油量按最省要求为500公升,即dk,k+1=500/(2k-1),
Way[k+1]=Way[k]+dk,k+1=Way[k]+500/(2k-1);
此时的状况如图22所示。
最后,I=n至始点的距离为1000-Way[n],oil[n]=500*n。
为了在I=n处取得n*500公升汽油,卡车至少从始点开n+1次满载车至I=n,加上从I=n返回始点的n趟返程空车,合计2n+1次,2n+1趟的总耗油量应正好为(1000-Way[n])*(2n+1),即始点藏油为oil[n]+(1000-Way[n])*(2n+1)。
程序设计如下:
programOil_lib;
var
K:
Integer;{贮油点位置序号}
D,{累计终点至当前贮油点的距离}
D1:
Real;{I=n至终点的距离}
Oil,Way:
array[1..10]ofReal;
i:
Integer;
begin
Writeln(‘No.’,‘Distance’:
30,‘Oil’:
80);
K:
=1;
D:
=500;{从I=1处开始向终点倒推}
Way[1]:
=500;
Oil[1]:
=500;
repeat
K:
=K+1;
D:
=D+500/(2*K–1);
Way[K]:
=D;
Oil[K]:
=Oil[K–1]+500;
untilD>=1000;
Way[K]:
=1000;{置始点到终点的距离值}
D1:
=1000–Way[K–1];{求I=n处至至点的距离}
Oil[K]:
=D1*(2*k+1)+Oil[K–1];{求始点贮油量}
{由始点开始,逐一打印至当前贮油点的距离和贮油量}
fori:
=0toKdo
Writeln(i,1000–Way[K–i]:
30,Oil[K–i]:
80);
end.
二、顺推法
顺推法是从边界条件出发,通过递推关系式推出后项值,再由后项值按递推关系式推出再后项值……,依次类推,直至从问题初始陈述向前推进到这个问题的解为止。
看看下面的问题。
例22昆虫繁殖
科学家在热带森林中发现了一种特殊的昆虫,这种昆虫的繁殖能力很强。
每对成虫过x个月产y对卵,每对卵要过两个月长成成虫。
假设每个成虫不死,第一个月只有一对成虫,且卵长成成虫后的第一个月不产卵(过X个月产卵),问过Z个月以后,共有成虫多少对?
x>=1,y>=1,z>=x
输入:
x,y,z的数值
输出:
成虫对数
事例:
输入:
x=1y=2z=8
输出:
37
分析:
首先我们来看样例:
每隔1个月产2对卵,求过8月(即第8+1=9月)的成虫个数
月份
1
2
3
4
5
6
7
8
9
…
新增卵
0
2
2
2
6
10
14
26
46
…
成虫
1
1
1
3
5
7
13
23
37
…
设数组A[i]表示第I月新增的成虫个数。
由于新成虫每过x个月产y对卵,则可对每个A[I]作如下操作:
A[i+k*x+2]:
=A[i+k*x+2]+A[i]*y(1<=k,I+k*x+2<=z+1)
因为A[i]的求得只与A[1]~A[i-1]有关,即可用递推求法。
则总共的成虫个数为:
程序如下:
programexam22;
varx,y,z,i:
integer;
ans:
longint;
a:
array[1..60]oflongint;
procedureadd(i:
integer);
varj:
integer;
begin
j:
=i+2+x;{新生成虫要过x个月才开始产卵,即第I+2+x个月才出现第一群新成虫}
repeat
a[j]:
=a[j]+a[i]*y;{递推}
j:
=j+x
untilj>z+1
end;
begin
readln(x,y,z);
a[1]:
=1;{初始化}
fori:
=1tozdoadd(i);{对每个A[I]进行递推}
ans:
=0;
fori:
=1toz+1doans:
=ans+a[i];{累加总和}
writeln(ans);
end.
例23:
实数数列(NOI94第3题)
一个实数数列共有N项,已知
ai=(ai-1-ai+1)/2+d,(1
键盘输入N,d,a1,an,m,输出am。
输入数据均不需判错。
分析:
根据公式ai=(ai-1-ai+1)/2+d变形得,ai+1=ai-1-2ai+2d,因此该数列的通项公式为:
ai=ai-2-2ai-1+2d,已知a1,如果能求出a2,这样就可以根据公式递推求出am
∵ai=ai-2-2ai-1+2d……①
=ai-2-2(ai-3-2ai-2+2d)+2d
=-2ai-3+5(ai-4-2ai-3+2d)-2d
=5ai-4-12ai-3+8d
……
一直迭代下去,直到最后,可以建立ai和a1与a2的关系式。
设ai=Pia2+Qid+Ria1,我们来寻求Pi,Qi,Ri的变化规律。
∵ai=ai-2-2ai-1+2d
∴ai=Pi-2a2+Qi-2d+Ri-2a1-2(Pi-1a2+Qi-1d+Ri-1a1)+2d
=(Pi-2-2Pi-1)a2+(Qi-2-2Qi-1+2)d+(Ri-2-2Ri-1)a1
∴Pi=Pi-2-2Pi-1……②
Qi=Qi-2-2Qi-1+2……③
Ri=Ri-2-2Ri-1……④
显然,P1=0Q1=0R1=1(i=1)
P2=1Q2=0R2=0(i=2)
将初值P1、Q1、R1和P2、Q2、R2代入②③④可以求出Pn、Qn、Rn
∵an=Pna2+Qnd+Rna1
∴a2=(an-Qnd+Rna1)/Pn
然后根据公式①递推求出am,问题解决。
但仔细分析,上述算法有一个明显的缺陷:
在求由于在求a2要运用除法,因此会存在实数误差,这个误差在以后递推求am的过程又不断的扩大。
在实际中,当m超过30时,求出的am就明显偏离正确值。
显然,这种算法虽简单但不可靠。
为了减少误差,我们可设计如下算法:
∵ai=Pia2+Qid+Ria1
=Pi-1a3+Qi-1d+Ri-1a2
=Pi-2a4+Qi-2d+Ri-2a3
……
=Pi-2+kak+Qi-2+kd+Ri-2+kak-1
∴an=Pn-k+2ak+Qn-k+2d+Rn-k+2ak-1
ak=(an-Qn-k+2d+Rn-k+2ak-1)/Pn-k+2……⑤
根据公式⑤,可以顺推a2、a3、…、aM。
虽然仍然存在实数误差,但由于Pn-k+2递减,因此最后得出的am要比直接利用公式①精确得多。
程序如下:
programNOI94_3;
const
MaxN=60;
var
N,M,i:
Integer;
D:
Real;
A:
array[1..MaxN]ofReal;
F:
array[1..MaxN,1..3]ofReal;
{F[i,1]:
对应Pi;F[i,2]:
对应Qi;F[i,3]:
对应Ri}
procedureInit;
begin
Write(‘N,M,D=’);
Readln(N,M,D);{输入项数、输出项序号和常数}
Write(‘A1,A’,N,‘=’);
Readln(A[1],A[N]);{输入a1和an}
end;
procedureSolve;
{根据公式Pi←Pi-2-2*Pi-1,Qi←Qi-2-2*Qi-1,Ri←Ri-2-2*Ri-1求Pi、Qi、Ri}
begin
F[1,1]:
=0;F[1,2]:
=0;F[1,3]:
=1;
F[2,1]:
=1;F[2,2]:
=0;F[2,3]:
=0;
fori:
=3toNdo
begin
F[i,1]:
=F[i–2,1]–2*F[i–1,1];
F[i,2]:
=F[i–2,2]–2*F[i–1,2]+2;
F[i,3]:
=F[i–2,3]–2*F[i–1,3];
end;
end;
procedureMain;
begin
Solve;
{递推A2…Am}
fori:
=2toMdo
A[i]:
=(A[N]–F[N–i+2,2]*D–F[N–i+2,3]*A[i–1])/F[N–i+2,1];
Writeln(‘a’,m,‘=’,A[M]:
20:
10);
end;
begin
Init;
Main;
end.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 高中信息技术 全国青少年奥林匹克联赛教案 递推法 高中 信息技术 全国青少年 奥林匹克 联赛 教案
![提示](https://static.bingdoc.com/images/bang_tan.gif)