约瑟夫环问题 设有n个人站成一排,从左向右的编号分别为1~n,现在从左往右报数“1,2,3,…m”,数到“m”的人出列,数到“1到m-1”的人立即站到队伍的最右端【这些人出队后,再进队】。报数过程反复进行,直到n个人都出列为止。要求给出他们的出列顺序。
时间: 2024-06-06 22:08:42 浏览: 28
解法一:模拟
这是一道经典的问题,可以使用模拟的方法解决。我们可以用一个数组来记录每个人的出列顺序,每次数到m时,就将该人标记为已出列,然后再将从1到m-1的人放到队尾,直到所有人都出列为止。
具体实现可以使用一个指针来表示当前报数的人,每次数到m时,将该人标记为已出列,然后将指针后移m个位置,如果后移后超过了数组的长度,就从头开始循环。
时间复杂度:O(nm)
代码如下:
int josephus(int n, int m, int* order) {
int* a = new int[n + 1];
for (int i = 1; i <= n; i++) {
a[i] = i;
}
int cnt = 0, cur = 1;
while (cnt < n) {
int k = 0;
while (k < m) {
if (a[cur] > 0) {
k++;
}
if (k == m) {
order[cnt++] = a[cur];
a[cur] = 0;
}
cur++;
if (cur > n) {
cur = 1;
}
}
}
delete[] a;
return cnt;
}
解法二:递推公式
事实上,这个问题还有一个更为巧妙的解法,可以使用递推公式来解决。假设f(n,m)表示n个人报数到m时最后剩下的人的编号,那么我们可以得到如下的递推公式:
f(n,m) = (f(n-1,m)+m) % n
这个公式的含义是:当有n个人报数时,每报数到m时,就相当于从n个人中删除了第m个人,然后剩下n-1个人。假设剩下的人的编号是x,那么x在删除第m个人之后的编号是(x-1+m)%n+1。因此,f(n,m)就可以递推为f(n-1,m)在删除第m个人之后的编号。
时间复杂度:O(n)
代码如下:
int josephus(int n, int m, int* order) {
int x = 0;
for (int i = 2; i <= n; i++) {
x = (x + m) % i;
}
for (int i = 0; i < n; i++) {
order[i] = (x + i + 1) % n;
}
return n;
}
相关推荐
![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)
![](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)