算法学习 | 从几个有趣的故事说起，聊聊里面的算法

前言

提到故事我就来劲头了。一方面，我喜欢读故事、讲故事、搜集故事，另一方面，用讲故事的方式会为学习增加一些趣味性，有兴趣可以帮助坚持下去。

下面要介绍的故事，有些大家应该不陌生。我之前有读到过，但是没有认真的研究过，有种熟悉的陌生感。

今天分享读了的故事、研究了的解题过程、顺便总结的一些算法知识点和经验。

故事来咯

棋与麦子

故事内容

传说西塔发明了国际象棋而使国王十分高兴，他决定要重赏西塔，西塔说：“我不要您的重赏 ，陛下，只要您在我的棋盘上赏一些麦子就行了。在棋盘的第1个格子里放1粒，在第2个格子里放2粒，在第3个格子里放4粒，在第4个格子里放8粒，依此类推，以后每一个格子里放的麦粒数都是前一个格子里放的麦粒数的2倍，直到放满第64个格子就行了”。国王觉得几粒麦子，这要求很简单，满口答应着，令人如数付给西塔。

摆放麦子的工作开始了，没多久一袋麦子就空了。一袋又一袋的麦子被扛到国王面前来。但是，麦粒数一格接一格飞快增长着，国王很快就看出来，即便拿出全国的粮食，也兑现不了他对西塔的诺言。

所以64个格子到底能放多少粒麦子呢？

解题过程

假设总和是S，那么计算表达式是这样的：

①

将等式①等式左右两侧同时乘以2，等式依旧成立：

②

好，现在将两个等会进行相减，会得到下面的等式：

我用计算机算了一下S最终的值是18446744073709551615。

这么多粒麦子多重呢？百度中查到的小麦为0.023-0.058克左右，取个平均数吧，0.041克。

18446744073709551615✖️0.041 = 75631650702209152（克）

转换一下单位

≈ 7563 (亿吨)

这个数据相当可观，对比感受一下它大到什么程度。

据国家公布的数据，我们已经连续5年时间小麦年产量达到1.3亿吨。

书中提到这种函数被称为爆炸增量函数。时间复杂度是O(

)。想想，随着n的值不断增加，这个算法会怎么样？比如购物网站的下单系统，使用人数不断增加，页面可能会出现白屏、无法完成支付等问题。

O(

)也就是指数时间复杂度的运行效率极差，这样是算法要谨慎使用。

在设计算法的时候，一定要注意算法复杂度增量的问题，尽可能避免使用爆炸增量函数。

兔子数列

故事内容

一般而言，兔子在出生两个月后，就有繁殖能力，一对兔子每个月能生出一对小兔子来。如果所有兔子都不死：

第一个月小兔子没有繁殖能力，所以还是一对；

两个月后，生下一对小兔对数共有两对；

三个月以后，老兔子又生下一对，因为小兔子还没有繁殖能力，所以一共是三对；

......

那么12个月之后会有多少兔子呢？

解题过程

首先，先研究一下兔子出生和成熟规律，这个规律借助表格更加直观：

从第二个月开始，就有规律了，每过一个月，初生兔子变成熟，成熟兔子生出一对兔子，就有这样的等式：

• 初生对数=前一月的成兔对数
• 成兔对数=前一月的成兔对数+前一月的初生对数
• 总体对数=本月的成兔对数+本月的初生对数

这么有趣的规律，数学家就开始整活了，数学家莱昂纳多·斐波那契以兔子繁殖为例子引入了菲波那切数列，又称为“兔子数列”。

菲波那切数列如下：

1、1、2、3、5、8、13、21、34、55、89……

递归表达式：

重点来了，这个算法如何设计？

function fibFunc(n) {
  if (n < 1) {
    return 1;
  }
  if (n === 1 || n === 2) {
    return 1;
  }
  let f1 = 1;
  let f2 = 1;
  for (let i = 3; i <= n; i++) {
    f2 = f2 + f1; // 辗转相加法
    f1 = f2 - f1; // 记录前一项
  }
  return f2;
}
console.log(fibFunc(1)); // 1
console.log(fibFunc(2)); // 1
console.log(fibFunc(3)); // 2
console.log(fibFunc(11)); // 89

该算法的复杂性为：

空间复杂度：O(n)

时间复杂度：O(1)

未完待续

果然故事有趣，学起来也轻松不少。

还有一个更有趣的故事，叫做自然界里关于斐波那契的巧合。精炼一下这个故事就是

树木抽长新枝条的规律、一些花的花瓣数量，都符合斐波那契数列。而这种自然现象，是因为这些植物按照自然的规律才进化成这样。似乎是植物排列种子的“优化方式”，便于更好的生存和生长。

我有种不但逐渐熟悉了算法，还学习了自然相关的新知识的双重收获的快乐感觉。

老实说，除了故事本身，逐渐找到规律、研究规律，并找到对应的算法，真是一件非常愉快的事。

对算法的学习，逐渐上头。