题解 | #约瑟夫环#

先展示用数学的通项公式递推求解 (fun(n-1,m)+m)%n

int fun(int n,int m)
{
    if(n==1)
        return 0;
    else
        return (fun(n-1,m)+m)%n;
}
int main(){
    int n,m,k;
    scanf("%d%d%d",&n,&k,&m);
    printf("%d",(fun(n,m)+k)%n);
}

这样子看起来简单但是很难理解，推导起来很复杂，但是可以记一下。 接下来展示用数组这种易于理解的解法 对于求解这道题可以定义一个数组用来存放约瑟夫环内的各元素，并且这里要将数组内个元素初始化为0。

int mon[102] = { 0 };

初始化为0要放在main函数里进行，不要作为一个全局变量，不然只有90%的通过率。 对数组内的下标0~n-1的进行赋值1、2、3...n

for (int i = 0; i < n; i++) {
	mon[i] = i + 1;
}

设置pos作为下标在给mon[i]赋值时是从0下标开始的，那么对pos的初始值是要赋值为k-1才是前面for循环中所对应的下标，对num直接赋值为n

pos = k - 1, num = n;

接下来时核心代码区 当num>1时即还没有剩下一个人，进入while循环。在这里先分一个if-else语句若当前的这个值为0那么下标pos往后挪一位。因为这是一个环状，当下标为最后一位时候的下一位是第一位，我们的挪位采用

pos = (pos + 1) % n;

或者把上一个代码块更换为下面的代码块

pos++;
if(pos>=n)pos=0;

若mon[pos]值大于0（不等于0）进入下一个if-else语句 当计数器count不等于m时计数器count加一，下标往后移，、。等于0时令当前下标的值为0标志这个值被删除，下一次直接跳过，计数器count重置为1，总个数-1，坐标往后移。 输出时只要找不为0的下标是几就好了。

下面是全部的代码

#include<bits/stdc++.h>
using namespace std;
int n, m, k;

int main() {
	cin >> n >> k >> m;
	int num, count = 1, pos;
	int mon[102] = { 0 };
	if (n == 0 || m == 0) {
		return 0;
	}
	for (int i = 0; i < n; i++) {
		mon[i] = i + 1;
	}
	pos = k - 1, num = n;
	while (num > 1)
	{
		if (mon[pos] > 0) {
			if (count != m) {
				count++;
				pos = (pos + 1) % n;
			}
			else {
				mon[pos] = 0;
				count = 1;
				num--;
				pos = (pos + 1) % n;
			}
		}
		else {
			pos = (pos + 1) % n;
		}
	}
	for (int i = 0; i < n; i++) {
		if (mon[i] > 0) {
			cout << mon[i] << endl;
		}
	}
	return 0;
}