用猴子打印《莎士比亚全集》的办法解决字节跳动水壶题

偶然的一次聊天，看到了一道网传的字节跳动面试题，题目是这样的:

原题：给你一个装满水的 8 升满壶和两个分别是 5 升、3 升的空壶，请想个优雅的办法，使得其中一个水壶恰好装 4 升水，每一步的操作只能是倒空或倒满。

也不知道哪来的自信，：），鼓捣了起来。首先想找一下突破点，看了许久… 。一点思路都没有，除了想到这几点:

• 容量是4所以最后不会是三个杯子

• 需要有1个杯子有1这个数字

有点想放弃的时候，想到了那个故事，🐒猴子打印莎士比亚全集：

在科学界一直有一个这样的猜想，让无数只猴子坐在打字机前随机敲击键盘，如果不限定时间，那么它们总有一天会打出一部《莎士比亚全集》。简单地说，在无限的时间面前，当按键次数达到无穷时，猴子也几乎必然能够打出任何给定的文字。

对哇，我可以用代码来模拟倒水，接近无限的随机倒水，在强大的运算速度面前，时间相对也是接近无限的，那必然能运行到其中一个水杯为4升的情况！废话少说，打开IDE创建一个杯子Cup类:

变量capacity作为水杯容量,变量water作为当前水杯的水量，构造器传入这两个变量，简单点get和set方法就先省略了。

Cup.java

  public class Cup {
    final int capacity;
    int water;
    public Cup(int cap, int water) {
        this.capacity = cap;
        this.water = water;
    } 
}

再这个题目中，水杯可以向其他水杯倒水，那再在Cup中添加一个PourWater方法用于倒水。

既然要往其他水杯倒水，那就要知道:

• 要倒入水杯的剩余容量

• 两个水杯的最大容量

• 两个水杯的水量

情况则分为:

• 当前水杯的水 > 要倒入水杯的剩余容量

• 当前水杯的水 <= 要倒入水杯的剩余容量

忽略的情况

• 要倒入的水杯已经满了

• 当前的水杯没有水

这里题目说必须倒满过倒空，我理解为不能倒溢出

public boolean PourWater(Cup toCup) {
      int toCupSurplus = toCup.capacity - toCup.water;
      if (toCupSurplus == 0 || this.water == 0) {
          return false; 
      }
      
      if (toCupSurplus < this.water) { //当前水杯的水大于要倒入水杯的水
          this.water = this.water-toCupSurplus; 
          toCup.water = toCup.capacity;
      } else if (toCupSurplus >= this.water) {
          toCup.water =  toCup.water + this.water;
          this.water = 0;
      }
  return true;
  }

让PourWater返回true/false，为的是检测是否真实执行了倒入了操作。

现在创建Main.java，然后

要做的事

• 创建3杯水对象，对应题目水杯数据

• 实现猴子打印的随机性

• 记录倒水的操作数据

• 监控是否有某一个水杯水量达到了4升

Main.java

public class Main {
    static Cup[] table = new Cup[]{
        new Cup(8, 8),
        new Cup(5, 0),
        new Cup(3, 0)
    };
    static Cup cup_a;
    static Cup cup_b;
    static Cup cup_c;
    static int o = 0;
    static int cup_o = 0;
    
    static ArrayList<String> EffectivePour;

    public static void main(String[] args) {
    cup_a = table[0];
        cup_b = table[1];
        cup_c = table[2];
        EffectivePour = new ArrayList<>();
        while(...){
        ...
        }
    }
}

为了实现随机性，所以吧cup_a丶cup_b丶cup_c水杯对象放入了数组Cup[]中🙉,ArrayList EffectivePour则用于记录操作, o记录循环的次数，cup_o记录实际倒水的次数(所以在Cup类中的PourWater方法中再联动cup_o变量).

差点还忘了还需要一个检查水杯水量是否为4的方法:

private static boolean checkWater() {
        o ++;
        //cup_c.water 其实可以省略
        if (cup_a.water == 4 || cup_b.water == 4 || cup_c.water == 4) {
            System.out.println("已有杯子水量为4,循环共执行了" + o + "次;");
            System.out.println("共执行了倒水" + cup_o + "次;");
            System.out.println("实际有效倒水" + EffectivePour.size() + "次;");
            
            for(String op:EffectivePour){
                System.out.println(op);
            }
            
            return false;
        } else {
            return true;
        }
    }

现在所有的东西已经准备好了，只需要写while部分的逻辑即可

while (checkWater() == true) {
            int random_cup1= new Random().nextInt(3);
            int random_cup2= new Random().nextInt(3);
            //System.out.println(random_cup1 + "/" + random_cup2);
            if (random_cup1 != random_cup2 && table[random_cup1].water != 0) {
                if (table[random_cup1].PourWater(table[random_cup2])) {
                    String Do = ("杯子" + random_cup1 + ">" + "杯子" + random_cup2 + "  -- " +
                                       " a:" + cup_a.water +
                                       " b:" + cup_b.water +
                                       " c:" + cup_c.water);
                     //System.out.println(Do);
                    EffectivePour.add(Do);
                 
                }

            }

        }

大功告成！

运行看看效果如何？

虽然最终解开了，但是看到有很多的重复sao操作，使得之前的许多次倒水成了白做，我们只需要最少的不重复的操作，那么,在while中再添加一下判断:

if(cup_a.water == 8 && cup_b.water == 0 && cup_c.water == 0){                
                       EffectivePour.clear();             
                   }
    

如果三个水杯的数据变成了初始数据，则清除EffectivePour。

效果:

到这里就算完成了，虽然有些勉强..🙊

全部代码:
Cup.java

public class Cup {
    final int capacity;
    int water;
    public Cup(int cap, int water) {
        this.capacity = cap;
        this.water = water;
    }
    public boolean PourWater(Cup toCup) {
        int toCupSurplus = toCup.capacity - toCup.water;
        if (toCupSurplus == 0 || this.water == 0) {
            return false; 
        }
        
        if (toCupSurplus < this.water) { //当前水杯的水大于要倒入水杯的水
            this.water = this.water-toCupSurplus; 
            toCup.water = toCup.capacity;
            
        } else if (toCupSurplus >= this.water) {
            toCup.water =  toCup.water + this.water;
            this.water = 0;
        }

    Main.cup_o++;
    return true;
    }
}

Main.java

import java.util.Random;
import java.util.ArrayList;

public class Main {
    static Cup[] table = new Cup[]{
        new Cup(8, 8),
        new Cup(5, 0),
        new Cup(3, 0)
    };
    static Cup cup_a;
    static Cup cup_b;
    static Cup cup_c;
    static int o = 0;
    static int cup_o = 0;
    
    static ArrayList<String> EffectivePour;

    public static void main(String[] args) {
        cup_a = table[0];
        cup_b = table[1];
        cup_c = table[2];
        EffectivePour = new ArrayList<>();
        while (checkWater() == true) {
            int random_cup1= new Random().nextInt(3);
            int random_cup2= new Random().nextInt(3);
            //System.out.println(random_cup1 + "/" + random_cup2);
            if (random_cup1 != random_cup2 && table[random_cup1].water != 0) {
                if (table[random_cup1].PourWater(table[random_cup2])) {
                    String Do = ("杯子" + random_cup1 + ">" + "杯子" + random_cup2 + "  -- " +
                                       " a:" + cup_a.water +
                                       " b:" + cup_b.water +
                                       " c:" + cup_c.water);
                     //System.out.println(Do);
                    EffectivePour.add(Do);
                    if(cup_a.water == 8 && cup_b.water == 0 && cup_c.water == 0){                
                        EffectivePour.clear();             
                    }
                                       
                }

            }

        }


    }

    private static boolean checkWater() {
        o ++;
        if (cup_a.water == 4 || cup_b.water == 4 || cup_c.water == 4) {
            System.out.println("已有杯子水量为4,循环共执行了" + o + "次;");
            System.out.println("共执行了倒水" + cup_o + "次;");
            System.out.println("实际有效倒水" + EffectivePour.size() + "次;");
            
            for(String op:EffectivePour){
                System.out.println(op);
            }
            
            return false;
        } else {
            return true;
        }
    }


}

java — Mar 22, 2020