Joseph 问题
设编号为1,2，....n的n个人围坐成一圈，约定编号为K（1<k<=n）的人从1开始报数，数到m的那个人出列，他的下一位又开始从1报数，数到m的那个人又出列，以此类推，直到所有的人出列为止，由此产生一个出队编号的序列。
约瑟夫链表创建思路
image.png
小孩出圈思路
image.png
python代码：
#创建一个Boy类，表示一个节点
class Boy:
def __init__(self,no):
self.no = no
self.next = None
def getNo(self):
return self.no
def setNo(self,no):
self.no = no
def getNext(self):
return self.next
def setNext(self,next):
self.next = next
#创建一个环形单向链表
class CircleSingleLinkedList:
def __init__(self):
#创建一个first节点，当前没有编号
self.first = Boy(-1)
def addBoy(self,nums):
#nums 做一个数据检验
if nums < 1 :
print("nums的值不正确")
return
curBoy = Boy(None) #辅助指针构建环形链表
#使用for循环创建环形链表
r1 = range(0,nums)
for i in r1:
#根据编号创建小孩
boy = Boy(i+1)
#如果是第一个小孩
if i==0:
self.first = boy
self.first.setNext(self.first) #构成环
curBoy = self.first #让curBoy指向第一个小孩
else:
curBoy.setNext(boy)
boy.setNext(self.first)
curBoy = boy
#遍历当前环形链表
def showBoy(self):
if self.first ==None:
print('链表为空')
return
curBoy = self.first
while True:
print("小孩的编号 "+ str(curBoy.getNo()))
if curBoy.getNext()==self.first: #说明已经遍历完成
break
curBoy = curBoy.getNext()
#根据用户的输入，算出小孩出圈的顺序
"""
@param startNo 表示从第几个小孩开始数数
@param contNum 表示数几下
@param nums 表示最初有多少个小孩在圈中
"""
def countBoy(self, startNo, countNum, nums):
#先对数据进行校验
if self.first==None or startNo < 1 or startNo > nums:
print('参数输入有误，请重新输入')
return
#传概念要给辅助指针，帮助小孩出圈
helper = self.first
while True:
if helper.getNext() == self.first:#说明helper指向最后小孩节点
break
helper = helper.getNext()
#小孩报数前，先让first和helper移动k-1次
for j in range(0,startNo-1):
self.first = self.first.getNext()
helper = helper.getNext()
#当小孩报数时，让first和helper指针同时移动 m - 1次,然后出圈
#这里是一个循环操作，知道圈中只有一个节点
while True:
if helper == self.first: #说明圈中只有一个节点
break
#让first和helper 指针同时的移动countNum - 1
for j in range(0,countNum-1):
self.first = self.first.getNext()
helper = helper.getNext()
#这时first指向的节点，就是要出圈的小孩节点
print(str(self.first.getNo())+"号小孩出圈\n")
#将first指向的小孩节点出圈
self.first = self.first.getNext()
helper.setNext(self.first)
print("最后留在圈中的小孩编号: "+str(helper.getNo()))
def main():
#进行测试
#先创建节点
circleSingleLinkedList = CircleSingleLinkedList()
circleSingleLinkedList.addBoy(5)
circleSingleLinkedList.showBoy()
#测试小孩出圈是否正确
circleSingleLinkedList.countBoy(1,2,5)
if __name__ == '__main__':
main()
