[数据结构]约瑟夫环问题-白红宇

1. 约瑟夫环问题

约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3…n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。

通过顺序表来解决.

2.顺序基本操作

2.1 顺序表定义

#define TRUE 1#define FALSE 0#define SPECIAL -1#define MAXNUM 30#include 
     
      #include 
      
       /*  线性表的定义*/typedef int DataType;struct Seqlist{    int length; // 存在限行表中元素的个数    DataType element[MAXNUM];};typedef struct Seqlist Seqlist,*PSeqList;//创建顺序表PSeqList craeteNullList_seq(void);//判断顺序表是否为空int isNullList_seq(PSeqList palist);//在palist所指顺序表中下标为p的元素之前插入元素xint insert_seq(PSeqList palist,int p,DataType x);//删除palist所指顺序表下标为p的元素int delete_seq(PSeqList palist,int p);//求x在palist所指顺序表中的下标.int locate_seq(PSeqList palist, DataType x);//求palist所指顺序表中下标为p的元素值.int retrieve_seq(PSeqList palist,int p);

2.2 创建顺序表

PSeqList craeteNullList_seq(){    PSeqList palist=(PSeqList)malloc(sizeof(struct Seqlist));    if (palist)    {        palist->length=0;    }else{        printf("存储空间分配失败\n");    }    return palist;}

2.3判断顺序表是否为空

int isNullList_seq(PSeqList palist){    if (palist->length>=1)    {        printf("线性表不为空\n");        return TRUE;    }else if(palist->length==0){        printf("线性表为空\n");        return FALSE;    }    return FALSE;}

2.4 插入操作

int insert_seq(PSeqList palist,int p,DataType x){    //1.判断顺序表是否溢出    if (palist->length>=MAXNUM)    {        printf("线性表溢出\n");        return FALSE;    }    //2.不存在下标为p的元素    if (p<0||p>palist->length)    {        printf("不存在下标为p的元素的元素\n");        return FALSE;    }    int q;    for(q=palist->length-1;q>p;q--){      palist->element[q+1]=palist->element[q];    }    palist->element[p]=x;    palist->length++;    return TRUE;}

2.5 删除操作

int delete_seq(PSeqList palist,int p){     if (p<0||p>palist->length)     {         printf("不存在为置为p的元素,删除失败\n");         return FALSE;     }     int q;     for (q=p; q< palist->length; q++)     {        palist->element[q]=palist->element[q+1];     }     palist->length=palist->length-1;     return TRUE;}

2.6查询指定元素操作

int retrieve_seq(PSeqList palist,int p){    if (p<0||p>=palist->length)    {        printf("不存在位置为%d的元素\n",p);        return FALSE;    }    return palist->element[p];}

2.7查询指定位置操作

int locate_seq(PSeqList palist,int x){    int loc;    if (palist->length==0)    {        printf("链表为空,查找位置失败\n");        return FALSE;    }    for (int i = 0; i < palist->length; ++i)    {        if (palist->element[i]==x)        {            loc=i;            break;        }    }    return loc;}

3.求解约瑟夫环

3.1 初始化顺序表

//初始化约瑟夫环 int initJlist(PSeqList palist,int n){  //n为人的个数    if(palist==NULL) return FALSE;    if(n<1||n>MAXNUM){        printf("人的个数超过顺序表的最大长度，修改MAXNUM的值.\n");        return FALSE;    }    for(int i=0;i

3.2求解约瑟夫环

int josephus_seq(int n,int s,int m){     int s1=s-1,i,w; //s=2 s1=1 m=2     PSeqList list=craeteNullList_seq();     if (list==NULL)     {        printf("创建列表失败.\n");     }     if(initJlist(list,n)==FALSE){        printf("初始化约瑟夫环失败\n");            return FALSE;     }      printf("list长度:%d\n",list->length);      for (i = list->length; i>0; i--)      {          s1=(s1+m-1)%i;  //s1=1+2-1          printf("%d\t",retrieve_seq(list,s1));          delete_seq(list,s1);      }     printf("\n");     free(list);     return TRUE;}

3.4 输入输出函数

输出一个顺序表的所有元素

void outputList(PSeqList palist){    for (int i = 0; i < palist->length; i++)    {        printf("%d\t",palist->element[i]);    }    printf("\n");}

n，s，m的输入

void inputnsm(int *np,int *sp,int *mp){    printf("请输入n：\n");    scanf("%d",np);    printf("请输入s：\n");    scanf("%d",sp);    printf("请输入m：\n");    scanf("%d",mp);}

3.5 测试

int main(){    // 初始化    PSeqList list1=craeteNullList_seq();    //赋值    for(int i=0;i<10;i++){        insert_seq(list1,i,i+1);    }    //输出    outputList(list1);    int a;    printf("输入要删除元素的位置：\n");    scanf("%d",&a);    delete_seq(list1,a);    outputList(list1);    printf("要查找元素的位置：\n");    scanf("%d",&a);    printf("%d\n",retrieve_seq(list1,a));     int n,s,m;    inputnsm(&n,&s,&m);    josephus_seq(n,s,m);    return 0;}

这里写图片描述