(2020 浙江高三竞赛题）环中取数

做题人生

王守恩 发表于 2026-1-28 06:58
将1——2020的数字按顺时针方向围成一个圆圈，然后从1开始，按顺时针依次隔2个拿走1个，即拿走 1, 4, 7, .. ...

等有空了研究下约瑟夫环，就拿你这个做练习题吧。

Jack315

不同间距的模拟结果：
\(\begin{array}{|c|r|c|r|c|r|}
\hline
\textbf{间距} & \textbf{剩下的数} & \textbf{间距} & \textbf{剩下的数} & \textbf{间距} & \textbf{剩下的数}\\
\hline
\text{2} & \text{1992} & \text{12} & \text{582} & \text{22} & \text{1925}\\
\text{3} & \text{665} & \text{13} & \text{338} & \text{23} & \text{183}\\
\text{4} & \text{1539} & \text{14} & \text{844} & \text{24} & \text{1553}\\
\text{5} & \text{1818} & \text{15} & \text{1800} & \text{25} & \text{830}\\
\text{6} & \text{254} & \text{16} & \text{498} & \text{26} & \text{1963}\\
\text{7} & \text{1911} & \text{17} & \text{17} & \text{27} & \text{1556}\\
\text{8} & \text{912} & \text{18} & \text{1215} & \text{28} & \text{609}\\
\text{9} & \text{590} & \text{19} & \text{927} & \text{29} & \text{628}\\
\text{10} & \text{1488} & \text{20} & \text{1195} & \text{30} & \text{1328}\\
\text{11} & \text{1788} & \text{21} & \text{1503} & \text{31} & \text{845}\\
\hline
\end{array}\)

王守恩

{1992, 665, 1539, 1818, 254, 1911, 912, 590, 1488, 1788, 582, 338, 844, 1800, 498, 17, 1215, 927, 1195, 1503, 1925, 183, 1553, 830, 1963, 1556, 609, 628, 1328, 845}

Flatten@Table[Nest[Rest@RotateLeft[#, A] &, Range[2019], 2018] + 1, {A, 30}]——我们可以有万能公式。——谢谢 Jack315！！！谢谢 aimisiyou！！！

Jack315

模拟取数过程的 Python 代码：

1. class Ring:
   
2.     def __init__(self, length: int = 10, gap: int = 2) -> None:
   
3.         self.length = length
   
4.         self.gap = gap
   
5.         self.ring = None
   
6.         self.sequence = None
   
7. 
   
8.         self.reset()
   
9. 
   
10.     def reset(self) -> None:
    
11.         # 环中元素：[数字，是否被取走]
    
12.         self.ring = [[i + 1, False] for i in range(self.length)]
    
13.         # 取走数的过程。
    
14.         self.sequence = []
    
15. 
    
16.     def find_next(self, index: int) -> int:
    
17.         gap = self.gap
    
18.         while gap > 0:
    
19.             # 索引循环遍历。
    
20.             index += 1
    
21.             if index >= self.length:
    
22.                 index = 0
    
23. 
    
24.             # 找到未被取走的数。
    
25.             if not self.ring[index][1]:
    
26.                 gap -= 1
    
27.         return index
    
28. 
    
29.     # 统计环中尚未被取走数字的数量。
    
30.     def remain(self) -> int:
    
31.         count = 0
    
32.         for i in range(len(self.ring)):
    
33.             if not self.ring[i][1]:
    
34.                 count += 1
    
35.         return count
    
36. 
    
37.     # 模拟取数过程。
    
38.     def simulate(self) -> None:
    
39.         index = 0
    
40.         while self.remain() > 1:
    
41.             # 标志 index 处的元素被取走。
    
42.             self.ring[index][1] = True
    
43.             # 记录被取走的数。
    
44.             self.sequence.append(self.ring[index][0])
    
45.             # 查找下一个待取走的元素。
    
46.             index = self.find_next(index)
    
47. 
    
48.         # 模拟过程结束时， index 处的元素就是最后剩下的数字。
    
49.         print(f'间距： {self.gap}')
    
50.         print(f'剩下的数为： {self.ring[index][0]}')
    
51.         print(f'取数过程： {self.sequence}')
    
52. 
    
53. 
    
54. if __name__ == '__main__':
    
55.     # 创建环 Ring 对象。
    
56.     r = Ring()
    
57.     # 设置环长度。
    
58.     r.length = 2020
    
59.     # 遍历不同的间距。
    
60.     for g in range(2, 32):
    
61.         r.gap = g
    
62.         r.reset()
    
63.         r.simulate()

复制代码

王守恩

将1——n的数字按顺时针方向围成一个圆圈，然后从1开始, 按顺时针依次留A个,去B个,  这个过程一直进行下去, 直到剩下最后一个数字, 则最后剩下的数字是_____.

将1——n的数字按顺时针方向围成一个圆圈，然后从1开始, 按顺时针依次去B个,留A个,  这个过程一直进行下去, 直到剩下最后一个数字, 则最后剩下的数字是_____.

这2道题都会做, 也就差不多了。——也只是差不多！——A,B=正整数。要特别小心: 当剩下不足A+B时, 这个规矩不能变。

Jack315

使用双链表的 Python 代码。14# 的代码比较直白，这个代码性能比较高效。

1. # 节点类。
   
2. class Node:
   
3.     def __init__(self, data=None):
   
4.         self.data = data
   
5.         self.prev = None
   
6.         self.next = None
   
7. 
   
8. # 双链表类。
   
9. class DoublyLinkedList:
   
10.     def __init__(self):
    
11.         self.head = None
    
12.         self.tail = None
    
13.         self.current = None
    
14.         self.size = 0
    
15. 
    
16.     # 新节点在尾端插入。
    
17.     def insert(self, data):
    
18.         new_node = Node(data)
    
19.         if self.size == 0:
    
20.             new_node.prev = new_node
    
21.             new_node.next = new_node
    
22.             self.head = new_node
    
23.             self.tail = new_node
    
24.         else:
    
25.             new_node.prev = self.tail
    
26.             new_node.next = self.head
    
27.             self.head.prev = new_node
    
28.             self.tail.next = new_node
    
29.             self.tail = new_node
    
30.         self.size += 1
    
31. 
    
32.     # 删除当前节点 current 。
    
33.     def delete(self) -> Node or None:
    
34.         if self.size == 0:
    
35.             return None
    
36.         else:
    
37.             if self.current == self.head:
    
38.                 self.head = self.head.next
    
39.             if self.current == self.tail:
    
40.                 self.tail = self.tail.prev
    
41.             self.current.prev.next = self.current.next
    
42.             self.current.next.prev = self.current.prev
    
43.             self.size -= 1
    
44.             return self.current
    
45. 
    
46.     def move(self, steps) -> None:
    
47.         for _ in range(steps):
    
48.             self.current = self.current.next
    
49. 
    
50.     def tolist(self):
    
51.         result = []
    
52.         node = self.head
    
53.         for _ in range(self.size):
    
54.             result.append(node.data)
    
55.             node = node.next
    
56.         return result
    
57. 
    
58. # 环中取数模拟器类。
    
59. class Simulator:
    
60.     def __init__(self, length: int = 10) -> None:
    
61.         self.length = length
    
62.         self.ring = None
    
63.         self.sequence = None
    
64. 
    
65.     def simulate(self, gap: int = 2, num_left: int = 1) -> None:
    
66.         # 初始化 ring 和 sequence
    
67.         self.ring = DoublyLinkedList()
    
68.         for i in range(self.length):
    
69.             self.ring.insert(i + 1)
    
70.         self.sequence = []
    
71.         # 环中取数。
    
72.         self.ring.current = self.ring.head
    
73.         while self.ring.size > num_left:
    
74.             removed_node = self.ring.delete()
    
75.             self.ring.current = removed_node.next
    
76.             self.ring.move(gap - 1)
    
77.             self.sequence.append(removed_node.data)
    
78.             del removed_node
    
79.         # 输出结果。
    
80.         print(f'间距： {gap}')
    
81.         print(f'剩下的数为： {self.ring.tolist()}')
    
82.         print(f'取数过程： {self.sequence}')
    
83. 
    
84. if __name__ == "__main__":
    
85.     w = Simulator(length=2020)
    
86.     for g in range(2, 32):
    
87.         w.simulate(gap=g, num_left=1)

复制代码

aimisiyou

Jack315 发表于 2026-1-30 13:42
使用双链表的 Python 代表。14# 的代码比较直白，这个代码性能比较高效。

复杂度是O（N）吗？

Jack315

【代码性能比较】环（列表）长度：2020，间隔：2~31 。
14# 代码的性能：7092 ms

16# 代码的性能：223 ms

估计用单链表也行，或许性能还能再改善一点。

mathe

对于步长k (比如原始约瑟夫问题我们可以看成是k=2),
那么我们可以先计算长度为2,3,...,k的的环的结果a(2),a(3),...,a(k) 其中显然a(2)=2.
对于\(n\ge k+1\), 那么计算a(n)时，由于用户第一步必然取走数字1，并且下一步会取数字k+1,
我们可以将数据重排为k+1,k+2,...,n,2,3,...,k，这是一个长度为n-1的序列，所以
如果\(a(n-1)\le n-k\), 那么a(n)=a(n-1)+k, 但是如果\(a(n-1)\gt n-k\), 那么必然有a(n)=a(n-1)-(n-k)+1.
这样就可以得到一个简单的递推计算关系。
特别的，在n相对k很大的情况，我们看a(n)的规律会发现几乎每次都是按步长k递增，直到到达某个a(n)>n+1-k, 下一个需要在加k后再减(n-1).
或者说每次n加1,a(n)-n的值增加k-1,直到某次增加到正数时需要在减去n-1. 于是我们可以批量处理，比如每次可以一次性处理将近\(\frac{n-1}{k-1}\)个数，来增加计算速度，快速逼近目标n

Jack315

【参考】 约瑟夫环——公式法（递推公式）
递推公式：\(f(N,G)=[f(N-1,G)+G]\mod N\)
其中：\(N\) 为取数时环的长度；\(G\) 为取数间距。
公式的推导是根据最后剩下的数在每轮取数时的位置。

将原始序列右移 \(G-1\) 个位置即得到与上文中相同的约瑟夫环。
因此计算结果修正为：\(计算结果+1-(G-1)=计算结果-G+2\)。

相应的 Python 代码：

1. def Josephus(length: int, gap: int) -> int:
   
2.     index = 0
   
3.     for i in range(2, length + 1):
   
4.         index = (index + gap) % i
   
5.     result = index - gap + 2
   
6. 
   
7.     # 修正序列移位导致的负数（越界）。
   
8.     if result < 0:
   
9.         result += length
   
10.     return result
    
11. 
    
12. if __name__ == '__main__':
    
13.     for g in range(2, 32):
    
14.         print(Josephus(2020, g))

复制代码

环（列表）长度：2020，间隔：2~31，运行时间 3ms 。