第3讲 递推专题讲座 acm

《第3讲 递推专题讲座 acm》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第3讲递推递推是一种应用非常广泛的常用算法之一，与下一章的递归有着密切的联系。本章探讨递推在求解数列、数阵以及计数等应用案例方面的应用。3.1递推概述在纷繁变幻的世界，所有事物都随时间的流逝发生着微妙的变化。许多现象的变化是有规律可循的，这种规律往往呈现出前因后果的关系。某种现象的变化结果与紧靠它前面变化的一个或一些结果紧密关联。递推的思想正体现了这一变化规律。3.1.1递推算法所谓递推，是在命题归纳时，可以由n−k,…,n−1的情形推得n的情形。一个线性递推可以形式地写成其中f(n)=0时递推是齐次的，否则是非齐次的。递推的一般解

2、法要用到n次方程的求根。递推关系是一种高效的数学模型，是组合数学中的一个重要解题方法，在组合计数中有着广泛的应用。在概率方面利用递推可以解决一类基本事件个数较大的概率问题。在对多项式的求解过程中，很多情况可以使用递推算法来实现。在行列式方面，某些n阶行列式只用初等变换难以解决，但如果采用递推求解则显得较为容易。递推关系不仅在各数学分支中发挥着重要的作用，由它所体现出来的递推思想在各学科领域中更是显示出其独特的魅力。递推是利用问题本身所具有的一种递推关系求解问题的一种方法。设要求问题规模为n的解，当n=1时，解或为已知，或能非常方便地

3、得到解。能采用递推法构造算法的递推性质，能从已求得的规模为1,2,…,i−1的一系列解，构造出问题规模为i的解。这样，程序可从i=0或i=1出发，重复地由已知至i−1规模的解，通过递推，获得规模为i的解，直至得到规模为n的解。递推算法的基本思想是把一个复杂的庞大的计算过程转化为简单过程的多次重复，该算法充分利用了计算机的运算速度快和不知疲倦的特点，从头开始一步步地推出问题最终的结果。使用递推算法编程，既可使程序简练，又可节省计算时间。33对于一个序列来说，如果已知它的通项公式，那么要求出数列中某项之值或求数列的前n项之和是简单的。但

4、是，在许多情况下，要得到数列的通项公式是困难的，甚至无法得到。然而，一个有规律的数列的相邻位置上的数据项之间通常存在着一定的关系，可以借助已知的项，利用特定的关系逐项推算出它的后继项的值，直到找到所需的那一项为止。递推算法避开了求通项公项的麻烦，把一个复杂的问题的求解，分解成连续的若干步简单运算。递推算法的首要问题是得到相邻的数据项之间的关系，即递推关系。它针对这样一类问题：问题的解决可以分为若干步骤，每个步骤都产生一个子解（部分结果），每个子解都是由前面若干子解生成。不同的子解，其所相关的问题规模也随子解不同而递增。我们把这种由前

5、面的子解得出后面的子解的规则称为递推关系。我们在设计求解问题前，要通过细心的观察，丰富的联想，不断尝试推理，尽可能归纳总结其内在规律，然后再把这种规律性的东西抽象成递推数学模型。3.1.2递推实施步骤与描述利用递推求解实际问题，需要掌握递推的具体描述及其实施步骤。1．实施递推的步骤（1）确定递推变量应用递推算法解决问题，要根据问题的具体实际设置递推变量。递推变量可以是简单变量，也可以是一维或多维数组。（2）建立递推关系递推关系是指如何从变量的前一些值推出其下一个值或从变量的后一些值推出其上一个值的公式（或关系）。递推关系是递推的依据

6、，是解决递推问题的关键。有些问题，其递推关系是明确的，大多数实际问题并没有现成的明确的递推关系，需根据问题的具体实际，细心的观察，丰富的联想，不断尝试推理，才能确定问题的递推关系。（3）确定初始（边界）条件对所确定的递推变量，要根据问题最简单情形的数据确定递推变量的初始（边界）值，这是递推的基础。（4）对递推过程进行控制递推过程不能无休止地重复执行下去。递推过程在什么时候结束，满足什么条件结束，这是编写递推算法必须考虑的问题。递推过程的控制通常可分为两种情形：一种是所需的递推次数是确定的值，可以计算出来；另一种是所需的递推次数无法确

7、定。对于前一种情况，可以构建一个固定次数的循环来实现对递推过程的控制；对于后一种情况，需要进一步分析出用来结束递推过程的条件。2．递推算法框架描述递推通常由循环来实现，一般在循环外确定初始（边界）条件，在设置的循环中实施递推。下面归纳常用的递推模式并作简要的框架描述。首先，从递推流向可分为顺推与逆推。（1）简单顺推算法33顺推即从前往后推，从已求得的规模为1,2,…,i−1的一系列解，推出问题规模为i的解，直至得到规模为n的解。简单顺推算法框架描述：f(1−i−1)=<初始值>；//确定初始值for(k=i;k<=n;k++)f(k

8、)=<递推关系式>；//根据递推关系实施递推printf(f(n))；//输出n规模的解f(n)（2）简单逆推算法逆推即从后往前推，从已求得的规模为n,n−1,…,i+1的一系列解，推出问题规模为i的解，直至得到规模为1的解。简单逆推