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

柔光的暖阳◎ 2022-05-28 02:09 256阅读 0赞

笔者昨天看电视，偶尔看到一集讲述古罗马人与犹太人的战争——马萨达战争，深为震撼，有兴趣的同学可以移步：[http://finance.ifeng.com/a/20170627/15491157\_0.shtml][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 , k + 1 , k + 2 , . . . . . . , n − 2 , n − 1 , 0 , 1 , 2 , . . . k − 2

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

k−−>0k\+1−−>1k\+2−−>2...k−2−−>n−2k−1−−>n−1  k − − > 0 k + 1 − − > 1 k + 2 − − > 2 . . . k − 2 − − > n − 2 k − 1 − − > n − 1

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

f(1)=0f(i)=(f(i−1)\+m)%i(i>1)  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)) # 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('\nThe man left: %d' %left1)
    
        left2 = solve2(N, m)+1
        print('\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);
        }
    
    }

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

[http_finance.ifeng.com_a_20170627_15491157_0.shtml]: http://finance.ifeng.com/a/20170627/15491157_0.shtml