|
发表于 2007-12-17 17:23:44
|
显示全部楼层
约瑟夫环问题求解算法C语言源代码
.约瑟夫算法:n个人围成一圈,每人有一个各不相同的编号,选择一个人作为起点,然后顺时针从1到k数数,每数到k的人退出圈子,圈子缩小,然后从下一个人继续从1到k数数,重复上面过程。求最后推出圈子的那个人原来的编号。
思路:按照上面的算法让人退出圈子,直到有n-1个人推出圈子,然后得到最后一个退出圈子的人的编号。
程序:坐成一圈的人的编号不需要按序排列
#define N 100
int yuesefu1(int data[],int sum,int k)
{
int i=0,j=0,count=0;
while(count<sum-1)
{
if(data!=0)/*当前人在圈子里*/
j++;
if(j==k)/*若该人应该退出圈子*/
{
data=0;/*0表示不在圈子里*/
count++;/*退出的人数加1*/
j=0;/*重新数数*/
}
i++;/*判断下一个人*/
if(i==sum)/*围成一圈*/
i=0;
}
for(i=0;i<sum;i++)
if(data!=0)
return data;/*返回最后一个人的编号*/
}
void main()
{
int data[N];
int i,j,total,k;
printf("\nPlease input the number of every people.\n");
for(i=0;i<N;)/*为圈子里的人安排编号*/
{
int input;
scanf("%d",&input);
if(input==0)
break;/*0表示输入结束*/
for(j=0;j<i;j++)/*检查编号是否有重复*/
if(data[j]==input)
break;
if(j>=i&&input>0)/*无重复,记录编号,继续输入*/
{
data=input;
i++;
}
else
printf("\nData error.Re-input:");
}
total=i;
printf("\nYou have input:\n");
for(i=0;i<total;i++)
{
if(i%10==0)
printf("\n");
printf("%4d",data);
}
printf("\nPlease input a number to count:");
scanf("%d",&k);
printf("\nThe last one''''s number is %d",yuesefu1(data,total,k));
} |
|