这是本人顺序表解决约瑟夫环问题,里面有问题,但不知道怎么改,求大神帮忙,谢谢
约瑟夫环(Josephus)问题的求解具体描述是:设有编号为1,2,……,n的n(n>0)个人围成一个圈,从第K个人开始报数,报到m时停止报数,报m的人出圈,再从他的下一个人起重新报数,报到m时停止报数,报m的出圈,……,如此下去,直到所有人全部出圈为止。当任意给定n和m后,设计算法求n个人出圈的次序。
请根据以上描述,选择合适的存储结构,完成约瑟夫环的求解。请打印出圈人的序号。怎么改这个呢,谢谢!
#include<stdio.h>
#define MaxSize 100
typedef int DataType;
#include"SeqLin.h"
void main()
{
SeqList mylist;
int i,j,m,n,k,x;
ListInitiate(&mylist);
printf("请输入总共有几个人:");
scanf("%d",&n);
printf("请输入从第几个人开始:");
scanf("%d",&k);
printf("请输入数到几个人出来:");
scanf("%d",&m);
for(i=0;i<n;i++)
ListInsert(&mylist,i,i+1);
for(i=0;i<n;i++)
{
printf("%d ",mylist.list[i]);
}
printf("\n");
printf("输出出列顺序:");
j=0;
for(i=k-1;mylist.size>1;i++)
{
j++;
if(j==m)
{
x=mylist.list[i];
ListDelete(&mylist,x);
printf("%d ",x);
j=0;
i--;
}
if(i==mylist.size)
i=0;
}
printf("\n");
printf("请输入剩下最后的那一位人:");
for(i=0;i<mylist.size;i++)
printf("%d",mylist.list[0]);
printf("\n");
}
头文件如下:
typedef struct
{
DataType list[MaxSize];
int size;
} SeqList;
void ListInitiate(SeqList *L) /*初始化顺序表L*/
{
L->size = 0; /*定义初始数据元素个数*/
}
int ListInsert(SeqList *L, int i, DataType x)
/*在顺序表L的位置i(0 ≤ i ≤ size)前插入数据元素值x*/
/*插入成功返回1,插入失败返回0*/
{
int j;
if(L->size >= MaxSize)
{
printf("顺序表已满无法插入! \n");
return 0;
}
else if(i < 0 || i > L->size )
{
printf("参数i不合法! \n");
return 0;
}
else
{
for(j = L->size; j > i; j--) L->list[j] = L->list[j-1]; /*为插入做准备*/
L->list[i] = x; /*插入*/
L->size ++; /*元素个数加1*/
return 1;
}
}
int ListDelete(SeqList *L,DataType x)
{
int i,j;
for(i=0;i<L->size;i++)
if(x == L->list[i]) break;
if(i==L->size) return 0;
else
{
for(j=i;j<L->size-1;j++)
L->list[j]=L->list[j+1];
L->size--;
return 1;
}
}
[ 本帖最后由 巅峰对决zz 于 2014-10-15 00:01 编辑 ]