热门标签 | HotTags
当前位置:  开发笔记 > 编程语言 > 正文

Python实现约瑟夫环问题的方法

这篇文章主要介绍了Python实现约瑟夫环问题的方法,详细分析了约瑟夫环问题的描述、原理与解决方法,需要的朋友可以参考下
本文实例讲述了Python实现约瑟夫环问题的方法。分享给大家供大家参考,具体如下:

题目:0,1,...,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。

定义函数f(n,m),表示每次在n个数字(0,1,...,n-1)中每次删除第m个数字后最后剩下的数字。

在n个数字中,假设第一个被删除的数字为k,那么删除k之后剩下的n-1个数字为0~k-1,k 1~n-1,并且下一次删除从数字k 1开始计数。第二个序列最后剩下的数字也就是我们要求的数字。于是我们对于剩下的n-1个数字重新编号,k 1编号为0,k 2编号为1,...,0编号为n-k-1,1编号为n-k,k-1编号为n-2,假设f(n-1, m) = x,即n-1个数中,每次删除第m个,最后剩下的数字编号为x,那么这个x就对应着原序列(n个数)中的编号(x + m) % n。可以得到递推关系:

f(n,m)=0, n=1
f(n,m)=[f(n-1,m) + m]%n n>1

Python代码:

#coding=utf8
'''
题目:0,1,...,n-1这n个数字排成一个圆圈,从数字0开始每次从这个圆圈里删除第m个数字。求出这个圆圈里剩下的最后一个数字。
'''
def josephus(n, m):
  if type(n) != type(1) or n <= 0:
    raise Exception('n must be an integer(n > 0)')
  if n == 1:
    return 0
  else:
    return (josephus(n - 1, m) + m) % n
if __name__ == '__main__':
  print josephus(8, 3)
  print josephus(1, 2)
  print josephus(0, 2)

更多关于Python相关内容可查看本站专题:《Python正则表达式用法总结》、《Python数据结构与算法教程》、《Python Socket编程技巧总结》、《Python函数使用技巧总结》、《Python字符串操作技巧汇总》、《Python入门与进阶经典教程》及《Python文件与目录操作技巧汇总》

希望本文所述对大家Python程序设计有所帮助。

推荐阅读
  • 二维几何变换矩阵解析
    本文详细介绍了二维平面上的三种常见几何变换:平移、缩放和旋转。通过引入齐次坐标系,使得这些变换可以通过统一的矩阵乘法实现,从而简化了计算过程。文中不仅提供了理论推导,还附有Python代码示例,帮助读者更好地理解这些概念。 ... [详细]
  • Coursera ML 机器学习
    2019独角兽企业重金招聘Python工程师标准线性回归算法计算过程CostFunction梯度下降算法多变量回归![选择特征](https:static.oschina.n ... [详细]
  • Java 实现二维极点算法
    本文介绍了一种使用 Java 编程语言实现的二维极点算法。该算法用于从一组二维坐标中筛选出极点,适用于需要处理几何图形和空间数据的应用场景。文章不仅详细解释了算法的工作原理,还提供了完整的代码示例。 ... [详细]
  • 目录一、salt-job管理#job存放数据目录#缓存时间设置#Others二、returns模块配置job数据入库#配置returns返回值信息#mysql安全设置#创建模块相关 ... [详细]
  • 本次挑战涉及数组截断操作,初看似乎简单,但实际上考察了对数组切片方法的理解与应用。本文将详细解析该算法的实现逻辑,并提供多个示例以加深理解。 ... [详细]
  • 华为智慧屏:超越屏幕尺寸的智能进化
    继全球发布后,华为智慧屏于9月26日在上海正式亮相,推出65英寸和75英寸版本。该产品不仅在屏幕尺寸上有所突破,更在性能和智能化方面实现了显著提升。 ... [详细]
  • 本文介绍如何利用栈数据结构在C++中判断字符串中的括号是否匹配。通过顺序栈和链栈两种方式实现,并详细解释了算法的核心思想和具体实现步骤。 ... [详细]
  • Redux入门指南
    本文介绍Redux的基本概念和工作原理,帮助初学者理解如何使用Redux管理应用程序的状态。Redux是一个用于JavaScript应用的状态管理库,特别适用于React项目。 ... [详细]
  • 历经三十年的开发,Mathematica 已成为技术计算领域的标杆,为全球的技术创新者、教育工作者、学生及其他用户提供了一个领先的计算平台。最新版本 Mathematica 12.3.1 增加了多项核心语言、数学计算、可视化和图形处理的新功能。 ... [详细]
  • 机器学习核心概念与技术
    本文系统梳理了机器学习的关键知识点,涵盖模型评估、正则化、线性模型、支持向量机、决策树及集成学习等内容,并深入探讨了各算法的原理和应用场景。 ... [详细]
  • 如何使用Ping命令来测试网络连接?当网卡安装和有关参数配置完成后,可以使用ping命令来测试一下网络是否连接成功。以winXP为例1、打开XP下DOS窗口具体操作是点击“开始”菜 ... [详细]
  • 本文总结了优化代码可读性的核心原则与技巧,通过合理的变量命名、函数和对象的结构化组织,以及遵循一致性等方法,帮助开发者编写更易读、维护性更高的代码。 ... [详细]
  • 深入解析Java虚拟机(JVM)架构与原理
    本文旨在为读者提供对Java虚拟机(JVM)的全面理解,涵盖其主要组成部分、工作原理及其在不同平台上的实现。通过详细探讨JVM的结构和内部机制,帮助开发者更好地掌握Java编程的核心技术。 ... [详细]
  • 本文详细介绍了Hive中用于日期和字符串相互转换的多种函数,包括从时间戳到日期格式的转换、日期到时间戳的转换,以及如何处理不同格式的日期字符串。通过这些函数,用户可以轻松实现日期和字符串之间的灵活转换,满足数据处理中的各种需求。 ... [详细]
  • 1.执行sqlsever存储过程,消息:SQLServer阻止了对组件“AdHocDistributedQueries”的STATEMENT“OpenRowsetOpenDatas ... [详细]
author-avatar
mobiledu2502860957
这个家伙很懒,什么也没留下!
PHP1.CN | 中国最专业的PHP中文社区 | DevBox开发工具箱 | json解析格式化 |PHP资讯 | PHP教程 | 数据库技术 | 服务器技术 | 前端开发技术 | PHP框架 | 开发工具 | 在线工具
Copyright © 1998 - 2020 PHP1.CN. All Rights Reserved | 京公网安备 11010802041100号 | 京ICP备19059560号-4 | PHP1.CN 第一PHP社区 版权所有