递推算法思想

我会带着你远行 2022-07-12 05:23 603阅读 0赞

递推算法可分为顺推法和逆推法。

1.顺推法

所谓顺推法，是指从已知条件出发，逐步推算出要解决问题的方法。例如：斐波拉契数列就可以顺推法不断递推算出新的数据

2.逆推法

所谓逆推法，就是从已知的结果出发，用迭代表达式逐步推算出问题开始的条件，即顺推法的逆过程。

**顺推实例：斐波那契数列**

**   ** 13世纪初，欧洲数学家斐波那契在他的著作《算盘书》中出了一个有趣的题目：如果**一**对兔子每个月能生**1对**小兔子，而每对小兔在它出生后的**第三个月里**，又能开始生出**1对**小兔子，假定在不发生死亡的情况下，**由一对初生的兔子开始，一年后能繁殖出多少对兔子**？![20170213180526289][]

解题思路：从表1-2的最后一列数据可以看出，斐波那契数列可使用递推算法来得到，由上两个月的兔子数量相加得到本月的兔子总数，具体算法如下：

**(1)设初始值为F0=1，第一个月兔子总数F1=1；**

**(2)第二个月兔子总数F2=F0+F1；**

**(3)第三个月兔子总数F3=F1+F2；**

**(4)第n个月兔子总数Fn=F(n-2)+F(n-1)；**

按照这个算法，编写的C语言程序如下：

【程序1-2】斐波那契数列源代码

\#include <stdio.h>  
\#define NUM 13  
int main()  
\{  
int i;  
long fib\[NUM\] = \{ 1,1 \};  
for (i = 2;i < NUM;i++)  
\{  
fib\[i\] = fib\[i - 2\] + fib\[i - 1\];  
\}  
for (i = 0;i < NUM;i++)  
\{  
printf("%d个月的兔子总数为：%d\\n", i, fib\[i\]);  
\}  
getch();  
return 0;  
\}

![20170213193415659][]

**说明：**【程序1-2】按题意只输出了13个月的兔子总数，若要输出斐波那契数列中的更多项，修改程序中第2行的NUM值即可

**逆推实例：该存多少钱**

** ** 父亲准备为小龙的4年大学生活一次性储存一笔钱，使用整存零取的方式，控制小龙每月的月底只能提取1000元准备下月使用。假设银行一年的整存零取的年利率为1.71%，请编程计算出父亲至少需要一次性存入多少钱才够小龙4年大学生活（4年的利息也应计算在内）。

**解题思路：**

分析存钱和取钱的过程，可以采用逆推的方式。因为是按月取钱，因此需要将4年分为48个月，每个月分别进行计算。

若在第48个月小龙大学毕业时连本带息要去1000元，则要先求出第47个月银行存款的具体数额：

第47月月末存款=1000/(1+0.0171/12)；

**提示：**前面给出的是年利率，为简化程序，按年利率除以12得到月利率。

**     第46月月末存款=（第47月月末存款+1000）/（1+**0.**0171）;**

**     以此类推，可以求出第45月，第44月.....月末存款的数值；**

**     第45月月末存款=（第46月月末存款+1000）/（1+0.0171）;**

**     第44月月末存款=（第45月月末存款+1000）/（1+0.0171）;**

**     .....**

**     第2月月末存款=（第3月月末存款+1000）/（1+0.0171）;**

**     第1月月末存款=（第2月月末存款+1000）/（1+0.0171）;**

**     通过以上过程就可以很容易地求出最初要存入多少钱。**

**下面用C语言程序来计算本例：**

**【**程序1-3**】**用逆推法求最初存钱数值

\#include <stdio.h>  
\#define FETCH 1000  
\#define RATE 0.0171  
  
  
int main()  
\{  
double corpus\[49\];  
int i;  
corpus\[48\] = (double)FETCH;  
for (i = 47;i > 0;i--)  
\{  
corpus\[i\] = (corpus\[i + 1\] + FETCH) / (1+RATE/12);  
\}  
for (i = 48;i > 0;i--)  
\{  
printf("第%d月末本利合计：%.2f\\n", i, corpus\[i\]);  
\}  
getch();  
return 0;  
\}

![20170214111200755][]

**    **

[20170213180526289]: /images/20220711/8576f06d392946a2b562368ac8a66e68.png
[20170213193415659]: /images/20220711/0c116370accd426589b58d1efd2b6fbd.png
[20170214111200755]: /images/20220711/f4b144acda5942178f3948a8217da7e9.png