约瑟夫问题求解,玄关%%%
  • 板块灌水区
  • 楼主Aakw_Tea
  • 当前回复2
  • 已保存回复2
  • 发布时间2024/7/10 19:31
  • 上次更新2024/7/10 21:03:17
查看原帖
约瑟夫问题求解,玄关%%%
1211960
Aakw_Tea楼主2024/7/10 19:31

题目描述 求解约瑟夫(Joseph)问题。有n个小孩围成一圈,给他们从1开始依次编号,从编号为1的小孩开始报数,数到第m个小孩出列,然后从出列的下一个小孩重新开始报数,数到第m个小孩又出列,…,如此反复直到所有的小孩全部出列为止,求整个出列序列。 如当n=6,m=5时的出列序列是5,4,6,2,3,1。

1≤n,m≤20

输入 n m的值 输出 出列序列 样例输入 6 5 样例输出 5 4 6 2 3 1

代码如下:

#include <bits/stdc++.h>
using namespace std;
int n,m,nt[25],x;//x为坐标 
int main(){
	cin>>n>>m;
	for(int i=1;i<=n;i++){
		nt[i]=i+m-1;//nt数组表示:地i个数字的下m个坐标位置 
		if(nt[i]>n){//越边界处理 
			nt[i]-=n;
		}
	}
	x=1;
	for(int j=1;j<=n;j++){
		cout<<nt[x];//输出m个后 
		x=nt[x]+1;//坐标移动至m个后的后一个 
		int t=x;
		//出列处理  { 
		for(int i=1;i<=m;i++){//把出列的前m个+1; 
			t--;
			if(nt[t]==-1){//找到了的跳过    标记在33行 
				while(nt[t]>-1){
					t--;
				}
			}
			if(t<=0)//越边界处理 
				t+=n;
			nt[t]++;//++
			if(nt[t]>n){
				nt[t]=1;//nt数组越边界处理
			}
		}
		//  } 
		nt[x]=-1;//找到了的标记一下 
	}
	return 0;
}
2024/7/10 19:31
加载中...