Reskyd

用户名：a756256994

访问量：15507

签　名：

无事勿扰

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

　　自我简介：

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

TA的其他文章

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

你可能喜欢

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

　　作者: Reskyd　　　　发表时间：2019-06-12 11:29:13 浏览：9968　|　评论：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编程助手吧

　　评论区

直城多线金马转弩手海

简化版
#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;
}

2024-03-14 21:02:15

直城多线金马转弩手海

#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;
}

2024-03-14 20:36:49

旋转跳舞我闭着眼

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

2023-07-31 16:10:51

pointer

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

2023-02-07 18:38:13

明月几时有

#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);
}

2023-01-08 20:13:23

吕金洋

这里的m好像没有用到

2022-01-24 17:44:53

Scc丶流苏

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

2020-09-28 20:14:04

犹豫就会白给

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

2020-05-13 00:00:49

英格拉姆 2020-08-27 15:03:06 |

这段代代码白给吧

fj1984 2021-03-04 10:18:59 |

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

懒散 2021-03-13 22:21:46 |

他不是循环3次吗，S第一次直接赋值成了3，还是？

Reskyd

TA的其他文章

你可能喜欢

弟弟的作业（C++代码）

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

不容易系列2 （C语言代码）

人民币问题（C语言代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

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

评论区

精彩推荐

点我有惊喜！你懂得！

点我有惊喜！你懂得！

C二级辅导-阶乘数列（C语言代码）

模拟计算器（C语言代码）

程序员的表白（C语言代码）

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

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

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

C语言训练-列出最简真分数序列* （C语言代码）

【蟠桃记】（C语言代码）

Reskyd

TA的其他文章

你可能喜欢

弟弟的作业 （C++代码）

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

不容易系列2 （C语言代码）

人民币问题 （C语言代码）

产生数 （C++代码）（大数乘法也是可以避免的么hhhh）

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

评论区

精彩推荐

点我有惊喜！你懂得！

点我有惊喜！你懂得！

C二级辅导-阶乘数列 （C语言代码）

模拟计算器 （C语言代码）

程序员的表白 （C语言代码）

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

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

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

C语言训练-列出最简真分数序列* （C语言代码）

【蟠桃记】 （C语言代码）

弟弟的作业（C++代码）

人民币问题（C语言代码）

产生数（C++代码）（大数乘法也是可以避免的么hhhh）

　　评论区

C二级辅导-阶乘数列（C语言代码）

模拟计算器（C语言代码）

程序员的表白（C语言代码）

【蟠桃记】（C语言代码）