Josephus Problem的詳細算法及其Python、Java實現

yimo 發布于2019-07-31 11:07 / 3421人閱讀

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

??筆者昨天看電視，偶爾看到一集講述古羅馬人與猶太人的戰爭——馬薩達戰爭，深為震撼，有興趣的同學可以移步：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);
    }
    
}

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

GPU云服務器云服務器 java實現離群算法 java遺傳算法實現 sa算法java實現計步算法java實現

文章版權歸作者所有，未經允許請勿轉載,若此文章存在違規行為，您可以聯系管理員刪除。

轉載請注明本文地址：http://m.specialneedsforspecialkids.com/yun/44693.html

Josephus Problem的詳細算法及其Python、Java實現

摘要：然而和他的朋友并不想遵從，要他的朋友先假裝遵從，他將朋友與自己安排在第個與第個位置，于是逃過了這場死亡游戲。問最后一個人的最開始的編號是幾先是筆者的樸素想法。這種想法雖然素樸，比較容易實現，但是時間復雜度為接著是數學方法。 ??筆者昨天看電視，偶爾看到一集講述古羅馬人與猶太人的戰爭——馬薩達戰爭，深為震撼，有興趣的同學可以移步：http://finance.ifeng.com/a/20...

big_cat 2019-08-16 11:08 評論0 收藏0
動態規劃法（八）最大子數組問題（maximum subarray problem）

摘要：動態規劃法用表示最大子數組的結束下標為的情形，則對于，有這樣就有了一個子結構，對于初始情形，遍歷就能得到這個數組，其最大者即可最大子數組的和。動態規劃法想法巧妙，運行效率也高，但是沒有普遍的適用性。問題簡介 ??本文將介紹計算機算法中的經典問題——最大子數組問題（maximum subarray problem）。所謂的最大子數組問題，指的是：給定一個數組A，尋找A的和最大的非空連續...

jzman 2019-07-30 16:46 評論0 收藏0
Python代碼面試必讀 - Data Structures and Algorithms in P

摘要：使用及其各自的實現呈現每個數據結構，并引入重要的設計模式作為將這些實現組織到類，方法和對象中的方法。提供有關基礎數據結構分析和設計的全面討論。使用插圖以清晰，直觀的方式呈現數據結構和算法及其分析。注：點擊標題，免費下載資源 Data Structures and Algorithms in Python showImg(https://segmentfault.com/img/rem...

dongfangyiyu 2019-07-31 10:02 評論0 收藏0
自然語言理解-從規則到深度學習

摘要：本文詳細討論了自然語言理解的難點，并進一步針對自然語言理解的兩個核心問題，詳細介紹了規則方法和深度學習的應用。引言自然語言理解是人工智能的核心難題之一，也是目前智能語音交互和人機對話的核心難題。摘要：自然語言理解是人工智能的核心難題之一，也是目前智能語音交互和人機對話的核心難題。之前寫過一篇文章自然語言理解，介紹了當時NLU的系統方案，感興趣的可以再翻一番，里面介紹過的一些內容不再贅...

CntChen 2019-07-31 12:23 評論0 收藏0