但行好事,莫问前程

挖了太多坑,一点点填回来

算法题:羊生羊问题

实战, 算法, 编程

面试题:

农夫有一只羊,这只羊在第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;
    }
}