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

September 1, 2015
JavaAlgorithm

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

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

此文章作者为周毅刚,归属于其个人网站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

  1. public class rabbit {
  2. public static void main(String[] args){
  3. //最大月份
  4. int maxMonth=12;
  5. //储存每个月兔子数量
  6. int[] fib=new int[maxMonth+1];
  7. //设置前两个月兔子数量
  8. fib[0]=1;
  9. fib[1]=1;
  10. //开始计算
  11. for (int i=2;i<=maxMonth;i++){
  12. fib[i]=fib[i-1]+fib[i-2];
  13. }
  14. //遍历数组
  15. for (int i=1;i<=maxMonth;i++){
  16. System.out.println("第"+i+"个月兔子数量为:"+fib[i]);
  17. }
  18. }
  19. }

输出结果:
第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

来看代码:

  1. /**
  2. * miektech.it
  3. * Created by Mike on 9/1/2015.
  4. */
  5. public class savemoney {
  6. public static void main(String[] args){
  7. //每个月取出金额
  8. double fetch=1000.0;
  9. //利率
  10. double rate=0.0171;
  11. //创建数组存储每个月的钱数
  12. double[] money=new double[49];
  13. //第48个月总共是100元
  14. money[48]=1000;
  15. //开始逆推
  16. for (int i=47;i>0;i--){
  17. money[i]=(money[i+1]+fetch)/(1+rate/12);
  18. }
  19. //遍历数组
  20. for (int i=48;i>0;i--){
  21. System.out.println("第"+i+"个月本利合计:"+money[i]);
  22. }
  23. }
  24. }

输出结果:
第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

Comments

July 21, 2018 at 10:52 am

There are no comments

keyboard_arrow_up