一张纸对折103次,我们的宇宙就放不下它了吗?
相传,国际象棋起源于古印度,是由一位名叫西萨·班·达依尔的宰相发明的。
当时的舍罕王打算重赏国际象棋的发明者,于是宰相在国王面前提出请求:“陛下,请您在这张棋盘的第一个小格内赏我1粒麦子;第二个小格内给2粒,第三格内给4粒……照这样下去,每一格都比前一个小格加一倍。陛下啊,把这样摆满棋盘上所有格(共64格)的麦粒,都赏给您的仆人吧!”
国王慷慨地答应了宰相的要求,计数麦粒的工作很快就开始了。一袋又一袋的麦子被扛到棋盘前,但是麦粒数一格接一格增长得越来越迅速,国王很快就发现,即使拿出全印度的小麦,也无法兑现他对宰相许下的诺言!
那么这位宰相到底要求国王赏赐给他多少粒麦子呢?用中学数学所学的方法就可以算出,共需18,446,744,073,709,551,615个麦粒!
这个数字究竟有多大呢?
根据麦粒的重量,近似估算的结果大约为两千多亿吨,而即使是农业现代化技术高速发展的现在,全世界小麦的年产量也不过数亿吨而已!
虽然这个故事的真假已经无从考证,但是由它透露出的数学的神奇与宏大,无疑震撼了我们的心灵,这一令人惊叹的结果背后究竟隐藏着怎样的原理呢?
接下来,就让我们一起进入到今天要介绍的重点——“指数爆炸”。
1
2
在天文,测量,航海,计算机和其他实用数学的分支中,常用到指数函数和它的各种性质,尤其是计算机编程领域,我们在解决问题时,经常会用到指数函数及其相关函数。
这时就要格外注意了,因为一旦处理不好,该问题在解决过程中,我们需要计算的数字很可能会膨胀到难以计算的地步。
相反,如果“指数爆炸”这一数学现象能够得到合理的利用,也可以大大减少计算步骤,成为帮助我们解决问题的利器。
>>>>密码越长就越安全?
我们在注册新的账户或者进行密码修改时,密码设置那一栏的旁边经常会提示我们所设密码的安全程度。
随着密码长度和所含数字、字母、符号种类的增加,密码的安全系数也会越来越高,这背后蕴含的原理就可以利用我们前面提到的“指数爆炸”来解释。
我们现在所使用的密码,是使用俗称“密钥”的随机字节流来进行加密的。
在加密算法没有漏洞的情况下,要想破解密码就必须“一个一个”地进行尝试,即列出与密钥长度相同的字节流,与密码逐一进行比对,直到找到正确的密钥,这种密码破译法又被称为“暴力破解”。
那么密码的长度又是如何影响密码的安全性的呢?
我们假设密码全部由两种数字(1和0)来表示。如果密码的长度只有3位,那么正确的结果必定是下列8种情况之一:
000,001,010,100,011,101,110,111
最多尝试8次就能成功将其破解。
而密码每增加一位,其可能出现的排列组合的种类就会增加一倍,破解密码所需要尝试的次数也随之翻倍。
随着密码位数的增加,暴力破解最多需要尝试的次数如爆炸般增长,破解难度和成本飞速增大。
那么,这种利用“指数爆炸”增加密码安全性的方法效果究竟如何呢?
在这里,小编就给大家举一个比较直观的例子,如果我们要破解一串512位的密码,并且每一位只可能是0和1两个数字中的任一个,需要多久才能尝试遍每种可能呢?答案如下:
这个数字意味着:即便有一台现代超级计算机,并从宇宙诞生的那一刻起就开始解密,不停地尝试各种数字的组合一直到现在(公元2020年),它也无法列举完这串密钥所有可能的情况。
>>>>程序员必备算法:二分法查找
二分法查找是计算机科学里常用的算法,它能帮助人们在一组有序数组中迅速找出某一特定的元素,其基本过程可以总结为:
从数组的中间元素开始,如果中间元素恰好是所要查找的元素,则搜索过程结束。
如果要查找的元素大于或小于中间元素,则在数组大于或小于中间元素的那一半开始,而且同最初时一样,也从中间元素开始比较。
这种算法的好处是,每一次比较都能使搜索的范围缩小一半。这可以看作是“指数爆炸”的另一种应用。
例如,我们怎样才能快速地在下列9个从小到大排列的数中寻找出数字4呢?
1 ,3 ,4 ,6 ,7 ,8 ,10 ,13 ,14
可能有的小伙伴会说,从第一个数开始检查呗,如果第一个数不是4,就查看第二个数,还不是,就查第三个,以此类推总能找到4在哪里。
想想看,如果4在这列数的最后一位,这种方法岂不是要比较所有位置的数吗?这个计算量是很大的。
然而,如果用刚才介绍的二分法,每次都从中间开始找起,仅需3次比较就能找到4在哪里,大大提高了效率。
随着数组的扩大,这一方式的优势也逐渐显现出来,例如,只需要判断10次,就能在2047个数据中找到目标元素。
运算20次就能在2097151个数据中找出想要的结果;而比较30次时,所能搜寻的数据范围甚至变成了2147483647个!
数学作为人类思维表达形式的一种,反映了人们积极进取的意志,缜密周详的推理,以及对完美境界的追求,它与我们的生活息息相关,它的魅力也一直影响着我们。
这篇文章中为大家简要介绍的指数爆炸,不过是无数瑰丽景象的冰山一角,数学世界中还有更多美丽动人的风景等待我们去欣赏和发掘,如果你恰好也对它感兴趣的话,不如就一起来探索一下,看看数学还会给我们带来哪些出人意料又合乎逻辑的惊喜吧!
来源:数字北京科学中心