Josephus Problem的詳細(xì)算法及其Python、Java實現(xiàn)

big_cat 發(fā)布于2019-08-16 11:08 / 3023人閱讀

摘要：然而和他的朋友并不想遵從，要他的朋友先假裝遵從，他將朋友與自己安排在第個與第個位置，于是逃過了這場死亡游戲。問最后一個人的最開始的編號是幾先是筆者的樸素想法。這種想法雖然素樸，比較容易實現(xiàn)，但是時間復(fù)雜度為接著是數(shù)學(xué)方法。

??筆者昨天看電視，偶爾看到一集講述古羅馬人與猶太人的戰(zhàn)爭——馬薩達(dá)戰(zhàn)爭，深為震撼，有興趣的同學(xué)可以移步：http://finance.ifeng.com/a/20... .
??這不僅讓筆者想起以前在學(xué)數(shù)據(jù)結(jié)構(gòu)時碰到的Josephus問題：
??據(jù)說著名猶太歷史學(xué)家 Josephus有過以下的故事：在羅馬人占領(lǐng)喬塔帕特后，39 個猶太人與Josephus及他的朋友躲到一個洞中，39個猶太人決定寧愿死也不要被敵人找到，于是決定了一個自殺方式，41個人排成一個圓圈，由第1個人開始報數(shù)，每報數(shù)到第3人該人就必須自殺，然后再由下一個重新報數(shù)，直到所有人都自殺身亡為止。然而Josephus 和他的朋友并不想遵從，Josephus要他的朋友先假裝遵從，他將朋友與自己安排在第16個與第31個位置，于是逃過了這場死亡游戲。
??以前我們都是用鏈表的方法編程來解決這個問題的，這次筆者將會講述兩個不同的方法，一個是筆者自己的樸素想法，一個是數(shù)學(xué)方法。

樸素方法

數(shù)學(xué)方法

??首先我們先將Josephus問題描述出來，即：共有N個人圍成一圈，編號分別為1,2,...,N,從第一個人開始從1到m報數(shù)，報到m的人退出，如此循環(huán)下去，直至最后一個人。問最后一個人的最開始的編號是幾？
??先是筆者的樸素想法。
??將N個人儲存在列表（list）中，每次報到m的元素剔除，并記錄下最后一個人報的數(shù)i，然后將縮短后的數(shù)組從i+1報數(shù)，如此循環(huán)下去，直至列表的長度為1，這樣剩下來的元素就是我們要求的答案。
??這種想法雖然素樸，比較容易實現(xiàn)，但是時間復(fù)雜度為O(Nm).
??接著是數(shù)學(xué)方法。
??假設(shè)一開始的Josephus環(huán)編號為0,1,2,...,N-1.我們知道第一個人(編號一定是m%N-1) 出列之后，剩下的N-1個人組成了一個新的Josephus環(huán)（以編號為k=m%n的人開始）:
$$ k, k+1, k+2,......, n-2, n-1, 0, 1, 2, ... k-2$$
并且從k開始報0.
??現(xiàn)在我們把他們的編號做一下轉(zhuǎn)換：
$$k --> 0
k+1 --> 1
k+2 --> 2
...
k-2 --> n-2
k-1 --> n-1$$

變換后就成為了(N-1)個人報數(shù)的子問題，這啟示我們可以用歸納法來解決這個問題。假如我們知道這個子問題的解為$x$，原來問題的答案為$x^{"}$,則$x^{"}=(x+k)\%n.$因此，遞推公式就有了！令$f(i)$表示$i$個人玩游戲報$m$退出最后勝利者的編號，我們要求的結(jié)果是$f(N)$，其遞推公式如下：
$$f(1)=0
f(1)=(f(i-1)+m)% i qquad (i>1)$$
??數(shù)學(xué)方法簡單明了，計算效率高，但是推導(dǎo)比較困難。
??最后，我們給出以下兩種方法的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);
    }
    
}

??本次分享到此結(jié)束，歡迎大家交流~~