“约瑟夫问题”教学思路:环球视点

说在前面

约瑟夫问题是一个经典的数学应用问题，它通过循环报数不断删除序列中的元素，直至剩下1个（或多个）人为止。编程解决约瑟夫问题的算法很多，基本思想都是模拟报数过程，区别在于数据结构不同，删除元素的方法也不一样。

约瑟夫问题可以考查使用模运算实现循环报数功能，使用循环链表、循环队列等数据结构模拟报数和删除元素过程，变例繁多、算法难度较高、综合性强，是需要重点掌握的经典案例。

(资料图片仅供参考)

教材文本

教材处理教材2.2.1例2“约瑟夫问题”采用循环单链表来存储数据，节点数据域为参与人员的编号。通过遍历链表来模拟报数过程，并删除节点以实现淘汰人员功能，直至只剩一个节点为止。总体来说，例2程序逻辑清晰，可读性强，学生容易理解。但我们不应该满足于单一解法，可在理解例题的基础上，拓展思考程序改进方案和采用不同数据结构实现算法功能。学生任务单阅读教材P49例2“约瑟夫问题”，思考如下问题：（1）书中程序节点的数据域和指针域分别存储了什么内容？它是如何构造循环单链表的？（2）书中程序设置了多个指向节点的指针变量，例如head,k和t，它们分别指向哪些节点？（3）书中程序是如何实现删除节点功能的？（4）书中程序使用变量long来记录链表长度，并用long>1作为循环条件，这样做是必需的吧？能否去除变量long，使用其他方法来判断循环链表长度是否为1？（5）下列程序也能解决约瑟夫问题，试比较其与教材程序的异同，并完成填空。

n=int(input("请输入参与人数（N）："))

m=int(input("请输入淘汰数（M）："))

a = [[i+1,i+1] for i in range(n-1)]

a.append(填空1) # 最后一个人的下一位是第一个人

pre = len(a) - 1 # 指向前驱节点

while 填空2: # 循环单链表中节点数量大于1

for i in range(1, m): # 报数[1,m-1]的人留下

pre = 填空3

a[pre][1] = 填空4 # 报数m的人离开（删除a[pre][1]）

print(f"幸存者位置为：{a[pre][0]}")

问题解析（1）书中程序节点的数据域存储的是参与人员的初始编号，指针域存储的是后继节点的位置（在列表llist中的下标）。程序通过将尾节点的指针指向头节点，构成循环单链表。（2）head指向单链表的头节点；k用来遍历链表，它指向当前节点；t用来指向k的后继节点，即被删除的节点，它只在删除节点时出现。（3）书中程序使用如下代码实现删除节点功能：

if i==m: # 报数为m时删除k的后继节点t

t=a[k][1] # 用t指向节点k的后继节点

a[k][1]=a[t][1] # 修改k的后继指针，以实现删除节点t功能

if t==head: # 删除头节点时需要修改头指针

head=a[k][1] # 或者head=a[t][1]

i=1 # 计数器归1

long-=1 # 链表长度减1

程序通过修改k的后继指针，实现删除其后继节点的功能。为了增强代码的可读性，程序设置变量t指向节点k的后继节点，然后修改a[k][1]=a[t][1]，这样就能实现删除节点t的功能了。为了使head始终指向链表的头节点，当被删除节点是头节点时需要修改头指针head。

删除某个节点后，程序让计数器i归1，并使记录链表长度的变量long减1，准备下一轮报数。

（4）书中程序使用变量long来记录链表长度，这不是必需的。可以利用循环链表自身特征来判断其长度是否为1。若t指向当前节点，则当a[t][1] == t时，表示链表长度为1。（5）如下程序直接使用pre指向报数人员的前驱节点，通过语句a[pre][1] = a[a[pre][1]][1]，可实现删除节点a[pre][1]的功能；把while循环条件改成a[pre][1]!= pre，可以判断循环单链表中节点数量是否大于1。这种做法无需引入变量long，甚至无需引入头指针head，代码较为简明。

n=int(input("请输入参与人数（N）："))

m=int(input("请输入淘汰数（M）："))

a = [[i+1,i+1] for i in range(n-1)]

a.append([n, 0]) # 最后一个人的下一位是第一个人

pre = len(a) - 1 # 指向前驱节点

while a[pre][1] != pre: # 循环单链表中节点数量大于1

for i in range(1, m): # 报数[1,m-1]的人留下

pre = a[pre][1]

a[pre][1] = a[a[pre][1]][1] # 报数m的人离开（删除a[pre][1]）

print(f"幸存者位置为：{a[pre][0]}")

课后作业

教材程序通过遍历链表来模拟报数过程，并删除节点以实现淘汰人员功能，直至只剩一个节点为止。除此之外，你还能想到别的方法来解决约瑟夫问题吗？例如使用一维数组和循环队列等数据结构来存储数据，又该如何编写代码呢？

需要本文word文档、源代码和课后思考答案的，可以加入“Python算法之旅”知识星球参与讨论和下载文件，“Python算法之旅”知识星球汇集了数量众多的同好，更多有趣的话题在这里讨论，更多有用的资料在这里分享。

我们专注Python算法，感兴趣就一起来！

相关优秀文章：

阅读代码和写更好的代码

最有效的学习方式

Python算法之旅文章分类

关键词： 删除节点 数据结构 循环链表