有趣的算法-约瑟夫问题（队列的应用）

首先我们先来了解一种数据结构叫做队列。

队列的工作原理与现实生活中的队列完全相同。假设你与朋友一起在公交车站排队，如果你排在他前面，你将先上车。队列的工作原理与此相同。你不能随机地访问队列中的元素。队列只支持两种操作：入队和出队。

如果你将两个元素加入队列，先加入的元素将在后加入的元素之前出队。因此，你可使用队列来表示查找名单！这样，先加入的人将先出队并先被检查。

队列是一种先进先出（First In First Out，FIFO）的数据结构。

约瑟夫问题

n个人排成一圈。从某个人开始，按顺时针方向依次编号。从编号为1的人开始顺时针“报数，报到k的人退出圈子。这样不断循环下去，圈子里的人将不断减少。由于人的个数是有限的，因此最终会剩下一个人。试问最后剩下的人是谁。

可以用队列这种数据结构来模拟这个游戏，报数的人相当于一个一个出队，然后再一个一个入队（排到队尾），报到x相应数字的那个人就从队列中删除。（可以用Scratch中的列表来模拟队列）

点我查看Scratch解决问题方法

python 解决方法

# 约瑟夫问题仿真函数(几个人围城一个圈从1开始报数报到k的人就淘汰看谁留到最后)
# 以实际人名来仿真n个人，报数到7时删除，输出最后的胜利者
# 下面给出两种方法

# 方法一 循环队列
def ysf_result(name_list, k):
    queue = []  # 设置一个队列
    for i in range(len(name_list)):  # 把所有人加入到队列中
        queue.append(name_list[i])
    n = 1
    while len(queue) != 1:  # 当队列中的人不等于1个时重复执行下面代码  为1个人就是最后胜利者
        temp = queue.pop(0)  # 把队列中的第一个移除队列 
        if n != k:  # 如果报的数不为k则把刚刚移除队列的那个人再添加到队尾去
            queue.append(temp)
            n += 1
        else:      # 如果报的数正好等于k 那么就把报到的人移除队列不再添加到队尾了
            print('被移除的是{}'.format(temp))
            n = 1  # 重置n为1 相当于重新开始报数
    print('胜利者是：{}'.format(queue[0]))
    return queue[0]

# 方法二也是循环队列 是对方法一的优化
def ysf_result2(alist,k):
    ysf = alist[:]   # 把队列中的人复制一份到列表ysf中
    while len(ysf) > 1:
        for i in range(k-1):  # 这里i是从0开始 故此到第k个数是正好为k
            ysf.append(ysf.pop(0))  # 这里直接一行脚本代表没报到k的人直接添加到队尾
        ysf.pop(0)
        print(ysf)

if __name__ == '__main__':
    names = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h', 'i']
    dic = {}
    for k, v in enumerate(names):
        dic[v] = k
    k = 7
    # res = ysf_result(names, k)
    ysf_result2(names, k)
    # print('原来序列中胜利者的位置是{}'.format(dic[res]+1))

---

分享