2
算法题：羊生羊问题
source link: http://caiknife.github.io/blog/2018/12/01/yang-sheng-yang-wen-ti/
Go to the source link to view the article. You can view the picture content, updated content and better typesetting reading experience. If the link is broken, please click the button below to view the snapshot at that time.
算法题：羊生羊问题
Dec 1st, 2018
Posted by CaiKnife
农夫有一只羊，这只羊在第2、3年会生一只小羊，第4年不会生小羊，第5年时羊会死亡，生出来的小羊也是这个规律。求问50年后会有多少只羊？
这道题最直接的办法就是用递归来做，不过我暂时还没想到递归怎么做，所以先用最笨的方法——遍历50年，每一年遍历羊的数组，根据年纪来进行对应的处理。详细见下面的代码：
(sheep.php) download
<?php
/**
* Created by PhpStorm.
* User: caiknife
* Date: 2018/12/1
* Time: 18:29
*/
namespace App\Cron;
class Sheep
{
public function __construct()
{
ini_set("memory_limit", "2048M");
}
public function main()
{
$sheeps = [0];
$startTime = microtime(true);
for ($i = 1; $i <= 10; $i++) {
foreach ($sheeps as $key => $age) {
$sheeps[$key]++;
switch ($sheeps[$key]) {
case 1:
case 4:
// do nothing
break;
case 2:
case 3:
$sheeps[] = 0; // 刚出生算0岁
break;
case 5:
unset($sheeps[$key]);
break;
default:
break;
}
}
}
$endTime = microtime(true);
echo "Time cost:" . ($endTime - $startTime) . PHP_EOL;
echo count($sheeps) . PHP_EOL;
}
}
但是这个方法是有问题的，那就是数组占用的内存太大，用PHP来跑的话，50的数据量根本就没办法解决。
->php cli.php Sheep.main master [08f1c0ba] modified
PHP Fatal error: Allowed memory size of 1073741824 bytes exhausted (tried to allocate 1073741832 bytes) in /Users/caiknife/Projects/PHPLib/src/Cron/Sheep.php on line 34
PHP Stack trace:
PHP 1. {main}() /Users/caiknife/Projects/PHPLib/cli.php:0
PHP 2. App\Cron\Sheep->main() /Users/caiknife/Projects/PHPLib/cli.php:34
Fatal error: Allowed memory size of 1073741824 bytes exhausted (tried to allocate 1073741832 bytes) in /Users/caiknife/Projects/PHPLib/src/Cron/Sheep.php on line 34
Call Stack:
0.0003 369648 1. {main}() /Users/caiknife/Projects/PHPLib/cli.php:0
0.0335 5328840 2. App\Cron\Sheep->main() /Users/caiknife/Projects/PHPLib/cli.php:34下面尝试一下用递归的解法。
(sheep_recursive.php) download
<?php
/**
* Created by PhpStorm.
* User: caiknife
* Date: 2018/12/1
* Time: 18:54
*/
namespace App\Cron;
class SheepRecursive
{
public function __construct()
{
ini_set("memory_limit", "2048M");
}
public function main()
{
echo $this->_countSheep(50) . PHP_EOL;
}
protected function _countSheep($year)
{
if ($year == 3) {
return 3;
} elseif ($year == 2) {
return 2;
} elseif ($year == 1) {
return 1;
}
// $year >= 5时，表示有羊死去
return ($year >= 5 ? 0 : 1) + $this->_countSheep($year - 3) + $this->_countSheep($year - 2);
}
}
最后再使用一个移动窗口的解法。
(sheep_window.php) download
<?php
/**
* Created by PhpStorm.
* User: caiknife
* Date: 2018/12/1
* Time: 22:11
*/
namespace App\Cron;
class SheepWindow
{
public function __construct()
{
ini_set("memory_limit", "2048M");
}
public function main()
{
$startTime = microtime(true);
$arr = [1, 0, 0, 0, 0]; // 这个数组分别表示一到五年
for ($i = 1; $i <= 50; $i++) {
$tmp = $arr[1] + $arr[2]; // 只有2岁和3岁的羊会生小羊
array_unshift($arr, $tmp); // 这表示新一年生的小羊数
array_pop($arr); // 将5岁的小羊消灭
}
$endTime = microtime(true);
echo "Time cost:" . ($endTime - $startTime) . PHP_EOL;
echo array_sum($arr) . PHP_EOL;
}
public function another()
{
$startTime = microtime(true);
$arr = [1, 0, 0, 0, 0];
for ($i = 1; $i <= 50; $i++) {
list($one, $two, $three, $four, $five) = $arr;
$arr[0] = $two + $three;
$arr[1] = $one;
$arr[2] = $two;
$arr[3] = $three;
$arr[4] = $four;
}
$endTime = microtime(true);
echo "Time cost:" . ($endTime - $startTime) . PHP_EOL;
echo array_sum($arr) . PHP_EOL;
}
}
Posted by CaiKnife
Recommend
About Joyk
Aggregate valuable and interesting links.
Joyk means Joy of geeK