Josephubs(约瑟夫环)解

981 阅读3分钟

问题描述:

Josephubs(约瑟夫环):假设有n个人围坐一圈, 现在要求从k个人开始报数, 报到第m个数的人退出。然后从下一个人开始继续报数并按同样规则退出,直到所有人退出。要求按顺序输出各出列人的编号

问题分析:

  • 初始

    • 建立一个包含n个人(的编号)的表。
    • 找到第k个人, 那里开始。
  • 处理过程中采用把相应表元素修改为0的方式表示已出列, 反复做:

    • 数m个人(尚在座的人),遇到表的末端就转回下标0继续。
    • 把表示第m个人的 表元素修改为0。
  • n个人出列即结束

采用python自带的list ADT模块

思路描述:创建一个list, 当第m个位置被排出的时候该元素位置为0, 那么下次继续设置初始下标为 i+1 % n , count用于统计, 确定在排出所有空位置之后的真实第m个位置。


def josephus(n, k, m):
    people_num = list(range(1, n + 1))
    print(people_num)
    i = k - 1  # 第k个人的下标值
    for num in range(n):
        count = 0  # 用于计算是第几个人
        
        while count < m:
            if people_num[i] != 0:
                count += 1
           
            if m == count:
                print("找到该同学为:{}".format(people_num[i]))
                people_num[i] = 0
            i = (i+1) % n # 下标反转, 第二次查找时由于前面排出一个同学,所以需要+1
        
        if num < n-1:
            print('第{}次查找结束'.format(num))
        else:
            print('结束')
		   
  • 时间复杂度分析
    • 当m=1的时候, 内循环每次只要执行一次,所以内循环的时间复杂度为O(1), 所以综合时间度为O(n)
    • 当 m = n时,那么内循环需要把整个表遍历一遍,之后需要执行 i = (i+1) % n 语句,所以它的时间复杂度为O(n2)。

基于顺序表的解

设计思路:用python list 的pop取出需要元素, 重新计算i值,


def josephus1(n, k, m):
    people_num = list(range(1, n + 1))
    num, i = n, k-1
    
    for num in range(n, 0, -1): # 倒排
        i = (i + m - 1) % num
        print('第{}同学被排出'.format(people_num.pop(i)))
			
  • 时间复杂度分析

    该算法用了一个for循环,时间复杂度为O(n), python list pop()方法也是O(n),所以该方法的综合时间复杂度还是O(n2)

基于循环单链表的解

设计思路: 把围坐一圈的人当成循环链表, 通过next连接,先到初始第k后第m个next时, 删除该节点, 因为是循环节点, 所以可以按照节点顺序依次执行下去, 直到删除最后一个元素


# 首先要创建一个简单的链表节点
class LNode(object):
	def __init__(self, elem, next_=None)
		self.elem = elem
		self.next = next_

# 循环单链表基类
class LClist(objects):
	
	def __init__(self):
		self._rear = None
	
	def is_empty(self):
		return self._rear is None
	
	def prepend(self, elem):
		""" 从头部加入 """
		p = LNode(elem)
		if self._rear is None:
			p.next = p # 单节点组成环
			self._rear.next = p
		else:
			p.next = self._rear.next
			self._rear.next = p
	
	def append(self, elem):
		""" 从尾部插入 """
		self. prepend(elem)
		self._rear = self._rear.next
	
	def pop(self):
		""" 头部弹出 """
		if self._rear._rear is None:
			return False
		
		p = self._rear.next:
		if self._reear is p:
			self._rear = None
		else:
			self._rear = None
		
		return p.elem
	
class Josehups(LCList):
	def turn(self, m):
		for i in range(m):
			self._rear = self._rear.next
		
	
	def __init__(self, n, k, m):
		LCList.__init__(self)
		for i in range(n):
			self.append(i+1)
		
		self.turn(k-1)
		while not self.is_empty():
			self.turn(m-1)
			print(self.pop() if self.is_empty() else "")
	
	
  • 时间复杂度分析

    初建表的复杂度为O(n), 后面循环的算法复杂度为O(m x n), 每次旋转的时间复杂度为O()