博客

1.问题描述

几个人（以编号1，2，3，4，…..，n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列，他的下一个又从1开始报数，数到m的那个人又出列；按照此规律重复下去，直到圆桌周围只剩一个人，最后一人为“胜利者”，每一次出列的人姑且称之为“失败者”吧。

2.算法实现

2.1 数据结构的准备

创建一个节点类，初始化方法为存储每个人的编号和他的下一个节点。然后创建一个实现环链表的函数，输入为节点数，实现将每一节点连接起来，构成一个环链表（圆桌）。

2.2 实现流程

定义一个约瑟夫函数，输入为总人数n，以及出列数k（即每次报数报的是k就出列），首先根据人数，创建一个节点数为n的环链表，然后开始报数，直到报k-1的那个人，假设这个人叫

luck。

把

luck

的下一个人（

失败者

）移除链表

，

再从

失败者

的下一个人

（luck的下一个的下一个）

重新从

1

开始报数

，直到链表中只剩最后一人，

Game over。

3.实现代码

class Node():
    def __init__(self, value, next=None):
        self.value = value
        self.next = next

def CreatLink(n):
    if n <= 0:
        return False
    if n == 1:
        return Node(1)
    else:
        root = Node(1)
        tmp = root
        for i in range(2, n + 1):
            tmp.next = Node(i)
            tmp = tmp.next
        tmp.next = root
        return root

def ShowLink(root):
    tmp = root
    while 1:
        print(tmp.value)
        tmp = tmp.next
        if tmp.next == None or tmp == root:
            break

def josephus(n, k):
    if k == 1:
        print("Survive:", n)
        return 0
    root = CreatLink(n)
    tmp = root
    while 1:
        for i in range(k - 2):
            tmp = tmp.next
        print("Kill:", tmp.next.value)
        tmp.next = tmp.next.next
        tmp = tmp.next
        if tmp.next == tmp:
            break
    print("Survive:", tmp.value)

if __name__ == "__main__":
    n, k = map(int, input().split())
    josephus(n, k)

输出结果：

10 4
Kill: 4   
Kill: 8   
Kill: 2   
Kill: 7   
Kill: 3   
Kill: 10  
Kill: 9   
Kill: 1   
Kill: 6   
Survive: 5

总结：

约瑟夫问题是一个十分典型的数据结构问题，当然也可以通过其他方法实现，有兴趣的小伙伴务必亲自动手敲一下代码，链表本质上不难，关键是要准确把握链表节点之间的连接顺序，以及活用链表去解决实际问题，总的来说，还是有收获的。