2021-11-14 11:57  阅读(40)
文章分类:算法思想 文章标签:算法思想数据结构算法
©  原文作者:GoFuncChan 原文地址:https://www.jianshu.com/c/18862bffadd8

递推法

递推算法犹如稳重的有经验的老将,使用“稳扎稳打”的策略,不断利用已有的信息推导出新的东西。
在日常应用中有如下两种递推算法:
(1)顺推法:从已知条件出发,逐步推算出要解决问题的方法。
(2)逆推法:从已知的结果出发,用迭代表达式逐步推算出问题开始的条件,即顺推法的逆过程。

顺推法

例如斐波那契数列就可以通过顺推法不断递推算出新的数据:

兔子问题:有一对兔子,从出生后第3个月起每个月生一对兔子,小兔子长到第三个月后每个月又生一对兔子,假如兔子不死,问第二十个月的兔子对数是多少?

算法分析:

分析:我们要想办法找规律
兔子对数:
第一个月:1;第二个月:1;第三个月: 2;第四个月: 3;第五个月: 5;第六个月: 8;...
由此可见兔子的对象数据是:1,1,2,3,5,8...

规则:
A:从第三项开始,每一项是前两项之程
B:而且说明前两项是已知的

假如相邻的两个月的兔子对数是a,b
第一个相邻的数据:a=1,b=1
第二个相邻的数据:a=1,b=2
第三个相邻的数据:a=2,b=3
第四个相邻的数据:a=3,b=5
看到了:下一次的a是以前的b,下一次的b是以前的a+b;

GO语言描述:
    // 获取斐波那契数列
    func getFibonacciArray(n int) []int {
        fArr := make([]int, n, n) // 数列第一位从下标1开始
        fArr[0] = 1
        fArr[1] = 1
        for i := 2; i < n; i++ {
            fArr[i] = fArr[i-1] + fArr[i-2]
        }
        return fArr
    }
    
    
逆推法

银行存款问题:用户A为用户B在银行整存了4年的生活费,B每个月的月初取1000元作为这个月的生活费。而银行的年利率是1.7%,求用户A最少需要存多少钱?

算法分析

可采用逆推法分析存钱和取钱的过程,因为按照月为周期取钱,所以4年可以分为48个月,并对每个月进行计算。
如果第48个月后sun大学毕业连本带息要取1000元,则要求第47个月银行的存钱金额为:
第47个月月末存款=1000/(1+0.0172/12);
第46个月月末存款=(第47存款+1000)/(1+0.0172/12);
第45月末存款=(第46存款+1000)/(1+0.0172/12);
…….
第2月月末存款=(第3月月末存款+1000)/(1+0.0172/12);
第1月月末存款=(第2月末存款+1000)/(1+0.0172/12);

GO语言描述
    // 逆推法解决银行存款问题
    func F() {
        fArr := make([]float64, 48, 48)
        fArr[47] = 1000
        for i := 46; i >= 0; i-- {
            fArr[i] = (fArr[i+1] + 1000) / (1 + 0.017/12)
            fmt.Printf("逆推第%d月存款余额为%.2f元\n",i+1,fArr[i])
        }
    }
    

打印结果:

    逆推第47月存款余额为1997.17元
    逆推第46月存款余额为2992.93元
    逆推第45月存款余额为3987.28元
    ...
    逆推第4月存款余额为43567.08元
    逆推第3月存款余额为44504.03元
    逆推第2月存款余额为45439.66元
    逆推第1月存款余额为46373.96元
    
版权归原创作者所有,任何形式转载请联系作者; Java 技术驿站 >> 常见算法思想2:递推法
上一篇
常见算法思想1:枚举法
下一篇
常见算法思想3:递归法