算法问题求助

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. 最后计算数组和即可
优化思路：
在仔细读题后发现，所有的数量变化都是围绕着最近六个月的信息来进行变动的。
而且是每六个月一个周期进行循环（初始月份不在循环范围内）。
那么，我们的数组只需要六个位置即可。超过六个月的数据直接覆盖过期数据即可。

1. ewwok = int(raw_input("Enter initial population of Ewwoks?"))
   
2. month = int(raw_input("Find population in month?"))
   
3. queue = [0,0,0,0,0,0]
   
4. for index in range(month):
   
5.     if index == 0:
   
6.         queue[0] = ewwok
   
7.     else:
   
8.         if index % 6 == 0:  # 第1个月
   
9.             queue[3] = max(0, int(queue[3]) - 1)
   
10.         elif index % 6 == 1:  # 第2个月
    
11.             queue[1] = (int(queue[3]) + int(queue[5]) + int(queue[0])) * 2
    
12.         elif index % 6 == 2:  # 第3个月
    
13.             queue[0] = max(0, int(queue[0]) - 1)  # 首月可能减为负值
    
14.             queue[5] = max(0, int(queue[5]) - 1)
    
15.         elif index % 6 == 3:  # 第4个月
    
16.             queue[3] = (int(queue[5]) + int(queue[1]) + int(queue[0])) * 2
    
17.         elif index % 6 == 4:  # 第5个月
    
18.             queue[1] = max(0, int(queue[1]) - 1)
    
19.         elif index % 6 == 5:  # 第6个月
    
20.             queue[0] = 0  # 初始的会在第六个月全部死亡
    
21.             queue[5] = (int(queue[1]) + int(queue[3])) * 2
    
22.     return sum(queue)
    
23.     # print queue
    
24.     # print sum(queue)
    
25. print('Ewwok population in month ' + str(month) + ' is ' + str(sum(queue)))
    

复制代码