【導(dǎo)讀】sthebestwecando？mthetask?eareTLdisks.dT2=3.disks!rgetower?1smallestt. oadifferentpeg(requiringTn-1moves),thenmovethelargest(requiringonemove),and. Tn≤2Tn—1+1，forn>0.

　　

【正文】 (即使它們有時(shí)候是無(wú)意義的 )。 但現(xiàn)在，我們需要改變這種觀點(diǎn)，并盡量往更大規(guī)模的問(wèn)題考慮 。怎樣去轉(zhuǎn)移大型塔？在三個(gè)磁盤的移動(dòng)問(wèn)題上，成功的做法是先將最上面的兩個(gè)盤移動(dòng)到中間桿上，然后移動(dòng)第三個(gè)盤，接著把其他兩個(gè)移到第三個(gè)盤上面。這給了我們一個(gè)關(guān)于如何移動(dòng) n 個(gè)磁盤的思路：首先將第 n?1 個(gè)盤按最小步數(shù)移動(dòng)到一個(gè)不同的柱上（需要 Tn1 步數(shù)），然后移動(dòng)最大的那個(gè)盤（需要一步），并最后將第 n?1 個(gè)盤轉(zhuǎn)移到最大盤上面（需要另外的 Tn1步）。因此，我們最多可以使用 2Tn1+1 步來(lái)移動(dòng) n 個(gè)磁盤（ n0）： Tn ≤ 2 Tn1+1， (n＞ 0)． 此公式使用 39。≤ 39。而不是 39。=39。，因?yàn)樯鲜龇治鰞H能證明 2Tn1+1 步移動(dòng)是充分的 。并沒(méi)有說(shuō)明 2Tn1+1 步移動(dòng)是必要的。聰明人可能會(huì)想到的這樣的一個(gè)捷徑 。 但有沒(méi)有一個(gè)更好的辦法呢？當(dāng)然沒(méi)有。在某些時(shí)候，我們必須移動(dòng)最大的磁盤。當(dāng)我們移動(dòng)最大磁盤時(shí)，其他 n?1 個(gè)較小的盤必須在一根桿上，并 且至少需要 Tn1個(gè)步數(shù)來(lái)把它們移動(dòng)到那里。如果我們不是太留心的話，有時(shí)候最大的磁盤可能會(huì)被移動(dòng)不止一次。但在最后一次移動(dòng)最大的磁盤后，我們必須要移動(dòng) n1 個(gè)較小磁盤（必須在一根柱上）到最大磁盤上面，這也需要 Tn1步數(shù)。因此 , Tn ≥ 2 Tn1+1， (n＞ 0)． 這兩個(gè)不等式，與退化解 n = 0 一起，可得到 T0 = 0 Tn = 2 Tn1+1， (n＞ 0)． （ ） （請(qǐng)注意，這個(gè)公式是與已知值 T1=1 和 T2=3 一致的。我們對(duì)于小規(guī)模的樣本的研究，不僅有助于我們推導(dǎo)出通用的公式，它也把檢驗(yàn)是否推導(dǎo)有誤變得更加簡(jiǎn)單。這種檢查是很有價(jià)值的，在后面的章節(jié)中做更復(fù)雜的演算時(shí)就會(huì)體現(xiàn)出來(lái)。） 像等式（ ）那樣一組等式被稱為遞歸（又名遞推關(guān)系或遞歸關(guān)系）。它給出了一個(gè)邊界值和根據(jù)叫造紙表達(dá)一般只的一個(gè)方程。我們把一般方程單獨(dú)作為一個(gè)遞歸，但是在技術(shù)上，它需要一個(gè)邊界值來(lái)解決。 遞推關(guān)系，讓我們可以計(jì)算我們?nèi)魏?n 的 Tn 值。但當(dāng) n 很大時(shí)，沒(méi)有人真的喜歡使用遞推 。當(dāng) n 很大時(shí)需要的計(jì)算時(shí)間太長(zhǎng)。遞推只能提供間接的局部的信息。遞推的解使我們很開心。也就是說(shuō)，我們想要一個(gè)良好的，簡(jiǎn)潔的“封閉形式”，讓我們能夠快速計(jì)算即使是大的 n。依據(jù)一個(gè)封閉的形式，我們可以了解到真正的 Tn。 武漢科技大學(xué)本科畢業(yè)論文外文翻譯 4 那么，我們?nèi)绾谓鉀Q遞推呢？一種方法是猜測(cè)正確的解，然后，證明我們的猜測(cè)是正確的。而且我們最希望的猜測(cè)解是看小規(guī)模情況下的情況。因此，我們依次計(jì)算T3=23+1=7； T4=27+1=15； T5=215+1=31； T6=231+1=63。 確實(shí)滿足， Tn =2n?1， (n≥0). （ ） 至少對(duì)于 n≤ 6 成立。 數(shù)學(xué)歸納法是證明某個(gè)命題當(dāng)整數(shù) n(n≥n0時(shí) )成立的一個(gè)一般性方法。首先，我們證明當(dāng) n 為最小值 n0時(shí)命題成立，這稱為基礎(chǔ)。然后我們需要證明 n≥n0時(shí)的命題成立，先假設(shè) n0到 n?1 之間的值已經(jīng)被證明成立，這成為歸納。這樣的證明提供無(wú)限多的結(jié)果，只用數(shù)量有限的工作。 數(shù)學(xué)歸納法為遞推提供了完美的解決準(zhǔn)備。在我們的案例中，從（ ）很容易得到（ ）：因?yàn)?T0＝ 201＝ 0，所以基 礎(chǔ)是微不足道的。假設(shè)當(dāng) n 被 n?1 取代后（ ）成立且 n0： Tn= 2Tn1+1= 2(2n?1?1)+1=2n?1. 因此對(duì)于（ ），問(wèn)題規(guī)模為 n 也成立。我們關(guān)于 Tn 的問(wèn)題已成功結(jié)束。 當(dāng)然，牧師的任務(wù)還沒(méi)有結(jié)束，他們?nèi)匀槐M職盡責(zé)地移動(dòng)磁盤，還需要一段時(shí)間，因?yàn)閷?duì)于 n = 64 需要移動(dòng) 2641 步（約 1810006）。即使以不可能速率每微秒移動(dòng)一次，他們也需要 5000 多世紀(jì)的時(shí)間轉(zhuǎn)移梵天塔。盧卡斯最初的難題實(shí)際一些，需要 281 = 255的步數(shù)，快的話需時(shí)約 4 分鐘。 漢諾塔的遞推思想在解決各種應(yīng)用提出的問(wèn)題中是很典型的。在尋找一個(gè)封閉的表達(dá)式來(lái)解決像 Tn 這樣有趣的問(wèn)題時(shí)，我們經(jīng)歷了三個(gè)階段： 1 看小規(guī)模問(wèn)題。這一步讓我們深入了解問(wèn)題，并為第 2 和第 3 階段提供幫助。 2 找到并證明關(guān)系量的一個(gè)數(shù)學(xué)表達(dá)式。對(duì)于漢諾塔問(wèn)題，遞推表達(dá)式（ ），讓我們可以計(jì)算任意 n 的 Tn 值。 3 為我們的數(shù)學(xué)表達(dá)找到并證明一個(gè)封閉形式，對(duì)于漢諾塔問(wèn)題，這是遞推的解()。第三階段是我們將在整本書都集中精力研究的一個(gè)階段。事實(shí)上，我們經(jīng)常會(huì)跳過(guò)階段 1 和 2，因?yàn)槲覀儞碛幸粋€(gè) 作為起點(diǎn)的數(shù)學(xué)表達(dá)式。但即使這樣，子問(wèn)題的解仍然將通過(guò)所有的三個(gè)階段。 分析漢諾塔可以找到問(wèn)題的正確答案，但它要求一個(gè)“歸納飛躍”，這里的解答依賴于僥幸的猜測(cè)。這本書的一個(gè)主要目標(biāo)是解釋如何解遞歸式而并不要求讀者具有超人的洞察力。例如我們會(huì)看到遞歸表達(dá)式（ ）通過(guò)等式兩邊加 1 來(lái)簡(jiǎn)化： T0 + 1= 1。 Tn + 1= 2Tn1+ 2, (n 0). 現(xiàn)在我們讓 Un = Tn1+1，可以得到， 武漢科技大學(xué)本科畢業(yè)論文外文翻譯 5 U0 =1； Un= 2Un1， (n 0). （ ） 不難發(fā)現(xiàn)，這個(gè)遞歸式的解是 Un = 2n。因此 Tn = 2n ?1。 甚至計(jì)算機(jī)都能發(fā)現(xiàn)此解。