1、 本科毕业论文外文翻译 外文译文题目（中文） ： 具体数学：汉诺塔问题 学 院 : 专 业 : 学 号 : 学生姓名 : 指导教师 : 日 期 : 二一二年六月 武汉科技大学本科毕业论文外文翻译 1 1 Recurrent Problems THIS CHAPTER EXPLORES three sample problems that give a feel for whats to come. They have two traits in common: Theyve all been investigated repeatedly by mathematicians； and thei
2、r 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. 1.1 THE TOWER OF HANOI Lets look first at a neat little puzzle called the Tower of Hanoi,invented by the French mathematician Edouard Lucas in 1883. We
3、 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 mu
4、ch 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 pries
5、ts reportedly work day and night at their task. When they finish, the Tower will crumble and the world will end. 武汉科技大学本科毕业论文外文翻译 2 Its 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：
6、 Whats 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； lets consider what happens if there are TL disks. One advantage o
7、f this generalization is that we can scale the problem down even more. In fact, well see repeatedly in this book that its advantageous to LOOK AT SMALL CASES first. Its easy to see how to transfer a tower that contains only one or two disks. And a small amount of experimentation shows how to transfe
8、r a tower of three. The next step in solving the problem is to introduce appropriate notation： NAME ANO CONQUER. Lets say that Tn is the minimum number of moves that will transfer n disks from one peg to another under Lucass rules. Then T1 is obviously 1 , and T2 = 3. We can also get another piece o
9、f data for free, by considering the smallest case of all： Clearly T0 = 0， because no moves at all are needed to transfer a tower of n = 0 disks! Smart mathematicians are not ashamed to think small,because general patterns are easier to perceive when the extreme cases are well understood(even when th
10、ey are trivial). But now lets change our perspective and try to think big； how can we transfer a large tower? Experiments with three disks show that the winning idea is to transfer the top two disks to the middle peg, then move the third, then bring the other two onto it. This gives us a clue for tr
11、ansferring n disks in general： We first transfer the n1 smallest to a different peg (requiring Tn-1 moves), then move the largest (requiring one move), and finally transfer the n1 smallest back onto the largest (requiring another Tn-1 moves). Thus we can transfer n disks (for n 0)in at most 2Tn-1+1 moves： Tn 2Tn1+1， for n 0. This formula uses instead of = because our construction proves only that 2Tn1+1 moves suffice； we havent shown that 2Tn1+1 moves are necessary. A clever person might be able to think of a shortcut.
