算法洗脑系列——第一篇 递推思想

winston

像俺一样奋斗在一线的码农们，一谈到学编程，都是说要学会XX语言就OK了，其实我们理解的有一点点的偏差，因为我们只说到了
三分之一，其实真正的编程应该是：编程=数据结构+算法+XX语言。
对的，XX语言只是一个工具而已，就好比我们知道用笔来写字，但是不见得我们就能写出一手让张恨水为之倾倒的好字，其实我也说过
算法不仅仅用于程序设计中，在我们的生活中也处处存在着算法，比如记得我大二学C#的时候，无聊的我们就出了个猜美女芳龄的问题。 1  static void Main(string[] args)
2         {
3             Random random = new Random();
4
5             int mm = new Random().Next(16, 33);
6
7             int guess = 0;
8
9             int count = 0;
10
11             Console.WriteLine("现有一美女，请猜她的芳龄(16,32)\n");
12
13             do
14             {
15                 Console.Write("请输入你认为正确的年龄：\t");
16
17                 guess = int.Parse(Console.ReadLine());
18
19                 if (guess < mm)
20                     Console.WriteLine("低了!\n");
21
22                 if (guess > mm)
23                     Console.WriteLine("高了！\n");
24
25                 if (guess == mm)
26                     Console.WriteLine("恭喜，猜对了！\n");
27
28                 count = count + 1;
29
30             } while (mm != guess);
31
32             Console.WriteLine("你一共猜了：\t" + count + "次");
33
34             Console.ReadLine();
35         }

针对这个问题，大家如何 “又快又稳” 的猜出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

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


1             int month = 12;
2
3             int[] fab = new int[month];
4
5             fab[0] = 1;
6
7             fab[1] = 1;
8
9             //从已知条件出发推出结果
10             for (int i = 2; i < month; i++)
11             {
12                 fab = fab[i - 1] + fab[i - 2];
13             }
14
15             for (int i = 0; i < month; i++)
16             {
17                 Console.WriteLine("第{0}个月兔子为：{1}", i, fab);
18             }



<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 = (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);
18             }


本文链接