Python实现约瑟夫环问题的方法
作者:阿涵-_- 发布时间:2021-09-07 19:41:28
标签: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程序设计有所帮助。
0
投稿
猜你喜欢
- 先上一张效果图:以前用angularjs操作基本上都是要取到每个列表的id再循环判断是不是当前点击的列表来显示折叠。今天在这个项目 http
- 变量类型ECMAScript变量可能包含两种不同类型的数据值:基本类型和引用类型。基本类型基本类型指的是简单的数据段,5种基本数据类型:un
- 首先要介绍的是 Python Imaging Library,使用方法如下:from PIL import Imagefrom PIL.Ex
- 实时读取logstash日志,有异常错误keywork即触发报警。# /usr/bin/env python3# -*- coding: u
- 这篇文章主要介绍了Pycharm debug调试时带参数过程解析,文中通过示例代码介绍的非常详细,对大家的学习或者工作具有一定的参考学习价值
- 用ASP实现搜索引擎的功能是一件很方便的事,可是,如何实现类似3721的智能搜索呢?比如,当在搜索条件框内输入“中国人民”时,自动从中提取“
- 对于多层感知机而言,整个模型做的事情就是接收输入生成输出。但是并不是所有的多层神经网络都一样,所以为了实现复杂的神经网络就需要神经网络块,块
- 微博热搜的爬取较为简单,我只是用了lxml和requests两个库url= https://s.weibo.com/top/summary?
- 百度的资料,保存下来:在写按时间段查询的sql语句的时候 一般我们会这么写查询条件:where date>='2010-01-
- 前言当我们使用pandas处理数据的时候,经常会遇到数据重复的问题,如何找出重复数据进而分析重复原因,或者如何直接删除重复的数据是一个关键的
- 00. 什么是 freecache?freecache 是一个用 go 语言实现的本地缓存系统(类似于 lru)。相关的 github 地址
- 1.找到配置文件-打开“开始菜单--Anaconda3文件夹--Anaconda Prompt”-输入命令: jupyter noteboo
- 问题现象元素的属性中没有id、name;虽然有class,但比较大众化,且位置也不固定;例如:页码中的下一页;那该如何找到该元素?<a
- 这里说的“相对路径”是相对于“主调文件”所在的文件夹。#include file #include file后面跟的是文件的“相对路径”,不
- 1、有时候我们可能想让字符串倒序输出,下面给出几种方法方法一:通过索引的方法>>> strA = "abcdeg
- 1、你需要通过指定的文本模式去检查字符串的开头或者结尾,比如文件名后缀,URL Scheme 等等。检 查 字 符 串 开 头 或 结 尾
- 引言 今天和测试沟通一个百分比计算方式时遇到一个问题, 我在存储过程里用到了强转
- vue实现一个分页组件vue-paginaitonvue使用了一段时间的感触就是,我再也不想直接操作DOM了。数据绑定式的编程体验真是好。实
- 实训课期间忙里偷闲的学习了python的selenium包,唯一一点不好是要自己去查英文文档,明摆着欺负我这种英语不好的,想着用谷歌翻译一下
- 一,Socket编程(1)Socket方法介绍Socket是网络编程的一个抽象概念。通常我们用一个Socket表示“打开了一个网络链接“,而