约瑟夫问题

文章目录

• 约瑟夫问题
• 一、问题描述
• • 需求分析
• 二、解决方法
• • 1.使用静态循环链表
  • • 2.所有代码
  • 单向循环链表实现
  • • 结构体实现
    • 全部代码
• 总结

一、问题描述

约瑟夫问题的一种描述是：编号为1,2,…,n的n个人按顺时针方向围坐一圈，每人持有一个密码(正整数)。一开始任选一个正整数作为报数上限值m，从第一个人开始。按顺时针方向自1开始顺序报数，报到m时停止报数。报m的人出列，将他的密码作为新的m值，从他在顺时针方向上的下一个人开始重新从1报数，如此下去，直至所有人全部出列为止。试设计程序求出出列顺序

需求分析

1.创建一个存储结构储存相关数据（单向循环列表与顺序结构）。
2.要求输入一个正整数作为报数上限值M。
3.每个人都有一个密码，如果某人被选中，则该人的密码将成为新的M值继续下一轮游戏，直至全部选完。
4.选中的人将会被从存储结构中删除。
5.最终按选出的顺序将每个人的编号打印出来。

二、解决方法

1.使用静态循环链表

结构体定义

#define MaxSize 100
//定义一个结构体，存放人的编号和密码
typedef  struct  node{int data;	//存放数据int pass;	//密码int link;	//下一人的索引
}StaticNode;
//定义一个结构体数组，即静态链表
typedef  struct {StaticNode Nodes[MaxSize];int newptr;
}StaticLinkList;

2.所有代码

判断该人是否会被击杀，击杀需要从该链表去除掉

代码如下（示例）：

#include 
#include #define MaxSize 100
//定义一个结构体，存放人的编号和密码
typedef  struct  node{int data;int pass;int link;
}StaticNode;
//定义一个结构体数组，即静态链表
typedef  struct {StaticNode Nodes[MaxSize];int newptr;
}StaticLinkList;int List_Insert(StaticLinkList *Space,int Slink,int i,int x,int );
void InitSpace(StaticLinkList *Space);
void InitList(StaticLinkList *Space,int Slink);
void init_data(StaticLinkList *Space,int Slink,int people,int *all_pass);
void Show_list(StaticLinkList *Space);
int print_Slist(StaticLinkList *Space,int Slink,int people,int *result,int max);int main(){int people = 0;         //总人数int max = 0;            //第一个密码printf("请输入总人数:\n");scanf("%d",&people);printf("请输入密码上线值:\n");scanf("%d",&max);printf("请输入密码(用空格分开)：\n");int all_pass[people];      //存放所有人的密码for(int i=0;i<people;++i){scanf("%d",&all_pass[i]);if(temp>max){printf("当前密码已经大于最大值，请重新输入\n");scanf("%d",&all_pass[i]);continue;}}int result[people];     //记录弹出的人的序号StaticLinkList p;InitSpace(&p);			//分配空间InitList(&p,0);			//相当于初始化带头节点，init_data(&p,0,people,all_pass);		//初始化编号int s =print_Slist(&p,0,people,result,max);		//获取人的顺序，s是长度，result存储结果for(int i = 0;i<s;i++){printf("%d->",result[i]);}}int print_Slist(StaticLinkList *copySpace,int Slink,int people,int *result,int max){StaticLinkList *Space = copySpace;if(Space->newptr==-1){printf("该链表不存在");exit(0);}int num = 0;    //记录弹出的人数的数量int pass = max;     //取第一个人的最大值int count = 1;while(Space->Nodes[Slink].link){Slink = Space->Nodes[Slink].link;
//        先找到下一个人先提前判断它是否需要被弹出if((count +1)%pass==0) {
//            删除这个元素int copy = Space->Nodes[Slink].link;Space->Nodes[Slink].link = Space->Nodes[copy].link;
//            保存弹出的人的序号和更新密码int temp = Space->Nodes[copy].data;pass = Space->Nodes[copy].pass;Space->Nodes[copy].link = Space->newptr;Space->newptr = copy;result[num] = temp;num++;count = 0;
//            由于当被弹出的人的密码是1时，不能同时弹出两人，所以需要单独考虑if (pass == 1) {
//                静态链表的删除部分int copy = Space->Nodes[Slink].link;Space->Nodes[Slink].link = Space->Nodes[copy].link;int temp1 = Space->Nodes[copy].data;        //先保存杀掉那个人的密码和编号pass = Space->Nodes[copy].pass;Space->Nodes[copy].link = Space->newptr;Space->newptr = copy;result[num] = temp1;num++;}}count++;
//        当这个link等于自身，就只剩一个人了if(Space->Nodes[Slink].link ==Space->Nodes[Space->Nodes[Slink].link].link){result[num++] = Space->Nodes[Slink].data;break;}}return num;
}
int List_Insert(StaticLinkList *Space,int Slink,int i,int x,int pass){int j = 0;int q =Slink;int p;while(q!=-1&&j<i -1){           //找到第i-1个元素q = Space->Nodes[q].link;j++;}if(q ==-1||i<1)return 0;if(Space->newptr!=-1){p = Space->newptr;          //分配结点，Space->newptr = Space->Nodes[Space->newptr].link;}elsereturn 0;
//    尾插法来插入每个人的编号Space->Nodes[p].data = x;Space->Nodes[p].pass = pass;Space->Nodes[p].link = Space->Nodes[q].link;Space->Nodes[q].link = p;}
void InitSpace(StaticLinkList *Space){
//    初始化链表Space->newptr = 0;for(int i = 0;i<MaxSize;i++){Space->Nodes[i].link = i+1;}Space->Nodes[MaxSize-1].link = -1;
}//初始化带头节点的链表
void InitList(StaticLinkList *Space,int Slink){if(Space->newptr!=-1){Slink = Space->newptr;Space->newptr = Space->Nodes[Space->newptr].link;Space->Nodes[Slink].link = -1;}
}
void init_data(StaticLinkList *Space,int Slink,int people,int *all_pass){for(int i = 0;i<people;i++){int j = List_Insert(Space,Slink,i+1,i+1,all_pass[i]);}Space->Nodes[people].link = 1;
//    Show_list(Space);
}
void Show_list(StaticLinkList *Space){if(Space->newptr==-1){return;}int j = 1;int Slink = 0;while(Space->Nodes[Slink].link!=-1){printf("%d",Space->Nodes[Space->Nodes[Slink].link].data);printf("%d",Space->Nodes[Space->Nodes[Slink].link].pass);Slink = Space->Nodes[Slink].link;}
}

单向循环链表实现

结构体实现

//初始化一个结构体来存放编号和密码
typedef struct node{int data;		//数据int password;	//密码struct node *next;	//下一个人
}ListNode,*list;		//头指针

全部代码

#include 
#include //初始化一个结构体来存放编号和密码
typedef struct node{int data;int password;struct node *next;
}ListNode,*list;
//typedef ListNode *ListList;void InitList(list l);
int  print_LiList(list l,int people,int *result,int max);
void createlist(list l,int all_data[],int people);int main() {int people = 0;         //总人数int max = 0;            //第一个密码值ListNode Listdata;printf("请输入总人数:\n");scanf("%d",&people);printf("请输入密码上线值:\n");scanf("%d",&max);printf("请输入密码(用空格分开)：\n");int all_pass[people];       //存放所有人的密码for(int i=0;i<people;++i){int temp = 0;scanf("%d",&temp);if(temp>max){printf("当前密码已经大于最大值，请重新输入\n");scanf("%d",&temp);continue;}all_pass[i] = temp;}int result[people];     //记录弹出的人的序号InitList(&Listdata);     //初始化一个带头结点的链表createlist(&Listdata,all_pass,people);      //把编号和对应密码存放到单链表中int s =print_LiList(&Listdata,people,result,max);       //记录好弹出人的编号和密码for(int i = 0;i<s;i++){printf("%d->",result[i]);}return 0;
}//建立头节点
void InitList(list l){if( l==NULL){printf("申请内存出错");return;}l->next = NULL;
}
//打印单链表中存在的所有元素
int  print_LiList(list l,int people,int *result,int max){printf("打印链表\n");if(l == NULL){printf("链表不存在");return 0;}list s = l;int count = 1;int num = 0;int pass = max;       //取第一个人的密码值while(s){s= s->next;if((count+1) % pass ==0){//    删除并且释放这个元素ListNode *q = s->next;s->next = q->next;int temp = q->data;pass = q->password;free(q);result[num] = temp;num++;count =0;if(pass==1){//删除并且释放这个元素ListNode *q = s->next;s->next = q->next;int temp = q->data;pass = q->password;free(q);result[num] = temp;num++;}}count++;if(s==s->next){result[num++] = s->data;break;}}return num;
}void createlist(list l,int all_data[],int people){
//建立头节点list first = l;int i;ListNode * newnode;     //新生成的节点for(i = 0;i<people;i++){newnode = (ListNode*) malloc(sizeof (ListNode));newnode ->data = i+1;         //生成人数的顺序编号newnode->password = all_data[i];
//        采用尾插法if(i==people - 1){newnode->next = first->next;}else{newnode->next = l->next;}l->next = newnode;l = l->next;}
}

总结

本文采用了两种结构实现，但是本人菜鸡一枚，代码有待改进，要是对你有帮助得到话，希望点个赞，有问题可以在评论区交流。

本文来自互联网用户投稿，文章观点仅代表作者本人，不代表本站立场，不承担相关法律责任。如若转载，请注明出处。 如若内容造成侵权/违法违规/事实不符，请点击【内容举报】进行投诉反馈！