Question

C语言编程Josephus问题

Josephus问题是说，一群小孩围成一圈，任意假定一个数m，从第一个小孩起，顺时针方向数，每数到第m个小孩时，该小孩便离开。小孩不断离开，圈子不断缩小。最后，剩下的一个小孩便是胜利者。究竟胜利者是第几个小孩呢？程序要求输入小孩的个数以及数m的值，输出最后获胜的小孩的编号。（用数组实现）

Answer 1

/*这个答案我不是已经给过了吗?
好象被删掉了,再给你发一次吧,补充一下,应作者要求,在这里解释一下代码的意思,我晕死.*/
#include <stdio.h>
#include <stdlib.h>
#define max 1024
void findout(int n,int m)//这函数的作用是找出最后剩下的小孩
{
int buf[max];//max上面有定义,为1024,大小你看实际需要改
int dex=0;
int in=0;
for(int i=1;i<=n;i++)//n是小孩的个数
{
buf[i]=i;//给小孩赋号码,第几个小孩,号码就为几
}
while(n>in+1)//剩下小孩个数大于1的时候才执行
{
for(i=1;i<=n;i++)//遍历所以小孩
{
if(buf[i]!=0)//小孩号码不为0的时候
{
dex++;
if(dex==m)//若是数到m,
{
buf[i]=0;//则把小孩号码改成0
in++;//被排除的小孩个数加1
dex=0;//判断值清0,从新开始找
}
}
}
}//while.退出的时候只剩下一个小孩
for(i=1;i<=n;i++)
if(buf[i]!=0)
printf("最后的小孩号码为:%d\n",buf[i]);//打印小孩的号码

}
void main()//这个函数够简单吧,这个自己看,我累死了
{
int n,m;
char c='y';
printf("#############测试开始了#############\n");
printf("\n");
while(c=='y')
{
printf("请输入小孩的个数：");
scanf("%d",&n);
printf("请输入m的值？：");
scanf("%d",&m);
if((n>0)&&(m>0))
{
findout(n,m);
}
else
{
printf("输入有误\n");
}
printf("继续吗?y or n\n");
getchar();
c=getchar();
}
printf("\n");
printf("#############测试结束了############\n");
}

Answer 2

/*这个答案我不是已经给过了吗?
好象被删掉了,再给你发一次吧,补充一下,应作者要求,在这里解释一下代码的意思,我晕死.*/
#include
#include
#define
max
1024
void
findout(int
n,int
m)//这函数的作用是找出最后剩下的小孩
{
int
buf[max];//max上面有定义,为1024,大小你看实际需要改
int
dex=0;
int
in=0;
for(int
i=1;i<=n;i++)//n是小孩的个数
{
buf[i]=i;//给小孩赋号码,第几个小孩,号码就为几
}
while(n>in+1)//剩下小孩个数大于1的时候才执行
{
for(i=1;i<=n;i++)//遍历所以小孩
{
if(buf[i]!=0)//小孩号码不为0的时候
{
dex++;
if(dex==m)//若是数到m,
{
buf[i]=0;//则把小孩号码改成0
in++;//被排除的小孩个数加1
dex=0;//判断值清0,从新开始找
}
}
}
}//while.退出的时候只剩下一个小孩
for(i=1;i<=n;i++)
if(buf[i]!=0)
printf("最后的小孩号码为:%d\n",buf[i]);//打印小孩的号码
}
void
main()//这个函数够简单吧,这个自己看,我累死了
{
int
n,m;
char
c='y';
printf("#############测试开始了#############\n");
printf("\n");
while(c=='y')
{
printf("请输入小孩的个数：");
scanf("%d",&n);
printf("请输入m的值？：");
scanf("%d",&m);
if((n>0)&&(m>0))
{
findout(n,m);
}
else
{
printf("输入有误\n");
}
printf("继续吗?y
or
n\n");
getchar();
c=getchar();
}
printf("\n");
printf("#############测试结束了############\n");
}

Answer 3

int main()
{
int children, m, winner, i;
int *circle, *p;

/* 从用户得到输入，人数和m值 */
printf("Input children number,m value:");
scanf("%d,%d", children, m);

/* 创建数组，并初始化为1，1表示这个位置有人 */
circle = malloc(sizeof(int) * children);
for (p=circle; p - circle <= m; p++) {
*p = 1;
}

p = circle;
count = children; /* count记录目前还剩下的人 */
do {
/* 如果当前只剩一个人，则这个人就是获胜者，算法结束 */
if (count == 1) {
winner = p - circle;
break;
}
/* 否则把这个位置设置为无人，算法继续 */
*p = 0;
count--;

/* 在剩下的人中数出第m个人 */
for (i = 0; i < m; i++) {
/* 找到下一个有人的位置 */
while (*((((++p) - circle) mod children) + circle)!= 1) ;
}
} while(1);

printf("The winner is %d \n", winner);
free(circle);
return 0;
}

没有上机测试，你自己调一下吧。时间比较紧，有些地方写的粗糙，比如对用户输入要做一下合法性判断。

Answer 4

#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();
}