约瑟环的python实现（举例说明）
N个人围成一圈报数，报到某一个数m的就出局，问你最后剩下来的人的号码？网上通用约瑟夫环的算法是：
//函数接收n和m，返回最后出圈的是第几个人
/*e.g. yuesefu(5,2)=3
yuesefu(2,100)=1*/
int yuesefu(int n,int m)
{
int i,r=0;
for (i=2;i <=n;i++) r=(r+m)%i;
return r+1;
}
用python实现上面算法为：
def yuesefu2(n, m):
# 网上常见方法，答案准确
# yuesefu2(50, 5)=19
i = 0
r = 0
for i in range(2, n + 1):
r = (r + m) % i
return r + 1
用python模拟报数出局的方法为：
def yuesefu3(n, m):
a = range(1, n + 1)
b = []
i = 0# 指针
while n > 1:
i = i + m
if i > n:
i = i % n
b.append(a.pop(i - 1))
# print a.pop(i-1)
n = n - 1
i = i - 1
if i == n or i == -1:# 特别处理，如果正好弹出最后一个，i值归0
i = 0
b.append(a)
return b
if __name__ == '__main__':
n = 60
m = 99
print u'约瑟环2:' + str(yuesefu2(n, m))
print u'约瑟环3:' + str(yuesefu3(n, m))
50人报5出局答案为：
约瑟环2:19
约瑟环3:
30人报3出局答案为：
约瑟环2:29
约瑟环3:
60人报99出局答案为：
约瑟环2:55
约瑟环3:
页:
[1]