关于Josephus的问题 我那循环总是弄不来 望高手指点
1、设n个人围坐在一个圆桌周围,现在从第s个人开始报数,数到第m个人,让他出局;然后从出局的下一个人重新开始报数,数到第m个人,再让他出局,……,如此反复直到所有的人全部...
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;
}
程序没有语法错误 但是运行有错 应该是算法有问题 那个循环我始终弄不清楚 希望高手指点指点啊 真心感谢 展开
下面是我写的程序:
#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;
}
程序没有语法错误 但是运行有错 应该是算法有问题 那个循环我始终弄不清楚 希望高手指点指点啊 真心感谢 展开
展开全部
#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;
}
我想说你的算法,有点问题,试试我这个行不行
#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;
}
我想说你的算法,有点问题,试试我这个行不行
本回答被提问者采纳
已赞过
已踩过<
评论
收起
你对这个回答的评价是?
推荐律师服务:
若未解决您的问题,请您详细描述您的问题,通过百度律临进行免费专业咨询