有 n 个人围成一圈,按顺序从1 到 n编号。从第一个人开始报数,报数 3 的人退出圈子,下一个人从1 开始重新报数,报数 3 的人退出圈子。如此循环,直 到留下最后一个人。问留下来的人的编号。 输入输出示例 Input n: 5 Last No.is:4
时间: 2023-12-23 07:56:28 浏览: 11
这是一个经典的约瑟夫问题,可以使用递归或数学公式来解决。
递归解法:
思路:每次从第一个人开始报数,报数为3的人出圈,剩下的人重新排列,然后再从第一个人开始报数,一直递归下去,直到只剩下一个人。
代码实现:
```python
def josephus(n, k):
if n == 1:
return 1
else:
return (josephus(n-1, k) + k-1) % n + 1
n = int(input("Input n: "))
last_no = josephus(n, 3)
print("Last No.is:", last_no)
```
数学公式解法:
思路:根据规律可以发现,每次出圈的人的编号都是从1开始每隔2个数取一个,即1, 4, 7, 10, ...,而且出圈的人的下一个人重新从1开始报数,所以每次报数的起点都会向后移动3个位置。因此,可以推出公式f(n) = (f(n-1) + 3) % n。
代码实现:
```python
n = int(input("Input n: "))
last_no = 0
for i in range(2, n+1):
last_no = (last_no + 3) % i
print("Last No.is:", last_no+1)
```
两种方法都可以得到正确的答案,其中数学公式方法更加简洁,但递归方法更易于理解和记忆。
相关问题
有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`个节点删除一个节点,最后输出剩下的最后一个节点的编号。
相关推荐
![](https://img-home.csdnimg.cn/images/20210720083646.png)
![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)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)
![](https://csdnimg.cn/download_wenku/file_type_ask_c1.png)