Java 递推思想

像俺一样奋斗在一线的码农们，一谈到学编程，都是说要学会XX语言就OK了，其实我们理解的有一点点的偏差，因为我们只说到了
三分之一，其实真正的编程应该是：编程=数据结构+算法+XX语言。
    对的，XX语言只是一个工具而已，就好比我们知道用笔来写字，但是不见得我们就能写出一手让张恨水为之倾倒的好字，其实我也说过
算法不仅仅用于程序设计中，在我们的生活中也处处存在着算法，比如记得我大二学C#的时候，无聊的我们就出了个猜美女芳龄的问题。

@Test  
public void testMeiMei() {  
    Random random = new Random();  
  
    Scanner scanner = new Scanner(System.in);  
    int mm = random.nextInt(17) + 16;  
  
    int guess = 0;  
  
    int count = 0;  
  
    System.out.println(mm + "现有一美女，请猜她的芳龄(16,32)\n");  
  
    do {  
        System.out.println("请输入你认为正确的年龄：\t");  
  
        try {  
            guess = scanner.nextInt();  
        } catch (Exception e) {  
            return;  
        }  
        if (guess < mm)  
            System.out.println("低了!\n");  
  
        if (guess > mm)  
            System.out.println("高了！\n");  
  
        if (guess == mm)  
            System.out.println("恭喜，猜对了！\n");  
  
        count = count + 1;  
  
    } while (mm != guess);  
  
    System.out.println("你一共猜了：\t" + count + "次");  
  
}  

针对这个问题，大家如何 “又快又稳” 的猜出mm的芳龄呢？如果是一个不懂算法的人，估计就是一个for循环进行查找，但是这个的复杂度是O(n)。
那么懂算法的人就会利用年龄有序这个特点进行"二分查找“，这个复杂度就是log2N，所以说学算法，懂算法可以给我们实际应用中带来更好的解决方案。

好了，不扯了，今天主要讲的是“递推思想”。
一： 概念
     通过已知条件，利用特定关系逐步递推，最终得到结果为止，核心就是不断的利用现有信息推导出新的东西。

二：分类
     当然递推中有两种，“顺推”和“逆推“
     顺推：从条件推出结果。
     逆推：从结果推出条件。
呵呵，是不是觉的有一种policeman破案的感觉。

三： 举例
<1> 顺推的例子
      上过大学的应该都知道著名的“斐波那契”数列吧，说的是繁殖兔子的问题，题目我就大概说一下。
如果1对兔子每月能生1对小兔子，而每对小兔在它出生后的第3个月就可以生1对小兔子，如果从1对初生的小兔子开始，1年后能
繁殖多少兔子？
思路：其实这个问题我们可以将兔子划分为“1月大的兔子“，”2月大的兔子“，”3月大的兔子“。
        ① 初始时：            一对1月大小兔子，总数为1对。
        ② 第一个月：         1月大的小兔子变成2月大的兔子，总数还是1对。
        ③ 第二个月：         2月大的小兔子变成3月大的兔子，繁殖了一对小兔子，总数为2对。
        ④ 第三个月：         3月大的兔子tmd有生了一对小兔子，上个月1月大的小兔子变成了2月大的兔子，总数为3对。
         ......                    ......
        F0=1
        F1=1
        F2=F0+F1
        F3=F1+F2
        ......
        Fn=Fn-2+Fn-1

大家看看，是不是体现了”递推“的核心思想，代码也很简单。

@Test  
public void feibonaqie() {  
    int month = 12;  
    int[] f = new int[month];  
    f[0] = 1;  
    f[1] = 1;  
  
    for (int i = 2; i < month; i++) {  
        f[i] = f[i - 2] + f[i - 1];  
    }  
  
    for (int i = 0; i < month; i++) {  
        System.out.println("第 " + i + " 个月，兔子总数：" + f[i]);  
    }  
}  

测试结果：
第 0 个月，兔子总数：1 
第 1 个月，兔子总数：1 
第 2 个月，兔子总数：2 
第 3 个月，兔子总数：3 
第 4 个月，兔子总数：5 
第 5 个月，兔子总数：8 
第 6 个月，兔子总数：13 
第 7 个月，兔子总数：21 
第 8 个月，兔子总数：34 
第 9 个月，兔子总数：55 
第 10 个月，兔子总数：89 
第 11 个月，兔子总数：144

<2> 逆推的例子
       这个一个关于存钱的问题，一个富二代给他儿子的四年大学生活存一笔钱，富三代每月只能取3k作为下个月的生活费，采用的是整存零取的方式，
   年利率在1.71%，请问富二代需要一次性存入多少钱。

思路: 这个题目是我们知道了结果，需要逆推条件， 第48月富三代要连本带息的把3k一把取走，那么
        第47月存款应为： (第48个月的存款+3000)/(1+0.0171/12(月))；
        第46月存款应为： (第47个月的存款+3000)/(1+0.0171/12(月));
         .....                    .....
        第1个月存款应为: (第2个月的存款+3000)/(1+0.0171/12(月));

@Test  
public void deposit() {  
    int month = 49;  
    double[] f = new double[month];  
    f[48] = 3000d;  
    double monthRate = 1.71 / 100 / 12;  
  
    for (int i = 47; i > 0; i--) {  
        f[i] = (f[i + 1] + 3000) / (1 + monthRate);  
    }  
    for (int i = 48; i > 0; i--) {  
        System.out.println("第 " + i + " 个月，本息总额：" + f[i]);  
    }  
}  

第 48 个月，本息总额：3000.0 
第 47 个月，本息总额：5991.462166412862 
第 46 个月，本息总额：8978.667565132548 
第 45 个月，本息总额：11961.622253421421 
第 44 个月，本息总额：14940.332279922532 
第 43 个月，本息总额：17914.803684671875 
第 42 个月，本息总额：20885.04249911064 
第 41 个月，本息总额：23851.054746097452 
第 40 个月，本息总额：26812.846439920566 
第 39 个月，本息总额：29770.423586310073 
第 38 个月，本息总额：32723.792182450085 
第 37 个月，本息总额：35672.95821699087 
第 36 个月，本息总额：38617.92767006103 
第 35 个月，本息总额：41558.706513279605 
第 34 个月，本息总额：44495.300709768184 
第 33 个月，本息总额：47427.716214163 
第 32 个月，本息总额：50355.958972627006 
第 31 个月，本息总额：53280.03492286193 
第 30 个月，本息总额：56199.94999412031 
第 29 个月，本息总额：59115.71010721753 
第 28 个月，本息总额：62027.3211745438 
第 27 个月，本息总额：64934.789100076196 
第 26 个月，本息总额：67838.11977939056 
第 25 个月，本息总额：70737.31909967352 
第 24 个月，本息总额：73632.3929397344 
第 23 个月，本息总额：76523.34717001712 
第 22 个月，本息总额：79410.18765261215 
第 21 个月，本息总额：82292.92024126834 
第 20 个月，本息总额：85171.55078140483 
第 19 个月，本息总额：88046.0851101229 
第 18 个月，本息总额：90916.5290562178 
第 17 个月，本息总额：93782.88844019052 
第 16 个月，本息总额：96645.1690742597 
第 15 个月，本息总额：99503.37676237331 
第 14 个月，本息总额：102357.5173002205 
第 13 个月，本息总额：105207.59647524328 
第 12 个月，本息总额：108053.6200666483 
第 11 个月，本息总额：110895.59384541858 
第 10 个月，本息总额：113733.52357432517 
第 9 个月，本息总额：116567.41500793885 
第 8 个月，本息总额：119397.27389264184 
第 7 个月，本息总额：122223.10596663937 
第 6 个月，本息总额：125044.91695997141 
第 5 个月，本息总额：127862.71259452422 
第 4 个月，本息总额：130676.49858404195 
第 3 个月，本息总额：133486.2806341383 
第 2 个月，本息总额：136292.064442308 
第 1 个月，本息总额：139093.85569793844 

参考：http://blog.csdn.net/m13666368773/article/details/7531453