需求:现在只有两只杯子,容量分别是: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就直接能得到结果。
希望有更好的算法能与大家交流
网友评论