學(xué)過(guò)計(jì)算機(jī)的基本都對(duì)漢諾塔問(wèn)題很熟悉了，即使沒(méi)有學(xué)過(guò)計(jì)算機(jī)的的，想必也或多或少的了解漢諾塔問(wèn)題，這篇文章通過(guò)數(shù)學(xué)的方式來(lái)求解這個(gè)問(wèn)題。

漢諾塔

傳說(shuō): 在世界中心貝拿勒斯（在印度北部）的圣廟里，一塊黃銅板上插著三根寶石針。印度教的主神梵天在創(chuàng)造世界的時(shí)候，在其中一根針上從下到上地穿好了由大到小的64片金片，這就是所謂的漢諾塔。不論白天黑夜，總有一個(gè)僧侶在按照下面的法則移動(dòng)這些金片：一次只移動(dòng)一片，不管在哪根針上，小片必須在大片上面。僧侶們預(yù)言，當(dāng)所有的金片都從梵天穿好的那根針上移到另外一根針上時(shí)，世界就將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

遞歸

這是一個(gè)非常經(jīng)典的遞歸問(wèn)題。 思路很簡(jiǎn)單： 假設(shè)有n個(gè)金片，需要把這些金片從第一根寶石針移動(dòng)到第三個(gè)寶石針中。

1.首先需要把n-1個(gè)金片移動(dòng)到第二根寶石針上2.再把最后一個(gè)也就是最大的那一個(gè)移動(dòng)到第三根寶石針上3.最后再把那n-1個(gè)金片移動(dòng)到第3根寶石針上

這是典型的遞歸問(wèn)題, 定義f(n)是需要移動(dòng)的次數(shù)

f(1) = 1 f(2) = 3 f(3) = 7 ... f(n) = 2f(n-1)+1

數(shù)學(xué)歸納法

高中的時(shí)候接觸了數(shù)學(xué)歸納法，如果忘記了也每關(guān)系，這里給出完整的"套路"。

根據(jù)以上內(nèi)容，可知： f(0)=0 f(1) = 1 f(2) = 3 f(3) = 7 f(4) = 15 f(5) = 31 ... 好像有點(diǎn)規(guī)律， f(n) = 2^n -1

那么這個(gè)猜想正確嗎?用數(shù)學(xué)歸納法證明一下。

定義

數(shù)學(xué)歸納法是證明某個(gè)命題關(guān)于整數(shù)n(對(duì)所有的n>=n0)成立的一種一般的方法。首先，當(dāng)n為最小值n0時(shí)我們證明命題，這稱(chēng)為基礎(chǔ)，然后假設(shè)對(duì)于包含再n0和n-1之間的所有值，已經(jīng)證明命題成立，對(duì)于n>n0證明命題，這種方法稱(chēng)為數(shù)學(xué)歸納法。

證明

f(0) = 2^0 -1, 顯然基礎(chǔ)是正確的 假設(shè)n-1取代n的時(shí)候上述猜想成立，且對(duì)于n>0建立歸納， f(n) = 2f(n-1) + 1 = 2(2^(n-1)-1)+1 = 2^n-2+1 = 2^n -1 因此，對(duì)于n來(lái)說(shuō)，上面的猜想依然成立，至此證明完畢，鼓掌。

到底需要多久

對(duì)于漢諾塔問(wèn)題，f(n) = 2^64-1 這是一個(gè)什么概念, 即使是每微秒移動(dòng)一次， 也需要5000世紀(jì)的時(shí)間， 到那個(gè)時(shí)候，世界也許真的將在一聲霹靂中消滅，而梵塔、廟宇和眾生也都將同歸于盡。

類(lèi)似問(wèn)題

傳說(shuō): 罕王打算獎(jiǎng)賞國(guó)際象棋的發(fā)明人──宰相西薩·班·達(dá)依爾。國(guó)王問(wèn)他想要什么，他對(duì)國(guó)王說(shuō)：“陛下，請(qǐng)您在這張棋盤(pán)的第1個(gè)小格里賞給我一粒麥子，在第2個(gè)小格里給2粒，第3個(gè)小格給4粒，以后每一小格都比前一小格加一倍。請(qǐng)您把這樣擺滿棋盤(pán)上所有64格的麥粒，都賞給您的仆人吧！”國(guó)王覺(jué)得這個(gè)要求太容易滿足了，就命令給他這些麥粒。當(dāng)人們把一袋一袋的麥子搬來(lái)開(kāi)始計(jì)數(shù)時(shí)，國(guó)王才發(fā)現(xiàn)：就是把全印度甚至全世界的麥粒全拿來(lái)，也滿足不了那位宰相的要求。

還有直線分割圓形，約瑟夫環(huán)問(wèn)題等等。

寫(xiě)在最后

書(shū)到用時(shí)方恨少。

公眾號(hào)

更多內(nèi)容，歡迎關(guān)注我的微信公眾號(hào):無(wú)情劍客。