当前位置：首页 > 编程日记 > 正文

Josephus Problem的详细算法及其Python, Java语言的实现

编程日记 2024-10-30 12:20:00

笔者昨天看电视，偶尔看到一集讲述古罗马人与犹太人的战争——马萨达战争，深为震撼，有兴趣的同学可以移步：http://finance.ifeng.com/a/20170627/15491157_0.shtml .
这不仅让笔者想起以前在学数据结构时碰到的Josephus问题：
据说著名犹太历史学家 Josephus有过以下的故事：在罗马人占领乔塔帕特后，39 个犹太人与Josephus及他的朋友躲到一个洞中，39个犹太人决定宁愿死也不要被敌人找到，于是决定了一个自杀方式，41个人排成一个圆圈，由第1个人开始报数，每报数到第3人该人就必须自杀，然后再由下一个重新报数，直到所有人都自杀身亡为止。然而Josephus 和他的朋友并不想遵从，Josephus要他的朋友先假装遵从，他将朋友与自己安排在第16个与第31个位置，于是逃过了这场死亡游戏。
以前我们都是用链表的方法编程来解决这个问题的，这次笔者将会讲述两个不同的方法，一个是笔者自己的朴素想法，一个是数学方法。

朴素方法
数学方法

首先我们先将Josephus问题描述出来，即：共有N个人围成一圈，编号分别为1,2,…,N,从第一个人开始从1到m报数，报到m的人退出，如此循环下去，直至最后一个人。问最后一个人的最开始的编号是几？
先是笔者的朴素想法。
将N个人储存在列表（list）中，每次报到m的元素剔除，并记录下最后一个人报的数i，然后将缩短后的数组从i+1报数，如此循环下去，直至列表的长度为1，这样剩下来的元素就是我们要求的答案。
这种想法虽然素朴，比较容易实现，但是时间复杂度为O(Nm).
接着是数学方法。
假设一开始的Josephus环编号为0,1,2,…,N-1.我们知道第一个人(编号一定是m%N-1) 出列之后，剩下的N-1个人组成了一个新的Josephus环（以编号为k=m%n的人开始）:

k, k + 1, k + 2, . . . . . ., n - 2, n - 1, 0, 1, 2, . . . k - 2

并且从k开始报0.
现在我们把他们的编号做一下转换：

k - - > 0 k + 1 - - > 1 k + 2 - - > 2 . . . k - 2 - - > n - 2 k - 1 - - > n - 1

变换后就成为了(N-1)个人报数的子问题，这启示我们可以用归纳法来解决这个问题。假如我们知道这个子问题的解为x，原来问题的答案为x′,则x′=(x+k)%n.因此，递推公式就有了！令f(i)表示i个人玩游戏报m退出最后胜利者的编号，我们要求的结果是f(N)，其递推公式如下：

f (1) = 0 f (i) = (f (i - 1) + m) % i (i > 1)

数学方法简单明了，计算效率高，但是推导比较困难。
最后，我们给出以下两种方法的Python代码和朴素方法的Java代码，希望能给大家一点思考。
完整的Python代码如下：

# -*- coding: utf-8 -*-# This code is devoted to solve the Josephus Problem by Python.# N: numper of people
# m: cycle number
def solve1(N, m):a = list(range(1, N+1)) # sequenceend = 0 # the number of last man in sequencewhile len(a) > 1:b = []for i in a:if not (end+a.index(i)+1)%m:b.append(i)# print(i, end=' ') # print the order of removingif a.index(i) == len(a)-1: # last man of sequenceend = (end+a.index(i)+1)%m# remove elements in b from afor i in b:a.remove(i)return a[0]# solve the problem by math method
def solve2(N, m):return 0 if N == 1 else (solve2(N-1, m)+m)%N# main function for execution
def main():N, m = 41, 3left1 = solve1(N, m)print('\nThe man left: %d' %left1)left2 = solve2(N, m)+1print('\nThe man left: %d' % left2)main()

完整的Java代码如下：

import java.util.ArrayList;public class Josephus {public static void main(String[] args) {int N = 41;int m = 3;int left = solve(N, m);System.out.println("\nThe man left is "+left+".");}public static int solve(int N, int m) {ArrayList<Integer> a = new ArrayList<Integer>();int end = 0;for(int i=0; i < N; i++)a.add(i+1);while(a.size() > 1) {ArrayList<Integer> b = new ArrayList<Integer>();for(int i: a) {if ((end+a.indexOf(i)+1)%m == 0)b.add(i);// System.out.print(i+"-->");if(a.indexOf(i) == a.size()-1)end = (end+a.indexOf(i)+1)%m;       }for(Object i: b) {a.remove(i);}}return a.get(0);}}

本次分享到此结束，欢迎大家交流~~

https://www.dkcj.cn/info/25307.html

Josephus Problem的详细算法及其Python, Java语言的实现

相关文章：

SlightPHP

bzoj1178

编程能力差，学不好Python、AI、Java等技术，90%是输在了这点上！

cglib代理的使用

使用PHP+Sphinx建立高效的站内搜索引擎

9个必知的 Python 操作文件/文件夹方法

Get/POST方法提交的长度限制

Bitmap上下合成图片

PHP 符号大全

添加Net4CollectionTypeFactory的原因

LTSM 实现多元素时序数据植物健康预测

如何扩大以太坊的规模：分片简介(How to Scale Ethereum: Sharding Explained)

Xdebug的安装-（无错可执行版）

云游戏、VR、AI，云计算给元宇宙提供了哪些想象力？

sys.check_constraints

什么是Bootstrap Aggregating

柯南君：看大数据时代下的IT架构（5）消息队列之RabbitMQ--案例（Work Queues起航）...

图像分析用 OpenCV 与 Skimage，哪一个更好？

NetBeans配置Xdebug

[译] Don’t call me, I’ll call you：使用 Redux-Saga 管理 React 应用中的异步 action （上）...

CentOS下安装NetBeans集成开发环境

我的Android进阶之旅------Android嵌入图像InsetDrawable的用法

沉痛悼念游戏开发大神毛星云

April Fools Contest 2018

如何查找僵尸进程并Kill之，杀不掉的要查看父进程并杀之

PHP计划任务:如何使用Linux的Crontab执行PHP脚本（转）

OpenAI 开放 GPT-3 微调功能，让开发者笑开了花

PHP----------php封装的一些简单实用的方法汇总

PHP函数--var_dump

Mozilla公布WebVR API标准草案