python-约瑟夫环问题

约瑟夫环问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到k的那个人被杀掉；他的下一个人又从1开始报数，数到k的那个人又被杀掉；依此规律重复下去，直到圆桌周围的人只剩最后一个。

思路：把所有人放到一个列表里1-n，若报的数字不是k则把将其放到列表最后一个位置，若是k就把这个数字从列表中删掉；直到列表剩下一个人为止，代码如下：

def fun(n,k):
    arr = list(range(1,n+1))
    index = 0
    while arr:
        temp = arr.pop(0)
        index += 1
        if index==k:
            print(temp)
            index = 0
            continue
        arr.append(temp)
        if len(arr)==1:
            print(arr)
            break
       

if __name__=='__main__':
    fun(41,3)

单向循环链表法

class Node(object):
    '''结点'''
    def __init__(self,elem):
        self.elem = elem
        self.next = None

class SingleCycleList(object):
    '''单向循环链表'''
    def __init__(self):
        self.head = None
    
    def append(self,elem):
        node = Node(elem)
        if self.head is None:
            self.head = node
            self.head.next = node
        else:
            cur = self.head
            while cur.next!=self.head:
                cur = cur.next
            cur.next = node
            node.next = self.head
    
    def remove(self,item):
        '''删除节点'''
        cur = self.head
        pre = None
        while cur.next != self.head:
            if cur.elem == item:
                #头节点的情况
                if cur == self.head:
                    rear = self.head
                    while rear.next != self.head:
                        rear = rear.next
                    rear.next = cur.next
                    self.head = cur.next
                else:
                    #中间结点的情况
                    pre.next = cur.next
                return
            else:
                pre = cur
                cur = cur.next
    #尾节点的情况和一个元素的情况
        if cur.elem == item:
                # 一个元素的情况
            if cur == self.head:
                self.head = None
                # 尾节点元素的情况
            else:
                pre.next = self.head
                # pre.next = cur.next
    
    def josephus(self,k):
        cur = self.head
        index = 1
        while cur != cur.next:
            cur = cur.next
            index += 1
            if index == k:
                self.remove(cur.elem)
                print("%d-->"%cur.elem,end="")
                index = 0
        print(cur.elem)

if __name__=='__main__':
    n = 41
    k = 3
    scl = SingleCycleList()
    for i in range(1,n+1):
        scl.append(i)
        
    scl.josephus(3)