美文网首页
算法之倒水的问题

算法之倒水的问题

作者: 心随你咚 | 来源:发表于2019-04-30 13:05 被阅读0次

    需求:现在只有两只杯子,容量分别是: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 水
    

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

    1. 无法判断方案是否行的通,如果得不到对应的水的话,会无限循环下去
    2. 这里只有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用求余的方式表示,精简了代码

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

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

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

    相关文章

      网友评论

          本文标题:算法之倒水的问题

          本文链接:https://www.haomeiwen.com/subject/clwmnqtx.html