当前位置: 首页 > news >正文

每日一练:约瑟夫生者死者小游戏

在这里插入图片描述

1. 问题描述

  约瑟夫问题(Josephus problem)是一个经典的数学和计算机科学问题,源于犹太历史学家弗拉维奥·约瑟夫斯(Flavius Josephus)的著作《犹太战记》。问题的描述如下:
  在这个问题中,有n个人站成一个圈,从1n编号。从第一个人开始,每次数m个人,数到第m个人就将其从圈中删除,然后从下一个人开始重新数,重复这个过程,直到所有人都被删除。问题是,最后剩下的那个人的编号是多少?
  为了解决约瑟夫问题,可以使用递归或迭代的方法。下面是一个简单的递归解法的伪代码:

function josephus(n, m):if n == 1:return 1else:return (josephus(n - 1, m) + m - 1) % n + 1

  这个递归函数的基本思想是:假设已知n-1个人的问题的解,那么在这个基础上,考虑第n个人加入的情况。在每一轮中,我们实际上将问题规模缩小为n-1个人。
  注意,这里的编号是从1开始的,因为在问题的原始描述中,人的编号是从1到n的。在某些变体中,编号可能从0开始,因此在实现时需要注意这一点。

2. 解题思路

  解决约瑟夫问题的一般思路是通过模拟每一轮的删除过程,不断更新当前位置,并在满足终止条件时停止模拟。下面是一种基于迭代的解题思路和设计:
  解题思路

  1. 初始化: 创建一个包含n个人初始编号的列表,并初始化一个变量表示当前位置。
  2. 循环删除过程:
  • 在当前位置开始数m个人。
  • 计算出要删除的人的位置。
  • 从列表中删除该位置的人。
  • 更新当前位置为删除位置。
  1. 终止条件: 当剩下的人数满足终止条件时,停止循环。
  2. 返回结果: 根据具体要求返回结果。在约瑟夫问题中,通常是返回最后剩下的一个人的编号或一组编号。

3. 代码实现

3.1 代码实现一

  30 个人在一条船上,超载,需要 15 人下船。于是人们排成一队,排队的位置即为他们的编号。报数,从 1 开始,数到 9 的人下船。如此循环,直到船上人不能数到9人为止,问剩下的人的编号?

def josephus(n, m):# 创建一个列表,表示n个人的初始编号people = list(range(1, n + 1))# 初始化变量,表示当前位置current = 0# 循环,直到剩下8个人while len(people) > 8:# 计算下一个要删除的人的位置current = (current + m - 1) % len(people)# 删除当前位置的人del people[current]# 返回剩下的最后一个人的编号return people# 示例:有30个人,每次数9个人
result = josephus(30, 9)
print("最后剩下的人的编号是:", result) 

运行效果:

在这里插入图片描述

3.2 代码实现二

  题目修改为:
  30 个人在一条船上,超载,需要 15 人下船。于是人们排成一队,排队的位置即为他们的编号。报数,从 1 开始,数到 9 的人下船。如此循环,直到船上仅剩 15 人为止,问剩下的人的编号?

def josephus(n, m, k):# 创建一个包含n个人初始编号的列表people = list(range(1, n + 1))# 初始化变量,表示当前位置current = 0# 循环,直到剩下的人数满足终止条件while len(people) > k:# 在当前位置开始数m个人,计算出要删除的人的位置current = (current + m - 1) % len(people)# 从列表中删除该位置的人del people[current]# 返回剩下的人的编号return people# 示例:有30个人,每次数9个人删除,直至剩下15个人
result = josephus(30, 9, 15)
print("剩下的人的编号是:", result)

在这里插入图片描述

3.3 代码实现三

  题目修改为:
  30 个人在一条船上,超载,需要 15 人下船。于是人们排成一队,排队的位置即为他们的编号。报数,从 5 开始,数到 9 的人下船。如此循环,直到船上仅剩 15 人为止,问剩下的人的编号?

def josephus_with_start(n, m, k, start):people = list(range(1, n + 1))current = start - 1  # 起始位置while len(people) > k:current = (current + m - 1) % len(people)del people[current]return people# 示例:有30个人,每次数9个人删除,直至剩下15个人,起始位置为5
result = josephus_with_start(30, 9, 15, 5)
print("剩下的人的编号是:", result)

在这里插入图片描述

3.4 代码实现四

  题目修改为:
  30 个人在一条船上,超载,需要 15 人下船。于是人们排成一队,排队的位置即为他们的编号。报数,从 1 开始,数到 9 的人下船,但是每隔一轮人才下船。如此循环,直到船上仅剩 15 人为止,问剩下的人的编号?

def josephus_with_custom_deletion(n, m, k, deletion_rule):people = list(range(1, n + 1))current = 0while len(people) > k:current = deletion_rule(current, m, len(people))del people[current]return people# 示例:有30个人,每次数9个人删除,直至剩下15个人,但是每隔一轮删除一个人
def custom_deletion_rule(current, m, length):return (current + m) % lengthresult = josephus_with_custom_deletion(30, 9, 15, custom_deletion_rule)
print("剩下的人的编号是:", result)

在这里插入图片描述

4.参考:

https://www.runoob.com/python3/python-joseph-life-dead-game.html

在这里插入图片描述

相关文章:

每日一练:约瑟夫生者死者小游戏

1. 问题描述 约瑟夫问题(Josephus problem)是一个经典的数学和计算机科学问题,源于犹太历史学家弗拉维奥约瑟夫斯(Flavius Josephus)的著作《犹太战记》。问题的描述如下:   在这个问题中,有n…...

双指针算法(题目与答案讲解)

文章目录 题目移动零复写零两数之和N数之和(>2个数) 答案讲解移动零复写零两数之和N数之和 题目 力扣 移动零 1、移动零:题目链接 复写零 2、复写零:题目链接 两数之和 3、两数之和题目链接 N数之和(>2个数) 4、N数之和(三个数、四个数) 三个数:题目链接 四个数题目链接…...

python服装电商系统vue购物商城django-pycharm毕业设计项目推荐

系统面向的使用群体为商家和消费者,商家和消费者所承担的功能各不相同,所对象的权限也各不相同。对于消费者和商家设计的功能如下: 对于消费者设计了五大功能模块: (1) 商品信息:用户可在商品…...

数据治理技术:研究现状与数据规范

随着信息技术的迅速发展,数据规模逐渐扩大,与此同时,劣质数据也随之而来,极大地降低了数据挖掘的质量,对信息社会造成了严重的困扰,劣质数据大量存在于很多领域和机构,国外权威机构的统计表明:美…...

一文彻底理解索引下推

了解索引下推吗?二级索引取出的数据是依次回表还是一次回表?索引下推是为了什么发明的? 看完这个文章你将知道上面的问题。 索引下推的概念 从MySQL5.6开始引入的一个特性,索引下推通过减少回表的次数来提高数据库的查询效率; 注意&#…...

Springboot3+vue3从0到1开发实战项目(一)

一. 可以在本项目里面自由发挥拓展 二. 知识整合项目使用到的技术 后端开发 : Validation, Mybatis,Redis, Junit,SpringBoot3 ,mysql,Swagger, JDK17 ,JWT,项目部署 前端开发: Vue3,Vite&am…...

[字符串操作] 有年代的病历单

有年代的病历单 题目描述 小英是药学专业大三的学生,暑假期间获得了去医院药房实习的机会。 在药房实习期间,小英扎实的专业基础获得了医生的一致好评,得知小英在计算概论中取得过好成绩后,主任又额外交给她一项任务&#xff0c…...

怎么批量提取文件名字到Excel中?

怎么批量提取文件名字到Excel中?Excel是由微软公司开发的一种电子表格软件,它是Microsoft Office办公套件的一部分。Excel提供了强大的数据处理和分析功能,用户可以使用Excel创建、编辑和管理电子表格,进行各种计算、数据分析、图…...

QT搭建的Ros/librviz的GUI软件

1.前言 开发初期学习了下面博主的文章,也报了他在古月局的课,相当于感谢吧。 ROS Qt5 librviz人机交互界面开发一(配置QT环境)-CSDN博客​​​​​​​r 软件前期也是参考他的开源项目 GitHub - chengyangkj/Ros_Qt5_Gui_App …...

Docker 概述与安装

文章目录 1. Docker简介2. 传统虚拟机和容器3. Docker运行速度快的原因4. Docker软件4.1 Docker镜像4.2 Docker容器4.3 Docker仓库 5. Docker架构6. CentOS安装Docker6.1 卸载旧版本6.2 配置yum资源库6.3 安装Docker引擎6.4 启动docker引擎6.5 设置开机自启 7. 卸载Docker8. 运…...

JS作用域与作用域链

让我为大家介绍一下作用域与作用域链吧! 作用域 作用域规定了变量能够访问的“范围”,离开了这个“范围”变量便不能被访问。 作用域分为:局部作用域,全局作用域 一、局部作用域 局部作用域分为函数作用域与块作用域 1.函数作…...

elmentui 查看大图组件 点击图片关闭弹窗方法

elmentui 查看大图组件 点击图片关闭弹窗方法 html <el-imageref"Imgs":src"item.url ? item.url : ":preview-src-list"item.url ? [item.url] : []"click.stop"handlePreviewClose"class"alarm_img"/>js //图片…...

蓝桥杯官网练习题(最长子序列)

题目描述 我们称一个字符串S 包含字符串 T 是指 T 是 S 的一个子序列&#xff0c;即可以从字符串 S 中抽出若干个字符&#xff0c;它们按原来的顺序组合成一个新的字符串与 T 完全一样。 给定两个字符串 S 和 T&#xff0c;请问 T 中从第一个字符开始最长连续多少个字…...

Make sure that using this pseudorandom number generator is safe here.

问题类型&#xff1a;安全热点 安全问题级别&#xff1a;MEDIUM 一、问题代码 工具类Package&#xff1a; Java commons-lang3 库 RandomUtils 随机数工具类 import org.apache.commons.lang3.RandomUtils; 用法&#xff1a; RandomUtils.nextInt(0, 999999999) //生成 0…...

【C/C++】常见模拟题题解

题解 模拟双目运算符一元二次方程求解水仙花数统计学生成绩学生成绩管理模拟选举大小写字符转换最大公约数、最小公倍数字符串反序 模拟双目运算符 编写一个根据用户键入的两个操作数和一个双目运算符&#xff0c;由计算机输出结果的程序。 #include<stdio.h>int opera…...

TikTok 购物和直播的 5 个简单技巧

TikTok 的一切都很大&#xff1a;应用程序下载量、受众规模和病毒式营销活动。因此&#xff0c;该公司多方面进军社交商务也就不足为奇了。是的&#xff0c;这将是巨大的。自去年年底以来&#xff0c;TikTok Shopping 和TikTok 直播购物活动已在一些市场上线&#xff0c;并将于…...

神经网络中BN层简介及位置分析

1. 简介 Batch Normalization是深度学习中常用的技巧&#xff0c;Batch Normalization: Accelerating Deep Network Training by Reducing Internal Covariate Shift (Ioffe and Szegedy, 2015) 第一次介绍了这个方法。 这个方法的命名&#xff0c;明明是Standardization, 非…...

BGP基础配置

EBGP是AS之间 IBGP是AS内 R1-R2是EBGP,R4-R5是EBGP R2-R3-R4是IBGP 第一步基础配置&#xff1a;IP地址 [r1-GigabitEthernet0/0/0]ip ad 12.0.0.1 24 [r1-LoopBack0]ip ad 1.1.1.1 32 [r2-GigabitEthernet0/0/0]ip ad 12.0.0.2 24 [r2-LoopBack0]ip ad 2.2.2.2 32 [r2-Loop…...

【开题报告】基于深度学习的驾驶员危险行为检测系统

研究的目的、意义及国内外发展概况 研究的目的、意义&#xff1a;我国每年的交通事故绝对数量是一个十分巨大的数字&#xff0c;造成了巨大的死亡人数和经济损失。而造成交通事故的一个很重要原因就是驾驶员的各种危险驾驶操作行为。如果道路驾驶员的驾驶行为能够得到有效识别…...

Linux云服务器打包部署前端Vue项目

1. 打包 在项目包的终端使用命令打包成dist文件。 npm run build2. Linux云服务器上创建文件夹 mkdir /home/www/dist注&#xff1a;dist文件夹不用创建&#xff0c;将打包好的dist.zip放进去&#xff0c;然后解压就行。 3. 安装nginx yum install -y nginx4. 修改配置文件…...

React Native 开发环境搭建(全平台详解)

React Native 开发环境搭建&#xff08;全平台详解&#xff09; 在开始使用 React Native 开发移动应用之前&#xff0c;正确设置开发环境是至关重要的一步。本文将为你提供一份全面的指南&#xff0c;涵盖 macOS 和 Windows 平台的配置步骤&#xff0c;如何在 Android 和 iOS…...

23-Oracle 23 ai 区块链表(Blockchain Table)

小伙伴有没有在金融强合规的领域中遇见&#xff0c;必须要保持数据不可变&#xff0c;管理员都无法修改和留痕的要求。比如医疗的电子病历中&#xff0c;影像检查检验结果不可篡改行的&#xff0c;药品追溯过程中数据只可插入无法删除的特性需求&#xff1b;登录日志、修改日志…...

【JVM】- 内存结构

引言 JVM&#xff1a;Java Virtual Machine 定义&#xff1a;Java虚拟机&#xff0c;Java二进制字节码的运行环境好处&#xff1a; 一次编写&#xff0c;到处运行自动内存管理&#xff0c;垃圾回收的功能数组下标越界检查&#xff08;会抛异常&#xff0c;不会覆盖到其他代码…...

Go 语言接口详解

Go 语言接口详解 核心概念 接口定义 在 Go 语言中&#xff0c;接口是一种抽象类型&#xff0c;它定义了一组方法的集合&#xff1a; // 定义接口 type Shape interface {Area() float64Perimeter() float64 } 接口实现 Go 接口的实现是隐式的&#xff1a; // 矩形结构体…...

五年级数学知识边界总结思考-下册

目录 一、背景二、过程1.观察物体小学五年级下册“观察物体”知识点详解&#xff1a;由来、作用与意义**一、知识点核心内容****二、知识点的由来&#xff1a;从生活实践到数学抽象****三、知识的作用&#xff1a;解决实际问题的工具****四、学习的意义&#xff1a;培养核心素养…...

html-<abbr> 缩写或首字母缩略词

定义与作用 <abbr> 标签用于表示缩写或首字母缩略词&#xff0c;它可以帮助用户更好地理解缩写的含义&#xff0c;尤其是对于那些不熟悉该缩写的用户。 title 属性的内容提供了缩写的详细说明。当用户将鼠标悬停在缩写上时&#xff0c;会显示一个提示框。 示例&#x…...

rnn判断string中第一次出现a的下标

# coding:utf8 import torch import torch.nn as nn import numpy as np import random import json""" 基于pytorch的网络编写 实现一个RNN网络完成多分类任务 判断字符 a 第一次出现在字符串中的位置 """class TorchModel(nn.Module):def __in…...

【MATLAB代码】基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),附源代码|订阅专栏后可直接查看

文章所述的代码实现了基于最大相关熵准则(MCC)的三维鲁棒卡尔曼滤波算法(MCC-KF),针对传感器观测数据中存在的脉冲型异常噪声问题,通过非线性加权机制提升滤波器的抗干扰能力。代码通过对比传统KF与MCC-KF在含异常值场景下的表现,验证了后者在状态估计鲁棒性方面的显著优…...

(一)单例模式

一、前言 单例模式属于六大创建型模式,即在软件设计过程中,主要关注创建对象的结果,并不关心创建对象的过程及细节。创建型设计模式将类对象的实例化过程进行抽象化接口设计,从而隐藏了类对象的实例是如何被创建的,封装了软件系统使用的具体对象类型。 六大创建型模式包括…...

关于easyexcel动态下拉选问题处理

前些日子突然碰到一个问题&#xff0c;说是客户的导入文件模版想支持部分导入内容的下拉选&#xff0c;于是我就找了easyexcel官网寻找解决方案&#xff0c;并没有找到合适的方案&#xff0c;没办法只能自己动手并分享出来&#xff0c;针对Java生成Excel下拉菜单时因选项过多导…...