【正文】
甚至計(jì)算機(jī)都能發(fā)現(xiàn)此解。 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。這本書(shū)的一個(gè)主要目標(biāo)是解釋如何解遞歸式而并不要求讀者具有超人的洞察力。但即使這樣,子問(wèn)題的解仍然將通過(guò)所有的三個(gè)階段。第三階段是我們將在整本書(shū)都集中精力研究的一個(gè)階段。對(duì)于漢諾塔問(wèn)題,遞推表達(dá)式( ),讓我們可以計(jì)算任意 n 的 Tn 值。這一步讓我們深入了解問(wèn)題,并為第 2 和第 3 階段提供幫助。 漢諾塔的遞推思想在解決各種應(yīng)用提出的問(wèn)題中是很典型的。即使以不可能速率每微秒移動(dòng)一次,他們也需要 5000 多世紀(jì)的時(shí)間轉(zhuǎn)移梵天塔。我們關(guān)于 Tn 的問(wèn)題已成功結(jié)束。在我們的案例中,從( )很容易得到( ):因?yàn)?T0= 201= 0,所以基 礎(chǔ)是微不足道的。這樣的證明提供無(wú)限多的結(jié)果,只用數(shù)量有限的工作。首先,我們證明當(dāng) n 為最小值 n0時(shí)命題成立,這稱為基礎(chǔ)。 確實(shí)滿足, Tn =2n?1, (n≥0). ( ) 至少對(duì)于 n≤ 6 成立。而且我們最希望的猜測(cè)解是看小規(guī)模情況下的情況。依據(jù)一個(gè)封閉的形式,我們可以了解到真正的 Tn。遞推的解使我們很開(kāi)心。當(dāng) n 很大時(shí)需要的計(jì)算時(shí)間太長(zhǎng)。 遞推關(guān)系,讓我們可以計(jì)算我們?nèi)魏?n 的 Tn 值。它給出了一個(gè)邊界值和根據(jù)叫造紙表達(dá)一般只的一個(gè)方程。這種檢查是很有價(jià)值的,在后面的章節(jié)中做更復(fù)雜的演算時(shí)就會(huì)體現(xiàn)出來(lái)。因此 , Tn ≥ 2 Tn1+1, (n> 0). 這兩個(gè)不等式,與退化解 n = 0 一起,可得到 T0 = 0 Tn = 2 Tn1+1, (n> 0). ( ) (請(qǐng)注意,這個(gè)公式是與已知值 T1=1 和 T2=3 一致的。如果我們不是太留心的話,有時(shí)候最大的磁盤(pán)可能會(huì)被移動(dòng)不止一次。在某些時(shí)候,我們必須移動(dòng)最大的磁盤(pán)。聰明人可能會(huì)想到的這樣的一個(gè)捷徑 。因?yàn)樯鲜龇治鰞H能證明 2Tn1+1 步移動(dòng)是充分的 。而不是 39。因此,我們最多可以使用 2Tn1+1 步來(lái)移動(dòng) n 個(gè)磁盤(pán)( n0): Tn ≤ 2 Tn1+1, (n> 0). 此公式使用 39。怎樣去轉(zhuǎn)移大型塔?在三個(gè)磁盤(pán)的移動(dòng)問(wèn)題上,成功的做法是先將最上面的兩個(gè)盤(pán)移動(dòng)到中間桿上,然后移動(dòng)第三個(gè)盤(pán),接著把其他兩個(gè)移到第三個(gè)盤(pán)上面。精明的數(shù)學(xué)家不為思索小的情形而感到害臊 ,因?yàn)樵跇O端情形下,小規(guī)模問(wèn)題往往是容易理解的 (即使它們有時(shí)候是無(wú)意義的 )。則 T1顯然是 1, T2= 3。 武漢科技大學(xué)本科畢業(yè)論文外文翻譯 3 解決這個(gè)問(wèn)題的下一步是引入適當(dāng)?shù)姆?hào):取名并求解。事實(shí)上我們將反復(fù)從這本書(shū)里發(fā)現(xiàn)先處理小規(guī)模問(wèn)題的好處。讓我們考慮如果有 n 個(gè)磁盤(pán)會(huì)發(fā)生什么情況?,F(xiàn)在問(wèn)題出現(xiàn)了:對(duì)于這個(gè)問(wèn)題最好的解法是什么?也就是說(shuō),需要移動(dòng)多少次才能完成這個(gè)任務(wù)。據(jù)說(shuō),牧師們不分晝夜的忙碌這項(xiàng)工作,到他們完成那一天,塔將碎裂世界也將到盡頭。據(jù)稱這個(gè)塔擁有 64 個(gè)純金磁盤(pán),按順序放在三個(gè)金剛針上。題目是有一個(gè)具有八個(gè)盤(pán)所堆成的塔,最初按尺寸從小到大的順序堆放在三根桿中的一個(gè)上: 目標(biāo)是將整個(gè)塔上的盤(pán)轉(zhuǎn)移到另一根桿上,每次只能移動(dòng)一個(gè)盤(pán)并且在移動(dòng)的過(guò)程中不允許將大盤(pán)放在小盤(pán)之上。 漢諾塔 讓我們先來(lái)看一個(gè)巧妙機(jī)智的小問(wèn)題稱為漢諾塔 ,它是由法國(guó)數(shù)學(xué)家愛(ài)德華他們有兩個(gè)共同特點(diǎn):一是他們都被數(shù)學(xué)家反復(fù)研究 。 Tn + 1= 2Tn1+ 2, for n 0. Now if we let Un = Tn+1, we have U0 =1; Un= 2Un1, for n 0. () It doesn39。ll be getting into subproblems whose solutions will take us through all three stages. Our analysis of the Tower of Hanoi led to the correct answer, but it required an“inductive leap”; we relied on a lucky guess about the answer. One of the main objectives of this book is to explain how a person can solve recurrences without being clairvoyant. For example, we39。s original puzzle is a bit more practical, It requires 28?1 = 255 moves, which takes about four minutes for the quick of hand. The Tower of Hanoi recurrence is typical of many that arise in applications of all kinds. In finding a closedform expression for some quantity of interest like Tn we go through thr