有n个人围成一圈,顺序排号。从第1人开始报数(从1到3),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。用指针
时间: 2023-09-09 11:04:28 浏览: 110
### 回答1:
假设现在有 n 个人,从第 1 个人开始报数。
1. 初始化指针 p 指向第 1 个人,计数器 count 置为 1。
2. 每次将指针 p 向后移动一位,并将计数器 count 加 1。
3. 当 count 等于 3 时,将指针 p 指向的人退出圈子,并将计数器 count 重置为 1。
4. 重复步骤 2 和 3,直到圈子中只剩下一个人为止。
最后剩下的那个人就是原来第几号的那位。
代码示例(使用 Python 语言):
```
n = 10 # 圈子中有 10 个人
p = 0 # 初始化指针 p 指向第 1 个人
count = 1 # 初始化计数器 count 为 1
while n > 1: # 圈子中还剩下多于 1 个人
p = (p + 1) % n # 移动指针 p 到下一个人
count += 1 # 将计数器 count 加 1
if count == 3: # 如果 count 等于 3
count = 1 # 重置计数器 count 为 1
n -= 1 # 将圈子中的人数减 1
print(p + 1) # 输出最后剩下的那个人的编号
```
### 回答2:
假设有 n 个人围成一圈,初始情况下,可以用一个长度为 n 的数组 arr 来表示,数组中的每个元素代表每个人的编号。初始状态下,arr 的元素依次为 1, 2, 3, ..., n。
定义两个指针:start 和 end,初始时,start 指向第一个元素,即编号为 1 的人,end 指向最后一个元素,即编号为 n 的人。
接下来进行一个循环,直到只剩下一个人为止。在每一轮循环中,指针 start 指向的人开始报数,并根据报数结果进行相应的操作。
当报数为 1 时,指针 start 不动,并将指针 end 指向的人移动到 start 的后面一个位置。
当报数为 2 时,将指针 start 和 end 都向后移动一位。
当报数为 3 时,将指针 start 指向的人移出圈子,即从数组 arr 中删除该元素,并将指针 start 和 end 都向后移动一位。
循环结束时,只剩一个人,返回该人的编号即为结果。
下面是用指针的伪代码实现:
```python
def lastRemaining(n):
arr = [i for i in range(1, n + 1)]
start = 0
end = n - 1
while start != end:
for i in range(1, 4):
if i == 1:
# 报数为 1,不做操作
pass
elif i == 2:
# 报数为 2,指针都向后移动一位
start = (start + 1) % n
end = (end + 1) % n
else:
# 报数为 3,移出圈子
arr.pop(start)
n -= 1
start = start % n
end = (end - 1) % n
return arr[0]
# 测试
n = 6
print(lastRemaining(n)) # 输出:4
```
根据上述代码,最后留下的是原来第 4 号的那位。
### 回答3:
题目要求使用指针解答,那我们可以用一个指针p来代表当前报数的人。我们可以使用循环来模拟报数的过程。
首先,我们需要定义一个长度为n的循环链表,然后按照题目给出的要求进行报数。
1. 首先,我们创建一个长度为n的循环链表。
2. 然后,我们初始化一个指针p,指向链表的第一个节点。
3. 接下来,我们开始循环报数的过程。在每一轮中,我们首先将指针p向后移动两个节点(即报到3的人),然后将第三个节点(即报到3的人)从链表中删除。再次回到第一步直到只剩下一个人。
4. 最后,当链表中只剩下一个节点时,该节点就是最后留下的人。
例如,假设n=5,开始时链表的结构为1->2->3->4->5->1。
第一轮,指针p指向1。1->2->3,将3节点删除,链表变为1->2->4->5->1。
第二轮,指针p指向2。2->4->5,将5节点删除,链表变为2->4->1->2。
第三轮,指针p指向4。4->1->2,将2节点删除,链表变为4->1->4。
第四轮,指针p指向1。1->4,将4节点删除,链表变为1->1。
最后,只剩下1节点,所以最后留下的是原来的第1号人。
因此,当n=5时,最后留下的是原来的第1号人。
阅读全文