一道面试题

2020-01-26 16:00:32 +08:00
 zxc1234

一只兔子 ,在第 5 到 10 天每天生一只,第 10 天后死亡,开始有 1 只兔子,问第 100 天有几只兔子

4869 次点击
所在节点    程序员
29 条回复
lhx2008
2020-01-26 16:03:16 +08:00
动态规划,奶牛问题
natsji
2020-01-26 16:05:38 +08:00
一只兔子怎么生,我的答案是 0 只
pipapa
2020-01-26 16:12:18 +08:00
模拟以下不久完事
Jat001
2020-01-26 16:13:09 +08:00
一只兔子怎么生,人工受精?死的是小兔子还是母兔子?哪有兔子一窝只生一只的,而且兔子的孕期差不多是一个月。兔子是因为什么原因死亡的?如何处理死亡的兔子?
问题太多,打回去重编🐶
pwrliang
2020-01-26 16:28:03 +08:00
把兔子改成细胞不就完了
pwrliang
2020-01-26 16:37:46 +08:00
dp[1-4]=1,dp[i]=dp[i-1]*2, i=5~9, dp[i]=dp[i-1]*2-dp[i-5]不到对不对…死亡是咋死的没太懂
Maboroshii
2020-01-26 16:41:31 +08:00
写个程序模拟一下很方便
chenliangngng
2020-01-26 17:02:19 +08:00
兔兔那么可爱,你怎么可以让它们死掉
ppyybb
2020-01-26 17:13:01 +08:00
i 从 1 开始,定义 f ( i )是第 i 天出生的兔子,很容易得到动态规划的方程 f ( i )= f ( i-4 )+ f ( i-5 )+... f ( i-9 )
初始状态有 f ( 1 )= 1,f ( 2 )= f ( 3 )= f ( 4 )= 0
举例看看,f ( 9 )= f ( 5 )+ .. f ( 1 )= 2
f ( 10 )= f ( 6 )+ ... f ( 1 )= 2

而一只兔子活 10 天,f ( i )+ ... f ( i-9 )就是第 i 天的兔子数量
gosas
2020-01-26 17:13:09 +08:00
兔兔为啥死的 如果是类似这次 那不就是 0 只?
pwrliang
2020-01-26 17:23:59 +08:00
@ppyybb 66666,定义为第 i 天出生的就容易多了
RedisMasterNode
2020-01-26 20:36:45 +08:00
dp[i] = dp[i-1] + dp[i-5+1] - dp[i-10+1]
RickyC
2020-01-26 21:14:17 +08:00
我算, 第 56 已经有 9566300 只兔子了
RickyC
2020-01-26 22:49:46 +08:00
上面这个 56 天的结果不对, 但是计算机模拟到 60 天就算不下去了
RickyC
2020-01-26 22:52:47 +08:00
是不是得超级计算机才能算 100 天?
RickyC
2020-01-26 23:03:29 +08:00
第 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 只兔子
第 17 天有 72 只兔子
第 18 天有 98 只兔子
第 19 天有 132 只兔子
第 20 天有 176 只兔子
第 21 天有 236 只兔子
第 22 天有 318 只兔子
第 23 天有 428 只兔子
第 24 天有 573 只兔子
第 25 天有 768 只兔子
第 26 天有 1032 只兔子
第 27 天有 1388 只兔子
第 28 天有 1863 只兔子
第 29 天有 2499 只兔子
第 30 天有 3355 只兔子
第 31 天有 4507 只兔子
第 32 天有 6052 只兔子
第 33 天有 8123 只兔子
第 34 天有 10905 只兔子
第 35 天有 14644 只兔子
第 36 天有 19664 只兔子
第 37 天有 26399 只兔子
第 38 天有 35441 只兔子
第 39 天有 47586 只兔子
第 40 天有 63895 只兔子
第 41 天有 85787 只兔子
第 42 天有 115176 只兔子
第 43 天有 154639 只兔子
第 44 天有 207629 只兔子
第 45 天有 278772 只兔子
第 46 天有 374284 只兔子
第 47 天有 502524 只兔子
第 48 天有 674712 只兔子
第 49 天有 905898 只兔子
第 50 天有 1216287 只兔子
第 51 天有 1633024 只兔子
第 52 天有 2192560 只兔子
第 53 天有 2943819 只兔子
第 54 天有 3952477 只兔子
第 55 天有 5306729 只兔子
第 56 天有 7125005 只兔子
第 57 天有 9566300 只兔子
第 58 天有 12844065 只兔子
第 59 天有 17244896 只兔子
第 60 天有 23153614 只兔子
第 61 天有 31086890 只兔子

计算机算不下去了
========
代码如下

<?php
function getRabbit($day)
{
//第 1 天有 1 只兔子
$str = '1';

//从第 2 天开始遍历兔子窝
for ($i = 0; $i < $day - 1; $i++) {
//昨天记录的兔子只数
$len = strlen($str);

for ($m = 0; $m < $len; $m++) {
//取出一只兔子
$num = $str[$m];
//让它的年龄增加 1 天
$num++;
//5-10 天的兔子, 要生 1 只兔子
if ($num >= 5 && $num <= 10) {
$str .= 1;
}
//用第 a 天表是第 10 天
$num = $num == 10 ? 'a' : $num;
//记录这只兔子新的年龄
$str[$m] = $num;
}

//第 11 天的兔子已经去世
$str = str_replace('b', '', $str);

$count = strlen($str);
$date = $i + 2;

echo "第{$date}天有{$count}只兔子<br>";
}
}

$a = 61;
getRabbit($a);
ppyybb
2020-01-26 23:06:59 +08:00
这个不对,第 9 天应该有 7 只兔子,实际上按这个公式计算出来是 6 只,后面误差就更大了
dikcen
2020-01-26 23:23:22 +08:00
Xn 表示第 n 天出生的兔子数量:
Xn = Xn-10 + Xn-9 + Xn-8 + Xn-6 + Xn-5 + Xn-4 (且 X1 = X2 = X3 = X4 =1 )
第 30 天存活的兔子数量为:
X21+X22+X23+...X30
dikcen
2020-01-26 23:27:29 +08:00
@dikcen 错了,应该是 X0 = 1,X1 = X2 = X3 = X4 =0

就这个意思,已经把自己绕晕乎了。
aguesuka
2020-01-27 00:11:27 +08:00
兔子生命周期 m,n 天。我想到的算法,时间复杂度 n 空间复杂度 m。不知道能不能更低

这是一个专为移动设备优化的页面(即为了让你能够在 Google 搜索结果里秒开这个页面),如果你希望参与 V2EX 社区的讨论,你可以继续到 V2EX 上打开本讨论主题的完整版本。

https://www.v2ex.com/t/640384

V2EX 是创意工作者们的社区,是一个分享自己正在做的有趣事物、交流想法,可以遇见新朋友甚至新机会的地方。

V2EX is a community of developers, designers and creative people.

© 2021 V2EX