摘要：然而和他的朋友并不想遵从，要他的朋友先假装遵从，他将朋友与自己安排在第个与第个位置，于是逃过了这场死亡游戏。问最后一个人的最开始的编号是几先是笔者的朴素想法。这种想法虽然素朴，比较容易实现，但是时间复杂度为接着是数学方法。
笔者昨天看电视，偶尔看到一集讲述古罗马人与犹太人的战争——马萨达战争，深为震撼，有兴趣的同学可以移步：http://finance.ifeng.com/a/20... .
这不仅让笔者想起以前在学数据结构时碰到的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(1)=(f(i-1)+m)% i qquad (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)) # sequence
end = 0 # the number of last man in sequence
while 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 removing
if a.index(i) == len(a)-1: # last man of sequence
end = (end+a.index(i)+1)%m
# remove elements in b from a
for 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, 3
left1 = solve1(N, m)
print("
The man left: %d" %left1)
left2 = solve2(N, m)+1
print("
The 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("
The man left is "+left+".");
}
public static int solve(int N, int m) {
ArrayList a = new ArrayList();
int end = 0;
for(int i=0; i < N; i++)
a.add(i+1);
while(a.size() > 1) {
ArrayList b = new ArrayList();
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.ucloud.cn/yun/71041.html
摘要：然而和他的朋友并不想遵从，要他的朋友先假装遵从，他将朋友与自己安排在第个与第个位置，于是逃过了这场死亡游戏。问最后一个人的最开始的编号是几先是笔者的朴素想法。这种想法虽然素朴，比较容易实现，但是时间复杂度为接着是数学方法。 笔者昨天看电视，偶尔看到一集讲述古罗马人与犹太人的战争——马萨达战争，深为震撼，有兴趣的同学可以移步：http://finance.ifeng.com/a/20...
摘要：动态规划法用表示最大子数组的结束下标为的情形，则对于，有这样就有了一个子结构，对于初始情形，遍历就能得到这个数组，其最大者即可最大子数组的和。动态规划法想法巧妙，运行效率也高，但是没有普遍的适用性。 问题简介 本文将介绍计算机算法中的经典问题——最大子数组问题（maximum subarray problem）。所谓的最大子数组问题，指的是：给定一个数组A，寻找A的和最大的非空连续...
摘要：使用及其各自的实现呈现每个数据结构，并引入重要的设计模式作为将这些实现组织到类，方法和对象中的方法。提供有关基础数据结构分析和设计的全面讨论。使用插图以清晰，直观的方式呈现数据结构和算法及其分析。 注：点击标题，免费下载资源 Data Structures and Algorithms in Python showImg(https://segmentfault.com/img/rem...
摘要：本文详细讨论了自然语言理解的难点，并进一步针对自然语言理解的两个核心问题，详细介绍了规则方法和深度学习的应用。引言自然语言理解是人工智能的核心难题之一，也是目前智能语音交互和人机对话的核心难题。 摘要：自然语言理解是人工智能的核心难题之一，也是目前智能语音交互和人机对话的核心难题。之前写过一篇文章自然语言理解，介绍了当时NLU的系统方案，感兴趣的可以再翻一番，里面介绍过的一些内容不再赘...
阅读 2632·2021-11-23 09:51
阅读 875·2021-09-24 10:37
阅读 3616·2021-09-02 15:15
阅读 1963·2019-08-30 13:03
阅读 1883·2019-08-29 15:41
阅读 2629·2019-08-29 14:12
阅读 1427·2019-08-29 11:19
阅读 3303·2019-08-26 13:39
