(
课件网) 队列 n个人排成一圈，从某个人开始，按顺时针方向从1开始依次编号。从编号为1的人开始顺时针“1，2，3，…，m，1，2，3，…”报数，报到m（m＞1）的人退出圈子。按原始编号输出最后一个出圈的编号。 1 2 3 4 5 …… n 6 7 8 约瑟夫游戏 1 2 3 4 5 …… n 6 7 8 约瑟夫游戏 任务一：当n=8,m=3时，用队列数据结构，请每位同学按游戏规则模拟 一下，并按顺序输出出圈人员的编号。 1 2 3 4 5 6 7 8 约瑟夫游戏 1 2 3 4 5 6 7 8 … 4 5 6 7 8 1 2 … 输出：3 tail tail head head 约瑟夫游戏 4 5 6 7 8 1 2 … head tail 输出：3 6 1 7 8 1 2 4 5 … head tail 2 4 5 7 8 … head tail 队列 1.队列的概念 队列是一种先进先出的线性表，允许插入的一端称为队尾，允许删除的一端称为队首。队列中的数据元素称为队列元素。在队列中插入一个元素称为入队，从队列中删除一个元素称为出队。 队列 2.队列的特性 ① 先进先出、后进后出。队首元素a1优先出队，紧接着是a2，a3，…，an–1，队尾元素an最后出队。 ② 有限序列性。队列也是一种线性表结构，元素个数是有限的。队列可以是空的，也可以包含多个元素。队列中所有元素呈现线性特征，队首元素只有一个后继点，队尾元素只有一个前驱点，其他元素既有一个前驱点，又有一个后继点。 队列 3.队列的操作 ①队列的存储 队列一般按顺序结构存储，可以用数组来实现。如图所示，数组que中存储了一个队列，共有4个元素，队首元素为“A”，队尾元素为“D” 。由于在入队和出队的过程中，队首元素和队尾元素的位置会改变，因此需要设置头指针变量head和尾指针变量tail，head记录队首元素所在的位置，tail记录队尾元素的下一个位置。 队列 3.队列的操作 ② 队列的入队、出队 初始时，head指针变量与tail指针变量均记录下标为0的位置。元素“A”，“B”，“C”，“D”依次入队后，tail值为4，head值为0，如图所示。 队列 4.约瑟夫的队列实现 que=[] head=0 tail=0 n,m=map(int,input().split()) for i in range(n): que.append(i+1) tail+=1 tmp=0 cnt=0 while head
