2gua 今天上午在第三波 - 编程赢取《精益创业实战》中发布以下编码任务:


假设有一个池塘,里面有无穷多的水。现有2个空水壶,容积分别为5升和6升。如何只用这2个水壶从池塘里取得3升的水(最后,这三升水,在其中一个壶里)
用你熟悉的语言编码实现,代码极客、高效为评判依据。


我试着用 C# 语言编程解答。

水壶(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:     
11:     public Kettle(string name, int capacity)
12:     { // 构造函数
13:       Name = name;
14:       Capacity = capacity;
15:     }
16:     
17:     public string Clean()
18:     { // 倒空水壶
19:       Current = 0;
20:       return string.Format("[倒空:{0}]", Name);
21:     }
22:     
23:     public string FullUp()
24:     { // 装满水壶
25:       Current = Capacity;
26:       return string.Format("[装满:{0}]", Name);
27:     }
28:     
29:     public string Move(Kettle other)
30:     { // 将水倒入另一只壶中,直至本壶空或另一壶满
31:       var value = Math.Min(Current, other.Capacity - other.Current);
32:       Current -= value;
33:       other.Current += value;
34:       return string.Format("[从{0}倒入{1}:{2}]", Name, other.Name, value);
35:     }
36:     
37:     public override string ToString()
38:     { // 报告水壶自身的状态
39:       return string.Format("[{0}:{1}/{2}]" , Name, Current, Capacity);
40:     }
41:   }
42: }

这个水壶太简单,没什么需要解释的。

水(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 (var i = 0; ; )
30:       { // 主循环,算法1
31:         Solve(++i, kettles[1].FullUp);
32:         Solve(++i, kettles[1].Move, kettles[0]);
33:         Solve(++i, kettles[0].Clean);
34:         Solve(++i, kettles[1].Move, kettles[0]);
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: }

这个也很简单,我们的算法体现在第 29~35 行的主循环中,就是反复执行以下步骤:

  • 装满B水壶
  • 将水从B水壶倒入A水壶
  • 倒空A水壶
  • 将水从B水壶倒入A水壶

直到完成任务,或者达到步数限制。

控制台主程序(ConsoleRunner.cs)

 1: using System;
 2: 
 3: namespace Skyiv.Ben.Pond
 4: {
 5:   static class ConsoleRunner
 6:   {
 7:     static void Main(string[] args)
 8:     { // 解决水壶问题的主程序
 9:       int k = 0, limit = 20;
10:       if (args.Length > k && args[k].StartsWith(":"))
11:         limit = int.Parse(args[k++].Substring(1));
12:       if (args.Length - k <= 2) { Usage(); return; }
13:       var target = int.Parse(args[k++]);
14:       var capacitys = new int[args.Length - k];
15:       for (var i = 0; i < capacitys.Length; i++)
16:         capacitys[i] = int.Parse(args[k + i]);
17:       new Water(Console.Out, limit, target, capacitys).Solve();
18:     }
19:     
20:     static void Usage()
21:     { // 报告本程序的使用方法
22:       Console.WriteLine("ConsoleRunner [:limit] target capacity1 capacity2 ...");
23:     }
24:   }
25: }

这个控制台主程序更简单了。就是读取命令行参数,然后调用 Water 类的 Solve 方法解决问题。注意以下几点:

  • 我们的程序叫 ConsoleRunner,说明以后有可能搞一个 GraphicRunner 。
  • 命令行参数用于指定步数限制(可选)目标各水壶的容量
  • 这说明目标水量和各水壶的容量都可以由我们指定,而且水壶可以多于两个。
  • 但我们目前的算法只用到前两个水壶,对多余的水壶(如果有的话)不理不睬。

扩展方法(StringExtensions.cs)

 1: using System.Text;
 2: 
 3: namespace Skyiv.Extensions
 4: {
 5:   public static class StringExtensions
 6:   {
 7:     static readonly Encoding Encode = Encoding.GetEncoding("GB18030");
 8:   
 9:     public static string ChinesePadRight(this string str, int count)
10:     { // 对齐汉字字符串,右补空格
11:       return Encode.GetString(Encode.GetBytes(str.PadRight(count)), 0, count);
12:     }
13:   }
14: }

这个不用解释了吧?就是对齐汉字字符串。Microsoft .NET Framework Base Class Library 自带的string.PadRight只能对齐半角字符,对全角字符无效。

编译文件(Makefile)

CSC = dmcs

ConsoleRunner.exe : ConsoleRunner.cs Water.cs Kettle.cs StringExtensions.cs
    $(CSC) -out:$@ ConsoleRunner.cs Water.cs Kettle.cs StringExtensions.cs

编译和运行

在 Arch Linux 64-bit 操作系统的 Mono 2.10.8 环境下编译和运行:

Water$ make
dmcs -out:ConsoleRunner.exe ConsoleRunner.cs Water.cs Kettle.cs StringExtensions.cs
Water$ mono ConsoleRunner.exe
ConsoleRunner [:limit] target capacity1 capacity2 ...

上面是使用make编译,然后运行我们的程序,得知用法是需要在命令行参数指定步数限制(可选)目标各水壶的容量。好吧,我们给出命令行参数 3、5 和 6 来调用该程序:

Water$ mono ConsoleRunner.exe 3 5 6
步数限制: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]
---- 大功告成 ---------------

这就成功了。

算法的有效性

我们的算法对两个水壶的情况还是很有效的(水壶B的容量必须大于水壶A的容量)。试看以下运行结果:

目标(0)

Water$ mono ConsoleRunner.exe 0 5 6
步数限制:20 目标:0 水壶们:[A:0/5][B:0/6]
  1: [装满:B]      [A:0/5][B:6/6]
---- 大功告成 ---------------

注意,我们的算法有一个小小的缺陷。因为在目标(0)的情况下,不用做任何事就已经完成了任务。而我们多余地装满了B水壶。

目标(1)

Water$ mono ConsoleRunner.exe 1 5 6
步数限制:20 目标:1 水壶们:[A:0/5][B:0/6]
  1: [装满:B]      [A:0/5][B:6/6]
  2: [从B倒入A:5]  [A:5/5][B:1/6]
---- 大功告成 ---------------

目标(2)

Water$ mono ConsoleRunner.exe 2 5 6
步数限制:20 目标:2 水壶们:[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]
---- 大功告成 ---------------

目标(3)

Water$ mono ConsoleRunner.exe 3 5 6
步数限制: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]
---- 大功告成 ---------------

目标(4)

Water$ mono ConsoleRunner.exe 4 5 6
步数限制:20 目标:4 水壶们:[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]
 11: [倒空:A]      [A:0/5][B:3/6]
 12: [从B倒入A:3]  [A:3/5][B:0/6]
 13: [装满:B]      [A:3/5][B:6/6]
 14: [从B倒入A:2]  [A:5/5][B:4/6]
---- 大功告成 ---------------

目标(5)

Water$ mono ConsoleRunner.exe 5 5 6
步数限制:20 目标:5 水壶们:[A:0/5][B:0/6]
  1: [装满:B]      [A:0/5][B:6/6]
  2: [从B倒入A:5]  [A:5/5][B:1/6]
---- 大功告成 ---------------

从这可以看出,我们目前的算法不是最高效的。实际上目标(5)只需装满A水壶这一步就行了,用不着两步。

目标(6)

Water$ mono ConsoleRunner.exe 6 5 6
步数限制:20 目标:6 水壶们:[A:0/5][B:0/6]
  1: [装满:B]      [A:0/5][B:6/6]
---- 大功告成 ---------------

目标(7)

Water$ mono ConsoleRunner.exe 7 5 6 3
步数限制:20 目标:7 水壶们:[A:0/5][B:0/6][C:0/3]
  1: [装满:B]      [A:0/5][B:6/6][C:0/3]
  2: [从B倒入A:5]  [A:5/5][B:1/6][C:0/3]
  3: [倒空:A]      [A:0/5][B:1/6][C:0/3]
  4: [从B倒入A:1]  [A:1/5][B:0/6][C:0/3]
  5: [装满:B]      [A:1/5][B:6/6][C:0/3]
  6: [从B倒入A:4]  [A:5/5][B:2/6][C:0/3]
  7: [倒空:A]      [A:0/5][B:2/6][C:0/3]
  8: [从B倒入A:2]  [A:2/5][B:0/6][C:0/3]
  9: [装满:B]      [A:2/5][B:6/6][C:0/3]
 10: [从B倒入A:3]  [A:5/5][B:3/6][C:0/3]
 11: [倒空:A]      [A:0/5][B:3/6][C:0/3]
 12: [从B倒入A:3]  [A:3/5][B:0/6][C:0/3]
 13: [装满:B]      [A:3/5][B:6/6][C:0/3]
 14: [从B倒入A:2]  [A:5/5][B:4/6][C:0/3]
 15: [倒空:A]      [A:0/5][B:4/6][C:0/3]
 16: [从B倒入A:4]  [A:4/5][B:0/6][C:0/3]
 17: [装满:B]      [A:4/5][B:6/6][C:0/3]
 18: [从B倒入A:1]  [A:5/5][B:5/6][C:0/3]
 19: [倒空:A]      [A:0/5][B:5/6][C:0/3]
 20: [从B倒入A:5]  [A:5/5][B:0/6][C:0/3]
**** 出师未捷身先死 ****

这下失败了。但是这不是我们算法的错,因为这个任务是无论如何都是无法完成的。注意:我们这次给了三个水壶,虽然实际上我们的算法没用到第三个水壶。

算法的改进

目前的算法只处理前两个水壶,对多余的水壶(如果有的话)不理不睬。请移步下一篇文章:可以处理更多水壶的算法