PHP算法之倒水问题

这类题目在面试中会经常遇到，最常见的是给你一个容量为5升的桶和一个容量为3升的桶，水不限使用，要求精确得到4升水。

解法网上有很多，本文采用的是宽度优先搜索。

PHP代码：

<?php
#倒水问题
fwrite(STDOUT,'请输入A桶容量：');
$a=intval(fgets(STDIN));
fwrite(STDOUT,'请输入B桶容量：');
$b=intval(fgets(STDIN));
fwrite(STDOUT,'请输入需要量出的水：');
$want=intval(fgets(STDIN));
$question="问题：给你一个容量为{$a}升的A桶和一个容量为{$b}升的B桶，水不限使用，要求精确得到{$want}升水。\n";
echo $question;
$status=[['a'=>0,'b'=>0,'comment'=>['开始']]];
$processed=[];
pour_water($a,$b,$want,$status,$processed);
function pour_water($a,$b,$want,$status,&$processed){
    $newStatus=[];
    foreach ($status as $k=>$v){
        if(isset($processed[$v['a']][$v['b']])){
            continue;
        }else{
            $processed[$v['a']][$v['b']]=true;
        }
        if($v['a']==$want || $v['b']==$want){
            print_result($v['comment']);
            exit;
        }
        #1,把A倒满
        if($v['a']<$a){
            $tmp['a']=$a;
            $tmp['b']=$v['b'];
            $tmp['comment']=array_merge($v['comment'],["装满A桶(A:{$tmp['a']},B:{$tmp['b']})"]);
            $newStatus[]=$tmp;
        }
        #2,把B倒满
        if($v['b']<$b){
            $tmp['a']=$v['a'];
            $tmp['b']=$b;
            $tmp['comment']=array_merge($v['comment'],["装满B桶(A:{$tmp['a']},B:{$tmp['b']})"]);
            $newStatus[]=$tmp;
        }
        #3将A桶清空
        if($v['a']>0){
            $tmp['a']=0;
            $tmp['b']=$v['b'];
            $tmp['comment']=array_merge($v['comment'],["清空A桶(A:{$tmp['a']},B:{$tmp['b']})"]);
            $newStatus[]=$tmp;
        }
        #4将B桶清空
        if($v['b']>0){
            $tmp['a']=$v['a'];
            $tmp['b']=0;
            $tmp['comment']=array_merge($v['comment'],["清空B桶(A:{$tmp['a']},B:{$tmp['b']})"]);
            $newStatus[]=$tmp;
        }
        #5将A倒入B桶
        if($v['a']>0 && $v['b']<$b){
            $pour=min($v['a'],$b-$v['b']);
            $tmp['a']=$v['a']-$pour;
            $tmp['b']=$v['b']+$pour;
            $tmp['comment']=array_merge($v['comment'],["从A桶倒入B桶:{$pour} (A:{$tmp['a']},B:{$tmp['b']})"]);
            $newStatus[]=$tmp;
        }
        #6将B桶倒入A桶
        if($v['a']<$a && $v['b']>0){
            $pour=min($a-$v['a'],$v['b']);
            $tmp['a']=$v['a']+$pour;
            $tmp['b']=$v['b']-$pour;
            $tmp['comment']=array_merge($v['comment'],["从B桶倒入A桶:{$pour} (A:{$tmp['a']},B:{$tmp['b']})"]);
            $newStatus[]=$tmp;
        }
    }
    if($newStatus){
        pour_water($a,$b,$want,$newStatus,$processed);
    }
}

function print_result($c){
    foreach ($c as $k=>$v){
        echo "{$k},{$v}\n";
    }
    echo "结束\n";
}

执行结果：

请输入A桶容量：3
请输入B桶容量：5
请输入需要量出的水：4
问题：给你一个容量为3升的A桶和一个容量为5升的B桶，水不限使用，要求精确得到4升水。
0,开始
1,装满B桶(A:0,B:5)
2,从B桶倒入A桶:3 (A:3,B:2)
3,清空A桶(A:0,B:2)
4,从B桶倒入A桶:2 (A:2,B:0)
5,装满B桶(A:2,B:5)
6,从B桶倒入A桶:1 (A:3,B:4)
结束