# -*- coding: utf-8 -*-
# @Time         : 2019-09-18 21:57
# @Author       : Jayce Wong
# @ProjectName  : job
# @FileName     : josephus.py
# @Blog         : https://blog.51cto.com/jayce1111
# @Github       : https://github.com/SysuJayce

"""
約瑟夫斯（Josephus）問題是一個出現(xiàn)在計(jì)算機(jī)科學(xué)和數(shù)學(xué)中的問題。
在計(jì)算機(jī)編程的算法中，類似問題又稱為約瑟夫環(huán)。
約瑟夫斯問題：有n個囚犯站成一個圓圈，準(zhǔn)備處決。
首先從一個人開始，越過k-2個人（因?yàn)榈谝粋€人已經(jīng)被越過），并殺掉第k個人。
接著，再越過k-1個人，并殺掉第k個人。
這個過程沿著圓圈一直進(jìn)行，直到最終只剩下一個人留下，這個人就可以繼續(xù)活著。

給定了n和k，一開始要站在什么地方才能避免被處決？

遞推公式：
當(dāng)n = 1時，f(1, k) = 1
當(dāng)n > 1時，f(n, k) = (f(n - 1, k) + k) mod n
**注意**當(dāng)編號從1開始的時候，如果計(jì)算得到f(n, k) = 0，那么需要將其還原為n然后繼續(xù)遞推
"""

def josephus(n, k):
    if n <= 1:
        return 1
    res = 1
    # 注意這里我們使用遞推公式的時候，計(jì)算的是f(i, k)，因此需要對i取模
    for i in range(2, n + 1):
        res = (res + k) % i if (res + k) % i != 0 else i
    return res

print(josephus(5, 2))

另外有需要云服務(wù)器可以了解下創(chuàng)新互聯(lián)cdcxhl.cn，海內(nèi)外云服務(wù)器15元起步，三天無理由+7*72小時售后在線，公司持有idc許可證，提供“云服務(wù)器、裸金屬服務(wù)器、高防服務(wù)器、香港服務(wù)器、美國服務(wù)器、虛擬主機(jī)、免備案服務(wù)器”等云主機(jī)租用服務(wù)以及企業(yè)上云的綜合解決方案，具有“安全穩(wěn)定、簡單易用、服務(wù)可用性高、性價比高”等特點(diǎn)與優(yōu)勢，專為企業(yè)上云打造定制，能夠滿足用戶豐富、多元化的應(yīng)用場景需求。

創(chuàng)新互聯(lián)公司的客戶來自各行各業(yè)，為了共同目標(biāo)，我們在工作上密切配合，從創(chuàng)業(yè)型小企業(yè)到企事業(yè)單位，感謝他們對我們的要求，感謝他們從不同領(lǐng)域給我們帶來的挑戰(zhàn)，讓我們激情的團(tuán)隊(duì)有機(jī)會用頭腦與智慧不斷的給客戶帶來驚喜。專業(yè)領(lǐng)域包括網(wǎng)站建設(shè)、網(wǎng)站設(shè)計(jì)、電商網(wǎng)站開發(fā)、微信營銷、系統(tǒng)平臺開發(fā)。
名稱欄目：約瑟夫環(huán)-創(chuàng)新互聯(lián)
標(biāo)題鏈接：http://weahome.cn/article/gdocj.html