C++的编写约瑟夫(josephus)环函数

约瑟夫(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

{

i=(i+1)%n; //取下标加1的模，当i的值在0到n-1之间循环

if(Child[i]!=-1) //小孩在环中则数数有效；

j++;

}

if(k==n) //假如k==n则表示，此时数组中只留下一个小孩，

break; //序号为Child[i]中的值，跳出循环;

cout<

Child[i]=-1; //离开的小孩用-1作标记

k=k+1;

}

cout<

return(Child[i]); //返回最获胜小孩的序号

}

完整的程序，在VC6中调试通过。

//-----------------------------------------------------------

#include

int Josephus(int *Child,int n,int m);

void main()

{

int *allChild,j,k,l;

cin>>j>>k;

if((allChild= new int[j])!=NULL)

{

for(l=0;l

{

cout<

allChild[l]=l+1;

}

cout<

cout<

}

}

int Josephus(int *Child,int n,int m)

{

int i=-1,j=0,k=1;

while(1)

{

for(j=0;j

{

i=(i+1)%n;

if(Child[i]!=-1)

j++;

}

if(k==n)

break;

cout<

Child[i]=-1;

k=k+1;

}

cout<

return(Child[i]);

}