一道面试题

你大可不必模拟每只兔兔，记兔兔年龄数量（ 10 ），然后天数递增（ 100 ），复杂也是常量级别，你试试。

@RickyC 你试试换上面方法

直接说瘟疫好了。。。

@pipapa 解决了, 用了您说的统计的思想, 但是没有看懂他们上面的公式, 代码如下
----------------------
<?php
function getRabbit($day)
{
/**
* 初始数组: 用于统计每个年龄的兔子有几只
* 1. 键表示 年龄(几天大)
* 2. 值表示 该年龄的兔子的数量
*/
$arr = [
1 => 1,
2 => 0,
3 => 0,
4 => 0,
5 => 0,
6 => 0,
7 => 0,
8 => 0,
9 => 0,
10 => 0
];

//从第 2 天开始触发循环
for ($i = 0; $i < $day - 1; $i++) {
//先保存昨天记录
$yesterday = $arr;

/**
* 遍历而生成今天兔子年龄的统计情况:
* 1. 今天 1 天大的兔子数量, 是昨天 4-9 天大的兔子的数量的总和, 因为它们今天都到了生育年龄, 各生了 1 只兔子
* 2. 好比: 昨天 2 天大的兔子, 就是今天 3 天大的兔子
*/
foreach ($arr as $k => $v) {

$arr[$k] = $k == 1 ? $yesterday[4] + $yesterday[5] + $yesterday[6] + $yesterday[7] + $yesterday[8] + $yesterday[9] : $yesterday[$k - 1];
}
}

//返回兔子总数
return array_sum($arr);
}

echo getRabbit(100); //第 100 天有 3040556004272 只兔子

实践是检验真理的唯一标准*狗头

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp1
{
class Program
{
static void Main(string[] args)
{
long[] rabbits = new long[100];
rabbits[0] = 1;
long a=0,b=0,c=0;
Console.WriteLine("第 1 天有 1 只兔子");
for (int i = 1; i <= 99; i++)
{
if (i >= 9)
{
for (int j = 0; j <= 9; j++)
{
rabbits[i - j] -= rabbits[i - 9];
}
}

a = rabbits[i - 1];

if (i < 4)
{
b = 0;
}
else
{
b= rabbits[i - 4];
}

if (i < 9)
{
c = 0;
}
else
{
c = rabbits[i - 9];
}

rabbits[i] = a + b - c;
Console.WriteLine("第{0}天有{1}只兔子,新増{2}只", i + 1, rabbits[i],b-c);
}

long d=0;
for (int i = 91; i <= 99; i++)
{
Console.WriteLine("{0}岁的有{1}个", 100 - i, rabbits[i] - rabbits[i-1]);
d += rabbits[i] - rabbits[i - 1];
}
Console.WriteLine(d);
Console.WriteLine(d - rabbits[99]);
Console.ReadKey();
}
}
}
基本思想与 12 楼一致，但在第 n(n>=10)天后，从第 n-9 天到第 n 天要减去第 n-9 天的数量，否则会重复计算。
不过有更简单但不直观的算法，不减去第 n-9 天的数量，算出 92-100 天的增量后相加就是第 100 天的数量

```javascript
const foo = (n) => {
const rabbitObj = {
0: {
'passDay': 0,
'val': 1
}
};
let id = 1;
let sum = 1; //总数量
//day: 当前天数
const passOneDay = (day) => {
let total = 0; //当天将生产的数量
for (let i in rabbitObj) {
rabbitObj[i]['passDay']++;
if (rabbitObj[i]['passDay'] >= 5 && rabbitObj[i]['passDay'] <= 10) { //5~10 天
total += rabbitObj[i]['val'];
} else if (rabbitObj[i]['passDay'] === 11) { //第 11 天
sum -= rabbitObj[i]['val']; //兔子死去，总数量减去该值
delete rabbitObj[i]; //删除该属性
}
}
if (total) { //当天生产数量不为 0
sum += total;
rabbitObj[id++] = {
'passDay': 1,
'val': total
};
}
}
for (let day = 0; day < n; day++) {
passOneDay(day);
}
return sum;
}
for (let i = 1; i < 101; i++) {
console.log(`第${i}天有${foo(i)}只兔子`);
}
```
结果如下：
第 1 天有 1 只兔子
第 2 天有 1 只兔子
第 3 天有 1 只兔子
第 4 天有 1 只兔子
第 5 天有 2 只兔子
第 6 天有 3 只兔子
第 7 天有 4 只兔子
第 8 天有 5 只兔子
第 9 天有 7 只兔子
第 10 天有 10 只兔子
第 11 天有 12 只兔子
第 12 天有 16 只兔子
第 13 天有 22 只兔子
第 14 天有 31 只兔子
第 15 天有 41 只兔子
第 16 天有 54 只兔子
省略
第 96 天有 935663312748 只兔子
第 97 天有 1256255432122 只兔子
第 98 天有 1686694015993 只兔子
第 99 天有 2264616439357 只兔子
第 100 天有 3040556004272 只兔子

大哥你这第十天的兔子数量不对啊

``````
dp = [1] +[0] * 99

for i in range(100):
if 4 <= i < 10:
for j in range(i-3):
dp[i] += dp[j]
elif i >= 10 :
for j in range(i-9, i-3):
dp[i] += dp[j]
if i <= 9:
print(f'day {i+1} total: {sum(dp[:i+1])}')
else:
print(f'day {i+1} total: {sum(dp[i-9:i+1])}')
``````

对于 11 天以后，只考虑各自 5-10 天里每天新增的兔子数量