int Joseph(int n, int m) { if (n == 1) { return 1; } return (Joseph(n - 1, m) + m - 1) % n + 1; } 具体含义是什么
时间: 2024-05-26 15:13:48 浏览: 10
这段代码实现了约瑟夫问题的递归解法。约瑟夫问题是一个经典的数学问题,其描述如下:
$n$ 个人排成一圈,从第一个人开始报数,报到 $m$ 的人出圈,剩下的人继续从1开始报数,直到所有人都出圈。求出最后一个出圈的人在原序列中的位置。
这个递归函数的参数 $n$ 表示当前圈中人数,$m$ 表示报到 $m$ 的人出圈。当圈中只剩下一个人时,直接返回这个人的位置 $1$。否则,递归调用函数,求解规模为 $n-1$ 的子问题。假设子问题的解为 $x$,则在原问题中,由于每次都从 $m$ 开始报数,所以当前圈中第 $m$ 个人对应着子问题中的第 $x$ 个人,子问题中的第 $m$ 个人对应着原问题中的第 $(x+m-1)\%n+1$ 个人。因此递归函数返回的值为 $(x+m-1)\%n+1$,即原问题中最后一个出圈的人在圈中的位置。
这个递归函数的时间复杂度为 $O(n)$,空间复杂度为 $O(n)$,可以通过优化实现更高效的解法。
相关问题
int Joseph(int n, int m) { if (n == 1) { return 1; } return (Joseph(n - 1, m) + m - 1) % n + 1; }
这是一个递归函数,用于求解约瑟夫环问题。给定总人数 n 和每次出圈的数 m,求最后留下的人在原序列中的位置。
函数的基本思路是:假设已经求解了 n-1 个人的情况,现在再加入第 n 个人,那么最后留下的人的位置就是在 n-1 个人的基础上加上 m-1,然后对 n 取模,最后加 1。
具体来说,假设当前有 n 个人,每次出圈的数为 m。我们可以先假设从第 k 个人开始,每次数 m 个人出圈,最后剩下的是第 x 个人。那么我们可以得到一个递推式:
f(n,m)=(f(n−1,m)+m)%n
其中 f(n,m) 表示 n 个人时,每次数 m 个人出圈,最后剩下的人在原序列中的位置。这个递推式的意思是,n 个人时,先假设从第 m 个人开始,数 m 个人出圈,剩下 n-1 个人。那么在这 n-1 个人中,最后剩下的人在原序列中的位置就是 f(n-1,m)。但是我们要求的是 n 个人中最后剩下的人在原序列中的位置,因此需要把 f(n-1,m) 转换成 f(n,m)。由于从第 m 个人开始数,最后数到的是第 (m-1) mod n + 1 个人,因此要加上 m-1,然后对 n 取模,最后加 1。
最终的递推式为:
f(n,m)=(f(n−1,m)+m−1)%n+1
当 n=1 时,显然最后剩下的人就是第 1 个人,因此递归终止条件是 n=1,返回 1。
这个算法的时间复杂度是 O(n),因为需要递归 n 层。但是可以使用递推的方式,将时间复杂度优化到 O(1)。
C语言数据结构单向循环链表约瑟夫环问题用void Joseph(int n, int k, int m)函数代码实现
下面是使用 C 语言编写的单向循环链表约瑟夫环问题的代码,其中 `n` 表示总人数,`k` 表示开始报数的位置,`m` 表示数到第几个人出圈:
```c
#include <stdio.h>
#include <stdlib.h>
typedef struct node {
int num;
struct node *next;
} Node, *LinkList;
void CreateList(LinkList *L, int n) {
*L = (LinkList) malloc(sizeof(Node)); // 创建头结点
(*L)->num = 1;
(*L)->next = NULL;
Node *p = *L;
int i;
for (i = 2; i <= n; i++) {
Node *newNode = (Node *) malloc(sizeof(Node));
newNode->num = i;
newNode->next = NULL;
p->next = newNode;
p = newNode;
}
p->next = *L; // 最后一个结点指向头结点,形成循环链表
}
void Joseph(LinkList L, int k, int m) {
Node *p = L;
while (p->next != p) { // 只有一个结点时退出循环
for (int i = 1; i < k; i++) { // 找到第 k 个结点
p = p->next;
}
Node *q = p->next;
for (int i = 1; i < m; i++) { // 找到第 m 个结点
p = q;
q = q->next;
}
printf("%d ", q->num); // 输出出圈的结点的编号
p->next = q->next; // 删除出圈的结点
free(q);
}
printf("%d ", p->num); // 输出最后一个结点的编号
}
int main() {
int n, k, m;
printf("请输入总人数、开始报数的位置和数到第几个人出圈:");
scanf("%d%d%d", &n, &k, &m);
LinkList L;
CreateList(&L, n); // 创建单向循环链表
Joseph(L, k, m); // 解决约瑟夫环问题
return 0;
}
```
相关推荐
![application/msword](https://img-home.csdnimg.cn/images/20210720083327.png)
![pdf](https://img-home.csdnimg.cn/images/20210720083512.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)
![7z](https://img-home.csdnimg.cn/images/20210720083312.png)