细胞分裂问题

有一个细胞,每过一小时就会分裂一次,每次分裂产生一个子细胞。同时,这个细胞分裂三次后就会死亡。请问第 $n$ 小时时有多少细胞?

递归解决问题的思路就是把 n 的问题化归到比 n 小的问题上去,先解决小问题,大问题自然就解决了。

因为一个细胞分裂三次后会立即死亡,所以 n 时刻的所有细胞的已分裂次数都不会超过三次。

所以 n 时刻的细胞的已分裂次数有可能是 0 次,1 次,2 次。

记 n 时刻的细胞数目为 $f(n)$,按照已分裂次数将细胞分为三堆,则:
$$
f(n) = f_0(n) + f_1(n) + f_2(n)
$$
如下图所示:

image-20201021180049857

观察发现,无论 n 时刻会有多少细胞死亡,每个 n-1 时刻的细胞都会分裂出一个新的细胞。只是对于那些 n-1 时刻已经分裂了两次的细胞而言,它们在分裂后会立即死亡而已,故而
$$
f_0(n) = f(n-1)
$$
n 时刻所有已分裂次数为 1 的细胞都是 n-1 时刻已分裂次数为 0 的细胞,故而
$$
f_1(n) = f_0(n-1) = f(n-2)
$$
n 时刻所有已分裂次数为 2 的细胞都是 n-1 时刻已分裂次数为 1 的细胞,故而
$$
f_2(n) = f_1(n-1) = f(n-3)
$$
所以
$$
f(n) = f(n-1) + f(n-2) + f(n-3)
$$
综上
$$
f(n) = \begin{cases}
f(n-1) + f(n-2) + f(n-3) & n \ge 3 \\
4 & n = 2 \\
2 & n = 1 \\
1 & n = 0
\end{cases}
$$
这个递推公式表示的数列跟斐波那契数列十分相似,而且更复杂,时间复杂度更高。

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
#include <iostream>
#include <map>
using namespace std;

map<int,int> hist;
long countCell(int);

int main(){
int i;
long n;
for (i = 0; i < 100; ++i) {
n = countCell(i);
if (n < 0 ) {
cout << "too big" << endl;
break;
}
cout << "n = " << i << ", counts = " << n << endl;
}
return 0;
}

long countCell(int n) {
if (n == 0) {
hist.insert(pair<int,int>(0, 1));
return 1;
}
if (n == 1) {
hist.insert(pair<int,int>(1, 2));
return 2;
}
if (n == 2) {
hist.insert(pair<int,int>(2, 4));
return 4;
}
map<int,int>::iterator res;
int x1, x2, x3;
res = hist.find(n-1);
if (res != hist.end()) {
x1 = res->second;
} else {
x1 = countCell(n-1);
hist.insert(pair<int,int>(n-1, x1));
}
res = hist.find(n-2);
if (res != hist.find(n-2)) {
x2 = countCell(n-2);
hist.insert(pair<int,int>(n-2, x2));
} else {
x2 = res->second;
}
res = hist.find(n-3);
if (res != hist.end()) {
x3 = countCell(n-3);
hist.insert(pair<int,int>(n-3, x3));
} else {
x3 = res->second;
}
return x1 + x2 + x3;
}

STL map 的几个用法:

  • 初始化一个空的map:map<int,int> mapname;
  • 向map中插入数据:mapname.insert(pair<int,int>(M, N));
  • 查询key是否存在:mapname.find(KEY) 并与 mapname.end() 进行比较;
  • 声明一个迭代器:map<int,int>::iterator iter;,配合 .begin().end() 使用
    • 反向迭代器:map<int,int>::reverse_iterator,配合 .rbegin().rend() 使用
  • 访问迭代器的key和value:iter->first & iter->second
----- For reprint please indicate the source -----
0%