约瑟夫问题

时间:2022-02-27 01:20:24

P1996 约瑟夫问题 - 洛谷 | 计算机科学教育新生态 (luogu.com.cn) 

 

题目描述

n 个人围成一圈,从第一个人开始报数,数到 m 的人出列,再由下一个人重新从 1开始报数,数到 m 的人再出圈,依次类推,直到所有的人都出圈,请输出依次出圈人的编号。

注意:本题和《深入浅出-基础篇》上例题的表述稍有不同。书上表述是给出淘汰 n−1 名小朋友,而该题是全部出圈。

输入格式

输入两个整数 n,m。

输出格式

输出一行 n 个整数,按顺序输出每个出圈人的编号。

输入输出样例

输入 

10 3

输出 

3 6 9 2 7 1 8 5 10 4

说明/提示

1≤m,n≤100

//下面四篇博客和此题有一定联系。

约瑟夫环(分数10)_星河欲转。的博客-CSDN博客

约瑟夫环。_星河欲转。的博客-CSDN博客

猴子选大王_猴子选大王 go_星河欲转。的博客-CSDN博客

猴子选大王[加强版]_星河欲转。的博客-CSDN博客

//下面为大家提供六种解决办法,除第一种外,其他都参考自罗勇军《算法竞赛》一书。

//总的来说,此题考的是模拟,第一种方法比较简单易理解,其他的采用了链表知识,可以在草稿纸上推演一下过程就能更好的理解。

#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m,i,x=0,y=0;
	map<int,int>a;//可以用数组,不过记得初始化。
	cin>>n>>m;
	 while(y!=n){
	 	for(i=1;i<=n;i++){
	 		if(a[i]==0){
	 			x++;
			 }
			 	if(x==m){
	 			x=0;
                if(y)cout<<" ";
                cout<<i;
	 			a[i]=1;y++;
			 }
		 }
	 }
	return 0;
}

//动态链表 

#include<bits/stdc++.h>
using namespace std;
struct node{//定义链表节点 
	int data;//节点的值 
	node *next;//单向链表,只有一个next指针 
};
int main(){
	 int n,m;
	 cin>>n>>m;
	 node *head,*p,*now,*prev;//定义变量 
	 head=new node;head->data=1;head->next=NULL;//分配第1个节点,数据置为1
	 now=head;//当前指针是头
	 for(int i=2;i<=n;i++){
	 	p=new node;p->data=i;p->next=NULL;//p是新节点
	 	now->next=p;//把申请的新节点连到前面的链表上
	 	now=p;//尾针后移一个
	 }
	 now->next=head;//尾指针指向头:循环链表建立完成
//以上是建立链表,下面是此题的逻辑和流程,后面4种代码与下面的逻辑流程完全一致。
	 now=head,prev=head;//从第1个开始数
	 while((n--)>1){
	 	for(int i=1;i<m;i++){//数到m停下
	 		prev=now;//记录上一个位置,用于下面跳过第m个节点
	 		now=now->next;
		 } 
		 printf("%d ",now->data);//输出第m个节点
		 prev->next=now->next;//跳过这个节点
		 delete now;//释放这个节点
		 now=prev->next;//新的一轮
	 }
	 printf("%d",now->data);//打印最后一个节点
	 delete now;//释放最后一个节点
	return 0;
}

 //用结构体数组实现单向静态链表

#include<bits/stdc++.h>
using namespace std;
const int N=105;//定义静态链表的空间大小
struct node{//单向链表
	int id,nextid;//单向指针
	//int data;//如有必要,定义一个有意义的数据
}nodes[N];//定义在全局的静态分配
int main(){
	int n,m;
	cin>>n>>m;
	nodes[0].nextid=1;
	for(int i=1;i<=n;i++){
		nodes[i].id=i;nodes[i].nextid=i+1;
	}
	nodes[n].nextid=1;//循环链表:尾针向头
	int now=1,prev=1;//从第1个节点开始
	while((n--)>1){
		for(int i=1;i<m;i++){//数到m停下
			prev=now;now=nodes[now].nextid;
		}
		printf("%d ",nodes[now].id);//打印
		nodes[prev].nextid=nodes[now].nextid;//跳过now节点,即删除
		now=nodes[prev].nextid;//新的now
	}
	printf("%d",nodes[now].nextid);//打印最后一个节点
	return 0;
} 

//用结构体数组实现双向静态链表 

#include<bits/stdc++.h>
using namespace std;
const int N=105;
struct node{//双向链表
	int id;//节点编号
	//int data;
	int preid,nextid;//前后节点
}nodes[N];
int main(){
	int n,m;
	cin>>n>>m;
	nodes[0].nextid=1;
	for(int i=1;i<=n;i++){//建立链表
		nodes[i].id=i;
		nodes[i].preid=i-1;//前节点
		nodes[i].nextid=i+1; //后节点
	}
	nodes[n].nextid=1;//循环链表:尾针向头
	nodes[1].preid=n;//循环链表:头指向尾
	int now=1;//从第1个节点开始
	while((n--)>1){
		for(int i=1;i<m;i++)now=nodes[now].nextid;//数到m停下
		printf("%d ",nodes[now].id);//打印
		int prev=nodes[now].preid,next=nodes[now].nextid;
		nodes[prev].nextid=nodes[now].nextid;//删除now
		nodes[next].preid=nodes[now].preid;//新的开始
		now=next;
	}
	printf("%d",nodes[now].nextid);//打印
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
int nodes[150];
int main(){
	int n,m;
	cin>>n>>m;
	for(int i=1;i<=n-1;i++)nodes[i]=i+1;//下一个节点
	nodes[n]=1;//循环链表:尾指向头
	int now=1,prev=1;//从第1个节点开始
	while((n--)>1){
		for(int i=1;i<m;i++){//数到m停下
			prev=now;now=nodes[now];//下一个节点
		}
		printf("%d ",now);
		nodes[prev]=nodes[now];//跳过now节点
		now=nodes[prev];//新的now节点
	}
		printf("%d ",now);
	return 0;
}
#include<bits/stdc++.h>
using namespace std;
int main(){
	int n,m;
	cin>>n>>m;
	list<int>node;
	for(int i=1;i<=n;i++)node.push_back(i);//建立链表
	list<int>::iterator it=node.begin();
	while((n--)>1){//list的大小由STL自己管理
		for(int i=1;i<m;i++){//数到m
			it++;
			if(it==node.end())it=node.begin();//循环:到末尾再回头
		}
		cout<<*it<<' ';
		list<int>::iterator next=++it;
		if(next==node.end())next=node.begin();//循环链表
		node.erase(--it);//删除这个节点,node.size()自动减1
		it=next;
	}
	cout<<*it;
	return 0; 
}