不知道大家小的時候是不是都聽過這樣一個故事:
相傳,國際象棋起源於古印度,是由一位名叫西薩·班·達依爾的宰相發明的。
![指數爆炸:一張紙對摺103次,我們的宇宙就放不下它了嗎?](http://p2.ttnews.xyz/loading.gif)
當時的舍罕王打算重賞國際象棋的發明者,於是宰相在國王面前提出請求:“陛下,請您在這張棋盤的第一個小格內賞我1粒麥子;第二個小格內給2粒,第三格內給4粒……照這樣下去,每一格都比前一個小格加一倍。陛下啊,把這樣擺滿棋盤上所有格(共64格)的麥粒,都賞給您的僕人吧!”
國王慷慨地答應了宰相的要求,計數麥粒的工作很快就開始了。一袋又一袋的麥子被扛到棋盤前,但是麥粒數一格接一格增長得越來越迅速,國王很快就發現,即使拿出全印度的小麥,也無法兌現他對宰相許下的諾言!
那麼這位宰相到底要求國王賞賜給他多少粒麥子呢?用中學數學所學的方法就可以算出,共需18,446,744,073,709,551,615個麥粒!
這個數字究竟有多大呢?
![指數爆炸:一張紙對摺103次,我們的宇宙就放不下它了嗎?](http://p2.ttnews.xyz/loading.gif)
根據麥粒的重量,近似估算的結果大約為兩千多億噸,而即使是農業現代化技術高速發展的現在,全世界小麥的年產量也不過數億噸而已!
雖然這個故事的真假已經無從考證,但是由它透露出的數學的神奇與宏大,無疑震撼了我們的心靈,這一令人驚歎的結果背後究竟隱藏著怎樣的原理呢?
接下來,就讓我們一起進入到今天要介紹的重點——“指數爆炸”。
宇宙中放不下的紙
為了更形象地體現這一現象的威力,人們還提出了許多“國王與麥粒”故事的“變體”。
例如,一張厚度為0.1mm的紙,通過不斷對摺使厚度成倍增加,對摺51次後,其厚度便可達到2.25億千米,約為火星與太陽的距離。
而當對摺次數達到103次時,其厚度已經超過了930億光年,這是目前可觀測宇宙的直徑,也就是說,可觀測宇宙內已經放不下這張紙了!
紙的厚度與對摺次數正好滿足指數增長的規律,其增長速度如爆炸般驚人,相信大家也已經從上面的兩個小故事中體會到“指數爆炸”的威力了。
當然,上文說的都只是純數學上的計算,在實際實驗操作並不可行。有人做過實驗,一張紙對摺7次以上就已經非常困難了。
現代指數的概念是數學家笛卡爾在1637年引入的,他為乘方數設計了專門的記號系統,即指數函數。
所謂“指數爆炸”也並不是真正的爆炸,而是指計算過程中,指數函數值的“爆炸性”增長。
無所不在的“指數爆炸”
在天文,測量,航海,計算機和其他實用數學的分支中,常用到指數函數和它的各種性質,尤其是計算機編程領域,我們在解決問題時,經常會用到指數函數及其相關函數。
這時就要格外注意了,因為一旦處理不好,該問題在解決過程中,我們需要計算的數字很可能會膨脹到難以計算的地步。
相反,如果“指數爆炸”這一數學現象能夠得到合理的利用,也可以大大減少計算步驟,成為幫助我們解決問題的利器。
>>>>密碼越長就越安全?
我們在註冊新的賬戶或者進行密碼修改時,密碼設置那一欄的旁邊經常會提示我們所設密碼的安全程度。
隨著密碼長度和所含數字、字母、符號種類的增加,密碼的安全係數也會越來越高,這背後蘊含的原理就可以利用我們前面提到的“指數爆炸”來解釋。
我們現在所使用的密碼,是使用俗稱“密鑰”的隨機字節流來進行加密的。
在加密算法沒有漏洞的情況下,要想破解密碼就必須“一個一個”地進行嘗試,即列出與密鑰長度相同的字節流,與密碼逐一進行比對,直到找到正確的密鑰,這種密碼破譯法又被稱為“暴力破解”。
那麼密碼的長度又是如何影響密碼的安全性的呢?
我們假設密碼全部由兩種數字(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個!
數學作為人類思維表達形式的一種,反映了人們積極進取的意志,縝密周詳的推理,以及對完美境界的追求,它與我們的生活息息相關,它的魅力也一直影響著我們。
這篇文章中為大家簡要介紹的指數爆炸,不過是無數瑰麗景象的冰山一角,數學世界中還有更多美麗動人的風景等待我們去欣賞和發掘,如果你恰好也對它感興趣的話,不如就一起來探索一下,看看數學還會給我們帶來哪些出人意料又合乎邏輯的驚喜吧!
閱讀更多 北京科學中心 的文章