python解决约瑟夫环问题（容易理解版）

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

第一次写博客，请大家多多指教。

超级容易理解版：
思路：刚开始把所有的人放到一个列表里面去，报的数字不是3就把这个人放到列表的最后一个位置上面去，如果是3就把这个数字从列表中去掉。直到列表剩下一个人为止，代码如下：

def josephus(n,k):

    #n代表总人数，k代表报数的数字

    List = list(range(1,n+1))

    index = 0

    while List:

        temp = List.pop(0)

        index += 1

        if index == k:

            index = 0

            continue

        List.append(temp)

        if len(List)==1:

            print(List)

            break



if __name__ == '__main__':

    josephus(41,3)

—————————————————我是分割线——————————————————————

单向循环链表法（为了巩固链表的知识而去使用的方法）
思路：就是运用单向链表的循环，其实跟上面一种方法差不多，代码如下：

class Node(object):

    """结点"""

    def __init__(self,item):

        self.elem = item

        self.next = None



class SingleCycleLinkList(object):

    """单向循环链表"""

    def __init__(self):

        self.head = None



    def append(self,item):

        node = Node(item)

        if self.head is None:

            self.head = node

            node.next = node

        else:

            cur = self.head

            while cur.next != self.head:

                cur = cur.next

            cur.next = node

            node.next = self.head



    def travel(self):

        cur = self.head

        while cur.next != self.head:

            print(cur.elem, end=" ")

            cur = cur.next

        print(cur.elem)



    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 judgement(self):

        cur = self.head

        count = 1

        while cur != cur.next :

            cur = cur.next

            count += 1

            if count == 3:

                self.remove(cur.elem)

                print("%d-->"%cur.elem,end="")

                count = 0

        print(cur.elem)



if __name__ == '__main__':

    sll = SingleCycleLinkList()

    for i in range(1,42):

        sll.append(i)

    sll.judgement()