这是一个创建于 1745 天前的主题，其中的信息可能已经有所发展或是发生改变。
一只兔子 ，在第 5 到 10 天每天生一只，第 10 天后死亡，开始有 1 只兔子，问第 100 天有几只兔子
 |
1
lhx2008 2020-01-26 16:03:16 +08:00 via Android  1
动态规划，奶牛问题
|
 |
2
natsji 2020-01-26 16:05:38 +08:00 via Android 2
一只兔子怎么生，我的答案是 0 只
|
 |
3
pipapa 2020-01-26 16:12:18 +08:00
模拟以下不久完事
|
 |
4
Jat001 2020-01-26 16:13:09 +08:00 via iPhone 1
一只兔子怎么生，人工受精？死的是小兔子还是母兔子？哪有兔子一窝只生一只的，而且兔子的孕期差不多是一个月。兔子是因为什么原因死亡的？如何处理死亡的兔子？
问题太多，打回去重编🐶 |
 |
5
pwrliang 2020-01-26 16:28:03 +08:00 via Android
把兔子改成细胞不就完了
|
|
6
pwrliang 2020-01-26 16:37:46 +08:00 via Android
dp[1-4]=1,dp[i]=dp[i-1]*2, i=5~9, dp[i]=dp[i-1]*2-dp[i-5]不到对不对…死亡是咋死的没太懂
|
 |
7
Maboroshii 2020-01-26 16:41:31 +08:00 via Android
写个程序模拟一下很方便
|
 |
8
chenliangngng 2020-01-26 17:02:19 +08:00 via Android
兔兔那么可爱，你怎么可以让它们死掉
|
 |
9
ppyybb 2020-01-26 17:13:01 +08:00 via iPhone 6
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 天的兔子数量 |
 |
10
gosas 2020-01-26 17:13:09 +08:00
兔兔为啥死的 如果是类似这次 那不就是 0 只？
|
 |
12
RedisMasterNode 2020-01-26 20:36:45 +08:00 2
dp[i] = dp[i-1] + dp[i-5+1] - dp[i-10+1]
|
 |
13
RickyC 2020-01-26 21:14:17 +08:00
我算, 第 56 已经有 9566300 只兔子了
|
|
14
RickyC 2020-01-26 22:49:46 +08:00
上面这个 56 天的结果不对, 但是计算机模拟到 60 天就算不下去了
|
|
15
RickyC 2020-01-26 22:52:47 +08:00
是不是得超级计算机才能算 100 天?
|
|
16
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); |
|
17
ppyybb 2020-01-26 23:06:59 +08:00 via iPhone
这个不对，第 9 天应该有 7 只兔子，实际上按这个公式计算出来是 6 只，后面误差就更大了
|
 |
18
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 |
 |
20
aguesuka 2020-01-27 00:11:27 +08:00 via Android
兔子生命周期 m，n 天。我想到的算法，时间复杂度 n 空间复杂度 m。不知道能不能更低
|
|
21
pipapa 2020-01-27 01:08:23 +08:00 via Android
你大可不必模拟每只兔兔，记兔兔年龄数量（ 10 ），然后天数递增（ 100 ），复杂也是常量级别，你试试。
|
 |
23
bullfrog 2020-01-27 08:14:02 +08:00
直接说瘟疫好了。。。
|
|
24
RickyC 2020-01-27 09:51:33 +08:00
@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 只兔子 |
 |
25
studong 2020-01-27 10:44:40 +08:00 via Android
实践是检验真理的唯一标准*狗头
|
 |
26
stonewolfcjq 2020-01-27 15:15:38 +08:00
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 天的数量 |
 |
27
lisianthus 2020-01-27 19:05:26 +08:00 1
```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 只兔子 |
|
28
stonewolfcjq 2020-01-27 20:47:00 +08:00 via Android
大哥你这第十天的兔子数量不对啊
|
 |
29
zzz686970 2020-01-30 16:25:43 +08:00
``````
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 天里每天新增的兔子数量 |
Select Language