当前位置：首页 > news >正文

python经典百题之围圈报数

news 2025/8/10 21:46:02

题目:有n个人围成一圈，顺序排号。从第一个人开始报数（从1到3报数），凡报到3的人退出圈子，问最后留下的是原来第几号的那位。

程序分析

思路1：模拟游戏过程
- 使用一个循环队列模拟游戏过程，每次循环移除报数为3的人，直到剩下最后一个人为止。
思路2：数学规律
- 利用数学规律推导出最后留下的人的编号，而不需要实际模拟游戏过程。
思路3：递归计算
- 使用递归的方式来求解，递归函数表示从n个人中找出最后留下的人的编号。

现在让我们用这三种思路实现Python代码。

方法1：模拟游戏过程

解题思路

使用一个循环队列模拟游戏过程，每次循环移除报数为3的人，直到剩下最后一个人为止。

代码实现

def last_person_using_simulation(n):# Create a list of n peoplepeople = list(range(1, n + 1))# Index to keep track of current personcurrent_index = 0while len(people) > 1:# Find the person to be removedremove_index = (current_index + 2) % len(people)# Remove the personpeople.pop(remove_index)# Update the current index for the next iterationcurrent_index = remove_index % len(people)return people[0]# Example usage
n = 10  # Number of people
result = last_person_using_simulation(n)
print(f"The last person remaining is originally numbered {result}.")

优缺点

优点：
- 直观易懂，容易实现。
缺点：
- 需要维护一个列表，空间复杂度较高。

方法2：数学规律

解题思路

利用数学规律推导出最后留下的人的编号，而不需要实际模拟游戏过程。

代码实现

def last_person_using_math(n):if n == 1:return 1else:return (last_person_using_math(n - 1) + 3 - 1) % n + 1# Example usage
n = 10  # Number of people
result = last_person_using_math(n)
print(f"The last person remaining is originally numbered {result}.")

优缺点

优点：
- 时间复杂度为O(n)，空间复杂度为O(1)。
缺点：
- 可能在大规模n下会导致递归栈溢出。

方法3：递归计算

解题思路

使用递归的方式来求解，递归函数表示从n个人中找出最后留下的人的编号。

代码实现

def last_person_using_recursion(n):if n == 1:return 1else:return (last_person_using_recursion(n - 1) + 3 - 1) % n + 1# Example usage
n = 10  # Number of people
result = last_person_using_recursion(n)
print(f"The last person remaining is originally numbered {result}.")