本文實例講述了Python實現約瑟夫環(huán)問題的方法。分享給大家供大家參考，具體如下：

題目：0，1，...，n-1這n個數字排成一個圓圈，從數字0開始每次從這個圓圈里刪除第m個數字。求出這個圓圈里剩下的最后一個數字。

定義函數f(n,m)，表示每次在n個數字（0，1，...，n-1）中每次刪除第m個數字后最后剩下的數字。

在n個數字中，假設第一個被刪除的數字為k，那么刪除k之后剩下的n-1個數字為0~k-1，k 1~n-1，并且下一次刪除從數字k 1開始計數。第二個序列最后剩下的數字也就是我們要求的數字。于是我們對于剩下的n-1個數字重新編號，k 1編號為0，k 2編號為1，...，0編號為n-k-1，1編號為n-k，k-1編號為n-2，假設f(n-1, m) = x，即n-1個數中，每次刪除第m個，最后剩下的數字編號為x，那么這個x就對應著原序列（n個數）中的編號(x + m) % n。可以得到遞推關系：

f(n,m)=0, n=1

f(n,m)=[f(n-1,m) + m]%n n>1

Python代碼：

#coding=utf8

'''

題目：0，1，...，n-1這n個數字排成一個圓圈，從數字0開始每次從這個圓圈里刪除第m個數字。求出這個圓圈里剩下的最后一個數字。

'''

def josephus(n, m):

if type(n) != type(1) or n <= 0:

raise Exception('n must be an integer(n > 0)')

if n == 1:

return 0

else:

return (josephus(n - 1, m) + m) % n

if __name__ == '__main__':

print josephus(8, 3)

print josephus(1, 2)

print josephus(0, 2)

更多關于Python相關內容可查看本站專題：《Python正則表達式用法總結》、《Python數據結構與算法教程》、《Python Socket編程技巧總結》、《Python函數使用技巧總結》、《Python字符串操作技巧匯總》、《Python入門與進階經典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對大家Python程序設計有所幫助。

本條技術文章來源于互聯網，如果無意侵犯您的權益請點擊此處反饋版權投訴

本文系統(tǒng)來源：php中文網

超強干貨來襲 云風專訪：近40年碼齡，通宵達旦的技術人生

總結

以上是生活随笔為你收集整理的python约瑟夫环_Python实现约瑟夫环问题的方法的全部內容，希望文章能夠幫你解決所遇到的問題。

如果覺得生活随笔網站內容還不錯，歡迎將生活随笔推薦給好友。