PHP经典算法题1: 小偷分苹果问题
< 返回列表时间: 2020-07-07来源:OSCHINA
(题目来自网络) 有5个人偷了一堆苹果,他们准备在第二天进行分赃。晚上,有一个人溜出来,他把所有苹果分成了5份,但是多了一个,他顺手把这多的一个苹果扔给树上的猴子,自己先拿1/5藏了起来。没想到其他四人也都是这么想的,都如第一个人一样把苹果分成5份,把多的那一个扔给了树上的猴,偷走了1/5。第二天,大家分赃,也是分成5份多一个扔给猴子。最后一人分了一份。问:最少有多少个苹果?
假设总的苹果数量为s,上一个人对苹果划分时剩余的苹果为y,s/5为藏起来的一份,1为扔给猴子的一个苹果,则有公式y=s-s/5-1。从这个公式开始,第一个人分的苹果总数s为最初的苹果总数,第二个人开始分赃直到结束分赃时,这个s 都为上一个人分完苹果剩余的苹果数。所以可以根据这个式子,通过循环找出最后符合这个公式的解,从而得到苹果总数。
我们先来看一下最简单的代码写法: for($s=5;;$s++){ if($s % 5 == 1){ $l = $s - round($s/5) - 1; if($l % 5 == 1){ $q = $l - round($l/5) - 1; if($q % 5 == 1){ $w = $q - round($q/5) - 1; if($w % 5 == 1){ $x = $w - round($w/5) - 1; if($x % 5 == 1){ $y = $x - round($x/5) - 1; if($y % 5 == 1){ echo $s; exit; } } } } } } }
我们再用递归和闭包方式来处理类似的问题: class shareApples{ private $apple_quantity; //苹果总数量 private $men_quantity; //总人数 public function __construct(int $men_quantity) { $this->men_quantity = $men_quantity; $this->apple_quantity = 0; } /** * 递归检查苹果数量是否符合要求 * @param int $total 苹果数量 * @param int $num_left 剩余苹果数量 * @param int $seq 现在是第几个人 */ public function share(int $total, int $num_left, int $seq=1){ $men_quantity = $this->men_quantity; if($seq <= $men_quantity && $num_left % $men_quantity == 1){ $num_left2 = $num_left - (int)($num_left/$men_quantity) -1; if($num_left2 % $men_quantity == 1) { if($seq == $men_quantity){ $this->apple_quantity = $total; return true; }else { return $this->share($total, $num_left2, $seq + 1); } } } return false; } public function calc(){ for($i=5; ; $i++) { $rt = $this->share($i, $i, 1); if($rt === true){ $this->apple_quantity = $i; return $i; } } } /* * 闭包方式计算最小苹果数量 */ public function calc_closure(){ for($i=5; ; $i++){ $share = function (int $total, int $num_left, int $seq=1)use(&$share){ $men_quantity = $this->men_quantity; if($seq <= $men_quantity && $num_left % $men_quantity == 1){ $num_left2 = $num_left - (int)($num_left/$men_quantity) -1; if($num_left2 % $men_quantity == 1) { if($seq == $men_quantity){ $this->apple_quantity = $total; return true; }else { return $share($total, $num_left2, $seq + 1); } } } return false; }; $rt = $share($i, $i,1); if($rt === true){ return $this->apple_quantity; } } } public function get(){ return $this->apple_quantity; } } $m = new shareApples(5); echo 'min Total: '.$m->calc().PHP_EOL; echo 'min Total: '.$m->calc_closure().PHP_EOL;
闭包也可以实现递归功能. 但是经过测试, 时间消耗是直接递归的2倍+: $m = new shareApples(5); // 5, 6, 7, 8 $t1 = microtime(true); echo 'min Total: '.$m->calc().PHP_EOL; echo 'time: '.round(microtime(true) - $t1, 4).' s'.PHP_EOL; $t1 = microtime(true); echo 'min Total: '.$m->calc_closure().PHP_EOL; echo 'time: '.round(microtime(true) - $t1, 4).' s'.PHP_EOL;
人数为5时, 结果是: min Total: 15621 time: 0.0023 s min Total: 15621 time: 0.0049 s
人数为6时, 结果是: min Total: 279931 time: 0.041 s min Total: 279931 time: 0.0889 s
人数为7时, 结果是: min Total: 5764795 time: 0.8088 s min Total: 5764795 time: 1.7936 s
人数为8时, 结果是: min Total: 134217721 time: 18.268 s min Total: 134217721 time: 44.3141 s
运行环境是win10+php7.2, linux下没测试过。
热门排行