(
课件网) 链表的应用（第四课时） 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 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 8 出圈顺序为：3 6 1 5 2 8 4 7 7 约瑟夫游戏 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 8 任务二：如何用链表存储这n个人的数据？ 7 约瑟夫游戏 1 1 数据区域 指针区域 数组下标 2 2 3 3 4 4 5 5 6 6 7 7 8 0 0 1 2 3 4 5 6 7 每个人设置数据区域和指针区域，当n=8,m=3时，数据如下图所示： 约瑟夫游戏 1 1 数据区域 指针区域 数组下标 2 2 3 3 4 4 5 5 6 6 7 7 8 0 0 1 2 3 4 5 6 7 任务三：请模拟游戏过程中的指针区域的变化过程。 约瑟夫问题 1 1 数据区域 指针区域 数组下标 2 2 3 3 4 4 5 5 6 6 7 7 8 0 0 1 2 3 4 5 6 7 编号为3的人出圈 1 1 数据区域 指针区域 数组下标 2 3 3 3 4 4 5 6 6 6 7 7 8 0 0 1 2 3 4 5 6 7 编号为6的人出圈 1 1 数据区域 指针区域 数组下标 2 3 3 3 4 4 5 6 6 6 7 7 8 0 0 1 2 3 4 5 6 7 编号为1的人出圈 约瑟夫游戏 1 1 数据区域 指针区域 数组下标 2 3 3 3 4 4 5 5 6 6 7 7 8 0 0 1 2 3 4 5 6 7 编号为3的人出圈 算法设计： 任务四：请为约瑟夫游戏设计算法？ 约瑟夫游戏 1 1 数据域 指针域 数组下标 2 3 3 3 4 4 5 5 6 6 7 7 8 0 0 1 2 3 4 5 6 7 编号为3的人出圈 算法设计： 1.用二维数组a记录约瑟夫环，a[i][0]表示第i+1个人的编号，a[i][1]表示第i+1个人的指针区域。计数器cnt，初始值为0；总人数n,减少1人时，n的值减1；head表示链表头初始值为0；k表示当前位置，初始值为head，prev为k的前一个数的位置，初始值为n-1。 2.计数器cnt每次加1，分两种情况。 ①cnt=m时，当前位置k上的数需要出环，则需要修改prev上的指针域，a[prev][1]=a[k][1]，指向位置k上的指针域指向的数；同时，当前位置发生改变了，k=a[k][1]。并把cnt=0，n=n-1。如果当前的位置k恰好是链表头，则需要修改head的值为a[k][1]。 ②cnt!=m时，只需一起移动prev和k。 3.输出a[head][0]。 约瑟夫游戏 1 1 数据区域 指针区域 数组下标 2 2 3 3 4 4 5 5 6 6 7 7 8 0 0 1 2 3 4 5 6 7 问题一：如何新建单向环状链表？ n,m=map(int,input().split()) a=[] for i in range(n-1): a.append([i+1,i+1]) a.append([n,0]) for i in range(n): print(a[i]) 约瑟夫问题 n,m=map(int,input().split()) a=[] for i in range(n-1): a.append([i+1,i+1]) a.append([n,0]) head=0 prev=n-1 k=head cnt=0 while n>1: cnt+=1 if cnt==m: if k==head: head=a[k][1] a[prev][1]=a[k][1] k=a[k][1] cnt=0 n-=1 else: prev=k k=a[k][1] print(a[head][0]) 1 1 数据区域 指针区域 数组下标 2 2 3 3 4 4 5 5 6 6 7 7 8 0 0 1 2 3 4 5 6 7 约瑟夫游戏 思考：用数组存储数据，并设计算法，用程序实现约瑟夫游戏？ 约瑟夫游戏 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 1 2 3 4 5 6 7 8 算法：用一维数组a存储每个人的编号，用一维数组flag标记是否出列；顺时针记数， 记录在列的人数，到达m时，则输出该编号，并把flag数组对应的值标记为False。 约瑟夫游 ... ...
