python解决约瑟夫环问题

m个人围成1圈，从第一个人开始数数，数到n的人会被枪杀，然后下一个从头开始数，问一开始排第几个位置不会被枪杀？

def fun(m,n):
    array = list(range(1,m+1))
    print(array)

    while len(array)>1:
        if len(array) > n:
            print('kill%s'%array[n-1])
            array = array[n:] + array[:n-1]

        elif len(array)>1:
            array_new = array * n
            print('kill%s' % array_new[n - 1])
            array_new = array_new[n:] + array[:n-1]
            array = array_new[:len(array)-1]
    print(array)


fun(10000,3)

这个算法用列表去做的，很容易理解 

def fun(m,n):

    my_dict = dict.fromkeys(range(1, m))
    #print(my_dict)
    for index in range(1,m):
        my_dict[index] = index + 1
    my_dict[m] = 1
    print(my_dict)

    k=1
    v=2
    c=1
    while k!=v:
        if c!=(n-1):
            c = c+1
            k = my_dict[k]
            v = my_dict[k]
        else:
            print('kill%s'%k)
            my_dict[k] = my_dict[v]
            del my_dict[v]
            k = my_dict[k]
            v = my_dict[k]
            c = 1
    print( '活下来的只有%s'%my_dict)

fun(2000,3)

这个算法用字典去做，算法上有点像链表， O (nk)  

约瑟夫环