下载文档原格式
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中，如下表）走到(i,j)。
只要马能从（1，1）走到（i-dx[k],j-dy[k]），就一定能走到（i,j）,马走的坐标必须保证在棋盘上。
递推关系的建立及在信息学竞赛中的应用世界上的一切事物都在不经意之中变化着，在这纷繁的变幻中，许多现象的变化是有规律可循的。
这种规律往往呈现出前因和后果的关系，故我们可以运用递推的思想去研究这些变化。
本文着重说明了递推关系的建立，并在此基础上简略介绍求解递推关系的方法。
接着，阐明递推关系与动态规划之间的关系，并比较了一般递推关系与动态规划之间的异同，同时举例说明递推关系在竞赛中的应用。
在文章的最后，总结出学好递推关系，不仅可以提高我们的数学素质，对信息学竞赛更是大有帮助。
目录【正文】第02页一、引论第02页二、递推关系的定义第02页三、递推关系的建立第02页⒈五种典型的递推关系第03页⒉递推关系的求解方法第06页四、递推关系的应用第06页五、总结第10页【附录】第10页【参考书目】第12页【程序描述】第12页【正文】一、引论瞬息变幻的世界，每一件事物都在随时间的流逝发生着微妙的变化。
而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。
即是说，某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。
所谓“三岁看老”，说的就是这个道理。
这一道理也正体现了递推的思想。
递推关系几乎在所有的数学分支中都有重要作用，在一切向“更快、更高、更强”看齐的当今信息学奥林匹克竞赛中更因简洁高效而显示出其独具的魅力。
在递推关系发挥重要作用的今天，深入研究其性质、特点便成为一件十分必要的事情。
本文就将围绕着递推关系的三大基本问题中的如何建立递推关系展开论述，并通过例题说明递推关系在当今信息学竞赛中的应用。
二、递推关系的定义相信每个人对递推关系都不陌生，但若要说究竟满足什么样的条件就是递推关系，可能每个人又会有不同的说法。
为了更好地研究递推关系，首先让我们明确什么是递推关系。
【定义1】给定一个数的序列H0,H1,…,H n,…若存在整数n0，使当n≥n0时,可以用等号(或大于号、小于号)将H n与其前面的某些项H n(0≤i<n)联系起来，这样的式子就叫做递推关系。
递推法课题：递推法 目标：知识目标：递推概念与利用递推解决实际问题 能力目标：递推方程 重点：递推方程 难点：递推方程写出 板书示意：1） 递推的理解（例20） 2） 倒推法（例21）3） 顺推法（例22、例23）授课过程：递推就是逐步推导的过程。
我们先看一个简单的问题。
例20：一个数列的第0项为0，第1项为1，以后每一项都是前两项的和，这个数列就是著名的裴波那契数列，求裴波那契数列的第N 项。
分析：我们可以根据裴波那契数列的定义：从第2项开始，逐项推算，直到第N 项。
因此可以设计出如下算法：F[0] := 1; F[1] := 2; FOR I := 2 TO N DOF[I] := F[I – 1] + F[I – 2];从这个问题可以看出，在计算裴波那契数列的每一项目时，都可以由前两项推出。
这样，相邻两项之间的变化有一定的规律性，我们可以将这种规律归纳成如下简捷的递推关系式：F n =g(F n-1)，这就在数的序列中，建立起后项和前项之间的关系。
然后从初始条件（或是最终结果）入手，按递推关系式递推，直至求出最终结果（或初始值）。
很多问题就是这样逐步求解的。
对一个试题，我们要是能找到后一项与前一项的关系并清楚其起始条件（或最终结果），问题就可以递推了，接下来便是让计算机一步步了。
让高速的计算机从事这种重复运算，真正起到“物尽其用”的效果。
()()()⎪⎩⎪⎨⎧≥+===--2120121n f f n n f n n n递推分倒推法和顺推法两种形式。
算法流程如下：一、倒推法所谓倒推法，就是在问题的解或目标是由初始值递推得到的问题中，已知解或目标，根据递推关系，采用倒推手段，一步步的倒推直至求得这个问题的初始陈述的方法。
因为这类问题的运算过程是一一映射的，故可分析其递推公式。
看看下面的例题。
例21：贮油点一辆重型卡车欲穿过1000公里的沙漠，卡车耗汽油为1升/公里，卡车总载油能力为500公升。
算法在信息学奥赛中的应用 (递推法)所谓递推，是指从已知的初始条件出发，依据某种递推关系，逐次推出所要求的各中间结果及最后结果。
其中初始条件或是问题本身已经给定，或是通过对问题的分析与化简后确定。
可用递推算法求解的题目一般有以下二个特点：（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[ 12 2 -13 1 24 1 -2根据马走的规则，马可以由（i-dx[k],j-dy[k]）走到(i,j)。
信息学竞赛中问题求解常见题分析（二）递推问题瞬息万变的世界，每一件事物都在随时间的流逝发生着微妙的变化。
而在这纷繁的变幻中，许多现象的变化是有规律的，这种规律往往呈现出前因和后果的关系。
即是说，某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。
本文将围绕着递推关系的三大基本问题中如何建立递推关系展开论述，并通过例题说明递推关系在当今信息学竞赛中的应用。
一、递推关系的定义相信每个人对递推关系都不陌生，但若要说究竟满足什么样的条件就是递推关系，可能每个人又会有不同的说法。
为了更好地研究递推关系，首先让我们明确什么是递推关系。
【定义l】给定一个数的序列H。
，H1，……，Hn若存在整数no，使当n>=no时，可以用等号将H n与其前面的某些项H n。
(0<=i<n)联系起来，这样的式子就叫做递推关系。
二、递推关系的建立递推关系中存在着三大基本问题：如何建立递推关系，已给的递推关系有何性质，以及如何求解递推关系。
建立递推关系的关键在于寻找第n项与前面几项的关系式，以及初始项的值。
它不是一种抽象的概念，是需要针对某一具体题目或一类题目而言的。
在下文中，我们将对五种典型的递推关系的建立作比较深入具体的讨论。
1．四种典型的递推关系Ⅰ．Fibonacci数列型在所有的递推关系中，Fibonacci数列应该是最为大家所熟悉的，Fibonacci数列数列的代表问题是由意大利著名数学家Fibonacci于1202年提出的“兔子繁殖问题”(又祢“Fibonacci问题”)。
问题的提出：有雌雄一对兔子，假定过两个月便可繁殖雌雄各一的一对小兔子。
问过n个月后共有多少对兔子?解：设满x个月共有兔子F x，对，其中当月新生的兔子数目为N x对。
第x-1个月留下的兔子数目设为O x对。
则：F x=N x+O x，而O x =F x-1， N x=O x-1=F x -2(即第x-2个月的所有兔子到第x个月都有繁殖能力了) ，因此F x=F x-1+F x-2边界条件：F0=0，F1=1 由上面的递推关系可依次得到 F2=F1+F0=l，F3=F2+F1=2，F4=F3+F2=3，F5=F4+F3=5，…。
学科分类号110.81本科毕业论文题目递推关系的求解及其应用姓名杭勤霞学号10院（系）数学与计算机科学学院专业数学与应用数学年级2010级指导教师雍进军职称讲师二○一四年五月贵州师范学院本科毕业论文（设计）诚信声明本人郑重声明：所呈交的本科毕业论文（设计），是本人在指导老师的指导下，独立进行研究工作所取得的成果，成果不存在知识产权争议，除文中已经注明引用的内容外，本论文不含任何其他个人或集体已经发表或撰写过的作品成果。
对本文的研究做出重要贡献的个人和集体均已在文中以明确方式标明。
本人完全意识到本声明的法律结果由本人承担。
本科毕业论文作者签名：2014年5月11日贵州师范学院本科毕业论文(设计)任务书贵州师范学院本科毕业论文（设计）开题报告书开题报告会纪要贵州师范学院数学与计算机科学学院指导教师指导本科毕业论文(设计)情况登记表贵州师范学院数学与计算机科学学院本科毕业论文（设计）交叉评阅表学院（盖章）：贵州师范学院本科毕业论文（设计）答辩记录表目录摘要 0Abstract...................................................... 错误!未定义书签。
绪论 (2)1 线性递推关系 (3)线性递推数列的相关认识 (3)1.2 线性递推数列通项公式的求解分类 (4)1.3 利用线性递推数列通项公式解决问题 (4)1.4 利用线性递推数列通项公式解决数学中的一些问题 (7)斐波那契数 (7)2 递推关系与生成函数 (9)生成函数的定义及其性质 (9)2.1.1 生成函数的一些性质 (10)2.2 生成函数在求解递推关系中应用 (10)2.2.1 利用生成函数来求常系数线性非齐次递推关系 (10)2.2.2 生成函数求解方程递推关系 (11)3 递推关系在其它方面的应用 (12)排列组合问题 (12)3.2 九连环问题 (13)总结 ........................................................ 错误!未定义书签。
矿产资源开发利用方案编写内容要求及审查大纲
矿产资源开发利用方案编写内容要求及《矿产资源开发利用方案》审查大纲一、概述
㈠矿区位置、隶属关系和企业性质。
如为改扩建矿山, 应说明矿山现状、
特点及存在的主要问题。
㈡编制依据
(1简述项目前期工作进展情况及与有关方面对项目的意向性协议情况。
(2 列出开发利用方案编制所依据的主要基础性资料的名称。
如经储量管理部门认定的矿区地质勘探报告、选矿试验报告、加工利用试验报告、工程地质初评资料、矿区水文资料和供水资料等。
对改、扩建矿山应有生产实际资料, 如矿山总平面现状图、矿床开拓系统图、采场现状图和主要采选设备清单等。
二、矿产品需求现状和预测
㈠该矿产在国内需求情况和市场供应情况
1、矿产品现状及加工利用趋向。
2、国内近、远期的需求量及主要销向预测。
㈡产品价格分析
1、国内矿产品价格现状。
2、矿产品价格稳定性及变化趋势。
三、矿产资源概况
㈠矿区总体概况
1、矿区总体规划情况。
2、矿区矿产资源概况。
3、该设计与矿区总体开发的关系。
㈡该设计项目的资源概况
1、矿床地质及构造特征。
2、矿床开采技术条件及水文地质条件。
