写一段约瑟夫环问题的c++解决方案
时间: 2023-03-14 21:22:35 浏览: 71
答案:
/*
假设有n个人围成一个环形,每个人有一个编号,从1开始到n,现在要从1开始报数,报到m的人出列,然后从出列的下一位再从1开始报数,如此反复,直到所有人都出列为止。C语言解决方案:
#include <stdio.h>
int main()
{
int n, m, k, cnt;
scanf("%d %d", &n, &m);
int a[n];
for(int i=0; i<n; i++){
a[i] = i+1;
}
cnt = n;
k = 0;
while(cnt > 0){
k++;
if(k % m == 0){
printf("%d ", a[k-1]);
a[k-1] = 0;
cnt--;
}
if(k == n)
k = 0;
}
return 0;
}
*/
相关问题
约瑟夫环绕问题c++
约瑟夫环绕问题是一个经典的数学问题,也被称为约瑟夫问题或约瑟夫斯置换。问题的描述如下:
有n个人围成一圈排队,从第一个人开始报数,数到 m 的人出列,然后从出列的下一个人开始重新报数,直到所有人都出列。要求找出出列的顺序。
解决这个问题的一种常见方法是使用递归。首先,定义一个递归函数,命名为josephus(n,m),表示n个人中按照m进行报数的出列顺序。递归函数的返回是一个列表,表示出列的顺序。
递归函数的基本情况是,当只有一个人时,该人是最后出列的,直接返回一个只包含该人的列表。
当有多个人时,我们需要找到第一个出列的人。根据问题的要求,第一个出列的人是从出列的下一个人开始重新报数。所以,我们可以递归调用josephus(n-1,m),表示去掉第一个人后剩下的n-1个人按照m进行报数的出列顺序。然后,将返回的列表中第一个人加入到结果列表中。
最后返回结果列表,表示n个人按照m进行报数的出列顺序。
下面是一个用Python实现的例子:
def josephus(n,m):
if n == 1:
return [1]
else:
remaining = josephus(n-1,m)
idx = (m-1) % len(remaining)
return remaining[:idx] + [n] + remaining[idx+1:]
n = 10
m = 3
result = josephus(n,m)
print(result)
使用上述代码,当有10个人时,按照每次报数3个人出列的规则,最后出列的顺序为[4, 1, 8, 6, 2, 10, 3, 7, 5, 9]。
c++解决约瑟夫环问题
约瑟夫环问题是一个经典的问题,可以用循环链表来解决。具体的解决方法如下:
1. 首先,创建一个长度为n的循环链表,并将链表中的节点编号从1到n。
2. 定义一个指针p,指向链表的第一个节点。
3. 定义一个计数器count,初始值为1。
4. 从链表中删除第count个节点,并将指针p指向下一个节点。
5. 将计数器count加1。
6. 重复步骤4和5,直到链表中只剩下一个节点。
7. 输出最后剩下的节点编号,即为约瑟夫环的解。
下面是C语言代码实现:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int num;
struct node *next;
} Node;
Node *createList(int n) {
Node *head = (Node *)malloc(sizeof(Node));
Node *p = head;
for (int i = 1; i <= n; i++) {
Node *node = (Node *)malloc(sizeof(Node));
node->num = i;
p->next = node;
p = node;
if (i == n) {
p->next = head->next;
}
}
return head->next;
}
int josephus(int n, int m) {
Node *head = createList(n);
Node *p = head;
while (p->next != p) {
for (int i = 1; i < m - 1; i++) {
p = p->next;
}
printf("%d ", p->next->num);
Node *temp = p->next;
p->next = temp->next;
free(temp);
p = p->next;
}
printf("%d\n", p->num);
return p->num;
}
int main() {
int n, m;
scanf("%d%d", &n, &m);
josephus(n, m);
return 0;
}
```
在上面的代码中,我们首先定义了一个结构体Node,表示链表中的节点。然后,我们创建了一个长度为n的循环链表,并定义一个指针p,指向链表的第一个节点。接着,我们循环执行步骤4和5,直到链表中只剩下一个节点,输出该节点的编号即为约瑟夫环的解。