约瑟夫环问题
一、问题描述
约瑟夫环问题是一个很经典的问题：一个圈共有N个人（N为不确定的数字），按顺序第一个人的编号为1，第二个人的编号为2，第三个人的编号就为3，以此类推第N个人的编号就为N，现在提供一个数字K，从第一个人开始报数（从1到K），依次类推，报到M这个数字的人出局，紧接着从出局的这个人的下一个人重新开始从1报数，和上面过程类似，报到K的人出局，直到N个人全部出局，请问，这个出局的顺序是什么？
举一个简单的例子：假设一个圆桌上有8个人，即N的值为8，他们在进行一个小游戏，从第一个人开始报数，报到3的（即K的值为3），需要喝酒，喝的醉为止，喝醉后出局不能再喝，求出他们喝醉人的顺序。答案是：3 6 1 5 2 8 4 7
分析：如上图所示，圈内的数字代表每个人的编号，从1开始编号到8。圈中的数字代表出局的人数，黑色的是已经喝醉出局的人。注意：已经出局的人无需报数，报数的都是未出局的人。从第一个人开始报数，报到3的人出局，因此，第一个出局的人为3号，3号出局之后，要从出局的这个人（3号）的下一个未出局的人（4号）重新开始从1开始报数，所以4号从1开始继续报数，那么，第二个出局的人就是6号，6号出局之后，要从出局的这个人（6号）的下一个未出局的人（7号）重新开始从1开始报数，所以7号从1开始继续报数，那么，第三个出局的人就是1号，1号出局之后，要从出局的这个人（1号）的下一个未出局的人（2号）重新开始从1开始报数，所以2号从1开始继续报数，那么第四个出局的人就是5号（2号报1，4号报2，5号报3，5号出局），5号出局之后，要从出局的这个人（5号）的下一个未出局的人（7号，这边6号已经出局了，不能报数，所以直接跳到7号）重新开始从1开始报数，那么第五个出局的人就是2号，2号出局之后，要从出局的这个人（2号）的下一个未出局的人（4号）重新开始从1开始报数，那么第六个出局的人就是8号，8号出局之后，要从出局的这个人的下一个未出局的人（4号）重新开始从1开始报数，那么第七个出局的人就是4号，4号出局之后，也就只剩下了7号。
二：解题方式（数组）
要求：要求输出出局人的顺序。
变量设计：
为了方便理解，把ren:定义为人数变化，num:定义为总人数，k:为报的数，数组：初始化为0 ，并把下表为1到num初始化为1，出局后变为0 。
1：代码
#include<stdio.h>
//约瑟夫环
int main()
{
int ren=0;//人数
int k=0;//报数
int sum=8;
int arr[100]={0};
for(int i=1;i<=8;i++)
{
arr[i]=1;//为1时是没出局的，下面变为0时出列
}
while(sum>0)
{
k++;
ren++;
while(arr[ren]==0)
{
ren++;
if(ren>8)
{
ren=1;
}
}
if(k==3)
{
arr[ren]=0;
printf("%d ",ren);
k=0;
sum--;
}
}
return 0;
}2：代码分析
（1）数组初始化
int arr[100]={0};
for(int i=1;i<=8;i++)
{
arr[i]=1;//为1时是没出列的，下面变为0时出列
} （2）报数为3的出局
if(k==3)
{
arr[ren]=0;
printf("%d ",ren);
k=0;
sum--;
} 下面代码1：是跳过已经出局的人，2：是如果人数大于8，要回到第一个，然后再从1开始到while循环中进行判断是否已经出局。（while(arr[ren]==0)//不止一个人出局要用while）。
while(sum>0)
{
k++;
ren++;
1：while(arr[ren]==0)//不止一个人出局要用while
{
ren++;
2： if(ren>8)
{
ren=1;
}
}三：题目拓展！！
1：可以直接输入想报到几出局，以及想要得总人数
#include<stdio.h>
//约瑟夫环
int main()
{
int ren=0;//人数
int k=0;//报数
printf("请输入报到几出局的数\n");
int p=0;
scanf("%d",&p);//报到几出局的人。
printf("请输入参与游戏的总人数\n") ;
int sum=0;
scanf("%d",&sum);//总人数
int j=sum; //存一下总人数
int arr[100]={0};
for(int i=1;i<=j;i++)
{
arr[i]=1;//为1时是没出局的，下面变为0时出局
}
while(sum>0)
{
k++;
ren++;
while(arr[ren]==0)
{
ren++;
if(ren>j)
{
ren=1;
}
}
if(k==p)
{
arr[ren]=0;
printf("%d ",ren);
k=0;
sum--;
}
}
return 0;
}腾讯云开发者
