Publicitade E▼
⇨ definição - Wikipedia
Publicidade ▼
Wikipedia
本条目没有列出任何参考或来源。(2008年6月20日) |
河內塔是根据一个传说形成的一个问题:
有三根杆子A,B,C。A杆上有N个(N>1)穿孔圆盘,盘的尺寸由下到上依次变小。要求按下列规则将所有圆盘移至C杆:
提示:可将圆盘临时置于B杆,也可将从A杆移出的圆盘重新移回A杆,但都必须尊循上述两条规则。
问:如何移?最少要移动多少次?
目录 |
如取N=64,最少需移动264-1次。即如果一秒钟能移动一块圆盘,仍将需5845.54亿年。目前按照宇宙大爆炸理论的推测,宇宙的年龄仅为137亿年。
在真实玩具中,一般N=8;这将需移动255次。如果N=10,需移动1023次。如果N=15,需移动32767次;这就是说,如果一个人从3岁到99岁,每天移动一块圆盘,他仅能移动15块。如果N=20,需移动1048575次,即超过了一百万次。
傳說印度某間寺院有三根柱子,上串64个金盤。寺院裡的僧侶依照一個古老的預言,以上述規則移動這些盤子;預言說當這些盤子移動完毕,世界就會滅亡。這個傳說叫做梵天寺之塔問題(Tower of Brahma puzzle)。但不知道是盧卡斯自創的這個傳說,還是他受他人啟發。
若傳說屬實,僧侶們需要264 − 1步才能完成這個任務;若他們每秒可完成一個盤子的移動,就需要5846億年才能完成。整個宇宙現在也不過137億年。
這個傳說有若干變體:寺院換成修道院、僧侶換成修士等等。寺院的地點眾說紛紜,其中一說是位于越南的河內,所以被命名為「河內塔」。另外亦有「金盤是創世時所造」、「僧侶們每天移動一盤」之類的背景設定。
佛教中確實有「浮屠」(塔)這種建築;有些浮屠亦遵守上述規則而建。「河內塔」一名可能是由中南半島在殖民時期傳入歐洲的。
許多的河內塔玩具都有 8 個碟子(disks)。在初學者看起來似乎不太可能有解,然而其演算法是相當簡單的:
為了從任意初始結構中找尋最佳解(optimal solution),其演算法可以一般化(be generalized)如下:
以 Scheme 語言表示:
; Let conf be a list of the positions of the disks in order of increasing size. ; Let the pegs be identified by the numbers 0, 1 and 2. (define (hanoi conf t) (let ((c (list->vector conf))) (define (move h f t) (vector-set! c h t) (printf "move disk ~s from peg ~s to peg ~s~n" h f t)) (define (third-peg f t) (- 3 f t)) (define (hanoi h t) (if (> h 0) (let ((h (sub1 h))) (let ((f (vector-ref c h))) (if (not (= f t)) (let ((r (third-peg f t))) (hanoi h r) (move h f t))) (hanoi h t))))) (hanoi (vector-length c) t)))
在 C語言中:
int conf[HEIGHT]; /* Element conf[d] gives the current position of disk d. */ void move(int d, int t) { /* move disk d to peg t */ conf[d] = t; } void hanoi(int h, int t) { if (h > 0) { int f = conf[h-1]; if (f != t) { int r = 3 - f - t ; hanoi(h-1, r); move(h-1, t); } hanoi(h-1, t); } }
在PASCAL語言中:
procedure Hanoi(n: integer; from, to, by: char); Begin if (n=1) then writeln('Move the plate ',n,' from ', from, ' to ', to) else begin Hanoi(n-1, from, by, to); Writeln('Move the plate ',n,' from ', from, ' to ', to); Hanoi(n-1, by, to, from); end; End;
Excel VBA 汉诺塔演示 作者:ExcelHome xjg811 Dim i As Long
Dim R, H, Ql, Qw
Sub HanoiKs()
inputx:
n = InputBox("请输入盘子数,建议从小数开始,这个数最好不要大于20,否则,电脑可能运算不了。") If IsNumeric(n) = False Then MsgBox "您输入的不是数字,请重新输入" GoTo inputx End If If Int(n) <> Val(n) Then MsgBox "请输入整数,请重新输入" GoTo inputx End If If n > 32 Then MsgBox "数字太大,请重新输入" GoTo inputx End If If n < 3 Then MsgBox "数字太小,请重新输入" GoTo inputx End If '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' i = 0 l = 24 t = 410 w = 212 h0 = 10 l1 = 128 t1 = 70 w1 = 5 h1 = 360 l2 = 20 t2 = 410 w2 = 220 h2 = 30 Bt = 100 Bl = 300 Ct = -10 Cl = 600 ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ReDim R(0 To 2 ^ n, 1 To 3) ReDim H(0 To 2 ^ n - 1, 1 To 3) ReDim Ql(n) ReDim Qw(n) H(i, 1) = h1 - 10 * n + 60
H(i, 2) = h1 + Bt + 50
H(i, 3) = h1 + 60
Ql(0) = l
'''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ActiveSheet.Shapes.AddShape(msoShapeCan, l1, t1, w1, h1).Select Selection.Name = "A1#" With Selection.ShapeRange .Fill.ForeColor.SchemeColor = 13 .Fill.Visible = msoTrue .Fill.Solid End With Selection.ShapeRange.Line.ForeColor.SchemeColor = 13 ActiveSheet.Shapes.AddShape(msoShapeFlowchartMagneticDisk, l2, t2, w2, h2).Select Selection.Name = "A2#" With Selection.ShapeRange .Fill.ForeColor.SchemeColor = 8 .Shadow.Type = msoShadow14 .Fill.Visible = msoTrue .Fill.Solid End With Selection.ShapeRange.Line.ForeColor.SchemeColor = 8 ActiveSheet.Shapes("A1#").Select ActiveSheet.Shapes.Range(Array("A1#", "A2#")).Select Selection.ShapeRange.Group.Select Selection.Name = "A#" Selection.Copy ActiveSheet.Paste Selection.Name = "B#" ActiveSheet.Paste Selection.Name = "C#" ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ActiveSheet.Shapes.AddShape(msoShapeRectangle, 110, 410, 24, 30).Select Selection.Name = "An" Selection.Characters.Text = "A" With Selection.Characters(Start:=1, Length:=1).Font .Name = "宋体" .FontStyle = "常规" .Size = 20 .ColorIndex = 8 End With ActiveSheet.Shapes.Range(Array("A#", "An")).Select Selection.ShapeRange.Group.Select Selection.Name = "A" '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ActiveSheet.Shapes.AddShape(msoShapeRectangle, 129, 422, 24, 30).Select Selection.Name = "Bn" Selection.Characters.Text = "B" With Selection.Characters(Start:=1, Length:=1).Font .Name = "宋体" .FontStyle = "常规" .Size = 20 .ColorIndex = 52 End With ActiveSheet.Shapes.Range(Array("B#", "Bn")).Select Selection.ShapeRange.Group.Select Selection.Name = "B" ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ActiveSheet.Shapes.AddShape(msoShapeRectangle, 140, 432, 24, 30).Select Selection.Name = "Cn" Selection.Characters.Text = "C" With Selection.Characters(Start:=1, Length:=1).Font .Name = "宋体" .FontStyle = "常规" .Size = 20 .ColorIndex = 3 End With ActiveSheet.Shapes.Range(Array("C#", "Cn")).Select Selection.ShapeRange.Group.Select Selection.Name = "C" ''''''''''''''''''''''''''''''''''''''''''''''''''''''' ActiveSheet.Shapes("C").Select Selection.ShapeRange.IncrementLeft Cl Selection.ShapeRange.IncrementTop Ct ActiveSheet.Shapes("B").Select Selection.ShapeRange.IncrementLeft Bl Selection.ShapeRange.IncrementTop Bt For i = n To 1 Step -1 l = l + 3 t = t - 10 w = w - 6 Ql(i) = l Qw(i) = w ActiveSheet.Shapes.AddShape(msoShapeFlowchartMagneticDisk, l, t, w, h0).Select Selection.ShapeRange.Fill.ForeColor.SchemeColor = i + 7 Selection.ShapeRange.Fill.Visible = msoTrue Selection.ShapeRange.Fill.Solid Selection.ShapeRange.Line.ForeColor.SchemeColor = i + 5 Selection.ShapeRange.Shadow.Type = msoShadow14 Selection.Name = i & "#" Selection.Characters.Text = i With Selection.Characters(Start:=0, Length:=1).Font .Name = "宋体" .FontStyle = "常规" .Size = 5 .ColorIndex = i + 3 End With With ActiveSheet.Shapes(i & "#") .Placement = 3 With .TextFrame .HorizontalAlignment = -4108 .VerticalAlignment = -4108 End With End With Next
Range("E8").Select For Each bar In Application.CommandBars bar.Enabled = False Next ActiveWindow.DisplayHeadings = False Application.DisplayFullScreen = True ActiveWindow.DisplayGridlines = False i = 0 X = MsgBox("继续吗?,如果您点是,电脑玩;否则,您自己可以试试玩。", 1 + 2, "请您选择。") If X <> 6 Then Exit Sub Call Hanoi(n, "A", "B", "C") Call HanoiMove
End Sub
Sub Hanoi(ByVal M%, ByVal X, ByVal Y, ByVal Z)
If M = 1 Then i = i + 1 '''''''''''''''''''''''''''''''''''''''''''''''''' A1 = Asc(X) - 64 A2 = Asc(Y) - 64 A3 = Asc(Z) - 64 R(i, 1) = M R(i, 2) = X R(i, 3) = Z H(i, A1) = H(i - 1, A1) + 10 H(i, A2) = H(i - 1, A2) H(i, A3) = H(i - 1, A3) - 10 '''''''''''''''''''''''''''''''''''''''''''''''''' Else
Hanoi M - 1, X, Z, Y i = i + 1 ''''''''''''''''''''''''''''''''''''''''''''''' A1 = Asc(X) - 64 A2 = Asc(Y) - 64 A3 = Asc(Z) - 64 R(i, 1) = M R(i, 2) = X R(i, 3) = Z H(i, A1) = H(i - 1, A1) + 10 H(i, A2) = H(i - 1, A2) H(i, A3) = H(i - 1, A3) - 10
'''''''''''''''''''''''''''''''''''''''''''''''''''''
Hanoi M - 1, Y, X, Z End If
End Sub
Private Sub HanoiMove()
Range("E8").Select ActiveSheet.Shapes.AddShape(msoShapeSmileyFace, 232.5, 102.75, 39, 15.75).Select Selection.Name = "0#"
R(0, 3) = "C" R(0, 2) = "A" For j = 1 To i If R(j, 3) = "A" Then Tl = 0 Th = -20 Else Th = 0 End If If R(j, 3) = "B" Then Tl = 300 + 12 If R(j, 3) = "C" Then Tl = 600 + 25 '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ActiveSheet.Shapes("0#").Select Selection.ShapeRange.IncrementRotation -17.3545333333 'Range("E7").Select ' ActiveSheet.Shapes.Range(Array("Smiley Face 1058")).Select Selection.ShapeRange.IncrementRotation 30.0517166667 Selection.ShapeRange.IncrementRotation -12.6971833333 Range("E8").Select ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' Sheet1.Range("G8").Clear Sheet1.Range("G8") = "第" & j & "步:" & R(j, 1) & "盘从" & R(j, 2) & "搬到" & R(j, 3) On Error Resume Next Application.Speech.Speak "第" & j & "步:" & R(j, 1) & "盘从" & R(j, 2) & "搬到" & R(j, 3), , , False If Err.Number <> 0 Then Application.Speech.Speak "", , , True End If On Error GoTo 0 ActiveSheet.Shapes(R(j, 1) & "#").Select Selection.ShapeRange.IncrementLeft 0 Selection.ShapeRange.IncrementTop -(H(j - 1, Asc(R(j, 2)) - 64) - 200) Sheet1.Range("E8").Select For k1 = 1 To 50 ActiveSheet.Shapes(R(j, 1) & "#").Select Selection.ShapeRange.IncrementLeft 0 Selection.ShapeRange.IncrementTop -4 Sheet1.Range("E8").Select Next For k2 = 1 To 100 ActiveSheet.Shapes(R(j, 1) & "#").Select Selection.ShapeRange.IncrementLeft (Asc(R(j, 3)) - Asc(R(j, 2))) * 3 Selection.ShapeRange.IncrementTop 0 Sheet1.Range("E8").Select Next ActiveSheet.Shapes(R(j, 1) & "#").Select Selection.ShapeRange.IncrementLeft 12 * (Asc(R(j, 3)) - Asc(R(j, 2))) Selection.ShapeRange.IncrementTop 0 Sheet1.Range("E8").Select For k3 = 1 To 50 ActiveSheet.Shapes(R(j, 1) & "#").Select Selection.ShapeRange.IncrementLeft 0 Selection.ShapeRange.IncrementTop 4 Sheet1.Range("E8").Select Next ActiveSheet.Shapes(R(j, 1) & "#").Select Selection.ShapeRange.IncrementLeft 0 Selection.ShapeRange.IncrementTop H(j - 1, Asc(R(j, 3)) - 64) - 200 + 3 * Th Sheet1.Range("E8").Select ActiveSheet.Shapes(R(j, 1) & "#").Delete ActiveWorkbook.Save ''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ActiveSheet.Shapes.AddShape(msoShapeFlowchartMagneticDisk, Ql(R(j, 1)) + Tl, H(j - 1, Asc(R(j, 3)) - 64) + Th, Qw(R(j, 1)), 10).Select Selection.ShapeRange.Fill.ForeColor.SchemeColor = R(j, 1) + 7 'Selection.ShapeRange.Fill.OneColorGradient 1, 4, 0.23 Selection.ShapeRange.Fill.Visible = msoTrue Selection.ShapeRange.Fill.Solid Selection.ShapeRange.Line.ForeColor.SchemeColor = R(j, 1) + 5 Selection.ShapeRange.Shadow.Type = msoShadow14 Selection.Name = R(j, 1) & "#" Selection.Characters.Text = R(j, 1) With Selection.Characters(Start:=0, Length:=1).Font .Name = "宋体" .FontStyle = "常规" .Size = 4 .ColorIndex = R(j, 1) + 3 End With With ActiveSheet.Shapes(R(j, 1) & "#") .Placement = 3 With .TextFrame .HorizontalAlignment = -4108 .VerticalAlignment = -4108 End With End With Sheet1.Range("E8").Select '''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''''' ActiveWorkbook.Save Next
End Sub
Sub HanoiFy()
Cells.ClearContents Dim sha As Shape
For Each sha In ActiveSheet.Shapes If sha.Type <> 12 Then sha.Delete Next For Each bar In Application.CommandBars bar.Enabled = True Next
ActiveWindow.DisplayHeadings = True Application.DisplayFullScreen = False
ActiveWindow.DisplayGridlines = True Set R = Nothing
Set H = Nothing Set Ql = Nothing Set Qw = Nothing ActiveWorkbook.Save End Sub
Private Sub cmdH_Click()
If cmdH.Caption = "开始" Then cmdH.Caption = "复原" Call HanoiKs Else cmdH.Caption = "开始" Call HanoiFy End If
End Sub
2011年電影《猿人爭霸戰:猩凶革命》曾出現河內塔以測試猩猩的智商。
Conteùdo de sensagent
calculado em 0,015s