约瑟环的python实现（举例说明）

5imobi

　　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[0])
　　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:[5, 10, 15, 20, 25, 30, 35, 40, 45, 50, 6, 12, 18, 24, 31, 37, 43, 49, 7, 14, 22, 29, 38, 46, 3, 13, 23, 33, 42, 2, 16, 27, 39, 1, 17, 32, 47, 11, 34, 4, 26, 48, 28, 9, 44, 41, 8, 21, 36, 19]
　　30人报3出局答案为：
　　约瑟环2:29
　　约瑟环3:[3, 6, 9, 12, 15, 18, 21, 24, 27, 30, 4, 8, 13, 17, 22, 26, 1, 7, 14, 20, 28, 5, 16, 25, 10, 23, 11, 2, 19, 29]
　　60人报99出局答案为：
　　约瑟环2:55
　　约瑟环3:[39, 19, 1, 45, 30, 17, 7, 58, 52, 48, 46, 47, 51, 57, 6, 16, 29, 44, 10, 32, 2, 31, 9, 43, 28, 21, 14, 13, 20, 27, 42, 8, 38, 22, 4, 60, 11, 26, 54, 36, 34, 41, 12, 56, 5, 40, 49, 23, 33, 25, 18, 15, 37, 50, 59, 53, 24, 3, 35, 55]