【数据结构代码】 线性表 相关运用
程序员文章站
2024-01-03 12:37:58
线性表代码约瑟夫环的问题双向链表循环链表公式约瑟夫环的问题问题描述:编号是1,2,……,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。设计一个程序来求出出列顺序。双向链表#include using namespace std;//初始...
约瑟夫环的问题
问题描述:编号是1,2,……,n的n个人按照顺时针方向围坐一圈,每个人只有一个密码(正整数)。一开始任选一个正整数作为报数上限值m,从第一个仍开始顺时针方向自1开始顺序报数,报到m时停止报数。报m的人出列,将他的密码作为新的m值,从他在顺时针方向的下一个人开始重新从1报数,如此下去,直到所有人全部出列为止。设计一个程序来求出出列顺序。
双向链表
#include <iostream>
using namespace std;
//初始化
struct LNode{
int value;
LNode *prior;
LNode *next;
};
//main函数
int main(){
cout<<"一共有几个小朋友参加游戏:"<<endl;
int num_of_people;
cin>>num_of_people;
//初始化一个头节点
LNode *nowNode=new LNode;
nowNode->value=1;
//建立双向链表,包含链表的插入
for(int i=2;i<=num_of_people;i++){
nowNode->next=new LNode();
nowNode->next->prior=nowNode;
nowNode=nowNode->next;
nowNode->prior->next=nowNode;
nowNode->value=i;
}
//创建完双向链表后,将首位连接起来,建立成一个环状。
nowNode->next->prior=nowNode;
nowNode=nowNode->next;
//输入第几个小孩在应该出去
int m;
cout<<"第几个小朋友退出:"<<endl;
cin>>m;
//开始循环,包含链表的删除
LNode *temp=new LNode;//建立临时节点
int count=1;
while(nowNode->next!=nowNode){
if(count==m){
cout<<nowNode->value<<" ";
//删除
nowNode->prior->next=nowNode->next;
nowNode->next->prior=nowNode->prior;
temp=nowNode->next;
delete nowNode;
nowNode=temp;
count=1;
}
else{
nowNode=nowNode->next;
count++;
}
}
cout<<nowNode->value<<"幸存"<<endl;
delete(nowNode);
}
循环链表
#include <iostream>
using namespace std;
typedef struct CLinkList{
int num;
struct CLinkList *next;
}node;
int main(){
//建立循环链表、
node *L,*r,*s;//r是尾指针
L=new node;
r=L;
int i;
int n;
cin>>n;
int m;
cin>>m;
//利用后插法来建立链表
for(i=1;i<=n;i++){
s=new node;
s->num=i;
r->next=s;
r=s;
}
r->next=L->next;
node *p;
p=L->next;
delete L;
//解决约瑟夫环的问题
while(p->next!=p){
for(int i=1;i<m-1;i++){
//每数k个人后死亡一人
p=p->next;//向后推进
}
cout<<p->next->num<<"->";//将该点删去
p->next=p->next->next;
p=p->next;
}
cout<<p->num<<endl;
return 0;
}
公式
#include <iostream>
using namespace std;
/* run this program using the console pauser or add your own getch, system("pause") or input loop */
int Joseph(int n,int m){
if(n==1){
return 0;//从这里返回,从0开始,只有一个元素就是剩余的元素0
}
else{
return (Joseph(n-1,m)+m)%n;//n是总共多少个数
}
}
int main(){
int a,b;
//递归求最后一个的编号
cin>>a;
cin>>b;
//使用从正向思考
cout<<"最后一个人是:"<<Joseph(a,b)+1<<endl;
int result=b-1;
//第一个自杀的人为b-1
cout<<b;
//每次自杀的都是b-1号,但是不同的b-1号换算到最初的序号所需要的次数是不同的
//外循环是循环不同的换算次数
for(int i=a;i>=2;i--){
result=b-1;
//内循环是开始运算
for(int j=i;j<=a;j++){
result=(result+b)%j;
}
cout<<"->"<<result+1;//从0开始变1开始,所以加1
}
return 0;
}
本文地址:https://blog.csdn.net/qq_44705973/article/details/107892393