递推算法思想

时间:2021-05-22 11:11:00

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

1.顺推法

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

2.逆推法

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


顺推实例:斐波那契数列

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

 解题思路:从表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;
}

递推算法思想

说明:【程序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;
}

递推算法思想