成人国产在线小视频_日韩寡妇人妻调教在线播放_色成人www永久在线观看_2018国产精品久久_亚洲欧美高清在线30p_亚洲少妇综合一区_黄色在线播放国产_亚洲另类技巧小说校园_国产主播xx日韩_a级毛片在线免费

資訊專欄INFORMATION COLUMN

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

big_cat / 3028人閱讀

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

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

樸素方法

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

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

變換后就成為了(N-1)個(gè)人報(bào)數(shù)的子問(wèn)題，這啟示我們可以用歸納法來(lái)解決這個(gè)問(wèn)題。假如我們知道這個(gè)子問(wèn)題的解為$x$，原來(lái)問(wèn)題的答案為$x^{"}$,則$x^{"}=(x+k)\%n.$因此，遞推公式就有了！令$f(i)$表示$i$個(gè)人玩游戲報(bào)$m$退出最后勝利者的編號(hào)，我們要求的結(jié)果是$f(N)$，其遞推公式如下：
$$f(1)=0
f(1)=(f(i-1)+m)% i qquad (i>1)$$
??數(shù)學(xué)方法簡(jiǎn)單明了，計(jì)算效率高，但是推導(dǎo)比較困難。
??最后，我們給出以下兩種方法的Python代碼和樸素方法的Java代碼，希望能給大家一點(diǎn)思考。
??完整的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é)束，歡迎大家交流~~

文章版權(quán)歸作者所有，未經(jīng)允許請(qǐng)勿轉(zhuǎn)載,若此文章存在違規(guī)行為，您可以聯(lián)系管理員刪除。

轉(zhuǎn)載請(qǐng)注明本文地址：http://systransis.cn/yun/71041.html

相關(guān)文章

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

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

    yimo 評(píng)論0 收藏0

  • 動(dòng)態(tài)規(guī)劃法（八）最大子數(shù)組問(wèn)題（maximum subarray problem）

    摘要：動(dòng)態(tài)規(guī)劃法用表示最大子數(shù)組的結(jié)束下標(biāo)為的情形，則對(duì)于，有這樣就有了一個(gè)子結(jié)構(gòu)，對(duì)于初始情形，遍歷就能得到這個(gè)數(shù)組，其最大者即可最大子數(shù)組的和。動(dòng)態(tài)規(guī)劃法想法巧妙，運(yùn)行效率也高，但是沒(méi)有普遍的適用性。 問(wèn)題簡(jiǎn)介 ??本文將介紹計(jì)算機(jī)算法中的經(jīng)典問(wèn)題——最大子數(shù)組問(wèn)題（maximum subarray problem）。所謂的最大子數(shù)組問(wèn)題，指的是：給定一個(gè)數(shù)組A，尋找A的和最大的非空連續(xù)...

    jzman 評(píng)論0 收藏0

  • Python代碼面試必讀 - Data Structures and Algorithms in P

    摘要：使用及其各自的實(shí)現(xiàn)呈現(xiàn)每個(gè)數(shù)據(jù)結(jié)構(gòu)，并引入重要的設(shè)計(jì)模式作為將這些實(shí)現(xiàn)組織到類，方法和對(duì)象中的方法。提供有關(guān)基礎(chǔ)數(shù)據(jù)結(jié)構(gòu)分析和設(shè)計(jì)的全面討論。使用插圖以清晰，直觀的方式呈現(xiàn)數(shù)據(jù)結(jié)構(gòu)和算法及其分析。 注：點(diǎn)擊標(biāo)題，免費(fèi)下載資源 Data Structures and Algorithms in Python showImg(https://segmentfault.com/img/rem...

    dongfangyiyu 評(píng)論0 收藏0

  • 自然語(yǔ)言理解-從規(guī)則到深度學(xué)習(xí)

    摘要：本文詳細(xì)討論了自然語(yǔ)言理解的難點(diǎn)，并進(jìn)一步針對(duì)自然語(yǔ)言理解的兩個(gè)核心問(wèn)題，詳細(xì)介紹了規(guī)則方法和深度學(xué)習(xí)的應(yīng)用。引言自然語(yǔ)言理解是人工智能的核心難題之一，也是目前智能語(yǔ)音交互和人機(jī)對(duì)話的核心難題。 摘要：自然語(yǔ)言理解是人工智能的核心難題之一，也是目前智能語(yǔ)音交互和人機(jī)對(duì)話的核心難題。之前寫過(guò)一篇文章自然語(yǔ)言理解，介紹了當(dāng)時(shí)NLU的系統(tǒng)方案，感興趣的可以再翻一番，里面介紹過(guò)的一些內(nèi)容不再贅...

    CntChen 評(píng)論0 收藏0

發(fā)表評(píng)論

0條評(píng)論

最新活動(dòng)
閱讀需要支付1元查看
<