兔生兔，求总数
Tags：算法
其实这个出自面试题，当时没做出来，哭丧脸...
我们先来看个比较常见的问题：
有一对兔子，从出生后第3个月起每个月每只兔子都生一对兔子，小兔子长到第三个月后每个月每只又生一对兔子，假如兔子都不死，问第N个月的兔子总数为多少？
由题目意思可看出第N个月的总数取决于第N-1个月的兔子的总数加上第N-2个月出生的兔子生出来新兔子的数目，简单粗暴点用公式来表示：
f(1) = 2 // 第一个月有2只兔子
f(2) = 2 // 第二个月有2之兔子
f(3) = f(2) + f(1) * 2 // 现在第一个月的兔子可以生小兔子了，第三个月的总数为第二个月的兔子总数加上第一个月兔子生下来的兔子
f(4) = f(3) + f(2) * 2 //现在第二个月的兔子可以生小兔子了，第四个月的总数为第三个月的总数加上第二个月
......
f(n) = f(n-1) + f(n-2) * 2 // 现在第n-2个月的兔子可以生小兔子了，不管是在第n-2个月之前就出生的还是在第n-2个月才出生的，在相对的第三个月后即第n个月都会生小兔子，然而在第n-1个月出生的兔子不能生小兔子，这部分作为基数直接计算进第n个月的总数中，所以第n个月的总数由两部分组成，一是上个月的兔子总数，二是这个月新出生的兔子。
思路有了，那我们就直接来代码吧～
def getSum(num):
if num == 1 or num == 2:
return 2
return getSum(num-1) + getSum(num-2) * 2
这种递归的代码还是有点慢啊，那可不可以给力点，让代码更快一点呢～那我们就不用递归来试试迭代呢～
def getSum(num):
a, b = 2, 2 # 第一个月，第二个月
if sum == 1 or sum == 2:
return 2
for i in range(3, sum+1):
a, b = b, a*2+b # a做为第n-2个月，b做为第n-1个月，计算后a与b的指向位置均向后移动了一位，此时a为n-1，b为n
return b
ok，这种不会死的兔子真是厉害啊，在哪里可以买，我也要～
哎，买不到不死的兔子哎，兔子都会死，就像这样：
有4只兔子，从出生后第3个月(经过两个月)起每个月每只兔子都生一对兔子，小兔子长到第三个月后每个月每只又生一对兔子，假如兔子只能活四个月也就是第一个月出生的兔子第五个月就死掉了，问第N个月的兔子总数为多少？
这个好眼熟，和上面的差不多耶～哎，不对啊，这个兔子有寿命的啊，那是不是有个公式像上面的那种递推公式呢，来推一下吧：
f(1) = 4 // 第一个月4只
f(2) = 4 // 第二个月4只
f(3) = 4 + 4*2 = f(2) + f(1) * 2 // 第一个月的兔子生小兔子啦
f(4) = f(3) + f(2) * 2 // 第二个月的兔子也生啦
f(5) = f(4) - f(1) + (f(3) - f(2)) * 2 // 第一个月的兔子死掉了，第三个月的兔子出生了
f(6) = 第五个月的总数加上第三个月兔子生的小兔子再加上第四个月的兔子生的小兔子...这个公式有点复杂啊，下面的会不会更可怕，害怕ing
好了好了，我放弃了，不用这个方法了，快快快想想其他的：
按着刚刚的思路，我们可不可以计算每个月的新出生的兔子数量，然后把还活着者的相加起来呢～但这样的话不就和上面的一样了吗，重点都是要计算新兔子的数量，那可不可以给力点～我们干嘛要自己维护这种计算过程的状态呢，为啥不让计算机自己维护呢，ok，让计算机自己维护要怎么让他自己能维护呢～这个时候面试官提点了一下：面向对象
对哇，来来来，让我们抛弃过程化的思路：
当有新兔子出生的时候就是new对象的时候，有多少个出生就new多少个，每个对象拥有自己的出生月份，这样就可以判断是否可以生兔子，是否还活着了
每次对月份进行递归迭代的时候就是判断对象的属性，不需要手动维护
还是先用递归来一遍：
# -*- coding:utf-8 -*-
class Rabbit:
def __init__(self, year):
self.year = year
def isDead(self, year):
"""死了为true,没死为false"""
return self.year + 3 < year
def isBirth(self, year):
return self.year + 1 < year
def __str__(self):
return '(Pig: year-%s)' % str(self.year)
__repr__ = __str__
def getSum(num):
if num == 1 or num == 2:
return [Rabbit(1)] * 4
pigList = getSum(num-1)
tempList = []
# 过滤掉死掉的兔子，新增新出生的兔子
for pig in pigList:
# 还活着的加入当月列表中
if not pig.isDead(num):
tempList.append(pig)
# 新出生的加入当月列表中
if not pig.isDead(num) and pig.isBirth(num):
tempList.extend([Rabbit(num)] * 2)
# 返回当月的兔子情况
return tempList
if __name__ == '__main__':
pigCharm = getSum(5)
print pigCharm
print len(pigCharm)
ok，下面就是迭代的版本了:
# -*- coding:utf-8 -*-
class Pig:
def __init__(self, year):
self.year = year
def isDead(self, year):
"""死了为true,没死为false"""
return self.year + 3 < year
def isBirth(self, year):
return self.year + 1 < year
def __str__(self):
return '(Pig: year-%s)' % str(self.year)
__repr__ = __str__
def getSum(num):
pigCharm = [Pig(1)] * 4
if num == 1:
return pigCharm
# 利用for循环进行迭代
for year in range(2, num+1):
tempList = []
for pig in pigCharm:
# 过滤掉死掉的兔子
if not pig.isDead(year):
tempList.append(pig)
# 加入新出生的兔子
if not pig.isDead(year) and pig.isBirth(year):
tempList.extend([Pig(year)] * 2)
pigCharm = tempList
return pigCharm
if __name__ == '__main__':
pigCharm = getSum(5)
print pigCharm
print len(pigCharm)
看来，以后解决问题的时候还需要多想想，换个思路会更好啊～
(刚面试完，等回复好心急...)
你这里满篇的兔子嘛，猪呢？对哇，猪呢？！猪可能是被兔子吃掉了吧～(原面试题就是猪，到了我这猪就被兔子吃了，惨啊)