Question

C++ 约瑟夫环问题 代码求解释~

#include<iostream>
using namespace std;
int main()
{
const int n=100;
int m=30;
int a[n];

for(int j=0;j<n;j++)
a[j]=j+1;
int k=1;
int i=-1;
while(1)
{
for(int j=0;j<m;)
{
i=(i+1)%n;
if(a[i]!=0)
j++;
}
if(k==n)
break;
a[i]=0;
k++;
}
cout<<a[i]<<endl;
return 0;
}

Answer 1

首先，这个代码输出的是，约瑟夫环到达的最后位置。输出结果是15。
//把iostream这个文件中的内容复制到这个地方。
#include<iostream>
using namespace std;
int main()
{
//定义一个常量的整形100，表示人的个数。
const int n=100;
//定义约瑟夫环的参数。
int m=30;
//定义一个数组，用于计算约瑟夫环的位置。
int a[n];

//给数组赋值，让数组的每个值就是这个元素的编号。
for(int j=0;j<n;j++)
a[j]=j+1;
//定义一个标志k，当K等于N的时候，表示到达约瑟夫环的最后位置。
int k=1;
int i=-1;
while(1)
{
for(int j=0;j<m;)
{
//不停的取数组的下一个元素。
i=(i+1)%n;
//如果这个元素没有被标记为0，说明这个位置还没有被排除，j加1，进入下一个循环
if(a[i]!=0)
j++;
}
//如果标志K等于n，说明约瑟夫环的循环到达最后一个位置，跳出While死循环。
if(k==n)
break;
//否则，把这个位置的元素设为零，标志它被排除。
a[i]=0;
//标志+1。
k++;
}
//输出约瑟夫环到达的最后一个位置。
cout<<a[i]<<endl;
return 0;
}

Answer 2

int main()
{//计算约瑟夫环最后一次取出的号码，约瑟夫环编号方式为1,2,3,4…… 每次隔m个取出下一个
const int n=100;
int m=30;
int a[n];

for(int j=0;j<n;j++)//为约瑟夫环赋值
a[j]=j+1;
int k=1;//记录已经取出个数
int i=-1;//记录当前取出的编号
while(1)
{
for(int j=0;j<m;)
{//在当前环内往前走m步，用a[i]=0表示该编号已经取出，若遇此编号不算入步数。
//每次前进1步后对n取余数，实现环的遍历
i=(i+1)%n;
if(a[i]!=0)
j++;
}
if(k==n)//已经取出n个，退出循环
break;
//尚未取完，将当前要取出的赋为0，表示已经取出
a[i]=0;
k++;//取出个数加1
}
//跳出循环时a[i]的值表示当前要取出的编号，即最后取出编号
cout<<a[i]<<endl;
return 0;
}