斐波那契兔子的衍生问题

写在头里的公式:

a[i] = a[i-1] + a[i-(x-1)]

今天要说的是跟可爱的兔子有关的问题

大家在学习C语言基础或其他语言基础的时候,肯定都学过斐波那契数列的问题,这就是由兔子产仔问题引申出来的,如百度百科中所述。

问题的引申

但是昨天在网上看到一个问题,是这么说的:

1
古典问题:有一对兔子,从出生后第3个月起每个月都生一对兔子,小兔子长到第四个月后每个月又生一对兔子,假如兔子都不死,问每个月的兔子总数为多少?

看了解法是用斐波那契数列去解得,当时也没想到斐波那契的来由,就自己掰手指算了一下,感觉不对劲,最后掰出来的结果是这样的:

1
1 1 2 3 4 6 9 13 19 ....

这完全不是斐波那契啊 ~ 把这个问题抛给朋友们去解,然后才发现原来是题主写错问题了而且问题还有歧义……
于是,引申一下问题:

1
假如每对兔子从出生第4个月开始每个月都会生一对兔子,而且兔子不死,那现在刚出生一对兔子,在第n个月的时候共有多少兔子

这就跟题主的问题有些类似了。
看着这个问题有3个关键点:

  • 兔子年龄每月要增加1
  • 兔子长大后每个月都还能生一对兔子
  • 兔子不死

引申问题的初步解法

于是动手写了第一版的解决方案(方法1,最后有优化):

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
#coding=utf-8
# 类似链表的解决方法
s = 0
class Rabbit:
def __init__(self):
self.childs = []
self.age = 0
global s
s += 1
def add_year(self):
if len(self.childs) > 0:
for child in self.childs:
child.add_year()
self.age += 1
if self.age >= 3:
self.childs.append(Rabbit())
if __name__ == "__main__":
t = Rabbit()
m = 20
for i in range(0, m - 1):
t.add_year()
print("第%d个月有%d对兔子" % (m, s))

通过类似链表的方法记录下每只兔子的年龄和孩子,然后对每次出生的(即在init的时候)小兔子加1,最后的结果就是共有多少对。
来个遍历:

1
2
3
4
5
6
7
if __name__ == "__main__":
for i in range(0, 20):
s = 0
t = Rabbit()
for j in range(0, i):
t.add_year()
print(s)

得到这样的结果:1 1 1 2 3 4 6 9 13 19 28 41 60 88 129 189
仔细看的话,可以发现这样的规律,即a[i] = a[i-1] + a[i-3],此时兔子产仔是在第4个月;
而斐波那契数列的规律是这样的:a[i] = a[i-1] + a[i-2],兔子产仔是在第3个月。

总结规律

貌似其中有蹊跷,假如把出生后产仔的时间设为一个变量x,应该会有这样的规律:a[i] = a[i-1] + a[i-(x-1)]
那么按照斐波那契数列的算法来写,会有这样的结果:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#coding=utf-8
# i 第几个数
# s 步长,斐波那契数列步长是3
def ter_fib(i, s):
if s <= 1:
print("步长太小,无法计算")
return -1
if i <= (s - 2):
return 1
return ter_fib(i - 1, s) + ter_fib(i - (s - 1), s)
if __name__ == "__main__":
for x in range(0,20):
print(ter_fib(x, 4))

然后把方法1改成带参数的如下(最后有优化):

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
#coding=utf-8
# 类似链表的解决方法
s = 0 # 有多少对兔子
d = 0
class Rabbit:
# gmonth 第几个月可以生小兔子
# dmonth 长到多少个月后会死去
def __init__(self, gmonth, dmonth = -1):
self.childs = [] # 兔子的孩子
self.age = 0 # 兔子的年龄(月)
self.gmonth = gmonth
self.dmonth = dmonth
global s
s += 1
# 兔子的年龄加1,它的孩子也都年龄加1
def add_year(self):
if len(self.childs) > 0:
for child in self.childs:
child.add_year()
self.age += 1
if self.age < self.dmonth or self.dmonth == -1:
if self.age >= self.gmonth - 1:
self.childs.append(Rabbit(self.gmonth, self.dmonth))
else:
global d
d += 1
# print("死了一对兔子")
if __name__ == "__main__":
for i in range(0, 30):
s = 0
d = 0
t = Rabbit(4, 10)
for j in range(0, i):
t.add_year()
print("%d %d" % (s, d))

多试验几次步长,用上述方法去验证,完美通过 ~

于是,斐波那契兔子问题,可以改成这样了:

1
假如每对兔子从出生第x个月开始每个月都会生一对兔子,而且兔子不死,那现在刚出生一对兔子,在第n个月的时候共有多少兔子

测试各种步长的前20个数据

步长 结果(前20个)
2 1 2 4 8 16 3 64 128 256 512 1024 2048 4096 8192 16384 32768 65536 131072 262144 524288
3 1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765
4 1 1 1 2 3 4 6 9 13 19 28 41 60 88 129 189 277 406 595 872
5 1 1 1 1 2 3 4 5 7 10 14 19 26 36 50 69 95 131 181 250
6 1 1 1 1 1 2 3 4 5 6 8 11 15 20 26 34 45 60 80 106

附 : 斐波那契数列

1
2
3
4
5
def ter_fib(i):
if i <= 1: return 1
return ter_fib(i - 1) + ter_fib(i - 2)
if __name__ == "__main__":
for x in range(0,20): print(ter_fib(x))

这个时候怎么少得了伟大的for循环呢,递归虽然很省事,但是很费事,做了很多无用功,for循环有时候在一定程度上还是能大大的提高性能,比如这个问题,用递归和for循环去计算第20个、第50个数试试?

兔子问题通用解法:

1
2
3
4
5
6
7
8
9
10
11
12
13
14
#coding=utf-8
# 第几个数
# 步长
def ter_fib(i, s):
fibs = []
if s <= 1: return -1 # 步长太短,无法计算
for t in range(0, s - 1): fibs.append(1)
for j in range(s - 1, i): fibs.append(fibs[j - 1] + fibs[j - (s - 1)])
return fibs
if __name__ == "__main__":
fibs = ter_fib(50, 3)
for x in range(0, 50): print(fibs[x])

方法1优化:
可以作为兔子问题的验证程序

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
#coding:utf-8
class Rabbit:
def __init__(self):
self.age = 0
# month 第几个月
# gmonth 长到几个月的时候可以生小兔子了
# lmonth 多少个月后死亡
def count_rabbit(month, gmonth, lmonth = -1):
rabbits = [] # 总共有多少兔子
d_rabbit = 0 # 死亡的兔子有多少对
if len(rabbits) == 0:
rabbits.append(Rabbit())
for i in range(0, month):
for j in range(0, len(rabbits)):
rabbit = rabbits[j]
rabbit.age += 1
if (rabbit.age < lmonth or lmonth == -1) and rabbit.age >= gmonth - 1:
rabbits.append(Rabbit())
else: d_rabbit += 1
return (len(rabbits), d_rabbit)
if __name__ == "__main__":
for i in range(0, 20):
print(count_rabbit(i, 4, 10))