使用C++写出.约瑟夫问题:N个人围成一圈,从第一个人开始报数,数到M的人出圈;再由下一个人开始报数,数到M的人出圈;…输出依次出圈的人的编号。N,M由键盘输入。
时间: 2023-09-23 12:05:31 浏览: 169
### 回答1:
好的,感谢您的问题。以下是用 C 语言解决约瑟夫问题的代码:
```c
#include <stdio.h>
#include <stdlib.h>
struct node {
int data; // data 存储编号
struct node *next; // next 指向下一个节点
};
// 创建一个长度为 n 的环形链表,返回指向第一个节点的指针
struct node* createList(int n) {
struct node *head = NULL, *prev = NULL, *curr = NULL;
for (int i = 1; i <= n; i++) {
curr = (struct node*) malloc(sizeof(struct node));
curr->data = i;
curr->next = NULL;
if (head == NULL) {
head = curr; // 第一个节点
} else {
prev->next = curr;
}
prev = curr;
}
prev->next = head; // 最后一个节点指向第一个节点,形成环
return head;
}
// 删掉 p 所指的节点,并返回下一个节点的指针
struct node* deleteNode(struct node *p) {
struct node *next = p->next;
p->next = next->next;
free(next);
return p->next;
}
// 约瑟夫问题求解
void josephus(int n, int m) {
struct node *p = createList(n);
int count = 1;
while (n > 0) {
if (count == m) {
// 输出出圈节点的编号
printf("%d ", p->data);
// 删除这个节点
p = deleteNode(p);
// 更新链表长度
n--;
// 重新开始计数
count = 1;
} else {
// 继续报数
p = p->next;
count++;
}
}
printf("\n");
}
int main() {
int n, m;
printf("请输入 N 和 M:");
scanf("%d%d", &n, &m);
josephus(n, m);
return 0;
}
```
希望能够解决您的问题。如果您有其他问题,请随时提问。
### 回答2:
约瑟夫问题是一个经典的数学问题,可以使用C语言编写算法来解决。
首先,我们需要通过键盘输入N和M的值。N表示总共有多少个人,M表示数到M的人出圈。
然后,我们可以使用一个循环来模拟游戏的过程。设定一个数组来表示圈中的人,数组元素的值表示编号。我们从第一个人开始报数,每数到M时,将该人出圈,并将其编号输出。
为了模拟数到M的人出圈的过程,我们可以使用一个变量来记录当前报数的位置,初始值为0。每次报数后,该变量自增1,若大于等于N,则将其置为0,继续报数。每当报数达到M时,将当前位置对应的人出圈,输出其编号,并将其从数组中移除。
我们可以使用一个循环来模拟游戏的进行,直到只剩下一个人。循环的条件可以是数组中剩余人的数量大于1。在循环中,我们按照上述规则遍历数组,输出出圈的人的编号,并将其从数组中移除。
最后,输出数组中剩下的最后一个人的编号,即为约瑟夫问题的解答。
下面是使用C语言编写的约瑟夫问题的代码:
```c
#include <stdio.h>
int main() {
int N, M;
printf("请输入参与游戏的人数N:");
scanf("%d", &N);
printf("请输入数到M的人出圈的数M:");
scanf("%d", &M);
int people[N];
int count = 0;
for (int i = 0; i < N; i++) {
people[i] = i + 1; // 初始化编号
}
while (N > 1) {
count = (count + M - 1) % N; // 更新当前位置
printf("第%d个人出局,编号为%d\n", N, people[count]);
for (int i = count; i < N - 1; i++) {
people[i] = people[i + 1]; // 移除出局的人
}
N--; // 减少剩余人的数量
}
printf("最后剩下的人的编号为%d\n", people[0]);
return 0;
}
```
这样,我们就可以使用C语言编写一个简单的约瑟夫问题的解答程序了。
### 回答3:
约瑟夫问题是一个经典的数学问题,可以使用C语言来解决。根据题目要求,我们可以通过使用循环和数组来模拟这个问题的过程。
首先,我们从键盘接受输入的N和M的值,分别表示围成一圈的人数和每次报数的数字。然后,我们创建一个长度为N的数组,用于表示N个人的编号。接下来,我们定义一个循环,通过不断进行报数和出圈的操作,直到只剩下1个人为止。
具体的步骤如下:
1. 从键盘接受用户输入的N和M值。
2. 创建一个长度为N的数组,用于表示N个人的编号。
3. 定义一个变量current表示当前报数的人的索引,并初始化为0。
4. 定义一个变量count表示报数的次数,并初始化为1。
5. 使用一个while循环,判断数组中的人数是否大于1,如果是则继续进行报数和出圈的操作。
- 在循环内部,首先判断当前报数的人是否为0。如果是,则将current的值置为N-1,以实现围成一圈的效果。
- 然后,判断count的值是否为M。如果是,则将当前报数的人出圈,即将数组中的对应元素置为-1,并将count重新置为1。
- 最后,将current的值加1,count的值加1,以便进行下一轮报数。
6. 循环结束后,遍历数组,输出所有值不等于-1的元素,即输出依次出圈的人的编号。
通过以上步骤,我们就可以使用C语言来解决约瑟夫问题。以上是一个简单的实现,可以根据需要进行扩展和优化。
阅读全文