阿笠博士的兔子

这是公司 ctf 活动分值最高的一个题目,是这样说的:

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

当时应该没有人做出来,仔细分析一下,就是一个斐波那契数列加素数的判断,本身并不难。即便如此,我今晚也花了近三个小时在调试下面几行 js 代码。惭愧、惭愧,实在为自己的数学能力堪忧,还说要去考研······

var afterMonth = 128 // 多少月之后
var primeCount = 0 // 出现质数对的次数

var beforeMonth = 0 // 前一个月兔子的对数
var currentMonth = 1 // 当前月兔子的对数
var nextMonth = 1 // 下一个月兔子的对数

var primeAppearedCount = 11 // 要出现质数对的次数

while (afterMonth > 0) {
  nextMonth = beforeMonth + currentMonth
  beforeMonth = currentMonth
  currentMonth = nextMonth

  if (primeCount == primeAppearedCount) {
    afterMonth-- // 注意这行代码的位置,必须是出现第十一次质数对后才开始运行
  }

  if (primeCount < primeAppearedCount && isPrime(nextMonth)) {
    primeCount++
    console.log(primeCount, nextMonth)
  }
}


function isPrime(num) {
  if (num <= 3) {
    return num > 1;
  } else if (num % 2 == 0 || num % 3 == 0) { // 排除能被2整除的数(2x)和被3整除的数(3x)
    return false;
  }   // 排除能被6x+1和6x+5整除的数
  for (var i = 5; i * i <= num; i += 6) {
    if (num % i ===0 || num % (i + 2) == 0) {
      return false;
    }
  }

  return true;
}

console.log('兔子数:' + nextMonth)

仔细看代码,我在关键位置做了注释。

让我误入歧途的地方

以下是错误代码:

var beforeMonth = 1 // 前一个月兔子的对数 
var currentMonth = 1 // 当前月兔子的对数 
var nextMonth = 2 // 下一个月兔子的对数

我将上述初始月份设置了为第二个月开始,所以导致了我的代码运行不出来,这个也和将题目调整为第十二次出现质数对的第 128 月后有多少对兔子一样,将会使得这个数字变得非常大,js 表示不出来。因为这其中又涉及到素数,素数的出现到现在为止并不能预测,所以这个临界值显得至关重要,说明了出题者的水平。

什么是素数?

质数(Prime number),又称素数,指在大于1的自然数中,除了1和该数自身外,无法被其他自然数整除的数。

参考链接

维基百科素数

李永乐老师讲素数

我要分享

曾小乱

作者: 曾小乱

喜欢写点有意思的东西