算法题：羊生羊问题
Posted by CaiKnife
实战, 算法, 编程
面试题：
农夫有一只羊，这只羊在第2、3年会生一只小羊，第4年不会生小羊，第5年时羊会死亡，生出来的小羊也是这个规律。求问50年后会有多少只羊？
这道题最直接的办法就是用递归来做，不过我暂时还没想到递归怎么做，所以先用最笨的方法——遍历50年，每一年遍历羊的数组，根据年纪来进行对应的处理。详细见下面的代码：
(sheep.php) download
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
| <?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的数据量根本就没办法解决。
1
2
3
4
5
6
7
8
9
10
11
| ->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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
| <?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
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
| <?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;
}
}
|