当前位置:首页 > 开发 > 编程语言 > 编程 > 正文

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

发表于: 2014-11-05   作者:home198979   来源:转载   浏览:
摘要: 形象化设计模式实战             HELLO!架构                     redis命令源码解析   倒水问题:有两个杯子,一个A升,一个B升,水有无限多,现要求利用这两杯子装C

形象化设计模式实战             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升的水的吗?

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

  • 0

    开心

    开心

  • 0

    板砖

    板砖

  • 0

    感动

    感动

  • 0

    有用

    有用

  • 0

    疑问

    疑问

  • 0

    难过

    难过

  • 0

    无聊

    无聊

  • 0

    震惊

    震惊

推荐文章
编辑推荐
版权所有 IT知识库 CopyRight © 2009-2015 IT知识库 IT610.com , All Rights Reserved. 京ICP备09083238号