有 n 个人围成一圈,按顺序从1 到 n编号。从第一个人开始报数,报数 3 的人退出圈子,下一个人从1 开始重新报数,报数 3 的人退出圈子。如此循环,直 到留下最后一个人。问留下来的人的编号。 输入输出示例 Input n: 5 Last No.is:4
时间: 2023-12-23 08:56:28 浏览: 53
这是一个经典的约瑟夫问题(Josephus problem),可以用递归或数学公式求解。
递归解法:
假设 f(n, m) 表示 n 个人报数,每次报到 m 的人出圈后剩下的人的编号。则有:
f(n, m) = (f(n - 1, m) + m) % n (n > 1)
f(1, m) = 0
其中,% 表示取模运算。
代码如下:
```python
def josephus(n, m):
if n == 1:
return 0
else:
return (josephus(n-1, m) + m) % n
n = int(input("Input n: "))
m = 3
last_no = josephus(n, m) + 1
print("Last No.is: ", last_no)
```
数学公式解法:
假设最后留下的人的编号为 f(n, m),则有:
f(n, m) = (f(n-1, m) + m) % n (n > 1)
f(1, m) = 0
化简得:
f(n, m) = (f(n-1, m) + m) % n
= (f(n-2, m) + m) % (n-1)
= ...
= (f(1, m) + m) % 2
当 n = 1 时,f(1, m) = 0;当 n = 2 时,f(2, m) = (f(1, m) + m) % 2。
综合得:
f(n, m) = (f(1, m) + m) % n (n > 1)
代码如下:
```python
n = int(input("Input n: "))
m = 3
last_no = 0
for i in range(2, n+1):
last_no = (last_no + m) % i
last_no += 1
print("Last No.is: ", last_no)
```
两种方法的时间复杂度都是 O(n)。数学公式解法的空间复杂度为 O(1),递归解法的空间复杂度为 O(n)(需要递归 n 层)。