题目:

Consider a special type of animal known as an Ewwok that reproduces following the rules below:
An Ewwok dies six months after it is born. That is, if an Ewwok is born in month 0, it will die in month 6.
An Ewwok gives birth to two Ewwoks every two months until it dies. That is, if an Ewwok is born in month 0, it will reproduce in months 2 and 4. It does not reproduce in month 6 or beyond.
In each month, among all the Ewwoks that have been alive for exactly three months, there is one that dies. That is, if there are n (n > 0) Ewwoks that are born in month 0, one of them will die in month 3.
Given an integer initial representing the number of Ewwoks born in month 0, and an integer m representing a month, your task in this question is to write a program that calculates and returns the number of Ewwoks alive in month m.

For example, if there is 1 Ewwok born in month 0 (initial = 1): In month 1, there is 1 Ewwok.
In month 2, there are 3 Ewwoks (2 are born by the initial Ewwok).
In month 3, there are 2 Ewwoks (the initial Ewwok dies).
In month 4, there are 6 Ewwoks (4 are born).
In month 5, there are 5 Ewwoks (1 of the Ewwoks born in month 2 dies).
In month 6, there are 15 Ewwoks (10 are born).
In month 7, there are 14 Ewwoks (1 of the Ewwoks born in month 4 dies).
In month 8, there are 39 Ewwoks (the remaining Ewwok born in month 2 dies; 26 are born).
...
You may assume that initial >= 0 and m >= 0. First sample session with the program:
Enter initial population of Ewwoks? 2, Find population in month? 8, Ewwok population in month 8 is 105
Second sample session with the program:
Enter initial population of Ewwoks? 5, Find population in month? 10, Ewwok population in month 10 is 825
Third sample session with the program:
Enter initial population of Ewwoks? 1, Find population in month? 48, Ewwok population in month 48 is 20424869889

翻译:

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

思路:

  1. 获取输入的两个数值
  2. 初始化一个月份长度的数组
  3. 从零开始循环
  4. 小于六个月单独处理
  5. 大于六个月了每过一个月就对前六个月数据进行相应的处理
  6. 最后计算数组和即可
  7. (代码过烂,看不下去)

优化:

  在仔细读题后发现,所有的数量变化都是围绕着最近六个月的信息来进行变动的。
  而且是每六个月一个周期进行循环(初始月份不在循环范围内)。
  那么,我们的数组只需要六个位置即可。超过六个月的数据直接覆盖过期数据即可。

优化后的代码:

if __name__=="__main__":
    ewwok = int(raw_input("Enter initial population of Ewwoks?"))
    month = int(raw_input("Find population in month?"))
    queue = [0] * 6

    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
        # print queue
        # print sum(queue)
    print('Ewwok population in month ' + str(month) + ' is ' + str(sum(queue)))