有n个人围成一圈,顺序排号。从第1人开始报数(从1到3),凡报到3的人退出圈子,问最后留下的是原来第几号的那位。(用指针方法处理)
时间: 2023-05-31 17:21:05 浏览: 94
### 回答1:
这道题可以用指针方法来处理。首先,我们可以用一个循环链表来表示这个围成一圈的人。每个节点表示一个人,节点中存储这个人的编号。然后,我们可以用一个指针p来指向当前报数的人。每次报数时,我们让p指向下一个人,直到报到3为止。这时,我们就可以将p指向的节点从链表中删除。最后,当链表中只剩下一个节点时,这个节点就是最后留下的人。
具体实现可以参考以下代码:
```c++
#include <iostream>
using namespace std;
struct Node {
int num;
Node* next;
};
int main() {
int n;
cout << "请输入人数n:";
cin >> n;
// 创建循环链表
Node* head = new Node{1, nullptr};
Node* p = head;
for (int i = 2; i <= n; i++) {
p->next = new Node{i, nullptr};
p = p->next;
}
p->next = head;
// 报数并删除节点
p = head;
while (p->next != p) {
// 报数
for (int i = 1; i < 3; i++) {
p = p->next;
}
// 删除节点
Node* q = p->next;
p->next = q->next;
cout << "删除第" << q->num << "个人" << endl;
delete q;
}
// 输出最后留下的人的编号
cout << "最后留下的是第" << p->num << "个人" << endl;
return ;
}
```
### 回答2:
这道题目是经典的约瑟夫问题,其实就是一种递归的思路。我们可以先创建一个指针数组,每个指针指向正数的位置。接下来,我们设定一个变量count,形别表示报数的顺序,如果count等于3,我们删除这个数。在删除之后,指针数组应该重新连接,使得其他元素的指针正确指向后面元素。同时,count也要重新开始计数。
我们可以使用链表来表示这个指针数组,每个结点指向下一个结点。然后,我们遍历这个链表,每次找到第3个元素并将其删除。当链表中只剩下一个元素时,这个元素就是最后留下的人。
在具体实现过程中,我们可以先用循环创建一个链表,然后使用一个指针指向链表开头。接下来,我们就可以开始报数和删除了。每次报数到3,就将当前结点的下一个结点拿来替换当前结点。当链表的长度为1时,我们就找到了最后留下的那个人。
下面是具体的实现代码:
```c++
#include <iostream>
using namespace std;
struct Node {
int val;
Node* next;
};
int main() {
int n;
Node* head = new Node;
Node* p = head;
cout << "请输入参与人数:";
cin >> n;
for (int i = 1; i <= n; i++) {
Node* q = new Node;
q->val = i;
p->next = q;
p = q;
}
p->next = head->next; // 将链表连成一个环
Node* q = head->next;
while (q->next != q) { // 只剩一个人时跳出循环
for (int i = 1; i < 3; i++) {
q = q->next;
}
Node* t = q->next;
q->next = t->next;
delete t;
}
cout << "最后留下的人是:" << q->val << endl;
return 0;
}
```
从运行结果可以看出,当参与人数为6时,最后留下的人是3,符合题目的要求。
虽然这道题目看上去很简单,但是却包含了很多算法思想,如链表、递归等,这对我们来说是一次很好的编程训练。
### 回答3:
这道问题其实是经典的约瑟夫问题,它可以使用指针方法来解决。
我们可以将这个圈子看作一个循环链表,每个节点代表一个人。设置一个指针p指向链表的第一个节点,然后从p开始报数并将p向前移动,直到报到第三个人。这时,我们就需要将p所指向的节点从链表中删除(即将p的前一个节点的next指向p的下一个节点),并将p指向下一个节点,再从这个节点开始重复上述的操作。直到链表中只剩下一个节点,这个节点就是最后留下的人。
具体实现可以如下:
```python
n = int(input("输入人数: "))
p = [i+1 for i in range(n)] # 初始化链表
i = 0 # 报数从1开始
while len(p) > 1: # 只要链表中还有超过1个节点就继续报数
i = (i+2) % len(p) # 报数到3时,将p所指节点从链表中删除
p.pop(i) # 并将p指向下一个节点
print("原来第{}号的人最后留下。".format(p[0]))
```
这里,我们使用了列表p来表示循环链表,每个元素都是一个人的编号。关键在于要记住p每次报数后需要指向下一个节点,并且在从链表中删除节点时需要注意索引的变化。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](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)
![](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)