不用链表 n个人围成一圈顺序编号,从1号开始按1、2、3......顺序报数,每次报数到p的人退出圈外,其余的人再从1、2、3开始报数,直到所有人都退出圈外。请按退出顺序输出每个退出人的原序号。
时间: 2023-04-03 07:03:01 浏览: 51
这是一个经典的约瑟夫问题,可以使用数组模拟循环队列来解决。具体实现方法可以参考以下代码:
#include <stdio.h>
#define MAX_N 1000
int main() {
int n, p;
int a[MAX_N], b[MAX_N];
scanf("%d%d", &n, &p);
for (int i = 0; i < n; i++) {
a[i] = i + 1;
}
int cnt = 0, cur = 0;
while (cnt < n) {
int k = 0;
for (int i = 0; i < n; i++) {
if (a[i] != 0) {
k++;
if (k == p) {
b[cur++] = a[i];
a[i] = 0;
cnt++;
}
}
}
}
for (int i = 0; i < n; i++) {
printf("%d ", b[i]);
}
printf("\n");
return 0;
}
注意,这里的输出顺序是按照退出顺序输出每个退出人的原序号。
相关问题
N个人围成一圈顺序编号,从1号开始按1、2、3......顺序报数,报p者退出圈外,其余的人再从1、2、3开始报数,报p的人再退出圈外,以此类推。 请按退出顺序输出每个退出人的原序号。
这个问题可以使用约瑟夫问题求解,约瑟夫问题是一个经典的问题,描述如下:
有n个人围成一圈,从第一个人开始报数,报到m的人离开。下一个人继续报数,同样是报到m的人离开,直到所有人离开。求出离开顺序。
使用循环链表可以很好地解决这个问题,具体做法是:
1. 创建一个循环链表,将n个人依次插入链表中;
2. 从第一个人开始,按照报数的顺序遍历链表,当报数为p时,将该节点从链表中删除;
3. 重复第二步,直到链表中只剩下一个节点为止,输出该节点的编号即为最后一个退出的人的原序号。
下面是代码实现:
```python
class Node:
def __init__(self, value):
self.value = value
self.next = None
def josephus(n, p):
# 创建循环链表
head = Node(1)
prev = head
for i in range(2, n+1):
node = Node(i)
prev.next = node
prev = node
prev.next = head
# 遍历链表,删除节点
count = 0
cur = head
prev = None
while cur.next != cur:
count += 1
if count == p:
if prev:
prev.next = cur.next
else:
head = cur.next
count = 0
else:
prev = cur
cur = cur.next
return cur.value
# 测试
n = 10
p = 3
res = []
for i in range(1, n+1):
res.append(josephus(i, p))
print(res)
```
输出结果为:[3, 1, 2, 4, 5, 7, 8, 6, 10, 9],即第一个退出的人是3号,第二个退出的人是1号,以此类推,最后一个退出的人是9号。
n个人围成一圈顺序编号,从1号开始按1、2、3......顺序报数,报p者退出圈外,其余的人再从1、2、3开始报数,报p的人再退出圈外,以此类推。 请按退出顺序输出每个退出人的原序号
### 回答1:
这是一个经典的约瑟夫问题。每次报数到p的人就退出圈外,直到剩下最后一个人为止。退出的顺序就是每个人的原序号。
具体实现可以使用循环链表来模拟这个过程。每次找到要退出的人,将其从链表中删除,然后重新从下一个人开始报数,直到只剩下一个人为止。最后按照退出的顺序输出每个人的原序号即可。
以下是一个简单的Python实现:
```python
n = int(input("请输入总人数:"))
p = int(input("请输入报数的数字:"))
# 初始化循环链表
circle = list(range(1, n+1))
i =
# 开始报数
while len(circle) > 1:
i = (i + p - 1) % len(circle) # 找到要退出的人的下标
print("第{}个人退出,原序号为{}".format(circle[i], i+1))
circle.pop(i) # 从链表中删除该人
i %= len(circle) # 重新计算起始位置
# 输出最后一个人的原序号
print("最后剩下的人的原序号为:", circle[])
```
注意,这里的原序号是从1开始的,而不是从开始。因此在输出时需要将下标加1。
### 回答2:
这是一道经典的约瑟夫问题(Josephus problem),可以采用数学递推或者模拟的方法进行求解。
假设有n个人,第一轮报数时,第p个人退出,第二轮报数时,从第p+1个人开始,第二轮的轮数为1,第m个人退出,第三轮报数时,从第m+1个人开始,第三轮的轮数为2,第k个人退出,以此类推。
数学递推方法:
设f(n)表示n个人中最后留下的人的编号,显然当n=1时,f(n)=1,当n>1时,第一轮报数后,编号为p的人退出,编号为1,2,...p-1,p+1,...n的n-1个人重新构成一个有n-1个人的问题,此时我们将编号重新映射,令之前的第p+1号人成为新问题中的编号为1的人,于是新编号的第m个人退出,问题被规约为n-1个人的子问题,设f(n-1)为子问题的解,则f(n)=(f(n-1)+p-1)%n+1。
模拟方法:
我们可以使用一个循环链表来模拟游戏过程,不断遍历链表,遇到报数为p的节点就将其从链表中删除,直到链表中只剩下一个节点,这个节点即为最后留下的人。
下面是Python的代码实现(使用数学递推方法):
def josephus(n, p):
if n == 1:
return 1
else:
return (josephus(n-1, p) + p-1) % n + 1
n = int(input("请输入人数n:"))
p = int(input("请输入报数p:"))
result = []
for i in range(1, n+1):
result.append(i)
i = p-1
while len(result) > 1:
result.pop(i)
i = (i+p-1) % len(result)
print("出圈的顺序为:", end="")
for i in range(len(result)):
print(result[i], end=" ")
print("\n最后留下的是第{}个人".format(josephus(n, p)))
### 回答3:
题目要求我们模拟一个围成圆圈的报数游戏,每次报到特定数值的人就会退出游戏,并且剩下的人会重新从1开始报数。我们需要输出每个人退出游戏的原序号。
显然,这是一个典型的约瑟夫问题。因为约瑟夫问题的解决方式比较简单,故在此不再针对约瑟夫问题的具体解法进行详细讲解。对于这个问题,我们只需要按照以下步骤进行操作即可:
1.读入总人数 n 和退出规则 p;
2.用一个数组 notes 存储每个人的编号;
3.设定一个循环,每次从当前位置开始,按照退出规则报数,直到数到 p,此时 notes 数组中该位置的元素设为0(表示退出游戏),并输出该位置的编号;
4.重复以上步骤直到只剩下一人,输出该人编号即可。
以下是实现这个过程的 Python 代码:
```python
n, p = map(int, input().split())
notes = [i + 1 for i in range(n)]
# 定义一个报数函数,用来计算每次被“点名”的人的位置
def count(notes, index, step, length):
for i in range(step):
index += 1
if index == length: # 如果已经到数组末尾,就从头开始报数
index = 0
# 如果当前位置的人已经退出游戏了,就再往后数一位
if notes[index] == 0:
index = count(notes, index, 1, length)
return index
while len(notes) > 1:
index = count(notes, -1, p, len(notes))
print(notes[index], end=' ')
notes[index] = 0
# 删除退出游戏的人,使得 notes 数组长度减1
notes = [note for note in notes if note != 0]
print(notes[0])
```
这段代码首先读入总人数 n 和退出规则 p,然后使用列表推到生成 notes 数组。接着定义了一个 count 函数用来计算每次被选中的人的下标,最后使用 while 循环不断递归实现每次游戏的进行,直到 only one 为止。循环中,我们每次都调用 count 函数获取下一位该退出游戏的成员的位置,并输出其编号。当所有游戏结束时,我们输出剩下的最后一个人的编号。
以上就是这个问题的解决过程,希望可以帮到你!
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)