代码实现任意容量倒水问题

形象化设计模式实战             HELLO!架构                     redis命令源码解析

 

倒水问题：有两个杯子，一个A升，一个B升，水有无限多，现要求利用这两杯子装C升的水。

 

想必很多人都可能被问到过这个问题，问题虽然简单的，但是要费些脑子。这个问题显然是个逻辑问题，那么就肯定能够用程序来实现。

 

现在我假设A=3,B=5,C=4。

 

大脑的运算过程：

第一步、把3装满，或把5装满（只有这两种选择吧）。

第二步、把装满的杯子的水倒入空杯子（没有人会把第二个杯子也装满吧）。

第三步、两个杯子的水做运算得出一个D（D不能和A、B相等，如果D等于C就成功啦）

第四步、跟第一步相同

第五步、跟第三步相同

。

。

。

直到D等于C就成功，这个要注意的是D的值不能相同，例如第一次运算得到D=2，如果第三次运算又是2，那就不能再继续下去，不然会无限2，够2的。

 

将这个过程转为机器逻辑：两个变量a=3,b=5,要使得变量c=4。这好像太简单了，但是注意的是，杯子容量，假设 3+3=6，但实际上杯子装不了6升的水，换作杯子3+3=1，因为5升杯子装满了，多下一升留在3升杯子中。换作逻辑运行就相当于是取余。

 

代码实现：

<?php
/**
 * 倒水算法
 *
 * @param int     $re    目标水位
 * @param int     $cup1  杯子1的大小
 * @param int     $cup2  杯子2的大小
 * @param int     $i     当前杯子有所装水]
 * @param array   $nocan 不能出现的水位，以免死循环
 * @return int
 */
function todo( $re, $cup1, $cup2, $i, $nocan = array() ) {
	$yu = max( $cup1, $cup2 );
	$arr = array( $cup1, $cup2 );
	if ( !$nocan )
		$nocan = array( 0, $i, $cup1, $cup2 );
	foreach ( $arr as $v ) {
		echo "尝试与{$v}运算\r\n";

		//##########做加法#################
		$tmp = $i + $v;
		echo "{$i}+{$v}\r\n";

		if ( $tmp > $yu ) {
			$tmp = $tmp%$yu;
			echo "取{$yu}的余数{$tmp}\r\n";
		}
		if ( $tmp == $re ) {
			return $tmp;
		}
		if ( !in_array( $tmp, $nocan, true ) ) {
			$nocan[] = $tmp;
			return todo( $re, $cup1, $cup2, $tmp, $nocan );
		}else {
			echo "failed\r\n";
		}

		//#########做减法###################
		$tmp = $i - $v;
		echo "{$i}-{$v}\r\n";
		if ( $tmp > $yu ) {
			$tmp = $tmp%$yu;
			echo "取{$yu}的余数\r\n";
		}
		if ( $tmp == $re ) {
			return $tmp;
		}
		if ( $tmp > 0 && !in_array( $tmp, $nocan ) ) {
			$nocan[] = $tmp;
			return todo( $re, $cup1, $cup2, $tmp, $nocan );
		}else {
			echo "failed\r\n";
		}

		//###########做被减##################
		$tmp = $v - $i;
		echo "{$v}-{$i}\r\n";
		if ( $tmp > $yu ) {
			$tmp = $tmp%$yu;
			echo "取{$yu}的余数\r\n";
		}
		if ( $tmp == $re ) {
			return $tmp;
		}
		if ( $tmp > 0 && !in_array( $tmp, $nocan ) ) {
			$nocan[] = $tmp;
			return todo( $re, $cup1, $cup2, $tmp, $nocan );
		}else {
			echo "failed\r\n";
		}
	}
	return false;
}

 

 

 

现在运行todo(4,3,5,3);就是先将3升杯子装满：

 

 

尝试与3运算
3+3
取5的余数1
尝试与3运算
1+3

 

 

再试下todo(4,3,5,5);先将5升杯子装满：

 

尝试与3运算
5+3
取5的余数3
failed
5-3
尝试与3运算
2+3
failed
2-3
failed
3-2
尝试与3运算
1+3

 

代码问题：

1、做加法，如果与A,B较大数做加法，那么是不是相当于没加？

2、做减法，减与被减用绝对值统一处理即可,abs

3、可能有多种倒水方法，而我最想知道的是最快的那种！

 

优化后代码：

<?php
/**
 * 倒水算法
 *
 * @param int     $re    目标水位
 * @param int     $cup1  杯子1的大小
 * @param int     $cup2  杯子2的大小
 * @param int     $i     当前杯子有所装水]
 * @param array   $nocan 不能出现的水位，以免死循环
 * @param string  $s     倒水过程
 * @return int
 */
function todo( $re, $cup1, $cup2, $i, $nocan = array() , $s ='' ) {
	global $return,$num;
	$yu = max( $cup1, $cup2 );//取较大值
	$arr = array( $cup1, $cup2 );
	if ( !$nocan )
		$nocan = array( 0, $i, $cup1, $cup2 );
	foreach ( $arr as $v ) {
		$str = "";

		//#########做减法###################
		$tmp = abs( $i - $v );//这里直接取绝对值

		$str .= "{$i}与{$v}相减\r\n";
		if ( $tmp > $yu ) {
			$tmp = $tmp%$yu;
			$str .= "取{$yu}的余数\r\n";
		}
		if ( $tmp == $re ) {
			$s .= $str;
			$num[] = array(substr_count( $s, "\r\n" ));
			$return[] = array( substr_count( $s, "\r\n" ), $s );
			return $tmp;
		}
		if ( $tmp > 0 && !in_array( $tmp, $nocan ) ) {
			$nocan[] = $tmp;
			$ss = $s.$str;
			todo( $re, $cup1, $cup2, $tmp, $nocan , $ss );
		}

		$str = "";

		//##########做加法#################
		if ( $yu != $v ) {//跟大杯做加法，相当于白做
			$tmp = $i + $v;
			$str .= "{$i}+{$v}\r\n";

			if ( $tmp > $yu ) {
				$tmp = $tmp%$yu;
				$str .= "取{$yu}的余数{$tmp}\r\n";
			}
			if ( $tmp == $re ) {
				$s .= $str;
				$num[] = array(substr_count( $s, "\r\n" ));
				$return[] = array( substr_count( $s, "\r\n" ), $s );
				return $tmp;
			}
			if ( !in_array( $tmp, $nocan, true ) ) {
				$nocan[] = $tmp;
				$ss = $s.$str;
				todo( $re, $cup1, $cup2, $tmp, $nocan , $ss );
			}
		}
	}
	return false;
}
todo( 4, 43, 77, 77 );
if($num && $return){
	array_multisort($num, SORT_ASC, $return);
	print_r(array_slice($return, 0,2));//方法有很多，只打印两种吧
}else{
	echo "no way!";
}

 

Array
(
    [0] => Array
        (
            [0] => 27
            [1] => 77与43相减
34与43相减
9+43
52+43
取77的余数18
18+43
61+43
取77的余数27
27+43
70+43
取77的余数36
36+43
取77的余数2
2+43
45+43
取77的余数11
11+43
54+43
取77的余数20
20+43
63+43
取77的余数29
29+43
72+43
取77的余数38
38+43
取77的余数4

        )

    [1] => Array
        (
            [0] => 27
            [1] => 77与43相减
34与43相减
9+43
52+43
取77的余数18
18+43
61+43
取77的余数27
27+43
70+43
取77的余数36
36+43
取77的余数2
2+43
45+43
取77的余数11
11+43
54+43
取77的余数20
20+43
63+43
取77的余数29
29与77相减
48与43相减
5与43相减
38+43
取77的余数4

        )

)

 可见最快27步可以搞定！

 

 

最后留一个问题：随意A,B升的水，一定能倒出C升的水的吗？

评论

1 楼 dsjt 2014-11-05  

下载了个应用就是倒水的。