约瑟夫环解法之一（一维动态数组存储结构）
这是我第一次在CSDN上发布文章
您好！ 这是我第一次在CSDN上发布文章，以前都是来这里查找资源，感谢同行码们的分享，在最近管理一个微信公众号循序渐进C++，发表了一些基础教学视频和文章，也愿意分享给您，如有不妥之处，请您提出宝贵意见。
约瑟夫环问题
Josephus 问题是说，numbers 个小孩而围成一圈做游戏，游戏将决出一个胜利者。假定一个间隔数 interval，从第 start 个小孩开始，顺时针计数，每数到第 interval 个小孩的时候，这个小孩就要离开队伍。接着又从下一个开始数数，数到第 interval 个小孩，这个小孩也要离开，如此不断反复地进行，最后剩下的一个小孩儿就是胜利者，对于一定的 numbers（人数）,interval(间隔数)和 start(起始位置)，那究竟谁是胜利者呢？
算法流程
- 输入人数，间隔数，和起始位置，分别进行有效数据验证；
- 根据人数初始化数组，并给出每个数据元素的赋值为 1，标志都者队列里面，用数据元素小标加 1 表示小孩的序号；
- 循环计数，排除 n-1 个小孩
while(小孩个数多余 1)
{
数到 interval 个小孩儿；
该小孩儿离开队伍，修改数组元素的值为 0，表示小孩儿离开队伍
小孩个数减去 1
} - 找到数组中，元素为 0 的唯一一个数组元素，输出下标+1 这个值，就是最后胜利的小孩儿的序号。
实现代码
#include <iostream>
using namespace std;
int main() {
int numbers,start,interval;
cout<<"输入小孩人数：";
cin>>numbers;
if(numbers<2) return 0;
cout<<"输入开始数数的位置：";
cin>>start;
if(start<1||start>numbers) return 0;
cout<<"输入间隔人数：";
cin>>interval;
if(interval<1||interval>numbers) return 0;
int leftNumbers=numbers;//初始化队列里剩下的人数
int count=0;//初始化计数器
int pos=start-1;//初始化位置下标，比如，第1个孩子，下标为0
int *children=new int[numbers];//初始化小孩数组，长度为numbers;
for(int i=0;i<numbers;i++)
children[i]=1;//数组元素全部设置为1，表示在队列中，出队后该数组元素设置为0
cout<<"共有:"<<numbers<<"个小孩儿"<<endl;;
cout<<"从"<<start<<"位置开始,按间隔"<<interval<<"出队序号是：";
while(leftNumbers>1)
{
if(children[pos]==1)//没有出队
{
count++;//计数器加1
}
if(count==interval)//到了那个指定的间隔数
{
cout<<(pos+1)<<"\t";//出队序号，序号比位序多1
children[pos]=0;//出队置0
count=0;//重置计数器
leftNumbers--;//队伍中的人数减少1人
}
pos++;//下一个位置1，
if(pos==numbers) pos=0;//下标不能 出界
}
cout<<endl;
for(int i=0;i<numbers;i++)
{
if(children[i]==1)//没有出队的那个人
cout<<(i+1)<<"是胜出者"<<endl;// i+1是胜出者的序号
}
delete []children;//释放申请空间，防止出现内存泄漏
system("pause");
return 0;
}
执行结果
输入用例一：
测试结果如下图所示：输入41，1，3
第31号小孩是胜利者。
输入用例二
输入10，1，3
输出结果如下图所示
第4号小孩儿是胜利者
感谢大家关注，如果想看更多的文章和视频，可关注我的微信公众号，循序渐进C++，可以扫描下面二维码。