题目：
1 个细胞的生命周期是 3 小时，1 小时分裂一次。求 n 小时后，容器内有多少细胞？
思路：
很明显要用递归，首先要写出 n 小时以后，细胞的数量 递归公式 f(n)
细胞的生命周期是3个小时，也就是分裂3次以后死亡
f(n) 和 f(n-1) 的关系为，f(n) = 2*f(n-1) - 死亡的细胞数
f(0), 1 个
f(1), 2 个
f(2), 4个
f(3), 8个，但是f(0)的细胞生命周期结束，所以f(3)应该是 7 个细胞
f(4), 14个，此时f(1)的细胞生命周期结束，直观上我们会直接减去 f(1)，剩下 12 个，得到公式 f(n) = 2*f(n-1) - f(n-3)，但这是错误的，因为f(1)两个细胞中的一个，在f(3)的时候已经死了，所以应该减去 1 个，剩下 13 个
f(5), 26个，同理，此时f(2)的细胞生命周期结束，但是f(2)的4个中2个已经死了，所以不应该减4，应该减2，剩下24个
从上面的分析来看死亡的细胞数计算，死掉的细胞数并不是前3小时的细胞总数f(n-3)，因为这里面包含n-3时刻新生的细胞和老细胞，很显然老细胞在n时刻之前就已经死完了。此时死掉的细胞数应该是n-3时刻新生的细胞数，而n-3时刻新生的细胞数正是前一时刻总的细胞数，即f(n-4)，因此正确的计算公式是f(n)=f(n-1)x2 - f(n-4)
代码： go 版本
func recursion(n int) int {
if n == 0 {
return 1
}
if n == 1 {
return 2
}
if n == 2 {
return 4
}
if n == 3 {
return 7
}
return recursion(n-1)*2 - recursion(n-4)
}
func main() {
n := 5
count := recursion(n)
fmt.Println(count)
}
网友评论