在上述约瑟夫问题中x是什么意思
时间: 2023-09-16 19:10:15 浏览: 53
在上述代码中,solve函数解决了一道约瑟夫问题,其传入三个参数,分别为人数n、报数上限m以及起始编号s。函数返回最后幸存者的编号。
在代码中,使用了两种情况的处理方式:
1. 当ans递增时,使用递推公式计算增加的次数x(即x=(i-ans-1)/(m-1)),然后判断i+x是否超过n,如果超过,则直接加上剩余的次数,退出循环。如果没有超过,将i增加x,ans增加x*m。
2. 当ans不递增时,使用普通的模运算方式计算ans(即ans=(ans+m)%i)。
其中,x表示增加的次数,即每隔m-1个人杀死一个人,杀死的人数为x*m,i则表示当前的人数,ans表示当前的编号。
相关问题
约瑟夫问题c
约瑟夫问题是一个经典的问题,可以使用循环链表来解决。以下是使用 C++ 语言实现的代码:
```c++
#include <iostream>
using namespace std;
// 定义循环链表节点结构体
struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};
// 定义函数实现约瑟夫问题
int josephus(int n, int m) {
// 构造循环链表
Node *head = new Node(1);
Node *cur = head;
for (int i = 2; i <= n; i++) {
cur->next = new Node(i);
cur = cur->next;
}
cur->next = head;
// 开始报数
Node *prev = NULL;
while (cur->next != cur) {
for (int i = 0; i < m-1; i++) {
prev = cur;
cur = cur->next;
}
prev->next = cur->next;
delete cur;
cur = prev->next;
}
int winner = cur->val;
delete cur;
return winner;
}
int main() {
int n = 5, m = 3;
int winner = josephus(n, m);
cout << "The winner is: " << winner << endl;
return 0;
}
```
在上述代码中,我们首先构造了一个循环链表,然后从链表头开始报数,每数到第 $m$ 个节点就将该节点删除,直到只剩下一个节点为止。最后返回剩下的节点的值即可。
注意,在链表中删除一个节点时,需要先保存该节点的前一个节点,以便在删除后将前一个节点与后一个节点相连。
约瑟夫问题c++
约瑟夫问题是一个经典的问题,可以使用循环链表来解决。以下是使用 C++ 语言实现的代码:
```c++
#include <iostream>
using namespace std;
// 定义循环链表节点结构体
struct Node {
int val;
Node *next;
Node(int x) : val(x), next(NULL) {}
};
// 定义函数实现约瑟夫问题
int josephus(int n, int m) {
// 构造循环链表
Node *head = new Node(1);
Node *cur = head;
for (int i = 2; i <= n; i++) {
cur->next = new Node(i);
cur = cur->next;
}
cur->next = head;
// 开始报数
Node *prev = NULL;
while (cur->next != cur) {
for (int i = 0; i < m-1; i++) {
prev = cur;
cur = cur->next;
}
prev->next = cur->next;
delete cur;
cur = prev->next;
}
int winner = cur->val;
delete cur;
return winner;
}
int main() {
int n = 5, m = 3;
int winner = josephus(n, m);
cout << "The winner is: " << winner << endl;
return 0;
}
```
在上述代码中,我们首先构造了一个循环链表,然后从链表头开始报数,每数到第 $m$ 个节点就将该节点删除,直到只剩下一个节点为止。最后返回剩下的节点的值即可。
注意,在链表中删除一个节点时,需要先保存该节点的前一个节点,以便在删除后将前一个节点与后一个节点相连。
相关推荐
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![rar](https://img-home.csdnimg.cn/images/20210720083606.png)
![zip](https://img-home.csdnimg.cn/images/20210720083736.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)