请问这道约瑟夫问题的代码如何理解呢?希望帮逐行注释一下代码,并说一下思路。
问题描述:
有n只猴子,按顺时针方向围成一圈选大王(编号从1到n),从第1号开始报数,一直数到m,数到m的猴子退出圈外,剩下的猴子再接着从1开始报数。就这样,直到圈内只剩下一只猴子时,这个猴子就是猴王。编程输入n和m,输出最后猴王的编号。
#include<cstdlib>
#include<cstdio>
int flag[305];
void int()
{
for (int index = 0; index < 305; index++)
{
flag[index] = 0;
}
}
int main()
{
int n, m;
scanf("%d", &n);
scanf("%d", &m);
while (n != 0 && m != 0)
{
int index = -1;
int count = 0;
init(); //全都没有数过
for (int i = 1; i < n; i++)
{
count = 0;
while (count != m)
{
index = (index + 1) % n; //到圈尾,取模
if (flag[index] == 0)
{
//如果还没有退出圈,累加数量
//如果累加到m,该位置的点退出圈,置1
count++;
if (count == m)
{
flag[index] = 1;
}
}
}
}
//打印出最后未出圈的点
for (int j = 0; j < n; j++)
{
if (flag[j] == 0)
{
printf("%d\n", j + 1);
break;
}
}
scanf("%d", &n);
scanf("%d", &m);
}
return 0;
}