【正文】
本科畢業(yè)論文外文翻譯 外文譯文題目(中文) : 具體數(shù)學:漢諾塔問題 學 院 : 專 業(yè) : 學 號 : 學生姓名 : 指導(dǎo)教師 : 日 期 : 二○一二年六月 武漢科技大學本科畢業(yè)論文外文翻譯 1 1 Recurrent Problems THIS CHAPTER EXPLORES three sample problems that give a feel for what’s to come. They have two traits in mon: They’ve all been investigated repeatedly by mathematicians。 and their solutions all use the idea of recurrence, in which the solution to each problem depends on the solutions to smaller instances of the same problem. THE TOWER OF HANOI Let’s look first at a neat little puzzle called the Tower of Hanoi,invented by the French mathematician Edouard Lucas in 1883. We are given a tower of eight disks, initially stacked in decreasing size on one of three pegs: The objective is to transfer the entire tower to one of the other pegs, moving only one disk at a time and never moving a larger one onto a smaller. Lucas furnished his toy with a romantic legend about a much larger Tower of Brahma, which supposedly has 64 disks of pure gold resting on three diamond needles. At the beginning of time, he said, God placed these golden disks on the first needle and ordained that a group of priests should transfer them to the third, according to the rules above. The priests reportedly work day and night at their task. When they finish, the Tower will crumble and the world will end. 武漢科技大學本科畢業(yè)論文外文翻譯 2 It39。s not immediately obvious that the puzzle has a solution, but a little thought (or having seen the problem before) convinces us that it does. Now the question arises: What39。s the best we can do? That is, how many moves are necessary and sufficient to perform the task? The best way to tackle a question like this is to generalize it a bit. The Tower of Brahma has 64 disks and the Tower of Hanoi has 8; let39。s consider what happens if there are TL disks. One advantage of this generalization is that we can scale the problem down even more. In fact, we39。ll see repeatedly in this book that it39。s advantageous to LOOK AT SMALL CASES first. It39。s easy to see how to transfer a tower that contains only one or two disks. And a small amount of experimentation shows how to transfer a tower of three. The next step in solving the problem is to introduce appropriate notation: NAME ANO CONQUER. Let39。s say that Tn is the minimum number of moves that will transfer n disks from one peg to another under Lucas39。s rules. Then T1 is obviously 1 , and T2 = 3. We can also get another piece of data fo