python 数据结构

Question

已知有n个人围坐在一张圆桌周围，从第s个人开始报数，数到m的那个人出列，他的下一个人又从1开始报数，数到m的那个人又出列；一次规律重复下去，直到圆桌周围的人数少于m时结束，输出剩下的人的序号。
提示：n个人围成一个圈可以用一个列表来表示。

```python
class Queue:
    def __init__(self):
        self.items = []

    def isEmpty(self):
        return self.items == []

    def enqueue(self, item):
        self.items.insert(0, item)

    def dequeue(self):
        return self.items.pop()

    def size(self):
        return len(self.items)


def circle(num):
    simqueue = Queue()
    for name in namelist:
        simqueue.enqueue(name)

```

Answer 1

该回答引用chatgpt:
从第s个人开始报数，我们通过将队列中的人按照报数顺序依次出队再入队，将第s个人移动到队列的开头位置。

然后，我们开始报数和出列的循环过程，直到队列中的人数少于m为止。在每一轮中，我们按照数到m的人出列的规则，将报数到m的人从队列中移除。

最后，我们将剩下的人的序号存储在remaining_people列表中，并返回该列表。

示例调用中的输出结果将会是剩下的人的序号。

class Queue:
    def __init__(self):
        self.items = []
 
    def isEmpty(self):
        return self.items == []
 
    def enqueue(self, item):
        self.items.insert(0, item)
 
    def dequeue(self):
        return self.items.pop()
 
    def size(self):
        return len(self.items)
 
 
def josephus(n, s, m):
    queue = Queue()
    for i in range(1, n + 1):
        queue.enqueue(i)
    
    # 从第s个人开始报数
    for _ in range(s - 1):
        queue.enqueue(queue.dequeue())
    
    # 数到m的人出列
    while queue.size() > m:
        for _ in range(m - 1):
            queue.enqueue(queue.dequeue())
        queue.dequeue()
    
    # 返回剩下的人的序号
    remaining_people = []
    while not queue.isEmpty():
        remaining_people.append(queue.dequeue())
    return remaining_people

# 示例调用
n = 10  # 人的总数
s = 3   # 从第s个人开始报数
m = 4   # 数到m的人出列
remaining_people = josephus(n, s, m)
print("剩下的人的序号:", remaining_people)