前言

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

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

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

故事来咯

棋与麦子

故事内容

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

解题过程

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

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

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

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

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

转换一下单位

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

书中提到这种函数被称为爆炸增量函数。时间复杂度是O()。想想，随着n的值不断增加，这个算法会怎么样？比如购物网站的下单系统，使用人数不断增加，页面可能会出现白屏、无法完成支付等问题。

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

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

兔子数列

故事内容

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

解题过程

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

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

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

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

菲波那切数列如下：

递归表达式：

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

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

该算法的复杂性为：

未完待续

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

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

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

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

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