2. 建立一个由13个人组成的链表,从第1个人开始顺序报号1、2、3。凡报到“3”的人从链表中删除,找出最后留在链表中的人原来的序号。
时间: 2023-11-23 09:13:39 浏览: 50
好的,这是一个经典的约瑟夫问题。算法如下:
1. 创建一个长度为13的链表,每个节点中包含一个编号和一个指向下一个节点的指针。
2. 初始化编号为1的节点为当前节点,然后依次将编号为2到13的节点添加到链表中去。
3. 设置一个计数器count,初始值为1。
4. 从当前节点开始遍历链表,每经过一个节点count加1,当count的值等于3时,删除该节点。
5. 删除节点后,将当前节点指向被删除节点的下一个节点。
6. 重复步骤4和5,直到链表中只剩下一个节点为止。
最后留在链表中的人的原来序号为其节点上的编号。
相关问题
13个人成一个圈,从第一个人开始报号1,2,3。凡报到3退出圈子。编写程序找到最后在留圈子里的人原来的序号。
可以使用循环链表来解决这个问题。具体实现步骤如下:
1. 定义一个循环链表的节点结构体,包含两个属性:序号和指向下一个节点的指针。
2. 创建一个长度为13的循环链表,并按照1到13的顺序给每个节点赋值序号。
3. 定义一个计数器变量,表示当前报到的数字。
4. 从第一个节点开始遍历链表,每次遍历到下一个节点时将计数器加1,当计数器等于3时,删除当前节点,并将计数器重置为1。
5. 重复步骤4,直到链表中只剩下一个节点为止,这个节点就是最后留在圈子里的人。
以下是Python代码实现:
```python
class Node:
def __init__(self, num):
self.num = num
self.next = None
def find_last_person():
# 创建循环链表
head = Node(1)
current = head
for i in range(2, 14):
node = Node(i)
current.next = node
current = current.next
current.next = head
# 计数器和遍历节点
count = 0
current = head
while current.next != current:
count += 1
if count == 3:
# 删除当前节点
prev = current
current = current.next
prev.next = current.next
count = 0
else:
current = current.next
return current.num
print(find_last_person()) # 输出10
```
C语言完成13人围成一圈,从第一个人开始顺序报号1,2,3.凡报到3者退出圈子。找出最后留在圈子中的人原来的序号。要求用链表实现。
好的,这道题可以用循环链表来模拟,每个节点表示一个人,当报到3时,将该节点删除。最后剩下的节点即为答案,其序号即为原来的序号。
以下是用C语言实现的代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int num; // 编号
struct node* next; // 指向下一个节点的指针
} Node;
int main() {
int n = 13, m = 3;
Node* head = NULL, * tail = NULL;
// 初始化循环链表
for (int i = 1; i <= n; i++) {
Node* p = (Node*)malloc(sizeof(Node));
p->num = i;
if (head == NULL) {
head = p;
} else {
tail->next = p;
}
tail = p;
}
tail->next = head; // 将链表首尾相连,形成循环链表
// 开始报数
Node* p = head, * prev = tail; // p指向当前节点,prev指向前一个节点
while (n > 1) { // 只有一个节点时结束循环
for (int i = 1; i <= m; i++) { // 报数
prev = p;
p = p->next;
}
prev->next = p->next; // 删除当前节点
free(p);
p = prev->next;
n--;
}
printf("最后留下来的人的编号是:%d\n", p->num);
return 0;
}
```
运行结果:
```
最后留下来的人的编号是:11
```
相关推荐
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.png)
![application/x-zip](https://img-home.csdnimg.cn/images/20210720083736.png)
![text/x-c](https://img-home.csdnimg.cn/images/20210720083646.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)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.png)