約瑟夫環(huán)

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

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

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

def josephus(n, k):
    if n <= 1:
        return 1
    res = 1
    # 注意這里我們使用遞推公式的時(shí)候，計(jì)算的是f(i, k)，因此需要對(duì)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))

分享文章：約瑟夫環(huán)
當(dāng)前路徑：http://bm7419.com/article34/goshse.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供定制網(wǎng)站、手機(jī)網(wǎng)站建設(shè)、網(wǎng)站維護(hù)、品牌網(wǎng)站設(shè)計(jì)、品牌網(wǎng)站制作、商城網(wǎng)站

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來(lái)源： 創(chuàng)新互聯(lián)