信息竞赛部分讲义

递推算法讲义

一．递推的概念与基本思想：

给定一个数的序列H0,H1,…,Hn,…若存在整数n0，使当n>n0时,可以用等号(或大于号、小于号)将Hn与其前面的某些项Hi(0<i<n)联系起来，这样的式子就叫做递推关系。

二．解决递推问题的一般步骤 1.建立递推关系式； 2.确定边界条件； 3.递推求解；

三．递推的形式递推分顺推法和倒推法两种形式。

1、顺推法： 从已知条件出发，逐步推出要解决的问题。 2、逆推法：从问题出发，逐步推到已知条件。

四．递推的应用分类

…… 此处隐藏0字 ……

1、一般递推问题 2、组合计数类问题 3、一类博弈问题的求解

4、动态规划问题的递推关系

五、递推的应用

1.一般递推问题