偷苹果引发的思考

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

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