Reskyd

用户名：a756256994

访问量：15505

签　名：

无事勿扰

等　　级
排　　名	922
经　　验	3476
参赛次数	7
文章发表	5
年　　龄	18
在职情况	学生
学　　校
专　　业	计科

　　自我简介：

铁牌选手/数论只会骗子/数据结构只会暴力

TA的其他文章

[编程入门]自定义函数之字符串拷贝-题解(C++代码)，STL大法好，string一键剪接函数substr讲解
浏览：1290

用筛法求之N内的素数。 -题解(C++代码)，普通写法，筛法，欧拉筛法全讲解
浏览：1289

你可能喜欢

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

　　作者: Reskyd　　　　发表时间：2019-06-12 11:29:13 浏览：9966　|　评论：13　

原题链接：[编程入门]报数问题

首先，该问题就是典型的约瑟夫环问题
# 什么是约瑟夫环问题？
约瑟夫环（约瑟夫问题）是一个数学的应用问题：已知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分

139 人评分

看不懂代码解释一下代码? 或者生成一段代码？试试AI编程助手吧

　　评论区

冲进前五百冲鸭

为什么差距这么大啊!!心痛!!!

2020-03-08 15:04:47

cuzz,rank的神

大佬能简单说一次 #include<bits/stdc++.h> 吗？

2020-02-28 15:20:34

星空

用队列简单易懂，赞！！

2020-02-04 12:35:02

wo是詔康

厉害了，楼主，点个赞

2019-12-23 21:53:08

元气

厉害的

2019-12-10 12:16:37

Reskyd

TA的其他文章

你可能喜欢

采药（C++代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

点我有惊喜！你懂得！

简单的a+b （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

九宫重排（C++代码）

C语言训练-计算1977！* （C++代码）

蛇行矩阵（C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

Tom数（C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

1392题解(大数相加)

Reskyd

TA的其他文章

你可能喜欢

采药 （C++代码）

C语言程序设计教程（第三版）课后习题8.2 （C语言代码）

C语言程序设计教程（第三版）课后习题7.4 （C语言代码）

点我有惊喜！你懂得！

简单的a+b （C语言代码）

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

评论区

精彩推荐

C语言程序设计教程（第三版）课后习题11.3 （C语言代码）

C语言程序设计教程（第三版）课后习题8.8 （C语言代码）

九宫重排 （C++代码）

C语言训练-计算1977！* （C++代码）

蛇行矩阵 （C语言代码）

C语言程序设计教程（第三版）课后习题5.7 （C语言代码）

C语言程序设计教程（第三版）课后习题9.3 （C语言代码）

Tom数 （C语言代码）

C语言程序设计教程（第三版）课后习题12.5 （C语言代码）

1392题解(大数相加)

采药（C++代码）

　　评论区

九宫重排（C++代码）

蛇行矩阵（C语言代码）

Tom数（C语言代码）