多个水壶的情况

昨天的文章中,我们的算法只处理前两个水壶。现在让我们修改算法,处理输入的所有水壶。下面就是修改后的Water.cs

 1: using System;
 2: using System.IO;
 3: using Skyiv.Extensions;
 4: 
 5: namespace Skyiv.Ben.Pond
 6: {
 7:   sealed class Water
 8:   {
 9:     TextWriter writer; // 往哪写?
10:     int limit;         // 解决方案的步数限制
11:     int target;        // 要达到的目标
12:     Kettle[] kettles;  // 水壶们: 最少两个
13:     
14:     public Water(TextWriter writer, int limit, int target, params int[] capacitys)
15:     { // 构造函数
16:       this.writer = writer;
17:       this.limit = limit;
18:       this.target = target;
19:       kettles = new Kettle[capacitys.Length];
20:       for (var i = 0; i < capacitys.Length; i++)
21:         kettles[i] = new Kettle(((char)('A' + i)).ToString(), capacitys[i]);
22:     }
23:     
24:     public void Solve()
25:     { // 寻找解决步骤
26:       writer.Write("步数限制:{0} 目标:{1} 水壶们:", limit, target);
27:       foreach (var kettle in kettles)  writer.Write(kettle);
28:       writer.WriteLine(); // 以上三行输出题目的条件
29:       for (int i = 0, k = 1; ; k = -k)
30:       { // 主循环,算法2
31:         if (k > 0) Solve(++i, kettles[kettles.Length - 1].FullUp);
32:         else Solve(++i, kettles[0].Clean);
33:         for (var j = kettles.Length - 1; j > 0; j--)
34:           Solve(++i, kettles[j].Move, kettles[j - 1]);
35:       }
36:     }
37: 
38:     void Solve(int step, Func<string> func)
39:     { // 适用于无参数动作:倒空水壶、装满水壶
40:       Solve(step, func());
41:     }  
42:     
43:     void Solve(int step, Func<Kettle, string> func, Kettle other)
44:     { // 适用于一个参数的动作:将水倒入另一只壶中
45:       Solve(step, func(other));
46:     }  
47:     
48:     void Solve(int step, string func)
49:     { // 解决步骤的一步
50:       writer.Write("{0,3}: {1}", step, func.ChinesePadRight(14));
51:       foreach (var kettle in kettles) writer.Write(kettle);
52:       writer.WriteLine();
53:       var isFinished = IsFinished();
54:       if (step < limit && !isFinished) return;
55:       if (isFinished) writer.WriteLine("---- 大功告成 ---------------");
56:       else if (step >= limit) writer.WriteLine("**** 出师未捷身先死 ****");
57:       Environment.Exit(0);
58:     }
59:     
60:     bool IsFinished()
61:     { // 是否完成任务?
62:       foreach (var kettle in kettles)
63:         if (kettle.Current == target) return true;
64:       return false;
65:     }
66:   }
67: }

注意,对比昨天的算法1,我们今天的算法2只修改了Water.cs源文件中第 29~35 行的主循环,其余代码都没有变动。其余的 C# 文件也没有改动。我们今天的算法2在主循环中反复执行以下步骤:

  • 装满最后一个水壶。
  • 将水从最后一个水壶依次倒入前一个水壶,直至第一个水壶。
  • 倒空第一个水壶。
  • 将水从最后一个水壶依次倒入前一个水壶,直至第一个水壶。

直到完成任务,或者达到步数限制。可以看出,如果只有两个水壶,这个算法2算法1是一样的。

编译和运行

好了,让我们来编译和运行吧:

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

这是两个水壶的情况,不出所料,运行结果和昨天算法1的一样。 注意在这里我们用&&连接makemono命令,在同一个命令行编译和运行,在调试程序时很方便。如果编译出错的话,后面的运行命令是不会执行的。下面是更多的水壶的运行实例:

Water$ mono ConsoleRunner.exe 8 2 5 7 12
步数限制:20 目标:8 水壶们:[A:0/2][B:0/5][C:0/7][D:0/12]
  1: [装满:D]      [A:0/2][B:0/5][C:0/7][D:12/12]
  2: [从D倒入C:7]  [A:0/2][B:0/5][C:7/7][D:5/12]
  3: [从C倒入B:5]  [A:0/2][B:5/5][C:2/7][D:5/12]
  4: [从B倒入A:2]  [A:2/2][B:3/5][C:2/7][D:5/12]
  5: [倒空:A]      [A:0/2][B:3/5][C:2/7][D:5/12]
  6: [从D倒入C:5]  [A:0/2][B:3/5][C:7/7][D:0/12]
  7: [从C倒入B:2]  [A:0/2][B:5/5][C:5/7][D:0/12]
  8: [从B倒入A:2]  [A:2/2][B:3/5][C:5/7][D:0/12]
  9: [装满:D]      [A:2/2][B:3/5][C:5/7][D:12/12]
 10: [从D倒入C:2]  [A:2/2][B:3/5][C:7/7][D:10/12]
 11: [从C倒入B:2]  [A:2/2][B:5/5][C:5/7][D:10/12]
 12: [从B倒入A:0]  [A:2/2][B:5/5][C:5/7][D:10/12]
 13: [倒空:A]      [A:0/2][B:5/5][C:5/7][D:10/12]
 14: [从D倒入C:2]  [A:0/2][B:5/5][C:7/7][D:8/12]
---- 大功告成 ---------------

要注意的是,这个算法2同昨天的算法1一样,也不是一定可以找到解答的。如果找到解答,也不一定是最优的。