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

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

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

在n個(gè)數(shù)字中，假設(shè)第一個(gè)被刪除的數(shù)字為k，那么刪除k之后剩下的n-1個(gè)數(shù)字為0~k-1，k 1~n-1，并且下一次刪除從數(shù)字k 1開(kāi)始計(jì)數(shù)。第二個(gè)序列最后剩下的數(shù)字也就是我們要求的數(shù)字。于是我們對(duì)于剩下的n-1個(gè)數(shù)字重新編號(hào)，k 1編號(hào)為0，k 2編號(hào)為1，...，0編號(hào)為n-k-1，1編號(hào)為n-k，k-1編號(hào)為n-2，假設(shè)f(n-1, m) = x，即n-1個(gè)數(shù)中，每次刪除第m個(gè)，最后剩下的數(shù)字編號(hào)為x，那么這個(gè)x就對(duì)應(yīng)著原序列（n個(gè)數(shù)）中的編號(hào)(x + m) % n?？梢缘玫竭f推關(guā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個(gè)數(shù)字排成一個(gè)圓圈，從數(shù)字0開(kāi)始每次從這個(gè)圓圈里刪除第m個(gè)數(shù)字。求出這個(gè)圓圈里剩下的最后一個(gè)數(shù)字。'''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) % nif __name__ == '__main__':  print josephus(8, 3)  print josephus(1, 2)  print josephus(0, 2)

更多關(guān)于Python相關(guān)內(nèi)容可查看本站專題：《Python正則表達(dá)式用法總結(jié)》、《Python數(shù)據(jù)結(jié)構(gòu)與算法教程》、《Python Socket編程技巧總結(jié)》、《Python函數(shù)使用技巧總結(jié)》、《Python字符串操作技巧匯總》、《Python入門(mén)與進(jìn)階經(jīng)典教程》及《Python文件與目錄操作技巧匯總》

希望本文所述對(duì)大家Python程序設(shè)計(jì)有所幫助。