CTF大赛-阿笠博士的兔子

题目来源于公司第三届(2018年)的CTF大赛题之一,分值:200

题目

柯南立刻想起阿笠博士培养出一对繁殖能力超强的兔子(雌雄),这种兔子嗅觉特别好,能快速找到丢失的镇馆之宝,这种兔子出生后一个月就会成年,成年的兔子再过一个月会生一对(雌雄)兔子,并且之后的每个月都会生一对兔子,兔子不会死亡,由于这种兔子一生只有一个伴侣,当兔子数量(对)越多对找回的镇馆之宝帮助最大,阿笠博士想知道当兔子数量(对)第11次出现素数之后过再128个月有多少对兔子,机智你能帮阿笠博士算出来吗?

解答

<?php

class App
{
    /**
     * 当前第几个月
     *
     * @var int
     */
    protected $m = 0;

    /**
     * 需要处理的剩余月数
     *
     * @var int
     */
    protected $remain = 128;

    /**
     * 兔纸对数
     *
     * @var int
     */
    protected $num = 1;

    /**
     * 出现质数的次数
     *
     * @var int
     */
    protected $z = 0;

    /**
     * 上一次的数量
     *
     * @var int
     */
    protected $prev = 0;

    /**
     * 处理
     *
     * @return [type] [description]
     */
    public function handle()
    {
        while ($this->remain) {
            // A. 月数增加
            ++$this->m;  // 这个属性没啥用,只是为了凸显我电脑性能好

            // B. 兔纸增加
            $prev = $this->num;  // 上个月的数量
            $this->num = bcadd($this->num, $this->prev);  // 当月数量  bcadd避免换算成科学计算显示方式
            $this->prev = $prev;  // 用于下次计算的上个月数量

            //  C. 如果z为11次时,则逐月递减
            if ($z == 11) {
                --$this->remain;
            }

            // D. 判断是否为质数
            if ($z < 11 && $this->isPrime($this->num)) {
                ++$z;
            }
        }

        return $this->num;
    }

    /**
     * 判断是否为质数(素数)
     *
     * NOTE:方法来源其他网友
     *
     * @param [type] $n [description]
     *
     * @return bool [description]
     */
    protected function isPrime($n)
    {
        if ($n <= 3) {
            return $n > 1;
        } elseif ($n % 2 === 0 || $n % 3 === 0) { // 排除能被2整除的数(2x)和被3整除的数(3x)
            return false;
        }   // 排除能被6x+1和6x+5整除的数
        for ($i = 5; $i * $i <= $n; $i += 6) {
            if ($n % $i === 0 || $n % ($i + 2) === 0) {
                return false;
            }
        }

        return true;
    }
}

$app = new App();
echo $app->handle();
赞 (0)
分享到:更多 ()

评论 0

  • 昵称 (必填)
  • 邮箱 (必填)
  • 网址