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

10332 阅读 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 人评分

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

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

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

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

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

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

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

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

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

评论列表共有 27 条评论

闹市眠 3年前回复TA

@Scc丶流苏 最后那种不是stl算法，stl是指上面那个用了stl封装的队列，最下面这个是递归的思路。

懒散 3年前回复TA

@犹豫就会白给 他不是循环3次吗，S第一次直接赋值成了3，还是？

fj1984 3年前回复TA

@犹豫就会白给 报个数（i），看报数的人（++s），如果到队尾了就返回到队首（s=1），如果这个人已经出列（visit[s]=1）,把报的数取消（i--），继续下轮（i++）

yxhctsw 4年前回复TA

@cuzz,rank的神 但是会影响编译速度

Scc丶流苏 4年前回复TA

能详细解释一下STL算法嘛？草草几行代码都代表着什么意思呢？

英格拉姆 4年前回复TA

@犹豫就会白给 这段代代码白给吧

冲进前五百冲鸭 4年前回复TA

@冲进前五百冲鸭 @H1910819097 我感觉我算法无从入手啊。不知道是不是题还是刷的少，或者题的质量不够高。

Stephen 4年前回复TA

@冲进前五百冲鸭 这就是带佬吗，爱了爱了

上单皇阿玛 4年前回复TA

@冲进前五百冲鸭 兄弟感同身受，我太难了

犹豫就会白给 4年前回复TA

for(int i=0;i<3;i++){if(++s>n)s=1;if(visit[s])i--;}这段代码啥意思啊

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

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

点进来你会后悔的

简简单单的循环

简单的回文数

评论列表 共有 27 条评论

发表评论 取消回复

评论列表共有 27 条评论

发表评论取消回复