c语言编程Josephus问题

来源：百度知道 编辑：UC知道 时间：2024/05/18 17:56:33
Josephus问题是说，一群小孩围成一圈，任意假定一个数m，从第一个小孩起，顺时针方向数，每数到第m个小孩时，该小孩便离开。小孩不断离开，圈子不断缩小。最后，剩下的一个小孩便是胜利者。究竟胜利者是第几个小孩呢？程序要求输入小孩的个数以及数m的值，输出最后获胜的小孩的编号。（用数组实现）

#include<stdio.h>
#include<conio.h>
main()
{
int *arrChild,iChild,m,iCount,iSkip,iCur;
printf("Please input the number of the children:\n");
scanf("%i",&iChild);
printf("Please input the random number m:\n");
scanf("%i",&m);

if (m>iChild)
m=m%iChild;
arrChild=new int[iChild];
for (int i=0;i<iChild;i++)
arrChild[i]=0;

for (iCount=iChild;iCount>1;iCount--)
{
if(m>iCount)
m=m%iCount;
iCur=0;
for(int i=0;i<iChild;i++)
{
if(arrChild[i]==0)
iCur++;
if (iCur==m)
{
arrChild[i]=1;
break;
}
}
}

for (int i=0;i<iChild;i++)
{
if (arrChild[i]==0)
{
printf("The %i child is the winner.\n",i+1);
break;
}
}

getch();
}