## 双重河内塔

《具体数学：计算机科学基础（第2版）》第 1 章作业题 11：

a 如果相同尺寸的圆盘是相互不可区分的，要把一个双重塔从一根桩柱移动到另一根桩柱需要移动多少次？

b 如果在最后的排列中要把所有同样尺寸的圆盘恢复成原来的从上到下的次序，需要移动多少次？ 提示：这是一个难题，实在应该是个“附加题”。

## 主程序

`````` 1: using System;
2: using System.IO;
3:
4: namespace Skyiv.Hanoi
5: {
6:   sealed class Runner
7:   {
8:     static void Main(string[] args)
9:     {
10:       var algorithm = (args.Length > 0) ? int.Parse(args[0]) : 1;
11:       if (algorithm < 1 || algorithm > 3) throw new ArgumentException("Invalid algorithm");
12:       var diskKinds = (args.Length > 1) ? int.Parse(args[1]) : 3;
13:       var tower = new Tower(new Configuration(diskKinds));
14:       tower.BitmapDirectory = new DirectoryInfo("Bitmap" + algorithm);
15:       using (tower.Writer = File.CreateText(algorithm + ".txt")) tower.Solve(algorithm);
16:       Console.WriteLine("[Algorithm:{0}, DiskKinds:{1}, Steps:{2}]", algorithm, diskKinds, tower.Step);
17:       Console.WriteLine("[{0}]", tower.BitmapDirectory.FullName);
18:     }
19:   }
20: }
``````

## 双重河内塔

``````  1: using System;
2: using System.IO;
3: using System.Drawing;
4: using Skyiv.Extensions;
5:
6: namespace Skyiv.Hanoi
7: {
8:   // 双重河内塔
9:   sealed class Tower
10:   {
11:     public int DiskKinds { get; private set; }
12:     public TextWriter Writer { get; set; }
13:     public DirectoryInfo BitmapDirectory { get; set; }
14:     public int Step { get; private set; }
15:     Peg[] pegs;
16:     int algorithm;
17:     Configuration config;
18:
19:     public Tower(Configuration config)
20:     {
21:       Writer = TextWriter.Null;
22:       this.config = config;
23:       DiskKinds = config.DiskKinds;
24:       pegs = new Peg[3];
25:       for (var i = 0; i < pegs.Length; i++) pegs[i] = new Peg(config, i);
26:       pegs[0].FillAllDisks();
27:     }
28:
29:     void Draw()
30:     {
31:       var size = config.BitmapSize;
32:       var bitmap = new Bitmap(size.Width, size.Height);
33:       var gc = Graphics.FromImage(bitmap);
34:       gc.FillRectangle(config.BackgroundBrush, 0, 0, size.Width, size.Height);
35:       gc.DrawString(Step.ToString(), config.Font, Brushes.Black, new PointF(0, 0));
36:       foreach (var peg in pegs) peg.Draw(gc);
37:       bitmap.Save(Path.Combine(BitmapDirectory.FullName,
38:         string.Format("{0}-{1:D4}.png", algorithm, Step)));
39:     }
40:
41:     public void Solve(int algorithm)
42:     {
43:       this.algorithm = algorithm;
44:       BitmapDirectory.CleanAndCreate();
45:       Writer.WriteLine("{0,4}: ------> {1}", Step, this);
46:       Draw();
47:       switch (algorithm)
48:       {
49:         case 1: Solve1(DiskKinds * 2, 0, 1, 2); break;
50:         case 2: Solve2(DiskKinds * 2, 0, 1, 2); break;
51:         case 3: Solve3(DiskKinds * 2, 0, 1, 2); break;
52:       }
53:       Writer.WriteLine("{0} [大功告成] {0}", "".PadLeft(13, '-'));
54:     }
55:
56:     void Solve1(int disks, int from, int to, int other)
57:     {
58:       if (disks <= 0) return;
59:       Solve1(disks - 2, from, other, to);
60:       for (var i = 0; i < 2; i++) Move(from, to);
61:       Solve1(disks - 2, other, to, from);
62:     }
63:
64:     void Solve2(int disks, int from, int to, int other)
65:     {
66:       if (disks <= 0) return;
67:       if (disks == 2) { Move(from, other); Move(from, to); Move(other, to); return; }
68:       Solve1(disks - 2, from, to, other);
69:       for (var i = 0; i < 2; i++) Move(from, other);
70:       Solve1(disks - 2, to, from, other);
71:       for (var i = 0; i < 2; i++) Move(other, to);
72:       Solve2(disks - 2, from, to, other);
73:     }
74:
75:     void Solve3(int disks, int from, int to, int other)
76:     {
77:       if (disks <= 0) return;
78:       Solve1(disks - 2, from, to, other);
79:       Move(from, other);
80:       Solve1(disks - 2, to, other, from);
81:       Move(from, to);
82:       Solve1(disks - 2, other, from, to);
83:       Move(other, to);
84:       Solve1(disks - 2, from, to, other);
85:     }
86:
87:     void Move(int from, int to)
88:     {
89:       Step++;
90:       var disk = pegs[from].Pop();
91:       pegs[to].Push(disk);
92:       Writer.WriteLine("{0,4}: {1}->{2}:{3} {4}", Step,
93:         pegs[from].Name, pegs[to].Name, disk, this);
94:       Draw();
95:     }
96:
97:     public override string ToString()
98:     {
99:       string s = "";
100:       foreach (var peg in pegs) s += peg;
101:       return s;
102:     }
103:   }
104: }
``````

• 第 19～27 行的构造函数构造双重河内塔，共有三个桩柱，并将所有圆盘放在第一个桩柱上。
• 第 29～39 行的 Draw 方法画出双重河内塔，解题步骤的每一步都会调用一次该方法。
• 第 41～54 行的 Solve 方法求解双重河内塔。
• 第 56～62 行的 Solve1 方法对应求解问题 a 的算法。
• 第 64～73 行的 Sovle2 方法对应求解问题 b 的第一种算法。
• 第 75～85 行的 Sovle3 方法对应求解问题 b 的第二种算法。
• 第 87～95 行的 Move 方法用来移动圆盘。它会调用 Draw 方法来画出双重河内塔。
• 第 97～102 行的重载的 ToString 方法将双重河内塔表示为字符串。

## 桩柱

`````` 1: using System.Text;
2: using System.Drawing;
3: using System.Collections.Generic;
4:
5: namespace Skyiv.Hanoi
6: {
7:   sealed class Peg
8:   {
9:     public string Name { get { return ((char)('A' + id)).ToString(); } }
11:     Stack<Disk> disks;
12:     Configuration config;
13:
14:     public Peg(Configuration config, int id)
15:     {
16:       this.config = config;
17:       this.id = id;
18:       disks = new Stack<Disk>();
19:     }
20:
21:     public void FillAllDisks()
22:     {
23:       for (var i = config.DiskKinds; i > 0; i--)
24:       {
25:         disks.Push(new Disk(config, i, 1));
26:         disks.Push(new Disk(config, i, 0));
27:       }
28:     }
29:
30:     public Disk Pop() { return disks.Pop(); }
31:     public void Push(Disk disk) { disks.Push(disk); }
32:
33:     public void Draw(Graphics gc)
34:     {
35:       var x = config.PegX0 + id * (config.PegWidth + config.PegGap);
36:       gc.DrawRectangle(config.PegPen, x + config.PegWidth / 2, config.PegY0,
37:         config.PegPenWidth, config.PegHeight);
38:       gc.DrawRectangle(config.PegPen, x, config.PegY0 + config.PegHeight,
39:         config.PegWidth, config.PegPenWidth);
40:       int i = 0, y = config.PegY0 - 5 + (config.Total - disks.Count) * (config.DiskHeight + 1);
41:       foreach (var disk in disks)
42:         disk.Draw(gc, x + 2 + config.PegWidth / 2, y + i++ * (config.DiskHeight + 1));
43:     }
44:
45:     public override string ToString()
46:     {
47:       var sb = new StringBuilder();
48:       sb.Append("[" + Name + ":");
49:       foreach (var disk in disks) sb.Append(disk);
50:       sb.Append("]");
51:       return sb.ToString();
52:     }
53:   }
54: }
``````

• 第 14～19 行的构造函数构造桩柱。用一个栈存储本桩柱上的圆盘。
• 第 21～28 行的 FillAllDisks 方法将本桩柱上放满圆盘。
• 第 30 行的 Pop 方法从本桩柱上移走一个圆盘。
• 第 31 行的 Push 方法将一个圆盘放入本桩柱。
• 第 33～43 行的 Draw 方法画出本桩柱。它被 Tower 类的 Draw 方法调用。
• 第 45～52 行的重载的 ToString 将本桩柱表示为字符串。

## 圆盘

`````` 1: using System.Drawing;
2:
3: namespace Skyiv.Hanoi
4: {
5:   sealed class Disk
6:   {
7:     public int Size { get; private set; }
8:     public int Kind { get; private set; }
9:     Configuration config;
10:
11:     public Disk(Configuration config, int size, int kind)
12:     {
13:       this.config = config;
14:       Size = size;
15:       Kind = kind;
16:     }
17:
18:     public void Draw(Graphics gc, int x0, int y0)
19:     {
20:       var width = Size * config.DiskRate;
21:       gc.DrawRectangle(config.DiskPens[Kind],
22:         x0 - width / 2, y0 + config.DiskY0, width, config.DiskHeight / 2);
23:     }
24:
25:     public override string ToString()
26:     {
27:       return ((Kind == 0) ? "-" : "+") + Size;
28:     }
29:   }
30: }
``````

• 第 11～16 行的构造函数构造圆盘。
• 第 18～23 行的 Draw 方法画出圆盘。它被 Peg 类的 Draw 方法调用。
• 第 25～28 行的重载的 ToString 方法将圆盘表示为字符串。

## 配置

`````` 1: using System;
2: using System.Drawing;
3:
4: namespace Skyiv.Hanoi
5: {
6:   sealed class Configuration
7:   {
8:     public readonly int DiskHeight = 10, DiskRate = 20, DiskY0 = 10;
9:     public readonly int PegPenWidth = 3, PegGap = 10, PegX0 = 4, PegY0 = 10, PegWidth, PegHeight;
10:     public readonly int DiskKinds, Total;
13:     public readonly Brush BackgroundBrush = new SolidBrush(Color.LightGray);
16:
17:     public Configuration(int diskKinds)
18:     {
19:       if (diskKinds < 1 || diskKinds > 10) throw new ArgumentException(
20:         "diskKinds (value:" + diskKinds + ") must be between 1 and 10");
21:       DiskKinds = diskKinds;
22:       Font = new Font("Lucida Console", (DiskKinds == 1) ? 14 : 20);
23:       PegPen = new Pen(Color.Gray, PegPenWidth) ;
24:       DiskPens = new Pen[2];
25:       DiskPens[0] = new Pen(Color.Blue, DiskHeight / 2);
26:       DiskPens[1] = new Pen(Color.DarkBlue, DiskHeight / 2);
27:       Total = 2 * DiskKinds;
28:       PegWidth = DiskKinds * DiskRate + 20;
29:       PegHeight = (DiskKinds * 2) * (DiskHeight + 1) + 4;
30:       BitmapSize = new Size(PegWidth * 3 + PegGap * 2 + 10, PegHeight + 20);
31:     }
32:   }
33: }
``````

## 扩展方法

`````` 1: using System.IO;
2:
3: namespace Skyiv.Extensions
4: {
5:   public static class DirectoryInfoExtensions
6:   {
7:     public static void CleanAndCreate(this DirectoryInfo directory)
8:     {
9:       if (directory.Exists) directory.Delete(true);
10:       directory.Create();
11:     }
12:   }
13: }
``````

## Makefile

``````CSC = dmcs
EXE1 = Runner.exe
SRC1 = Runner.cs Tower.cs Peg.cs Disk.cs Configuration.cs DirectoryInfoExtensions.cs

all: \$(EXE1)

\$(EXE1): \$(SRC1)
\$(CSC) -out:\$@ -r:System.Drawing.dll \$(SRC1)
``````

## 编译和运行

``````\$ make
dmcs -out:Runner.exe -r:System.Drawing.dll Runner.cs Tower.cs Peg.cs Disk.cs Configuration.cs DirectoryInfoExtensions.cs
\$ mono Runner.exe 1
[Algorithm:1, DiskKinds:3, Steps:14]
[/home/ben/src/Hanoi/Bitmap1]
\$ mono Runner.exe 2
[Algorithm:2, DiskKinds:3, Steps:27]
[/home/ben/src/Hanoi/Bitmap2]
\$ mono Runner.exe 3
[Algorithm:3, DiskKinds:3, Steps:27]
[/home/ben/src/Hanoi/Bitmap3]
\$ cat 1.txt
0: ------> [A:-1+1-2+2-3+3][B:][C:]
1: A->B:-1 [A:+1-2+2-3+3][B:-1][C:]
2: A->B:+1 [A:-2+2-3+3][B:+1-1][C:]
3: A->C:-2 [A:+2-3+3][B:+1-1][C:-2]
4: A->C:+2 [A:-3+3][B:+1-1][C:+2-2]
5: B->C:+1 [A:-3+3][B:-1][C:+1+2-2]
6: B->C:-1 [A:-3+3][B:][C:-1+1+2-2]
7: A->B:-3 [A:+3][B:-3][C:-1+1+2-2]
8: A->B:+3 [A:][B:+3-3][C:-1+1+2-2]
9: C->A:-1 [A:-1][B:+3-3][C:+1+2-2]
10: C->A:+1 [A:+1-1][B:+3-3][C:+2-2]
11: C->B:+2 [A:+1-1][B:+2+3-3][C:-2]
12: C->B:-2 [A:+1-1][B:-2+2+3-3][C:]
13: A->B:+1 [A:-1][B:+1-2+2+3-3][C:]
14: A->B:-1 [A:][B:-1+1-2+2+3-3][C:]
------------- [大功告成] -------------
\$ cat 2.txt
0: ------> [A:-1+1-2+2-3+3][B:][C:]
1: A->C:-1 [A:+1-2+2-3+3][B:][C:-1]
2: A->C:+1 [A:-2+2-3+3][B:][C:+1-1]
3: A->B:-2 [A:+2-3+3][B:-2][C:+1-1]
4: A->B:+2 [A:-3+3][B:+2-2][C:+1-1]
5: C->B:+1 [A:-3+3][B:+1+2-2][C:-1]
6: C->B:-1 [A:-3+3][B:-1+1+2-2][C:]
7: A->C:-3 [A:+3][B:-1+1+2-2][C:-3]
8: A->C:+3 [A:][B:-1+1+2-2][C:+3-3]
9: B->C:-1 [A:][B:+1+2-2][C:-1+3-3]
10: B->C:+1 [A:][B:+2-2][C:+1-1+3-3]
11: B->A:+2 [A:+2][B:-2][C:+1-1+3-3]
12: B->A:-2 [A:-2+2][B:][C:+1-1+3-3]
13: C->A:+1 [A:+1-2+2][B:][C:-1+3-3]
14: C->A:-1 [A:-1+1-2+2][B:][C:+3-3]
15: C->B:+3 [A:-1+1-2+2][B:+3][C:-3]
16: C->B:-3 [A:-1+1-2+2][B:-3+3][C:]
17: A->B:-1 [A:+1-2+2][B:-1-3+3][C:]
18: A->B:+1 [A:-2+2][B:+1-1-3+3][C:]
19: A->C:-2 [A:+2][B:+1-1-3+3][C:-2]
20: A->C:+2 [A:][B:+1-1-3+3][C:+2-2]
21: B->A:+1 [A:+1][B:-1-3+3][C:+2-2]
22: B->A:-1 [A:-1+1][B:-3+3][C:+2-2]
23: C->B:+2 [A:-1+1][B:+2-3+3][C:-2]
24: C->B:-2 [A:-1+1][B:-2+2-3+3][C:]
25: A->C:-1 [A:+1][B:-2+2-3+3][C:-1]
26: A->B:+1 [A:][B:+1-2+2-3+3][C:-1]
27: C->B:-1 [A:][B:-1+1-2+2-3+3][C:]
------------- [大功告成] -------------
\$ cat 3.txt
0: ------> [A:-1+1-2+2-3+3][B:][C:]
1: A->C:-1 [A:+1-2+2-3+3][B:][C:-1]
2: A->C:+1 [A:-2+2-3+3][B:][C:+1-1]
3: A->B:-2 [A:+2-3+3][B:-2][C:+1-1]
4: A->B:+2 [A:-3+3][B:+2-2][C:+1-1]
5: C->B:+1 [A:-3+3][B:+1+2-2][C:-1]
6: C->B:-1 [A:-3+3][B:-1+1+2-2][C:]
7: A->C:-3 [A:+3][B:-1+1+2-2][C:-3]
8: B->A:-1 [A:-1+3][B:+1+2-2][C:-3]
9: B->A:+1 [A:+1-1+3][B:+2-2][C:-3]
10: B->C:+2 [A:+1-1+3][B:-2][C:+2-3]
11: B->C:-2 [A:+1-1+3][B:][C:-2+2-3]
12: A->C:+1 [A:-1+3][B:][C:+1-2+2-3]
13: A->C:-1 [A:+3][B:][C:-1+1-2+2-3]
14: A->B:+3 [A:][B:+3][C:-1+1-2+2-3]
15: C->B:-1 [A:][B:-1+3][C:+1-2+2-3]
16: C->B:+1 [A:][B:+1-1+3][C:-2+2-3]
17: C->A:-2 [A:-2][B:+1-1+3][C:+2-3]
18: C->A:+2 [A:+2-2][B:+1-1+3][C:-3]
19: B->A:+1 [A:+1+2-2][B:-1+3][C:-3]
20: B->A:-1 [A:-1+1+2-2][B:+3][C:-3]
21: C->B:-3 [A:-1+1+2-2][B:-3+3][C:]
22: A->C:-1 [A:+1+2-2][B:-3+3][C:-1]
23: A->C:+1 [A:+2-2][B:-3+3][C:+1-1]
24: A->B:+2 [A:-2][B:+2-3+3][C:+1-1]
25: A->B:-2 [A:][B:-2+2-3+3][C:+1-1]
26: C->B:+1 [A:][B:+1-2+2-3+3][C:-1]
27: C->B:-1 [A:][B:-1+1-2+2-3+3][C:]
------------- [大功告成] -------------
``````