偷苹果引发的思考

分类:PHP | 作者:凹凸曼 | 发表于2012/06/13

网上搜一下算法来看哈,就看到喵了个咪博客 有一个算法题如下:

5个人偷了一堆苹果,准备在第二天分赃。晚上,有一人遛出来,把所有菜果分成5份,但是多了一个,顺手把这个扔给树上的猴了,自己先拿1/5藏了。没想到其他四人也都是这么想的,都如第一个人一样分成5份把多的那一个扔给了猴,偷走了1/5。第二天,大家分赃,也是分成5份多一个扔给猴了。最后一人分了一份。问:共有多少苹果?

<?php

function apple(){

	$re=0;
	for($i=1;;$i++){

		if($i%5==1){
			$a=$i-round($i/5)-1;
				if($a%5==1){
					$b=$a-round($a/5)-1;
						if($b%5==1){
							$c=$b-round($b/5)-1;
							if($c%5==1){
								$d=$c-round($c/5)-1;
								if($d%5==1){
									$e=$d-round($d/5)-1;
									 if($e%5==1){
										 $re=$i;
										 break;
									 }
								}

							}
					    }
			      } 

		   }

	}
return $re;
}

/**
/*重构 函数apple 并且新增人数变量参数
/*@param $people 偷苹果总人数
/*@return  $re 偷苹果总数
**/
function appleRec($people){
	$re=0;
	$flag=FALSE;
	for($i=1;;$i++){
		 $j=$people;
		 $a=$i;
		 for($j;$j>=0;$j--){
			 if($a%$people==1){
				$a=$a-intval($a/$people)-1;
				$flag=TRUE;
			 }else{
				 $flag=FALSE;break;
			 }
		 }
	    if($flag){$re=$i;break;}

	}

	return $re;
}

$s=microtime(true);
echo "5个人分的apple总数为:".apple()."<br>";
$e=microtime(true)-$s;
echo "apple所用时间:".$e."<br><br>";

$s=microtime(true);
$people=5;
echo "{$people}个人分的apple总数为:".appleRec($people)."<br>";
$e=microtime(true)-$s;
echo "appleRec所用时间:".$e."<br>";
//结果:
/*5个人分的苹果总数为:15621
apple函数所用时间:0.0039300918579102

5个人分的苹果总数为:15621
appleRec函数所用时间:0.0062911510467529
*/

总结:我重构了一下apple,appleRec 明显效率低下,因为for比if效率要低,并且通过测试发现intval效率比较round高很多。

所以对于他的算法还可以优化一下把round改写成intval.

如果这个题目改写一下5个人改写n个人(也许是6、7)  那明显用apple实用性不强,appleRec 通过测试

7个人分的苹果总数为:5764795
appleRec所用时间:2.0439360141754

是不是有点恐怖,这个appleRec不能很好的解决!

有木有更好的算法来解决这个问题呢?

 

 

本文出自 “凹凸曼” 博客,请务必保留此出处http://www.apoyl.com/?p=1376

Tag:

日志信息 »

该日志于2012-06-13 10:56由 凹凸曼 发表在PHP分类下, 你可以发表评论。除了可以将这个日志以保留源地址及作者的情况下引用到你的网站或博客,还可以通过RSS 2.0订阅这个日志的所有评论。

目前盖楼 (0)层:

发表评论 »

« »