算法之倒水的问题

需求：现在只有两只杯子，容量分别是：5升和7升，问题是：在只用这两个杯子的前提下，如何才能得到4升水？假设：水可以无限使用。

fun water(volume1 : Int, volume2: Int, volume: Int){
    println("得到两个杯子：${volume1}L，${volume2}L，目标为${volume}L")
    var x = 0
    var cup1 = 0
    var cup2 = 0
    loop@ while (x != volume){
        println("给 cup1 装满水")
        println("cup1 向 cup2 倒水")
        cup1 = volume1
        while (cup2 + cup1 >= volume2){
            cup1 -= (volume2 - cup2)
            cup2 = 0
            x = cup1
            if(x == volume){
                break@loop
            }
            println("cup2 水满倒掉")
            println("cup1 把剩下 $x 倒入 cup2")
        }
        if (cup2 + cup1 < volume2){
            cup2 += cup1
            cup1 = 0
            x = cup1
        }
        println("cup1 水量 $cup1 cup2 水量 $cup2")
    }
    println("cup1 得到 ${x}L 水")
}

fun main(){
    water(5, 7, 4)
}

输出结果

得到两个杯子：5L，7L，目标为4L
给 cup1 装满水
cup1 向 cup2 倒水
cup1 水量 0 cup2 水量 5
给 cup1 装满水
cup1 向 cup2 倒水
cup2 水满倒掉
cup1 把剩下 3 倒入 cup2
cup1 水量 0 cup2 水量 3
给 cup1 装满水
cup1 向 cup2 倒水
cup2 水满倒掉
cup1 把剩下 1 倒入 cup2
cup1 水量 0 cup2 水量 1
给 cup1 装满水
cup1 向 cup2 倒水
cup1 水量 0 cup2 水量 6
给 cup1 装满水
cup1 向 cup2 倒水
cup1 得到 4L 水

如果将上面的杯子调换一下

fun main(){
    water(7, 5, 4)
}

输出结果

得到两个杯子：7L，5L，目标为4L
给 cup1 装满水
cup1 向 cup2 倒水
cup2 水满倒掉
cup1 把剩下 2 倒入 cup2
cup1 水量 0 cup2 水量 2
给 cup1 装满水
cup1 向 cup2 倒水
cup1 得到 4L 水

算法看似行的通，但是还存在以下几点缺陷：

无法判断方案是否行的通，如果得不到对应的水的话，会无限循环下去
这里只有cup1能得到对应水，没有判断cup2得到相应水的情况。例如，是water(2, 5, 4)的情况下，就会无限循环，但是第二轮的时候cup2已经得到了4L水。
针对以上问题，对算法做改进：记录每次cup1和cup2的水量，如果出现重复，则不会得到结果；对cup2的水量也进行判断。
改进后的算法如下：

fun water(volume1 : Int, volume2: Int, volume: Int){
    println("得到两个杯子：${volume1}L，${volume2}L，目标为${volume}L")

    var record = mutableListOf<String>()
    var cup1 = 0
    var cup2 = 0

    loop@ while (cup1 != volume && cup2 != volume){
        if (record.contains("$cup1-$cup2")){
            println("得不到结果")
            break@loop
        }else{
            record.add("$cup1-$cup2")
        }
        println("给 cup1($cup1) 装满水")
        cup1 = volume1
        println("cup1($cup1) 向 cup2($cup2) 倒水")
        while (cup2 + cup1 >= volume2){
            cup1 -= (volume2 - cup2)
            cup2 = 0
            if(cup1 == volume){
                break@loop
            }
            println("cup2($cup2) 水满倒掉")
            if (cup1 == 0){
                continue@loop
            }
            println("把cup1($cup1) 剩下 $cup1 倒入 cup2($cup2)")
        }
        if (cup2 + cup1 < volume2){
            cup2 += cup1
            cup1 = 0
            if (cup2 == volume){
                break@loop
            }
        }
        println("cup1 水量 $cup1 cup2 水量 $cup2")
    }
    println("cup1 得到 ${cup1}L 水")
    println("cup2 得到 ${cup2}L 水")
    println(record)
}

以上算法，去掉了多余的中间变量X，同时将while内部的那个while用求余的方式表示，精简了代码

仔细考查，算法还存在一些不完美的地方。大致说几个问题：

比如给出2个1L的杯子，得到2L的水。这个算法会输入：不会得到结果。但是2个1L的杯子，不就是2L水嘛。
比如给出2个1L的杯子，得到1L的水。这个算法会先向cup1倒水，然后再倒入cup2，然后cup2倒掉，又回到0L和0L的两个杯子，给出得不到结果。但是1L的cup1就直接能得到结果。

希望有更好的算法能与大家交流

最后编辑于：2019.04.30 14:05:53