047题-[编程入门||数据结构入门]报数问题-题解(C/C++代码)约瑟夫环问题详解，最短代码，循环链表/队列标准，公式推导On实现

10293 阅读 27 评论 1 点赞

首先，该问题就是典型的约瑟夫环问题
# 什么是约瑟夫环问题？
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。通常解决这类问题时我们把编号从0~n-1，最后 [1]  结果+1即为原问题的解。
（华丽的分割线）
------------------------------------------------
下面我们来解决这个问题，我们先建立约瑟夫环的一个模型，如下图所示
![](/image_editor_upload/20190612034129_17534.jpg)
就是如上这么个模型，理解起来也很简单，但对于新手来说，将其变成代码才是比较复杂的，下面先贴上我写的模拟最短代码，带有详细的注释
```cpp
#include<bits/stdc++.h> 
using namespace std;
int main()
{
    int n,m,s=0;scanf("%d",&n);
    bool visit[200]={0};//visit赋初始值
    for(int k=0;k<n;k++)
	{//总共要出队n次
        for(int i=0;i<3;i++){if(++s>n)s=1;if(visit[s])i--;}//类似取模，而因为序列是从1开始的，所以不取模，加判断；若visit过，则i--，使其继续循环
        visit[s]=true;//输出，记录已出队
    }
    printf("%d ",s);
    return 0;
}
```
简单可靠！！！
就是不停的遍历模拟的过程，注意判重问题，**防止重复遍历**
## 下面实现比较容易理解的方法，循环链表
虽然有些复杂，但这就是题目希望我们去做的意思
```cpp
#include<bits/stdc++.h>
    using namespace std;
    struct peo
    {
        int ID;                                    //编号
        peo *next = NULL, *front = NULL;
    }n[100];
    void _cut(peo *num)
    {
        num = num->front;
        num->next = num->next->next;
        num = num->next;
        num->front = num->front->front;
    }
    int main()
    {
    	int sum=0;//记录当前出队人数 
        int tot, outNum, nowNum = 1;
        peo *now = &n[0];            //指向目前报数的人的指针
        cin >> tot;        //数据读入
        for (int i = 1; i < tot - 1; i++) 
		{ 
		   n[i].front = &n[i - 1]; n[i].next = &n[i + 1]; n[i].ID = i + 1; 
		}
        n[0].front = &n[tot - 1]; n[0].next = &n[1]; n[tot - 1].front = &n[tot - 2]; n[tot - 1].next = &n[0];
        n[0].ID = 1; n[tot - 1].ID = tot;
        //初始化链表
        while (tot > 0)
        {
            if (nowNum == 3)
            {
				if(tot==1) 
				{
					cout<<now->ID;//输出最后一个人 
				 } 
                //cout << now->ID << " "; 这是输出当前的 
                _cut(now);                    //出局
                nowNum = 1;                    //初始化数字
                tot--;                        //总人数-1
                now = now->next;            //下一个人
            }
            else
            {
                nowNum++;                    //数字+1
                now = now->next;            //下一个人
            }
        }
        return 0;
    }
```
下面再实现一种队列实现的方式，类似第一种模拟.
用了STL内封装的queue队列(不想手写队列，太懒了)
```cpp
#include<bits/stdc++.h>
    using namespace std;
    int main()
    {
        int tot, outNum, nowNum = 1;
        queue<int> q;
        cin >> tot;                        //读取数据
        for (int i = 1; i <= tot; i++)q.push(i);    //初始化队列
        while (!q.empty())                    //在队列不为空时继续模拟
        {
            if (nowNum == 3)
            {
            	if(q.size()==1) 
                cout << q.front() << " ";    //打印最后一个人的编号
                q.pop();                    //出局
                nowNum = 1;                    //初始化现在的数字
            }
            else
            {
                nowNum++;
                q.push(q.front());            //排至队尾
                q.pop();
            }
        }
        return 0;
}
```
# STL大法好！
这基本包括所有约瑟夫环的求解方式了
最后给大家附上进阶的最优算法，由推导优化得出公式来计算，由原复杂度On^2降为On，具体推导过程有需要的可以私聊问我
```cpp
#include<bits/stdc++.h>
using namespace std;
int main()  
{  
    int n, m,i,s=0;  
    cin>>n;  
    for(i=2;i<=n;i++)  
        s=(s+3)%i;  
    printf("%d", s+1);  
    return 0;  
}  
```
就这样，约瑟夫环降为了**On复杂度**
溜了溜了

0.0分

126 人评分

本文分类：题解列表
浏览次数：10293 次浏览
发布日期：2019-06-12 11:29:13
本文链接：https://blog.dotcpp.com/a/60298

C语言网提供由在职研发工程师或ACM蓝桥杯竞赛优秀选手录制的视频教程，并配有习题和答疑，点击了解：

一点编程也不会写的：零基础C语言学练课程

解决困扰你多年的C语言疑难杂症特性的C语言进阶课程

从零到写出一个爬虫的Python编程课程

只会语法写不出代码？手把手带你写100个编程真题的编程百练课程

信息学奥赛或C++选手的必学C++课程

蓝桥杯ACM、信息学奥赛的必学课程：算法竞赛课入门课程

手把手讲解近五年真题的蓝桥杯辅导课程

评论列表共有 27 条评论

直城多线金马转弩手海 10月前回复TA

简化版
#include<iostream>
using namespace std;
int shu(int n){
	int a[n]={0};
	int i=0,cnt=0,cnt2=0;
	for(;cnt2<n;i=(i!=n-1)?i+1:0){
		if(a[i]==0) {a[i]=(++cnt%3==0)?1:0;cnt2+=(cnt%3==0)?1:0;}
	}
	
	return (i==0?n:i);
}
int main()
{
	int n;
	while(cin>>n) cout<<shu(n)<<endl;
	return 0;
}

直城多线金马转弩手海 10月前回复TA

#include<iostream>
using namespace std;
int shu(int n){
	int a[n]={0};
	for(int i=0,cnt=0,cnt2=0;cnt2<n-1;i=(i!=n-1)?i+1:0){
		if(a[i]==0) {
			a[i]=(++cnt%3==0)?1:0;
			cnt2+=(cnt%3==0)?1:0;
		}
	}
	int k=0;
	for(int i=0;i<n;i++) k=(a[i]==0)?i:k;
	return k+1;
}
int main()
{
	int n;
	while(cin>>n) cout<<shu(n)<<endl;
	return 0;
}

kysa 1年前回复TA

@明月几时有 兄弟，你这就转了一圈就不转了是吧，666，改题大法

旋转跳舞我闭着眼 1年前回复TA

@旋转跳舞我闭着眼 对不起，我又检查了几遍，发现算法没问题，是我的问题，实在不好意思

旋转跳舞我闭着眼 1年前回复TA

最后的最优算法有问题，当n=3的时候它算的是1，而实际是2才对

pointer 1年前回复TA

@pointer 谢谢哥哥~

这个bug未免太机车了啦 1年前回复TA

@pointer 意义就是，在报数不是0的时候，这个编号进入最后一个人的下一位进行后续报数

pointer 1年前回复TA

q.push(q.front());            //排至队尾
                q.pop();
queue中，这两句什么意思，是把对头的数，在对尾又加了一个，再删去吗，有啥意义呢

明月几时有 2年前回复TA

#include<stdio.h>

void Num(int n);
int main()
{
	int n;
	scanf("%d",&n);
	Num(n);
}


void Num(int n)
{
    int num;
    if(n%3==0)
    {
        num=n-1;
    }
    else
    {
        num=n;
    }
    printf("%d",num);
}

吕金洋 2年前回复TA

这里的m好像没有用到

047题-[编程入门||数据结构入门]报数问题-题解(C/C++代码)约瑟夫环问题详解，最短代码，循环链表/队列标准，公式推导On实现

数位dp#2491: 信息学奥赛一本通T1587-Windy 数(C++)

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 27 条评论

发表评论 取消回复

评论列表共有 27 条评论

发表评论取消回复