python中队列的应用：约瑟夫斯问题

    著名的 约瑟夫斯问题（Josephus Problem）是应用队列（确切地说，是循环队列）的典型案例。 约瑟夫斯问题 讲的是，参与者围成一个圆圈，从某个人（队首）开始报数，报数到num的人退出圆圈，然后从退出人的下一位重新开始报数；重复以上动作，直到只剩下一个人为止。

    这个问题我们采用队列来解决，通过队列来存放所有参加游戏的人名，根据报数方向从队首排到队尾，保持队首始终是报数的人。

    报数开始，只需要将队首的人出队，随即再到队尾入队，算是报数的一次传递。传递到num次后，将队首的人移除不再入队。如此反复，直到只剩下一个人为止。

队列实现约瑟夫斯问题

    实现代码如下,其中使用的Queue模块是我上一篇文件写的Queue队列封装模块：

#!/usr/bin/env python

# -*- coding: utf-8 -*-

def josephus(namelist, num):

    simqueue = Queue()

    for name in namelist:

        simqueue.enqueue(name)

    while simqueue.size() > 1:

        for i in xrange(num):

            simqueue.enqueue(simqueue.dequeue())        //一次传递

        simqueue.dequeue()

    return simqueue.dequeue()

if __name__ == '__main__':

    print(josephus(["Bill", "David", "Kent", "Jane", "Susan", "Brad"], 3))

运行结果：

$ python josephus.py

Susan