加载中…第三节 层层递进——递推法与迭代法
(2011-10-22 20:46:03)
标签：
杂谈 |
分类： QBASIC教程 |
第三节
层层递进——递推法与迭代法
应
知
应
会
1.熟悉递推法和迭代法的思路；
2.能够用递推法和迭代法解决数列问题。
在数学中我们常常会遇到这样的问题：已知第
一项(或几项)，要求能得出后面项的值，这就
是用了一种叫“递推”的方法。
【学习任务9】有个爱好幻想的人，想知道一年内一对兔子能繁殖多少对小兔子。于是，他围了一个栅栏，把一对刚出生并且是雌雄成对的小兔子养在里面。假设小兔子生下后第二个月就能繁殖，以后每月生产一次且每次都是生一雌一雄两只兔子，那么一年后将有多少对兔子?假设没有兔子死亡。
这是一道有趣的数学题，也就是著名的意大利数学家斐波那契在《算盘书》中记载的“兔子问题”。
v
【问题分析】
v
第1个月，有一对小兔子；
v
第2个月，小兔子长成了大兔子；
v
第3个月，大兔子；生下一对小兔子，这时，有2对兔子了；
v
第4个月，大兔子又生了一对小兔子，小兔子也长成大兔子了，栅栏里有3对兔子；
v
第5个月，原来大兔子又生了一对小兔子，而第3个月出生的兔子已成熟，也生了一对小兔子，这时共有5对兔子；
v
……
v
以此类推，我们可以用如图10-2来表示(B为一对小兔子，A为一对大兔子)：
v
月数
v
B
1
第1个月
v
v
A
1
第2个月
v
v
A
B
2
第3个月
v
A
B
A
3
第4个月
v
A
B
A
A
B
5
第5个月
v
A
B
A A
A
8
第6个月
v
图
v
从图解分析来看，很容易得出兔子繁殖的规律：
v
v
v
斐波那契数列的规律是：数列中的第1及第2个数是1，从第3个数起，该数是其前面2个数之和。我们可以编写程序输出此数列的前20项。
v
【程序清单】
v
REM L10 -12A
v
CLS
v
f1 = 1
v
f2 = 1
v
PRINT f1,
f2,
v
FOR i = 3 TO
20
v
f3
= f1 + f2
v
PRINT
f3,
v
f1
= f2
v
f2
= f3
v
NEXT i
v
PRINT
v
END
v
【运行结果】
v
1
1
3
5
v
8
13
21
34
55
v
89
144
233
377
610
v
987
1597
2584
4181
6765
v
实际上，斐波那契数列中的各项存在如下递推关系：
v
Ｆn=Ｆn-1＋Ｆn-2
(n≥3)
v
这种后项由前面的项按一定的数学关系来求得的方法，叫递推。解决递推问题必须具备两个条件：
v
（1）初始条件；
v
（2）递推关系（或递推公式）。
v
在上例中，初始条件为：f1=1,f2=1；递推公式为：f3=f2+f1，用f1,f2,f3代表三个数，在每一次循环中它们代表不同的数。在程序运行过程中，这些变量不断地以新值取代原值，这种不断以新值取代原值得操作称为“迭代”。程序中的f1,f2,f3称为迭代变量，它们的值在不断地变化被迭代的。对于递推问题一般可以用迭代方法来处理，但有时不用迭代方法也很简洁。如上面的例子，由于我们知道了它的递推关系，就可以这样来设计程序：
v
【程序清单】
v
REM
L10-12B
v
DIM
f(20)
v
f(1) = 1
v
f(2) = 1
v
PRINT f(1),
f(2),
v
FOR i = 3 TO
20
v
f(i)
= f(i - 1) + f(i - 2)
v
PRINT
f(i),
v
NEXT i
v
PRINT
v
END
v
【学习任务10】有一堆游戏棒，第一个参加游戏的人取走了一半多一根，第二个游戏者再将剩下的取走一半多一根，以此类推，以后的游戏者均取走前一次剩下的一半多一根，到第10个人来取时，发现只剩下一根了。问：游戏开始前这堆游戏棒共有多少根?
v
【问题分析】
v
平时，我们比较习惯用顺推的方法来解决问题，但对本题类型的问题，不妨用反向思维来考虑。根据题意：
v
第10个人来取时
有1根，
v
推定第9个人来取时
有4根，
v
推定第8个人来取时
有10根，
即(4+1)*2
v
推定第7个人来取时
有22根，
即(10+1)*2
v
推定第6个人来取时
有46根，
即(22+1)*2
v
推定第5个人来取时
有94根，
即(46+1)*2
v
推定第4个人来取时
有190根，即(97+1)*2
v
推定第3个人来取时
有382根，即(190+1)*2
v
推定第2个人来取时
有766根，即(382+1)*2
v
推定第1个人来取时
有1534根，即(766+1)*2
v
根据以上的推导过程，可以设计出这样的算法：
v
（0）将1赋给S作为初值，S是迭代变量；
v
（1）通过循环完成逆推的过程，迭代公式(S+1)*2，其中S是在不断变化的；
v
（2）输出9遍循环后的S值。
【程序清单】
REM L10_13A
S = 1
FOR I = 9 TO 1 STEP -1
S = (S + 1) * 2
NEXT I
PRINT ＂S=＂；S
END
【运行结果】
S=1534
v
我们是否也可以采用顺推的方法来解决？我们还是先来分析一下：
v
设S为总游戏捧数，A为每次取走后的所剩游戏棒数。让S从0开始进行搜索，每次逐步递增1，直到找出经过9次取游戏棒后剩下的游戏捧数为1时结束。
v
每次取走游戏棒数为A／2+1
v
每次取走后的剩下的游戏棒数为A-(A／2+1)，于是得出递推公式为：
v
A=A-A／2-1
v
取9次后剩下的游戏棒数A=1就终止。这时的S应该是最初的总游戏棒数。
v
因此在上述的内循环外，还要有一个外循环来给S计数，当S计数的值满足按条件取9次后剩下A=l为止。
S的初值可以取0，终值到底取多少为好是个未知数，所以不能用计数循环，只能用条件循环，直到满足A=1终止。
v
特别要注意的：在这个条件循环中用S=S+1来为S计数，决不能再用S作为迭代变量。应该用 A来作迭代变量，每次在操作内循环之前，把S赋给A。由此可见，同一问题的顺推与逆推除了递推公式不同外，迭代变量也有所改变。
v
【程序清单】
v
REM
L10_13B
v
S = 0
v
DO
v
S =
S + 1: A = S
v
FOR
I = 1 TO 9
v
A
= A - A / 2 - 1
v
NEXT
I
v
LOOP UNTIL A = 1
v
PRINT
＂S=＂；S
v
END
v
上面分别介绍了两种递推方法：顺推和逆推。无论是哪一种递推方法，最关键的是要找到递推公式。只要找到了递推公式，程序就很容易实现。
v
【学习任务11】数列问题：有一数列
A(N)的前几项为0，1，2，6，16，44，120，328，…，已知后一项和前两项有某种关系，试编程求出前N项的和，并将这N个数及其和打印输出。
v
【问题分析】
v
问题的关键是找出数列A(N)的规律，然后将A(1)，A(2)…A(N)相加即可。
v
由题意知：A(N)与A(N—1)、A(N—2)之间存在关系
v
A(1)=0
v
A(2)=1
v
A(3)=2*(A(2)+A(1))=2*(1+0)=2
v
A(4)=2*(A(3)+A(2))=2*(2+1)=6
v
A(5)=2*(A(4)+A(3))=2*(6+2)=16
v
…
v
根据分析，很显然有A(N)=2*(A(N-1)+A(N-2))(N≥3)
v
【程序清单】
v
REM
L10-14
v
INPUT
＂输入要求数列的项数N=＂；N
v
DIM A(N)
v
A(1) = 0: A(2) =
1
v
S = A(1) +
A(2)
v
FOR I = 3 TO
N
v
A(I)
= 2 * A(I - 1) + 2 * A(I - 2)
v
S
= S + A(I)
v
NEXT I
v
PRINT
＂输出前＂；N；＂项，各项的值：＂
v
FOR I = 1 TO
N
v
PRINT
A(I),
v
NEXT I
v
PRINT
v
PRINT
＂前＂；N；＂项之和是I:＂；S
v
END
v
【运行结果】
v
输入要求数列的项数N=? 10
v
输出前10项，各项的值：
v
0
1
2
6
16
v
44
120
328
896
2448
前10项之和是3861
喜欢
0
赠金笔
前一篇：【学习任务6】找出一个自然数
后一篇：第四节 来来回回——递归法