军训队列
题目描述
某大学开学进行军训队列训练，将学生从一开始按顺序依次编号，并排成一行横队，训练的规则如下：从头开始一至二报数，凡报到二的出列剩下的依次向前靠拢，再从头开始进行一至三报数，凡报到三的出列，剩下的依次向前靠拢，继续从头开始进行一至二报数。。。以后每次从头开始轮流进行一至二报数、一至三报数直到剩下的人数不超过三人为止。
输入
第一行为组数N，接着为N行学生人数，学生人数不超过5000。
样例输入
2
20
40
输出
输出有N行，分别对应输入的学生人数，每行输出剩下的学生最初的编号，编号之间有一个空格。
样例输出
1 7 19
1 19 37
时间限制
C/C++语言：1000MS其它语言：3000MS
内存限制
C/C++语言：65536KB其它语言：589824KB
试题地址：http://exercise.acmcoder.com/online/online_judge_list_all
在赛码网上做算法题，遇到这样一道题。
我的能力虽然一般，还需要继续努力才能进步。
但是希望记录下来学会一道题的想法，可以提供给一些没有思路的朋友们一个参考！
代码捉襟见肘，还请见谅~
这是一道动态规划的题。
动态规划大致的思路就是：
把一个庞大的问题每次只完成一小步，每次都得到一个阶段的结果，然后用这个结果去当作下一阶段的开始状态。
并且每一步都是一个决策，不会影响接下来阶段的决策，每个阶段是独立的。
我的思路是：
1 根据输入人数m，初始化一个数组list，下标从0到m-1号依次存入1到m号，表示他们的编号
2 开启一个新的队列res，对list进行1至2报数：
把list所有报1的位置里面的值依次入队列res，一直到list遍历结束
执行3：对res 进行1至3报数
3 对res进行1至3报数：
开启一个队列res2
把所有喊1和2的位置的元素依次入队列到res2中 一直到res队列遍历结束
执行2：在对res2进行1至2报数
。。。。
最终，当结果队列里面少于三个元素时候，结束，得到了结果！
我是用python3来实现的：
# coding:utf8
#list是当前队列里按顺序排号的编号，step是本次要执行1到几报数
def result(list, step):
if len(list) <= 3: #如果不多于3人，则应该返回结果
return list
res = [] #用于存储结果
if step == 2: #如果是1到2报数
res = list[::2] # 把list里的所有报2的人踢出去，剩下1 的人存给新列表res
return result(res, 3) #递归调用：再对res进行1到3报数
else: #否则 当前是1到3报数
cur = 0 #临时变量 表示当前所在0号位置 我们进行向下遍历操作
while cur < len(list): #如果当前还没到队尾
res.append(list[cur]) #把当前这个人放到res里
if cur + 1 < len(list):
res.append(list[cur + 1]) #把这个人的下一个人也放res里
cur += 3 #cur向后移动3人的位置
#跳出循环后，我们把报1和2 的人都放进了res，在对res进行1到2报数
return result(res, 2)
#这样一直递归调用，每次都新开一个res来存留下来的人，一直到res里小于等于3个人的时候就是结果。
def main():
n = int(input()) #接收测试用例数
for i in range(n): #每一次测试用例都做的
m = int(input()) #接收一个队列人数
list = [j for j in range(1, m + 1)] #一个列表，从0到m-2 每个位置里面存了人的编号1到m
#调用方法得到列表，把列表转换成符合题目要求的字符串
res = str(result(list, 2)).lstrip("[").rstrip("]").replace(",", " ")
print(res)
if __name__ == '__main__':
main()
