编程基本算法之“递推算法”

feature

今天来介绍程序中一种基本的算法,递推算法。

递推算法的原理是使用“步步为营”的方法,不断利用已有的信息推导出新的东西的一种算法。

此文章作者为周毅刚,归属于其个人网站miketech.it,未经允许,不得转载。

递推算法有两种分别是顺推法逆推法

顺推法是指从已知条件出发,逐步退散出要解决问题的方法。最广为人知的一个例子就是斐波纳契数列的实现。

斐波那契数列指的是这样一个数列 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233,377……
特别指出:第0项是0,第1项是第一个1。
这个数列从第2项开始,每一项都等于前两项之和。
逆推法是从已知的结果出发,用迭代表达式逐步推算出问题开始的条件,是顺推法的逆过程
现在来看个顺推实例,这个实例和斐波纳契原理一样。大兔子每个月会生一个小兔子(但是1月大的和二月大的不行)。
程序将会从初始状态的兔子数量推算出来12个月后兔子的数量。
rabbits
public class rabbit {

    public static void main(String[] args){

        //最大月份
        int maxMonth=12;

        //储存每个月兔子数量
        int[] fib=new int[maxMonth+1];

        //设置前两个月兔子数量
        fib[0]=1;
        fib[1]=1;

        //开始计算
        for (int i=2;i<=maxMonth;i++){
            fib[i]=fib[i-1]+fib[i-2];
        }

        //遍历数组
        for (int i=1;i<=maxMonth;i++){
            System.out.println("第"+i+"个月兔子数量为:"+fib[i]);
        }

    }
}

输出结果:
第1个月兔子数量为:1
第2个月兔子数量为:2
第3个月兔子数量为:3
第4个月兔子数量为:5
第5个月兔子数量为:8
第6个月兔子数量为:13
第7个月兔子数量为:21
第8个月兔子数量为:34
第9个月兔子数量为:55
第10个月兔子数量为:89
第11个月兔子数量为:144
第12个月兔子数量为:233

现在来看个逆推实例,知道第48个月,推算出第一个月要存多少钱;

savemoney

 

来看代码:

/**
 * miektech.it
 * Created by Mike on 9/1/2015.
 */
public class savemoney {

    public static void main(String[] args){

        //每个月取出金额
        double fetch=1000.0;
        //利率
        double rate=0.0171;

        //创建数组存储每个月的钱数
        double[] money=new double[49];

        //第48个月总共是100元
        money[48]=1000;

        //开始逆推
        for (int i=47;i>0;i--){
            money[i]=(money[i+1]+fetch)/(1+rate/12);
        }

        //遍历数组
        for (int i=48;i>0;i--){
            System.out.println("第"+i+"个月本利合计:"+money[i]);
        }

    }
}

输出结果:
第48个月本利合计:1000.0
第47个月本利合计:1997.1540554709538
第46个月本利合计:2992.8891883775154
第45个月本利合计:3987.2074178071402
第44个月本利合计:4980.110759974176
第43个月本利合计:5971.601228223957
第42个月本利合计:6961.680833036879
第41个月本利合计:7950.351582032483
第40个月本利合计:8937.615479973521
第39个月本利合计:9923.474528770024
第38个月本利合计:10907.93072748336
第37个月本利合计:11890.98607233029
第36个月本利合计:12872.642556687011
第35个月本利合计:13852.902171093203
第34个月本利合计:14831.766903256063
第33个月本利合计:15809.238738054335
第32个月本利合计:16785.31965754234
第31个月本利合计:17760.01164095398
第30个月本利合计:18733.316664706774
第29个月本利合计:19705.236702405844
第28个月本利合计:20675.773724847935
第27个月本利合计:21644.929700025397
第26个月本利合计:22612.706593130188
第25个月本利合计:23579.106366557844
第24个月本利合计:24544.13097991147
第23个月本利合计:25507.782390005712
第22个月本利合计:26470.06255087072
第21个月本利合计:27430.973413756117
第20个月本利合计:28390.51692713495
第19个月本利合计:29348.695036707642
第18个月本利合计:30305.509685405937
第17个月本利合计:31260.962813396847
第16个月本利合计:32215.056358086575
第15个月本利合计:33167.79225412444
第14个月本利合计:34119.172433406835
第13个月本利合计:35069.1988250811
第12个月本利合计:36017.87335554944
第11个月本利合计:36965.197948472865
第10个月本利合计:37911.17452477506
第9个月本利合计:38855.80500264629
第8个月本利合计:39799.09129754728
第7个月本利合计:40741.03532221313
第6个月本利合计:41681.63898665714
第5个月本利合计:42620.90419817474
第4个月本利合计:43558.83286134732
第3个月本利合计:44495.426878046106
第2个月本利合计:45430.68814743601
第1个月本利合计:46364.618565979494

打赏

Leave a Reply

Your email address will not be published. Required fields are marked *