双重河内塔

《具体数学:计算机科学基础(第2版)》第 1 章作业题 11:

双重河内塔包含 2n 个圆盘,它们有 n 种不同的尺寸,每一种尺寸的圆盘有两个。如通常那样,要求每次只能移动一个圆盘,且不能把较大的圆盘放在较小的圆盘上面。

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

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

根据书上的答案,求解问题 a 有一种算法,求解问题 b 有两种算法。请参见我上个月发表的文章“双重河内塔”。让我们写 C# 程序来实现这些算法吧。

主程序

下面就是主程序 Runner.cs:

 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 个命令参数指定使用何种算法,第 2 个命令行参数指定圆盘的种类数。

双重河内塔

表示双重河内塔的 Tower.cs:

  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 方法将双重河内塔表示为字符串。

桩柱

表示桩柱的 Peg.cs:

 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(); } }
10:     readonly int id;
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 将本桩柱表示为字符串。

圆盘

表示圆盘的 Disk.cs:

 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 方法将圆盘表示为字符串。

配置

配置 Configuration.cs:

 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;
11:     public readonly Size BitmapSize;
12:     public readonly Font Font;
13:     public readonly Brush BackgroundBrush = new SolidBrush(Color.LightGray);
14:     public readonly Pen PegPen;
15:     public readonly Pen[] DiskPens;
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: }

这个类表示画出双重河内塔所需的各种参数。第 17~31 行的构造函数根据圆盘种类数计算出相应的参数。

扩展方法

扩展方法 DirecoryInfoExtensions.cs:

 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: }

第 7~11 行的 CleanAndCreate 扩展方法创建一个空目录,如果该目录已经存在则先删除之。

Makefile

供 make 工具使用的 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)

编译和运行

在 Arch Linux 操作系统 Mono 环境下编译和运行:

$ 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:]
------------- [大功告成] -------------

1

双重河内塔”这篇文章中的图就是用这个程序画出来的。


ConcreteMath