算法问题求助

huzeyu

考虑一种特殊类型的动物，称为Ewwok，按照以下规则进行繁殖：
Ewwok在出生六个月后去世。也就是说，如果Ewwok在第0个月出生，它将在第6个月死亡。
Ewwok每两个月产生两个Ewwok，直到它死亡。也就是说，如果Ewwok在第0个月出生，它将在第2个月和第4个月重现。它不会在第6个月或更长时间内重现。
在每个月，在所有已经活了三个月的Ewwoks中，有一个已经死了。也就是说，如果在第0个月出生的n（n> 0）个Ewwoks，其中一个将在第3个月死亡。
给定一个整数初始值表示出生在第0个月的Ewwoks数量，以及一个整数m表示一个月，你在这个问题中的任务是编写一个程序，计算并返回月份m中存活的Ewwoks数量。

请问这道题的解题思路应该是什么样子的，我大致想了一下应该是类似于一个树状图，求一定深度的和，但是始终写不出来函数的解法，求一个思路。

已经在网上找到了答案

编程鱼C

第六个月Ewwok也能重现

huzeyu

想了一上午还是不对

人造人

可以提供几组输入/输出吗？我找一下规律

huzeyu

在网上翻到了答案
解题思路：
        1. 获取输入的两个数值
        2. 初始化一个月份长度的数组
        3. 从零开始循环
        4. 小于六个月单独处理
        5. 大于六个月了每过一个月就对前六个月数据进行相应的处理
        6. 最后计算数组和即可
优化思路：
在仔细读题后发现，所有的数量变化都是围绕着最近六个月的信息来进行变动的。
而且是每六个月一个周期进行循环（初始月份不在循环范围内）。
那么，我们的数组只需要六个位置即可。超过六个月的数据直接覆盖过期数据即可。

ewwok = int(raw_input("Enter initial population of Ewwoks?"))
month = int(raw_input("Find population in month?"))
queue = [0,0,0,0,0,0]
for index in range(month):
    if index == 0:
        queue[0] = ewwok
    else:
        if index % 6 == 0:  # 第1个月
            queue[3] = max(0, int(queue[3]) - 1)
        elif index % 6 == 1:  # 第2个月
            queue[1] = (int(queue[3]) + int(queue[5]) + int(queue[0])) * 2
        elif index % 6 == 2:  # 第3个月
            queue[0] = max(0, int(queue[0]) - 1)  # 首月可能减为负值
            queue[5] = max(0, int(queue[5]) - 1)
        elif index % 6 == 3:  # 第4个月
            queue[3] = (int(queue[5]) + int(queue[1]) + int(queue[0])) * 2
        elif index % 6 == 4:  # 第5个月
            queue[1] = max(0, int(queue[1]) - 1)
        elif index % 6 == 5:  # 第6个月
            queue[0] = 0  # 初始的会在第六个月全部死亡
            queue[5] = (int(queue[1]) + int(queue[3])) * 2
    return sum(queue)
    # print queue
    # print sum(queue)
print('Ewwok population in month ' + str(month) + ' is ' + str(sum(queue)))