水（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：只使用前两只水壶，试图寻找最少操作步骤的解
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);
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);
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: }
``````

• 第 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

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 )
---- 大功告成 --------
``````

``````\$ mono ConsoleRunner.exe 3 4 7

1: 装满B    ( 0  7 )
2: 从B倒入A ( 4  3 )
---- 大功告成 --------
``````