上篇文章中的算法3在给定问题有解的情况下一定可以找到解答,但它给出的解答的操作步骤不一定是最少的。 现在让我们来看看算法4吧。

水(Water.cs)

  1: using System;
  2: using System.IO;
  3: using System.Linq;
  4: using System.Diagnostics;
  5: using System.Collections.Generic;
  6: using Skyiv.Extensions;
  7: 
  8: namespace Skyiv.Ben.Pond
  9: {
 10:   sealed class Water
 11:   {
 12:     TextWriter writer;    // 往哪写?
 13:     int target;           // 要达到的目标
 14:     Kettle[] kettles;     // 水壶们: 最少两个
 15:     List<string> actions; // 记录解答步骤的列表
 16:     List<int[]> currents; // 记录各水壶水量的列表
 17:     
 18:     public Water(TextWriter writer, int limit, int target, params int[] capacitys)
 19:     { // 构造函数:本算法无视步数限制,所以忽略了(limit)参数
 20:       this.writer = writer;
 21:       this.target = target;
 22:       if (target < 0) throw new ArgumentException("目标水量不能小于零");
 23:       kettles = new Kettle[capacitys.Length];
 24:       for (var i = 0; i < capacitys.Length; i++)
 25:       {
 26:         if (capacitys[i] < 0) throw new ArgumentException("水壶的容量不能小于零");
 27:         kettles[i] = new Kettle(((char)('A' + i)).ToString(), capacitys[i]);
 28:       }
 29:       actions = new List<string>();
 30:       currents = new List<int[]>();
 31:     }
 32:     
 33:     public void Solve()
 34:     { // 算法4:只使用前两只水壶,试图寻找最少操作步骤的解
 35:       Trace.Listeners.Add(new TextWriterTraceListener(writer)); // -d:TRACE
 36:       writer.Write("目标:{0} 水壶们:", target);
 37:       foreach (var kettle in kettles)  writer.Write(kettle);
 38:       writer.WriteLine(); // 以上三行输出题目的条件
 39:       if (HasSolution())
 40:       {
 41:         var n = GetTargetKettle();
 42:         var count = Solve(n < 0 ? 0 : n);
 43:         if (n < 0 && count < Solve(1)) Solve(0);
 44:         Report();
 45:       }
 46:       else writer.WriteLine("*** 无解(本算法仅使用前两个水壶) ***");
 47:     }
 48:     
 49:     int Solve(int n)
 50:     { // 寻找解决方案,返回所需操作步骤的数目
 51:       SetTargetKettle(n);
 52:       while (!kettles[0].IsEmpty || !kettles[1].IsEmpty)
 53:       { // 往回倒推,如果最后得到两只空壶就成功了
 54:         Trace.Assert(kettles[0].IsEmpty || kettles[1].IsEmpty);// 刚好一壶为空
 55:         if (kettles[1].IsEmpty && kettles[0].IsFull) { Clean(0); break; }
 56:         if (kettles[0].IsEmpty && kettles[1].IsFull) { Clean(1); break; }
 57:         int i = kettles[0].IsEmpty ? 0 : 1, j = 1 - i;
 58:         FullUp(i); // 挑选一只空壶,装满之 (此时必有一壶为空,另一壶不空也不满)
 59:         while (!kettles[i].IsEmpty)
 60:         { // 从刚装满的壶倒入另一壶,直到本壶为空
 61:           Move(i, j);
 62:           if (kettles[j].IsFull) Clean(j); // 如另一壶满了,则倒空之
 63:         }
 64:       }
 65:       return StepCount();
 66:     }
 67:     
 68:     bool HasSolution()
 69:     { // 检查是否有解
 70:       var imax = (kettles[0].Capacity > kettles[1].Capacity) ? 0 : 1;
 71:       var gcd = MathExtensions.Gcd(kettles[0].Capacity, kettles[1].Capacity);
 72:       return (gcd == 0 || target %  gcd == 0) && target <= kettles[imax].Capacity;
 73:     }
 74:     
 75:     int GetTargetKettle()
 76:     { // 目标水量应设置到哪只壶里? (-1)表示未定
 77:       var min = (kettles[0].Capacity < kettles[1].Capacity) ? 0 : 1;
 78:       return (target > kettles[min].Capacity) ? (1 - min)
 79:         : (target == 0 || target == kettles[min].Capacity) ? min : -1;
 80:     }
 81:     
 82:     void SetTargetKettle(int n)
 83:     { // 设置(n)壶的水量为目标水量,并做些准备工作
 84:       kettles[n].FullUp();
 85:       kettles[n].Move(new Kettle(null, kettles[n].Capacity - target));
 86:       actions.Clear();
 87:       currents.Clear();
 88:       Mark(null); // 记录最终完成时的各水壶的水量
 89:     }
 90:     
 91:     int StepCount()
 92:     { // 返回操作步骤的数目
 93:       var i = Math.Max(0, actions.Count - 1);
 94:       while (i >= 0 && currents[i][0] != target && currents[i][1] != target) i--;
 95:       return actions.Count - i;
 96:     }
 97: 
 98:     void FullUp(int n)
 99:     { // 倒推步骤:装满(n)壶,解答步骤:倒空(n)壶
100:       kettles[n].FullUp();
101:       Mark("倒空" + kettles[n].Name);
102:     }
103:     
104:     void Clean(int n)
105:     { // 倒推步骤:倒空(n)壶,解答步骤:装满(n)壶
106:       kettles[n].Clean();
107:       Mark("装满" + kettles[n].Name);
108:     }
109:     
110:     void Move(int n, int m)
111:     { // 倒推步骤:从(n)壶倒入(m)壶,解答步骤:从(m)壶倒入(n)壶
112:       kettles[n].Move(kettles[m]);
113:       Mark("从" + kettles[m].Name + "倒入" + kettles[n].Name);
114:     }
115:     
116:     void Mark(string action)
117:     { // 记录当前步骤和各水壶的水量
118:       if (action != null) actions.Add(action);
119:       currents.Add(kettles.Select(x => x.Current).ToArray());
120:     }
121:     
122:     void Report()
123:     { // 报告解答步骤
124:       for (var i = actions.Count - 1; i >= 0; i--)
125:       {
126:         writer.Write("{0, 3}: ", actions.Count - i);
127:         writer.Write("{0} (", actions[i].ChinesePadRight(8));
128:         foreach (var current in currents[i]) writer.Write("{0,2} ", current);
129:         writer.WriteLine(")"); // 下一行不是必须的,只是为了缩短解答步骤
130:         if (currents[i][0] == target || currents[i][1] == target) break;
131:       }
132:       writer.WriteLine("---- 大功告成 --------");
133:     }
134:   }
135: }

这个Water类的核心内容其实还是算法3的那一套,也是往回倒推,大部分内容都是相同的。

  • 第 68~73 行的HasSolution方法检查是否有解。
  • 第 75~80 行的GetTargetKettle方法决定目标水量应设置到哪只壶里。
    • 如果目标水量大于小壶的容量,则只能设置到大壶里。(第 78 行)
    • 如果目标水量等于零或者等于小壶的容量,则设置到小壶里。(第 79 行)
    • 否则目标水量就一定大于零而小于小壶的容量,我们无法决定应该设置到哪只壶里。(第 79 行)
  • 第 82~89 行的SetTargetKettle方法设置指定的壶的水量为目标水量,然后清除记录解答步骤和各水壶水量的列表、记录最终完成时各水壶的水量。
  • 第 91~96 行的StepCount计算已经求解出来的操作步骤的数目。(我怀疑运行到第 95 行时i值总是 1 或者 0(当 actions.Count == 0 时),不过没有证据)
  • 第 33~47 行的Solve方法是主控程序,根据需要调用后面的重载的Solve方法 0~3 次,然后报告运行结果。
    • 如果判断出给定的问题无解,则直接报告。(第 39 行、第 46 行)
    • 否则,先获取目标水量应设置到哪只壶里。(第 41 行)
    • 如果明确知道目标水量应设置到哪只壶里,直接调用重载的Solve方法解答之。(第 42 行)
    • 否则,先试着将目标水量设置到到第一只壶中,调用重载的Solve方法得到操作步骤的数目。(第 42 行)
    • 接着试着将目标水量设置到第二只壶中,再次调用重载的Solve方法得到操作步骤的数目。(第 43 行)
    • 如果前者小于后者,只好第三次调用重载的Solve方法以得到前者对应的操作步骤。(第 43 行)
    • 否则就没有必要再干什么了,直接报告答案就行了。(第 44 行)
  • 第 49~66 行的重载的Solve方法基本上和算法3中相同。只不过在往回倒推之前先设置目标水量到指定的壶中,计算完毕后再返回操作步骤的数目给调用者。
  • 这个程序的其他方面和算法3是一样的。

编译和运行

Water$ make
dmcs -out:ConsoleRunner.exe -d:TRACE ConsoleRunner.cs Water.cs Kettle.cs StringExtensions.cs MathExtensions.cs
$ mono ConsoleRunner.exe 3 5 6
目标:3 水壶们:[A:0/5][B:0/6]
  1: 装满A    ( 5  0 )
  2: 从A倒入B ( 0  5 )
  3: 装满A    ( 5  5 )
  4: 从A倒入B ( 4  6 )
  5: 倒空B    ( 4  0 )
  6: 从A倒入B ( 0  4 )
  7: 装满A    ( 5  4 )
  8: 从A倒入B ( 3  6 )
---- 大功告成 --------

可以看到,同样的输入条件(目标水量 3,水壶容量分别为 5 和 6),本算法只需要 8 步,而算法3需要 10 步。再看一个例子:

$ mono ConsoleRunner.exe 3 4 7
目标:3 水壶们:[A:0/4][B:0/7]
  1: 装满B    ( 0  7 )
  2: 从B倒入A ( 4  3 )
---- 大功告成 --------

从上面两个例子中可以看出,在目标水量大于零而小于小壶容量的情况下,为了求得最少操作步骤的解,有时需要将目标水量设置到大壶中,有时又需要将目标水量设置到小壶中。