溫馨提示×
您好，登錄后才能下訂單哦！
點擊 登錄注冊 即表示同意《億速云用戶服務條款》
您好，登錄后才能下訂單哦！
# -*- 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）問題是一個出現在計算機科學和數學中的問題。
在計算機編程的算法中，類似問題又稱為約瑟夫環。
約瑟夫斯問題：有n個囚犯站成一個圓圈，準備處決。
首先從一個人開始，越過k-2個人（因為第一個人已經被越過），并殺掉第k個人。
接著，再越過k-1個人，并殺掉第k個人。
這個過程沿著圓圈一直進行，直到最終只剩下一個人留下，這個人就可以繼續活著。
給定了n和k，一開始要站在什么地方才能避免被處決？
遞推公式：
當n = 1時，f(1, k) = 1
當n > 1時，f(n, k) = (f(n - 1, k) + k) mod n
**注意**當編號從1開始的時候，如果計算得到f(n, k) = 0，那么需要將其還原為n然后繼續遞推
"""
def josephus(n, k):
if n <= 1:
return 1
res = 1
# 注意這里我們使用遞推公式的時候，計算的是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))
免責聲明：本站發布的內容（圖片、視頻和文字）以原創、轉載和分享為主，文章觀點不代表本網站立場，如果涉及侵權請聯系站長郵箱：is@yisu.com進行舉報，并提供相關證據，一經查實，將立刻刪除涉嫌侵權內容。
