有 n 个人围成一圈,按顺序从1 到 n编号。从第一个人开始报数,报数 3 的人退出圈子,下一个人从1 开始重新报数,报数 3 的人退出圈子。如此循环,直 到留下最后一个人。问留下来的人的编号。 输入输出示例 Input n: 5 Last No.is:4
时间: 2023-12-23 08:48:40 浏览: 43
这是经典的约瑟夫问题,可以使用循环链表来模拟这个过程。具体实现如下:
```python
n = int(input("Input n: "))
last_no = 0
# 初始化循环链表
circle = [i for i in range(1, n+1)]
current = 0 # 当前报数的人在链表中的位置
while len(circle) > 1:
current = (current + 2) % len(circle) # 报数并找到要删除的位置
del circle[current]
last_no = circle[0]
print("Last No. is:", last_no)
```
这里用一个列表 `circle` 来表示循环链表,每个数字表示一个人的编号。`current` 变量表示当前报数的人在链表中的位置,每次报数后要找到下一个要删除的人在链表中的位置,即 `(current + 2) % len(circle)`。由于每删除一个人,链表的长度会减一,所以要对 `current` 取模以保证不会数组越界。最后剩下的一个人就是留下来的人,其编号即为 `circle[0]`。
相关问题
有n人围成一圈,顺序排号。从第1个人开始报数(从1到3报数),凡报到3的人退出圈子,问
最后留下的是原来第几号的那位?
这是一个经典的约瑟夫问题。根据引用中的解题思路,我们可以写一个函数来解决这个问题。具体步骤如下:
1. 定义一个大小为n的一维数组,初始化为从1到n。
2. 设一个计数器,按照题述条件,遍历每一个数组元素,并从1到3报数,若当前元素计数为3则将其从数组中删除(即标记该人出局),同时使计数器置0并记录出局人数。
3. 如果出局人数为n-1人(即只剩下1人)终止循环,否则由外层循环控制使得再次遍历数组,直到踢出n-1人。
4. 最后满足只剩1人的条件后,再次遍历数组,找出那个最终没有被踢出的人,并返回其序号。
因此,最后留下的是原来第几号的那位取决于n和报数的规则。如果n=5,报数规则为从1到3,则最后留下的是原来第3号的那位。如果n=10,报数规则为从1到2,则最后留下的是原来第5号的那位。
c语言有n个人围成一圈用指针,C语言 有n个人围成一圈,按顺序从1到n编号.从第一个人开始报数,报数3的人退出圈子...
好的,这是经典的约瑟夫问题,其解法可以用循环链表和递归两种方式实现。以下是用循环链表实现的C语言代码:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct Node {
int data;
struct Node* next;
} Node;
Node* create(int n) {
Node* head = (Node*)malloc(sizeof(Node));
head->data = 1;
head->next = NULL;
Node* tail = head;
for (int i = 2; i <= n; i++) {
Node* node = (Node*)malloc(sizeof(Node));
node->data = i;
node->next = NULL;
tail->next = node;
tail = node;
}
tail->next = head; // 将链表的尾节点指向头节点,形成循环链表
return head;
}
Node* remove(Node* head, int k) {
Node* p = head;
while (p->next != p) { // 当链表中只剩一个节点时结束循环
for (int i = 1; i < k; i++) {
p = p->next;
}
Node* temp = p->next;
p->next = temp->next; // 将当前节点的下一个节点从链表中删除
free(temp); // 释放被删除节点的内存
}
return p;
}
int main() {
int n = 10;
int k = 3;
Node* head = create(n);
Node* p = remove(head, k);
printf("The last one is %d\n", p->data);
free(p); // 释放最后一个节点的内存
return 0;
}
```
这段代码中,`create`函数用于创建一个有`n`个节点的循环链表,并返回头节点的指针。`remove`函数用于从循环链表中每隔`k-1`个节点删除一个节点,直到链表中只剩下一个节点,最后返回最后一个节点的指针。在主函数中,我们调用`create`函数创建了一个有`10`个节点的循环链表,然后调用`remove`函数从链表中每隔`2`个节点删除一个节点,最后输出剩下的最后一个节点的编号。
相关推荐
![pdf](https://img-home.csdnimg.cn/images/20210720083512.png)
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![java](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)