首页 > 代码库 > 第一篇 递推思想

第一篇 递推思想

<1> 顺推的例子

      上过大学的应该都知道著名的“斐波那契”数列吧,说的是繁殖兔子的问题,题目我就大概说一下。

如果1对兔子每月能生1对小兔子,而每对小兔在它出生后的第3个月就可以生1对小兔子,如果从1对初生的小兔子开始,1年后能

繁殖多少兔子?

思路:其实这个问题我们可以将兔子划分为“1月大的兔子“,”2月大的兔子“,”3月大的兔子“。

        ① 初始时:            一对1月大小兔子,总数为1对。

        ② 第一个月:         1月大的小兔子变成2月大的兔子,总数还是1对。

        ③ 第二个月:         2月大的小兔子变成3月大的兔子,繁殖了一对小兔子,总数为2对。

        ④ 第三个月:         3月大的兔子tmd有生了一对小兔子,上个月1月大的小兔子变成了2月大的兔子,总数为3对。

         ......                    ......

 1月份2月份3月份4月份5月份。。。6月份
1个月的兔子1 112                    3
2个月的兔子 1 11                    2
>=3个月的兔子  112                    3

        F0=1

        F1=1

        F2=F0+F1

        F3=F1+F2

        ......

        Fn=Fn-2+Fn-1

 

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

int month = 12;            int[] fab = new int[month];            fab[0] = 1;            fab[1] = 1;            //从已知条件出发推出结果            for (int i = 2; i < month; i++)            {                fab[i] = fab[i - 1] + fab[i - 2];            }            for (int i = 0; i < month; i++)            {                Console.WriteLine("第{0}个月兔子为:{1}", i, fab[i]);            }

 

 

<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(月));

        

 1   //银行取钱问题 2             double[] month = new double[49]; 3  4             ///最后一个月的连本带息是3000 5             month[48] = 3000; 6  7             double rate = 0.0171; 8  9             //逆推10             for (int i = 47; i > 0; i--)11             {12                 month[i] = (month[i + 1] + month[48]) / (1 + rate / 12);13             }14 15             for (int i = 48; i > 0; i--)16             {17                 Console.WriteLine("第{0}个月末本利合计:{1}", i, month[i]);18             }

第一篇 递推思想