使用python从三个角度解决josephus问题的方法

作者:johnjim0816 时间:2022-02-22 02:19:55 

0 写在前面

josephus问题是数据结构教材中的一个常见实例,其问题可以描述为:

设nnn个人围坐一圈,现在要求从第kkk个人开始报数,报到第mmm个的人退出。然后从下一个人开始继续按照同样规则报数并退出,直到所有人退出为止。要求按照顺序输出每个人的序列号。

1 基于数组概念的解法

首先考虑基于python的list和固定大小的数组概念,即将list看作元素个数固定的对象,只改变值而不删除元素,相当于摆了一圈nnn把椅子,人虽然退出但是椅子还在,我们可以给每个人从111到nnn编号,没有人的位置用000表示,思路如下:

初始

  • 建立包含nnn个人(编号)的list

  • 找到第kkk个人开始

运行

  • 从kkk的位置开始数到mmm,中间遇到000的就跳过

  • 数到mmm之后,将其值改为000

  • 然后继续循环,总共循环nnn次(因为每次循环就会退出一个人)

代码如下:


def josephus_A(n, k, m):
 people = list(range(1, (n+1)))
 i = k-1
 for num in range(n):
   count = 0
   while count < m:
     if people[i] > 0:
       count += 1
     if count == m:
       print(people[i], end=" ")
       people[i] = 0
     i = (i+1) % n # count只是flag,真正记的数是i
   if num < n-1:
     print(end=",", )
   else:
     print(" ")

2 基于顺序表的解法

顺序表是线性表的一种,即表中元素放在一块足够大的连续存储区里,首元素存入存储区开始位置,其余元素依次存放。顺序表在python中的也是list,跟第一种解法不同,当第mmm个人退出需要进行删除元素的操作,才是顺序表。而第一种解法的数组想要删除并不是那么容易,这里是因为python中没有内置对数组的支持,所以用list代替,具体可以参照c++中的数组,如果要删除中间的某个元素的话,必须对后面的元素重新编号。代码实现如下:


def josephus_L(n, k, m):
 people = list(range(1, (n+1)))
 i=k-1
 for num in range(n,0,-1):
   i=(i+m-1)%num
   print(people.pop(i),end=", " if num>1 else "\n")

3 基于循环单链表的解法

单链表即单向链接表,典型的就是c++中的链表,循环单链表就是头尾相连的单链表,也是线性表的一种,这道题目使用循环单链表记录nnn个人围坐一圈最为契合。我们只需要数到第mmm个结点就删除,删除操作对于链表来说比较容易,而且不需要有i = (i+1) % n这样的整除操作。但是问题在于python并没有像c++那样有内置对链表的支持,因此需要建立一个链表的类,建立是比较麻烦的,但是操作比较简单,如下:


class LNode: # 建立链表结点
 def __init__(self,elem,next_=None):
   self.elem=elem
   self.next=next_
class LCList: # 建立循环链接表
 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=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 is None:
     raise LinkedListUnderflow("in pop of CLList")
   p = self._rear.next
   if self._rear is p:
     self._rear =None
   else:
     self._rear.next=p.next
   return p.elem
 def printall(self): # 输出表元素
   if self.is_empty():
     return
   p = self._rear.next
   while True:
     print(p.elem)
     if p is self._rear:
       break
     p=p.next
class LinkedListUnderflow(ValueError): # 自定义异常
 pass
class Josephus(LCList):
 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(),end=("\n" if self.is_empty() else ", "))
 def turn(self,m):
   for i in range(m):
     self._rear = self._rear.next

来源:https://blog.csdn.net/JohnJim0/article/details/105088977

标签:python,josephus
0
投稿

猜你喜欢

  • 浅谈Python 对象内存占用

    2022-04-01 11:21:40
  • 如何解决国外空间显示乱码问题

    2007-11-18 14:28:00
  • 使用卷积神经网络(CNN)做人脸识别的示例代码

    2023-12-31 06:25:05
  • python pandas合并Sheet,处理列乱序和出现Unnamed列的解决

    2022-08-26 06:23:41
  • JavaScript面向对象之Prototypes和继承

    2024-04-23 09:14:54
  • swiper 自动图片无限轮播实现代码

    2024-06-09 17:26:12
  • 德国ebay购头记

    2009-04-29 11:10:00
  • python实现对求解最长回文子串的动态规划算法

    2023-11-09 10:18:49
  • OpenCV-Python实现人脸磨皮算法

    2022-12-29 18:00:06
  • python装饰器实现对异常代码出现进行自动监控的实现方法

    2021-05-29 16:52:13
  • python 利用百度API进行淘宝评论关键词提取

    2021-11-14 19:32:36
  • Git 命令使用技巧提供工作效率

    2022-05-11 18:01:33
  • asp如何用下拉列表显示数据库里的内容?

    2010-06-16 09:54:00
  • python字典序问题实例

    2023-07-31 05:46:58
  • 详解python中@的用法

    2022-05-15 04:52:32
  • Sanic框架Cookies操作示例

    2022-12-24 05:29:04
  • php获取访问者IP地址汇总

    2023-11-14 12:14:06
  • JavaScript属性操作

    2024-04-16 09:52:52
  • Python浮点数取整、格式化和NaN处理的操作方法

    2023-01-12 11:41:19
  • python队列Queue的详解

    2022-10-09 16:56:21
  • asp之家 网络编程 m.aspxhome.com