前两天的算法1算法2分别处理两个和多个水壶的情况,但都是有缺陷的,它们并不保证在给定的问题有解的情况下一定能够找到解答。今天我们要介绍的算法3只能处理两只水壶,但是它在给定的问题有解的情况下一定可以找到解答。

水壶(Kettle.cs)

 1: using System;
 2: 
 3: namespace Skyiv.Ben.Pond
 4: {
 5:   sealed class Kettle
 6:   {
 7:     public string Name { get; private set; }  // 水壶的名称
 8:     public int Capacity { get; private set; } // 最大容量
 9:     public int Current { get; private set; }  // 当前水量
10:     public bool IsEmpty { get { return Current == 0; } }
11:     public bool IsFull { get { return Current == Capacity; } }
12:     
13:     public Kettle(string name, int capacity)
14:     { // 构造函数
15:       Name = name;
16:       Capacity = capacity;
17:     }
18:     
19:     public void Clean()
20:     { // 倒空水壶
21:       Current = 0;
22:     }
23:     
24:     public void FullUp()
25:     { // 装满水壶
26:       Current = Capacity;
27:     }
28:     
29:     public void Move(Kettle other)
30:     { // 将水倒入另一只壶中,直至本壶空或另一壶满
31:       var value = Math.Min(Current, other.Capacity - other.Current);
32:       Current -= value;
33:       other.Current += value;
34:     }
35:     
36:     public override string ToString()
37:     { // 报告水壶自身的状态
38:       return string.Format("[{0}:{1}/{2}]" , Name, Current, Capacity);
39:     }
40:   }
41: }

这个新的水壶类Kettle较以前有了小小的修改:

  • 增加了IsEmptyIsFull两个属性(第 10~11 行)。这只是为了方便,因为它们都是其他属性的计算结果。
  • 表现水壶合法动作的三个方法(CleanFullUpMove)原来的返回值是表示其动作的字符串,现改为没有返回值,这更符合语义了。原来是为了简化算法才返回表示其自身动作的字符串的。

所以说,这个水壶类不做修改也行的,只不过算法更繁琐一点罢了。

水(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:     }
 30:     
 31:     public void Solve()
 32:     { // 寻找解决步骤
 33:       Trace.Listeners.Add(new TextWriterTraceListener(writer)); // -d:TRACE
 34:       writer.Write("目标:{0} 水壶们:", target);
 35:       foreach (var kettle in kettles)  writer.Write(kettle);
 36:       writer.WriteLine(); // 以上三行输出题目的条件
 37:       Initialize();
 38:       while (!kettles[0].IsEmpty || !kettles[1].IsEmpty)
 39:       { // 算法3(只使用前两只水壶):往回倒推,如果最后得到两只空壶就成功了
 40:         Trace.Assert(kettles[0].IsEmpty || kettles[1].IsEmpty);// 刚好一壶为空
 41:         if (kettles[1].IsEmpty && kettles[0].IsFull) { Clean(0); break; }
 42:         if (kettles[0].IsEmpty && kettles[1].IsFull) { Clean(1); break; }
 43:         int i = kettles[0].IsEmpty ? 0 : 1, j = 1 - i;
 44:         FullUp(i); // 挑选一只空壶,装满之 (此时必有一壶为空,另一壶不空也不满)
 45:         while (!kettles[i].IsEmpty)
 46:         { // 从刚装满的壶倒入另一壶,直到本壶为空
 47:           Move(i, j);
 48:           if (kettles[j].IsFull) Clean(j); // 如另一壶满了,则倒空之
 49:         }
 50:       }
 51:       Report();
 52:     }
 53:     
 54:     void Initialize()
 55:     { // 检查是否有解,并设置某只水壶的水量为目标水量
 56:       actions = new List<string>();
 57:       currents = new List<int[]>();
 58:       var imax = (kettles[0].Capacity > kettles[1].Capacity) ? 0 : 1;
 59:       var gcd = MathExtensions.Gcd(kettles[0].Capacity, kettles[1].Capacity);
 60:       if (gcd != 0 && target %  gcd != 0 || target > kettles[imax].Capacity)
 61:       {
 62:         writer.WriteLine("*** 无解(本算法仅使用前两个水壶) ***");
 63:         Environment.Exit(0);
 64:       }
 65:       kettles[imax].FullUp(); // 本行和下一行用于设置某只水壶的水量为目标水量
 66:       kettles[imax].Move(new Kettle(null, kettles[imax].Capacity - target));
 67:       Mark(null); // 记录最终完成时各水壶的水量
 68:     }
 69:     
 70:     void FullUp(int n)
 71:     { // 倒推步骤:装满(n)壶,解答步骤:倒空(n)壶
 72:       kettles[n].FullUp();
 73:       Mark("倒空" + kettles[n].Name);
 74:     }
 75:     
 76:     void Clean(int n)
 77:     { // 倒推步骤:倒空(n)壶,解答步骤:装满(n)壶
 78:       kettles[n].Clean();
 79:       Mark("装满" + kettles[n].Name);
 80:     }
 81:     
 82:     void Move(int n, int m)
 83:     { // 倒推步骤:从(n)壶倒入(m)壶,解答步骤:从(m)壶倒入(n)壶
 84:       kettles[n].Move(kettles[m]);
 85:       Mark("从" + kettles[m].Name + "倒入" + kettles[n].Name);
 86:     }
 87:     
 88:     void Mark(string action)
 89:     { // 记录当前步骤和各水壶的水量
 90:       if (action != null) actions.Add(action);
 91:       currents.Add(kettles.Select(x => x.Current).ToArray());
 92:     }
 93:     
 94:     void Report()
 95:     { // 报告解答步骤
 96:       for (var i = actions.Count - 1; i >= 0; i--)
 97:       {
 98:         writer.Write("{0, 3}: ", actions.Count - i);
 99:         writer.Write("{0} (", actions[i].ChinesePadRight(8));
100:         foreach (var current in currents[i]) writer.Write("{0,2} ", current);
101:         writer.WriteLine(")"); // 下一行不是必须的,只是为了缩短解答步骤
102:         if (currents[i][0] == target || currents[i][1] == target) break;
103:       }
104:       writer.WriteLine("---- 大功告成 --------");
105:     }
106:   }
107: }

这个Water类是算法的核心。 程序中已经有很好的注释了,现就算法的思路解释如下:

  • 我们的算法3只处理前两只水壶,忽略输入条件中的其他水壶(如果有的话)。
  • 如果目标水量在大水壶的容量之内并且是两只水壶容量的最大公约数的整数倍则问题有解,否则无解。(第 58~64 行)。
  • 本算法采用倒推法来解答,首先设置某只水壶的水量为目标水量,然后一步步往回倒推,如果最后得到两只空壶就成功了。
  • 程序中第 65~66 行就是用于设置某只水壶的水量为目标水量的。它先装满目标水壶,然后再将水倒一些到一个虚拟的恰当容量的水壶中去。使用这个巧妙的方法,就不用给Kettle类增加设置水量的方法了。
  • 由于采用倒推法,所以需要记录解答步骤以及各水壶的水量。第 15~16 行的实例字段就是干这个的,它们在第 56~57 行被初始化。第 88~92 行的Mark方法就是用来记录当前步骤和各水壶的水量的。
  • 第 67 行首先记录最终完成时的各水壶的水量。注意,这时没有记录解答步骤(还没开始解答呢)。这使得actionscurrents错开一位,正好符合我们的要求,因为倒推时解答步骤和水量正好是错开一位的。
  • 第 38~50 行的主循环是本算法的关键,它负责具体实施倒推的步骤。
    • 正如前面说过的,循环的结束条件是两只水壶均为空。(第 38 行)
    • 在主循环中,刚好有一只水壶为空(第 45~49 行的内层循环不算)。这体现为第 40 行的断言语句。
    • 如果一壶空,另一壶满,则倒空之,大功告成。(第 41~42 行)
    • 否则,必有一壶为空,另一壶不空也不满,则装满空壶。(第 43~44 行)
    • 然后从刚装满的壶倒入另一壶,直到本壶为空。其间如果另一壶满了,则倒空之。(第 45~49 行)
    • 请注意在这个主循环中并不是所有的动作都是合法的,要小心。有些动作,比如倒空一个未满的水壶,在算法1算法2中可以做,但在本算法的这个主循环中是不能做的。因为这是倒推步骤中的动作,它相当于正向步骤中的向水壶中加水但没加满,这是不允许的。未满的水壶只能由另一个水壶向它倒水得到,完成倒水动作后另一个水壶必定是空壶。
  • 第 70~86 行的三个和Kettle类同名的方法(FullUpCleanMove)的作用也相同,只不过是倒推过程的动作而已,并且还记录解答步骤。
  • 第 94~105 行的Report方法从记录的解答步骤中倒着报告出来。

扩展方法(MathExtensions.cs)

 1: namespace Skyiv.Extensions
 2: {
 3:   public static class MathExtensions
 4:   {
 5:     public static int Gcd(int a, int b)
 6:     { // 返回 a 和 b 的最大公约数
 7:       for (int t; b != 0; a = b, b = t) t = a % b;
 8:       return a;
 9:     }
10:   }
11: }

这就是求最大公约数的欧几里得辗转相除法,你懂的。 :)

算法3的正确性

上面的Gcd方法的使用减法而不使用除法的版本如下(也是欧几里得的贡献):

1:     public static int Gcd(int a, int b)
2:     { // 返回 a 和 b 的最大公约数
3:       if (a == 0) return b;
4:       while (b != 0)
5:         if (a > b) a -= b;
6:         else b -= a;
7:       return a;
8:     }

把第 4~6 行的循环和前面的Water类中第 45~49 行的内层循环对比,就会明白算法3为什么是正确的了。因为算法3只要能够在有限步结束而不陷入死循环,就表示找到一个解答。这里的减法就对应着算法3中的倒水的动作。

编译文件(Makefile)

CSC = dmcs
OPT = -d:TRACE
SRC = ConsoleRunner.cs Water.cs Kettle.cs StringExtensions.cs MathExtensions.cs

ConsoleRunner.exe : $(SRC)
    $(CSC) -out:$@ $(OPT) $(SRC)

在上述文件中:

  • 这里的 -d:TRACE 定义了一个宏,为的是前面的断言语句,请参见前面的Water.cs中第 33 行和第 40 行。如果不定义这个宏,前面的第 40 行语句是不起作用的。
  • 其余的 C# 程序(ConsoleRunner.csStringExtensions.cs)均没有修改,请参见前两篇文章。

编译和运行

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

可以看出,这个结果和算法1算法2一样。继续看几个结果:

Water$ mono ConsoleRunner.exe 3 5 7
目标:3 水壶们:[A:0/5][B:0/7]
  1: 装满B    ( 0  7 )
  2: 从B倒入A ( 5  2 )
  3: 倒空A    ( 0  2 )
  4: 从B倒入A ( 2  0 )
  5: 装满B    ( 2  7 )
  6: 从B倒入A ( 5  4 )
  7: 倒空A    ( 0  4 )
  8: 从B倒入A ( 4  0 )
  9: 装满B    ( 4  7 )
 10: 从B倒入A ( 5  6 )
 11: 倒空A    ( 0  6 )
 12: 从B倒入A ( 5  1 )
 13: 倒空A    ( 0  1 )
 14: 从B倒入A ( 1  0 )
 15: 装满B    ( 1  7 )
 16: 从B倒入A ( 5  3 )
---- 大功告成 --------
Water$ mono ConsoleRunner.exe 7 9 2
目标:7 水壶们:[A:0/9][B:0/2]
  1: 装满A    ( 9  0 )
  2: 从A倒入B ( 7  2 )
---- 大功告成 --------
Water$ mono ConsoleRunner.exe 0 0 0
目标:0 水壶们:[A:0/0][B:0/0]
---- 大功告成 --------

还有无解的情况:

Water$ mono ConsoleRunner.exe 3 6 10 3
目标:3 水壶们:[A:0/6][B:0/10][C:0/3]
*** 无解(本算法仅使用前两个水壶) ***
Water$ mono ConsoleRunner.exe 7 5 6 7
目标:7 水壶们:[A:0/5][B:0/6][C:0/7]
*** 无解(本算法仅使用前两个水壶) ***

最后再来个步骤比较多的:

Water$ mono ConsoleRunner.exe 9 8 15
目标:9 水壶们:[A:0/8][B:0/15]
  1: 装满B    ( 0 15 )
  2: 从B倒入A ( 8  7 )
  3: 倒空A    ( 0  7 )
  4: 从B倒入A ( 7  0 )
  5: 装满B    ( 7 15 )
  6: 从B倒入A ( 8 14 )
  7: 倒空A    ( 0 14 )
  8: 从B倒入A ( 8  6 )
  9: 倒空A    ( 0  6 )
 10: 从B倒入A ( 6  0 )
 11: 装满B    ( 6 15 )
 12: 从B倒入A ( 8 13 )
 13: 倒空A    ( 0 13 )
 14: 从B倒入A ( 8  5 )
 15: 倒空A    ( 0  5 )
 16: 从B倒入A ( 5  0 )
 17: 装满B    ( 5 15 )
 18: 从B倒入A ( 8 12 )
 19: 倒空A    ( 0 12 )
 20: 从B倒入A ( 8  4 )
 21: 倒空A    ( 0  4 )
 22: 从B倒入A ( 4  0 )
 23: 装满B    ( 4 15 )
 24: 从B倒入A ( 8 11 )
 25: 倒空A    ( 0 11 )
 26: 从B倒入A ( 8  3 )
 27: 倒空A    ( 0  3 )
 28: 从B倒入A ( 3  0 )
 29: 装满B    ( 3 15 )
 30: 从B倒入A ( 8 10 )
 31: 倒空A    ( 0 10 )
 32: 从B倒入A ( 8  2 )
 33: 倒空A    ( 0  2 )
 34: 从B倒入A ( 2  0 )
 35: 装满B    ( 2 15 )
 36: 从B倒入A ( 8  9 )
---- 大功告成 --------

仔细研究这个例子有助于理解本算法。