📄 hanoitower.htm
字号:
<!DOCTYPE html PUBLIC "-//W3C//DTD HTML 4.01 Transitional//EN">
<html>
<head>
<link rel="stylesheet" href="css/stdlayout.css" type="text/css">
<link rel="stylesheet" href="css/print.css" type="text/css">
<meta content="text/html; charset=gb2312" http-equiv="content-type">
<title>河内塔</title>
</head>
<body>
<h3><a href="http://caterpillar.onlyfun.net/GossipCN/index.html">From
Gossip@caterpillar</a></h3>
<h1><a href="AlgorithmGossip.htm">Algorithm Gossip: 河内塔</a></h1>
<h2> 说明</h2>
河内之塔(Towers of
Hanoi)是法国人M.Claus(Lucas)于1883年从泰国带至法国的，河内为越战时北越的首都，即现在的胡志明市；1883年法国数学家
Edouard
Lucas曾提及这个故事，据说创世纪时Benares有一座波罗教塔，是由三支钻石棒（Pag）所支撑，开始时神在第一根棒上放置64个由上至下依由小
至大排列的金盘（Disc），并命令僧侣将所有的金盘从第一根石棒移至第三根石棒，且搬运过程中遵守大盘子在小盘子之下的原则，若每日仅搬一个盘子，则当
盘子全数搬运完毕之时，此塔将毁损，而也就是世界末日来临之时。<br>
<h2>解法</h2>
如果柱子标为ABC，要由A搬至C，在只有一个盘子时，就将它直接搬至C，当有两个盘子，就将B当作辅助柱。 <br>
<div style="text-align: center;"><img style="width: 214px; height: 108px;" alt="河内塔" title="河内塔" src="images/hanoi-1.jpg"> <img style="width: 208px; height: 112px;" alt="河内塔" title="河内塔" src="images/hanoi-2.jpg"> <img style="width: 212px; height: 104px;" alt="河内塔" title="河内塔" src="images/hanoi-3.jpg"><br>
</div>
<br>
如果盘数超过2个，将第三个以下的盘子遮起来，就很简单了，每次处理两个盘子，也就是：A->B、A ->C、B->C这三个步骤，而被遮住的部份，其实就是进入程式的递回处理。<br>
<div style="text-align: center;"><img style="width: 242px; height: 86px;" alt="河内塔" title="河内塔" src="images/hanoi-4.jpg"><br>
<br>
<div style="text-align: left;">事实上，若有n个盘子，则移动完毕所需之次数为2^n - 1，所以当盘数为64时，则所需次数为：<br>
<br>
2<sup>64</sup>- 1 = 18446744073709551615<br>
<br>
为5.05390248594782e+16年，也就是约5000世纪，如果对这数字没什么概念，就假设每秒钟搬一个盘子好了，也要约5850亿年左右。 </div>
</div>
<h2> 演算法</h2>
<pre>Procedure HANOI(n, A, B, C) [<br> IF(n == 1) [<br> PRINT("Move sheet " n " from " A " to " C);<br> ]<br> ELSE [<br> HANOI(n-1, A, C, B);<br> PRINT("Move sheet " n " from " A " to " C);<br> HANOI(n-1, B, A, C); <br> ] <br>] <br></pre>
<h2> 实作</h2>
<ul>
<li> C
</li>
</ul>
<pre>#include <stdio.h><br><br>void hanoi(int n, char A, char B, char C) {<br> if(n == 1) {<br> printf("Move sheet %d from %c to %c\n", n, A, C);<br> }<br> else {<br> hanoi(n-1, A, C, B);<br> printf("Move sheet %d from %c to %c\n", n, A, C);<br> hanoi(n-1, B, A, C);<br> }<br>}<br><br>int main() {<br> int n;<br> printf("请输入盘数：");<br> scanf("%d", &n);<br> hanoi(n, 'A', 'B', 'C');<br> return 0;<br>} <br></pre>
<ul>
<li>Java
</li>
</ul>
<pre>import java.io.*;<br><br>public class Hanoi {<br> public static void main(String args[]) throws IOException {<br> int n;<br> BufferedReader buf;<br> buf = new BufferedReader(new InputStreamReader(System.in));<br><br> System.out.print("请输入盘数：");<br> n = Integer.parseInt(buf.readLine());<br><br> Hanoi hanoi = new Hanoi();<br> hanoi.move(n, 'A', 'B', 'C');<br> }<br><br> public void move(int n, char a, char b, char c) {<br> if(n == 1)<br> System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);<br> else {<br> move(n - 1, a, c, b);<br> System.out.println("盘 " + n + " 由 " + a + " 移至 " + c);<br> move(n - 1, b, a, c);<br> }<br> }<br>} </pre>
<br>
<br>
</body>
</html>
⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -