前言
提到故事我就来劲头了。一方面,我喜欢读故事、讲故事、搜集故事,另一方面,用讲故事的方式会为学习增加一些趣味性,有兴趣可以帮助坚持下去。
下面要介绍的故事,有些大家应该不陌生。我之前有读到过,但是没有认真的研究过,有种熟悉的陌生感。
今天分享读了的故事、研究了的解题过程、顺便总结的一些算法知识点和经验。
故事来咯
棋与麦子
故事内容
传说西塔发明了国际象棋而使国王十分高兴,他决定要重赏西塔,西塔说:“我不要您的重赏 ,陛下,只要您在我的棋盘上赏一些麦子就行了。在棋盘的第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(
O(
在设计算法的时候,一定要注意算法复杂度增量的问题,尽可能避免使用爆炸增量函数。
兔子数列
故事内容
一般而言,兔子在出生两个月后,就有繁殖能力,一对兔子每个月能生出一对小兔子来。如果所有兔子都不死:
第一个月小兔子没有繁殖能力,所以还是一对;
两个月后,生下一对小兔对数共有两对;
三个月以后,老兔子又生下一对,因为小兔子还没有繁殖能力,所以一共是三对;
......
那么12个月之后会有多少兔子呢?
解题过程
首先,先研究一下兔子出生和成熟规律,这个规律借助表格更加直观:
月数 | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 9 | 10 | 11 | … |
成兔对数 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | |
初生对数 | 1 | 0 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | |
总对数 | 1 | 1 | 2 | 3 | 5 | 8 | 13 | 21 | 34 | 55 | 89 | 144 |
从第二个月开始,就有规律了,每过一个月,初生兔子变成熟,成熟兔子生出一对兔子,就有这样的等式:
- 初生对数=前一月的成兔对数
- 成兔对数=前一月的成兔对数+前一月的初生对数
- 总体对数=本月的成兔对数+本月的初生对数
这么有趣的规律,数学家就开始整活了,数学家莱昂纳多·斐波那契以兔子繁殖为例子引入了菲波那切数列,又称为“兔子数列”。
菲波那切数列如下:
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)
未完待续
果然故事有趣,学起来也轻松不少。
还有一个更有趣的故事,叫做自然界里关于斐波那契的巧合。精炼一下这个故事就是
树木抽长新枝条的规律、一些花的花瓣数量,都符合斐波那契数列。而这种自然现象,是因为这些植物按照自然的规律才进化成这样。似乎是植物排列种子的“优化方式”,便于更好的生存和生长。
我有种不但逐渐熟悉了算法,还学习了自然相关的新知识的双重收获的快乐感觉。
老实说,除了故事本身,逐渐找到规律、研究规律,并找到对应的算法,真是一件非常愉快的事。
对算法的学习,逐渐上头。
标签:麦子,格子,故事,兔子,算法,聊聊,对数,有趣 From: https://blog.51cto.com/u_15838863/6355015