递推算法
关于房产税-
递推算法典型例题
一、
教学目标
1
、
2
、
由浅入深，了解递推算法
掌握递推算法的经典例题
二、
重点难点分析
1
、
2
、
重点：递推关系的建立
难点：如何将所求问题转化为数学模型
三、
教具或课件
微机
四、
主要教学过程
(
一
)
引入新课
客观世界中的各个事物之间
或者一个事物的内部各元素之间，
往往存在
(
< br>隐藏
)
着很多
本质上的关联。我
们设计程序前．应该要通过细心的观察、丰富的联想、不断的尝试推
理．尽可能先归纳总
结出其内在规律，然后再把这种规律性的东西抽象成数学模型，最
后再去编程实现。递推
关系和递归关系都是一种简洁高效的常见数学模型，我们今天先
来深入研究一下递推算法
如何实现。
(
二
)
教学过程设计
递推法是一种重要的数
学方法，在数学的各个领域中都有广泛的运用，也是计算机
用于数值计算的一个重要算法
。这种算法特点是：一个问题的求解需一系列的计算，在
已知条件和所求问题之间总存在
着某种相互联系的关系，在计算时，如果可以找到前后
过程之间的数量关系（即递推式）
，那么，这样的问题可以采用递推法来解决。从已知
条件出发，逐步推出要解决的问题，
叫顺推；从问题出发逐步推到已知条件，此种方法
叫逆推。无论顺推还是逆推，其关键是
要找到递推式。这种处理问题的方法能使复杂运
算化为若干步重复的简单运算，充分发挥
出计算机擅长于重复处理的特点。
递推算法的首要问题是得
到相邻的数据项间的关系（即递推关系）
。递推算法避开了
通项
公式的麻烦，把一个复杂的问题的求解，分解成了连续的若干步简单运算。一般说
来可以
将递推算法看成是一种特殊的迭代算法。
（在解题时往往还把递推问题表现为迭代
形式，用循环处理。所谓
“
迭代
”
，就是在程序中用同一个变量来存放每一次推算出来的
值，每一次循环都执行同一个语句，给同一变量赋以新的值，即用一个新值代替旧值，
这种方法称为迭代。
）
1
．递推关系的定义和求解递推关系的方法
有一类试题，每相邻两项数之间的变化有一定的规律性，我们可将这种规律归纳成
如下简捷的递推关系式：
f
n
=g(f
n-1
)
或者
f
n-1
=g'(f
n
)
这样就
在数的序列中，
建立起后项和前项之间的关系。
然后从初始条件
(
或最终结果
)
入手，
一步步地按递推关系式递推，
直至求出最终结果
(
或初始值
)
。很多
程序就是按这样
的方法逐步求解的。如果对一个试题，我们要是能找到后一项数与前一项
数的关系并清
楚其起始条件
(
或最终结
果
)
，问题就比较容易解决，
让计算机
一步步计算就是了。让高速
的计算机从事这种重复运算，可真正起到“物尽其用”的效果
。递推分倒推法和顺推法
两种形式。一般分析思路：
If
求解初始条件
f1
then begin
{
倒推
}
由题意
(
或递推关系
)
确定最终结果
fn
；
求出倒推关系式
f
i-1
< br>=g'(f
i
)
；
for
i
←
n downto 2 do f
i-1
←
g(f
i
)
；
{
从最终结果
fn
出发进行倒推
}
输出倒推结果
fl
；
end{then}
else begin
{
顺推
}
由题意
(
或
递推关系
)
确定初始值
f1(
边界条件
)
；
求出顺推关系式
< br>f
i
=g(f
i-1
)
：
for
i
←
2 to n do f
i
←
g(f
i-1
)<
/p>
；
{
由边界条件
f1
出发进行顺推
}
输出顺推结果
fn
；
end
；
{else}
由此可见，
递推算法的时间复杂度一般为
W(n)<
/p>
。
我们之所以将递推法划入归纳策略，
是
因为初始条件
(
或最终结果
)
除试题已明确给定外，
都是通过对问题的整理与化简而确定
的，其递推式也是对实际问题的分析与归纳而得到的，因此递推本质上属于归纳。
2
．递推关系的建立
递推关系中存在着三大基本问题：如何建立递推关系，已给出的递推关系有何性质，
以及如何求解递推关系。其中核心问题是如何建立递推关系。
建立递推关系的关键在于寻找第
n
项与前面
(
或后面
)
几项的关系
式，
以及初始项的值
(
或
最终结果值
)
。它不是一种抽象的概念，而是针对某
一具体题目或一类题目而言的。
3
、问题举例
【例
1
】
有
2
×
n
的一个长方形方格，
用一个
1
×
2
的骨牌铺满方格。<
/p>
例如
n=3
时，
为
2
×
3
方格
。此时用一个
1
×
2
< br>的骨牌铺满方格，共有
3
种铺法：
编写一个程序，试对给出的任意一个
n(n>0),
输出铺法总数。
【问题分析】
（
1
）面对上述问题，如果思考方法不恰当，要想获得问题
的解答是相当困难的。可以用
递推方法归纳出问题解的一般规律。
（
2
）当
n=1
时，只能是一种铺法
如左
图，铺法总数表示为
X
1
=1
；
（
3
）当
N=2
时：骨牌
可以两个并列竖排，也可以并列横排，再无其他方法，如下左图所
示，因此，铺法总数表
示为
X
2
=2
；
（
4
）当
N=3
< br>时：骨牌可以全部竖排，也可以认为在方格中已经有一个竖排骨牌，则需要
在方格
中排列两个横排骨牌（无重复方法），若已经在方格中排列两个横排骨牌，则必
须在方格
中排列一个竖排骨牌。如题图，再无其他排列方法，因此铺法总数表示为
x
3
=3.
由此可以看出，当
n=3
时的排列骨牌的方法数是
n=1
和
n=2
排列方法数的和。
（
5
）推出
一般规律：对一般的
n
，要求
X
n
可以这样来考虑，若第一个骨牌是
竖排列放
置，剩下有
n-1
个骨牌需要排列，这时排列方法数为
X
n
-1
；若第一个
骨牌是横排
列，整个方格至少有
2
个骨
牌是横排列（
1*2
骨牌），因此剩下
n-2
个骨牌需要排列，这
是骨牌排列方法数为
X
n
-2
。从第一骨牌排列方法考虑，只有这两种可能，所以有：
X
n
=X
n
-1
+X
n -2
（
N>2
）
X
1
=1
X
2
=2
以上就是问题求解的递推
公式。任给
N
都可以从中获得解答。例如
N=5
，
X
3
=X
2
+X
1
=3
X
4<
/p>
=X
3
+X
2<
/p>
=5
X<
/p>
5
=X
4
+X<
/p>
3
=8
下面是输入
N
，输出
X
1
~ X
n
的
Pascal
程序：
program p12_20;
var
x,y,z:longint;
i,n:integer;
begin
write('Input n:');
read(n);
x:=0;
y:=1;
for i:=1 to n
do
begin
z:=y+x;
writeln('x[',i:2,']=',z);
x:=y;y:=z;
end;
end.
下面是运行程序输入
n=30
，输出的结果：
input n:30
x[1]=1
x[2]=2
x[3]=3
x[4]=5
x[5]=8
...............................
x[28]=514229
x[29]=832040
x[30]=1346269
问题的结果就是有名的斐波那契
（
Fibonacci
）
数列问题，
F(1)=0
，
F(2)=1
，
在
n>2
时有：
F(n)=F(n-1)+F(n-2)
。
1/
3
【例
2
】
用迭代方法求
Y=X
的值。
X
由键盘输入。利用下列迭代公式计算：
2
-4
y
n
+ 1
=2/3y
n
+x/(3y
n
),
初始值
y0
=x,
误差要求ε
=10
。
【问题分析】
（<
/p>
1
）迭代法即反复代入法。在上式中，将
Y
n
代入公式的右端，可以计算出
Y<
/p>
n
+
1
，然
后
将
Y
n + 1
作为新的
Y
n
代入右端，以计算出
新的
Y
n +
1
，如此重复直到
|Y
n + 1
-Y
n
|<
ε为止
。
初始值
Y
0
=X
，意味着么一次代入公式右端的
Y
n
的取值为
X
。
-4
（
2
）本题算法特点：循环，变量迭代，直到前后两次的计算误差小于
10
结束并输出
结果。
程序如下：
program p12_21;
const e=0.0001;
var x,y0,y1,y2:real;
begin
write('Input x:');
read(x);writeln;
y1:=x;y2:=x;
repeat
y1:=y2;
y2:=2/3*y1+x/(3*y1*y1);
<
br>X=8 过河卒 <
br>) <
br>．该马所在的点和所 ( ， <
br>，
until abs(y2-y1)
writeln(x,':3x=',y2);
end.
当
则输出结果：
8
：
3X=2.000000011E+00
当
X=27
则输出结果：
27
：
3X=3.E+
00
【例
3
】
(NOIP2002
初中组第四题
【问题描述】棋盘上
A
点有
一个过河卒，需要走到目标
B
点。卒行走的规则：可以
向下、或者向右。同时在棋盘上的任一点有一个对方的马
(
如
C
点
)
有跳跃一步可达的点称为对方马的拄制点
如下图中的
c
点和
P1
，
P2
，…，
P8)
。卒不能
通过对方马的控制点．棋盘用坐
标表示，
A
点
(0
0)
、
B
点
(n
，
m)(n
m
为不超过
20
的整
数
)
．同样马的位置坐
标是需要给出的
C(x,y)
．
C
≠
A C
≠
B<
/p>
。现在从键盘输入
n,m
．
,
要
你计算出卒从
A
点能够到达
B
点的路径的条数。
【问题分析】跳马一般是在学习回溯或搜索等算
法的时候．很多书上也有类似的题
目，一些比赛中也经常出现这一问题的变形
(
如
NOIPl997
初
中组第三题
)
。有些同学一看
到这种类
型的题目就去盲目搜索，但事实证明：当
n
，
< br>m=15
就会超时。
其实，
对本题稍加分析就能发现，要到达棋盘上的一个点，只能从左边过来
(
< br>我们称
之为左点
)
或是从上面过
来
(
我们称之为上点
)
。根据加法原理．到达某一点的路径数目，
就等于到达其相邻的上点和左点的路
径数目之和．因此我们可以使用逐列
(
或逐行
< br>)
递推
的方法来求出起点到终点的路径数目。障碍点
(
马的控制点
)
也
完全适用，只要将到达该
点的路径数目设置为
0
即可。
假设用
F[i,j
]
表示到达点
(i,j)
的路径数目，
用
g[i,j]
表示点
(i,j)
是否是对方马的
控制点
g[i,j]=0
表示不是对方马的控制点
,g[i,j]
=1
表示是对方马的控制点。
则
,
我们可
以得到如下的递推关系式：
F[0,0]=1
F[i,j]=0
{g[x,y]=1]
F[i,0]=F[i-1,0]
{i>0
，
g[x,y]=0}
F[0,j]=F[0,j-1] {j>0,g[x,y]=0}
F[i,j]=F[i-1,j]+F[i,j-1] {i>0
，
j>0
．
G[x,
y]=0}
上述递推关系式的边界为：
F[0,0]=l<
/p>
。考虑到最大情况下；
n=20,m=20
．路径条数可
能会超出长整数范围，所以要使用
int64<
/p>
类型计数或高精度运算。
【参考程序】
program
p2_1(input,output);
const
dx: array[1..8] of Shortint=(-2, -1, 1, 2, 2, 1,
-1, -2);
dy: array[1..8] of
Shortint=(1, 2, 2, 1, -1, -2, -2, -1);
var
n, m, x, y, i, j:
Byte;
g: array[0..20, 0..20] of Byte;
f: array[0..20, 0..20] of int64;
begin
Readln(n, m, x, y);
Fillchar(g, Sizeof(g), 0);
g[x,y]:=1;
for i:=1 to 8
do
if (x+dx[i]>=0)and(x+dx[i]<=n)and
(y+dy[i]>=0)and(y+dy[i]<=m)then
g[x+dx[i],y+dy[i]]:=1;
f[0,0]:=1;
for i:=1 to n
do
if g[i,0]=0 then
f[i,0]:=f[i-1,0];
for i:=1 to m do
if g[0,i]=0 then f[0,i]:=f[0, i-1];