Question

关于Josephus的问题 我那循环总是弄不来 望高手指点

1、 设n个人围坐在一个圆桌周围，现在从第s个人开始报数，数到第m个人，让他出局；然后从出局的下一个人重新开始报数，数到第m个人，再让他出局，……，如此反复直到所有的人全部出局为止。下面要解决的Josephus问题是：对于任意给定的n, s和m，求出这n个人的出局序列。（另有上机条件的同学使用n = 9, s = 1, m = 5，以及n = 9, s = 1, m = 0，或者n = 9, s = 1, m = 10作为输入数据，检查你的程序的正确性和健壮性。）最后分析所完成算法的时间复杂度。
下面是我写的程序：
#include<stdio.h>
#include"malloc.h"
#define MaxSize 50
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList ;
SqList *LA;
void CreateList(SqList * &L,ElemType a[],int n);
void InitList(SqList * &L);
void FindList(SqList * &L,int &n,int &s,int &m);
int DeleteList(SqList * &L,int i,ElemType &e);
void DestoryList(SqList * &L);
int main()
{
int x=9,y=2,z=5;

int a[9];
printf("numbers:\n");
for(int i=0;i<9;i++)
{
scanf("%d",&a[i]);
}
for(i=0;i<9;i++)
{
printf("%d ",a[i]);
}
printf("\n");
InitList(* &LA);
CreateList(* &LA,a,x);
FindList(* &LA,x,y,z);
DestoryList(* &LA);
return 0;
}

void InitList(SqList * &L)
{
L=(SqList *)malloc(sizeof(SqList));
L->length=0;
}
void CreateList(SqList * &L,ElemType a[],int n)
{
L=(SqList *)malloc(sizeof(SqList));
for(int i=0;i<n;i++)
L->data[i]=a[i];
L->length=n;
}
void FindList(SqList * &L,int &n,int &s,int &m)
{
int out;
int i;
if(m<=n)
{
out=L->data[m+s-2];
printf("%d\n",out);
i=m+s-2;
ElemType e=out;
DeleteList(L,i,e);
}
else
{
out=L->data[m-n+s-2];
printf("%d\n",out);
i=m-n+s-2;
ElemType e=out;
DeleteList(L,i,e);

}
int k;
k=i;
for(int j=L->length-1;j>0;j--)
{
if(j-k>m-1)
{
out=L->data[k];
printf("%d",out);
ElemType e=out;
DeleteList(L,k,e);
k=m+s-2;
}
else if(m+k+1-j>j)
{
int b=m-n;
while(b>j)
{
b=b-j;
}
int u=b;
if((j-k)==0)
{
out=L->data[u-1];
printf("%d",out);
ElemType e=out;
DeleteList(L,k,e);
}

else
{
out=L->data[k+u-1];
printf("%d",out);
k=k+u-1;
ElemType e=out;
DeleteList(L,k,e);
}
}

else
{
out=L->data[m-(j-k)-1];
printf("%d",out);
k=m-(j-k)-1;
ElemType e=out;
DeleteList(L,k,e);
}
k=m-(j-k)-1;

}
}

void DestoryList(SqList * &L)
{
free(L);
}
int DeleteList(SqList * &L,int i,ElemType &e)
{
int j;
if(i<1||i>L->length)
return 0;
i--;
e=L->data[i];
for(j=i;j<L->length-1;j++)
L->data[j]=L->data[j+1];
L->length--;
return 1;
}
程序没有语法错误 但是运行有错 应该是算法有问题 那个循环我始终弄不清楚 希望高手指点指点啊 真心感谢

Answer 1

#include<stdio.h>
#include"malloc.h"
#define MaxSize 50
typedef int ElemType;
typedef struct
{
ElemType data[MaxSize];
int length;
}SqList ;
SqList *LA;
void CreateList(SqList * &L,ElemType a[],int n);
void InitList(SqList * &L);
void FindList(SqList * &L,int &n,int &s,int &m);
int DeleteList(SqList * &L,int i,ElemType &e);
void DestoryList(SqList * &L);
int main()
{
int x=9,y=2,z=5;

int a[9];
printf("numbers:\n");
for(int i=0;i<9;i++)
{
scanf("%d",&a[i]);
}
for(int i=0;i<9;i++)
{
printf("%d ",a[i]);
}
printf("\n");
InitList(* &LA);
CreateList(* &LA,a,x);
FindList(* &LA,x,y,z);
DestoryList(* &LA);
return 0;
}

void InitList(SqList * &L)
{
L=(SqList *)malloc(sizeof(SqList));
L->length=0;
}
void CreateList(SqList * &L,ElemType a[],int n)
{
L=(SqList *)malloc(sizeof(SqList));
for(int i=0;i<n;i++)
L->data[i]=a[i];
L->length=n;
}
void FindList(SqList * &L,int &n,int &s,int &m)
{
int out;
int i;
if(m<=n-s)///////
{
out=L->data[m+s-1];
printf("%d\n",out);
i=m+s-1;
ElemType e=out;
DeleteList(L,i,e);
}
else
{
int index =(m+s)%n;
if (index == 0)
{
out=L->data[n-1];
}
else
out=L->data[index -1];
printf("%d\n",out);
i = index - 1;
ElemType e=out;
DeleteList(L,i,e);

}
int k = i;
for(int j = L->length-1; j>0; j--)
{
int index = (k + m +1)% j;
if (index == 0)
{
out=L->data[j-1];
k = j-1;
}
else
{
out=L->data[index -1];
k = index -1;
}
printf("%d\n",out);
ElemType e=out;
DeleteList(L,k,e);
/*if(j-k>m-1)
{
out=L->data[k];
printf("%d\n",out);
ElemType e=out;
DeleteList(L,k,e);
k=m+s-2;
}
else if(m+k+1-j>j)
{
int b=m-n;
while(b>j)
{
b=b-j;
}
int u=b;
if((j-k)==0)
{
out=L->data[u-1];
printf("%d\n",out);
ElemType e=out;
DeleteList(L,k,e);
}

else
{
out=L->data[k+u-1];
printf("%d\n",out);
k=k+u-1;
ElemType e=out;
DeleteList(L,k,e);
}
}

else
{
out=L->data[m-(j-k)-1];
printf("%d\n",out);
k=m-(j-k)-1;
ElemType e=out;
DeleteList(L,k,e);
}
k=m-(j-k)-1;*/

}
}

void DestoryList(SqList * &L)
{
free(L);
}
int DeleteList(SqList * &L,int i,ElemType &e)
{
int j;
if(i<1||i>L->length)
return 0;
e=L->data[i];
for(j=i;j<=L->length-1;j++)////////
L->data[j]=L->data[j+1];
L->length--;
return 1;
}

我想说你的算法，有点问题，试试我这个行不行