使用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
猜你喜欢
- 本文实例讲述了Python3.5装饰器原理及应用。分享给大家供大家参考,具体如下:1、装饰器:(1)本质:装饰器的本质是函数,其基本语法都是
- 在部署一套内网测试环境时,频繁宕机,开机后不断的吃内存,重启apache之后内存占用会不停的上涨,直到swap用完,直到死机,由于是内网环境
- 1. 用户输入内容与打印输入:input()输出:print()例1,输入字符串,并原样输出a = input('请输入一些字符
- 创建py文件总是为txt格式问题记录写代码过程中创建.py文件时,一直正常,但创建名称为train.py文件时总是为txt格式,即使选择了p
- 今天有个需要需要传递中文参数给URL但是在GBK环境下的脚本传递GBK的参数老是给我报UNICODE的解码错误。烦的很。所以我们果断选择用u
- 解释机器学习模型是一个困难的过程,因为通常大多数模型都是一个黑匣子,我们不知道模型内部发生了什么。创建不同类型的可视化有助于理解模型是如何执
- 1、新建独立运行环境,命名为env[root@vultr ~]# mkdir projects # 测试的项目总目录[root@vultr
- 先来看一个例子:>>> def foo(*args, **kwargs): print
- 不错,这个是一个文章详细页,没有左右两栏布局,不过这里我重点要讲的是合理的布局,在稍后的文章中我会详细的介绍浮动元素。好,回到刚才的话题,大
- ★二维数组的使用方式:先声明或者定义,再赋值1)语法:var 数组名[大小][大小]类型2)比如:var arr[2][3]int[][]两
- [Python标准库]decimal——定点数和浮点数的数学运算 &n
- Socket服务器是网络服务中常用的服务器。使用go语言实现这个业务场景是很容易的。这样的网络通讯,需要一个服务端和至少一个客户端。我们计划
- 130 :文件格式不正确。(还不是很清楚错误的状况) 145 :文件无法打开。 1005:创建表
- 在印刷排版中“point”是一个绝对的单位,它等于 1/72 英寸。可以用尺子丈量的,物理的英寸。但在CSS中pt的含义
- I. 前言在上一篇文章深入理解PyTorch中LSTM的输入和输出(从input输入到Linear输出)中,我详细地解释了如何利用PyTor
- 从有道词典网页获取某单词的中文解释。import reimport urllibword=raw_input('input a wo
- 核心代码:#!/usr/bin/python# -*- coding: UTF-8 -*-import smtplibimport osim
- XmlDocume
- 本文实例讲述了Python 私有化操作。分享给大家供大家参考,具体如下:私有化xx: 公有变量_x: 单前置下划线,私有化属性或方法,fro
- 本文为大家分享了python爬取酷狗音乐排行榜的具体代码,供大家参考,具体内容如下#coding=utf-8from pymongo imp