题目

How to solve 约瑟夫问题 by C++ ?
约瑟夫问题：设编号为1,2,…,n的n（n>0）个人按顺时针方向围坐一圈,每人持有一正整数密码.开始时任选一个正整数作为报数上限值m,从第一个人开始顺时针方向自1起顺序报数,报到m时停止报数,报m的人出列,将他的密码作为新的m值,从他在顺时针方向上的下一个人起重新从1报数.如此下去,直到所有人全部出列为止.令n最大值取30.要求设计一个程序模拟此过程,求出出列编号序列（采用循环单链表结构）.

提问时间：2021-03-18

答案

约瑟夫(josephus)环是这样的：假设有n个小孩坐成一个环,假如从第一个小孩开始数,如果数到m个小孩,则该小该离开,问最后留下的小孩是第几个小孩?例如：总共有6个小孩,围成一圈,从第一个小孩开始,每次数2个小孩,则游戏情况如下：
小孩序号：1,2,3,4,5,6
离开小孩序号：2,4,6,3,1
最后获胜小孩序号：5
这样的问题,我可以先考虑输入的内容有哪些?输出内容有哪些?
要求用户输入的内容有：
1、是小孩的个数,也就是n的值；
2、是离开小孩的间隔是多少?也就是m的值.
3、所有小孩的序号要求存在数组或者链表中,所以需要定义一个指针,这里我们用数组来存放小孩的序号.
而要求输出的内容是：
1、离开小孩的序号；
2、最后留下小孩的序号；
所以,根据上面分析输入输出参数,我们考虑离开小孩的序号可以直接输出,这样可以使函数的复杂性.那么函数定义如下：
//输入参数：
//Childs为指向一个整形指针,指向保存小孩数组的首地址；
//n为小孩的个数；
//m为数小孩的个数；
int Josephus(int *Child,int n,int m)
{
int i=-1,j=0,k=1;
//开始数小孩,只到留下一个小孩
while(1)
{
//数m个小孩
for(j=0;j