试题 算法训练 报数

资源限制

时间限制：1.0s 内存限制：64.0MB

问题描述

　　现有n个同学站成一圈，顺时针编号1至n。从1号同学开始顺时针1/2报数，报到1的同学留在原地，报到2的同学退出圆圈，直到只剩一名同学为止。问最后剩下的同学编号。

输入格式

　　仅一行，一个正整数n。

输出格式

　　仅一行，一个正整数。

样例输入

400

样例输出

289

数据规模和约定

　　n<=2000000

法一：

解题方法：

• 使用C++中队列queue来解决：

push() 在队尾插入一个元素

pop() 删除队列第一个元素

size() 返回队列中元素个数

empty() 如果队列空则返回true

front() 返回队列中的第一个元素

back() 返回队列中最后一个元素

转载于：C++队列queue用法详解

• 详细说明见程序注释。

源程序：

#include<iostream>
#include <queue>//对应的头文件
using namespace std;
queue<int>m;
void init(int n)//对应的编号，并存入队列
{
   for (int i = 1; i <= n; i++)
   	m.push(i);
}
void print(int n)
{
   int flag = 1;//报数
   while (!m.empty())
   {
   	if (flag == 2)//当报数报到2时
   	{
   		m.pop();//将对应的编号出队
   		flag = 1;//重置报数
   	}
   	else
   	{
   		m.push(m.front());//将头元素入队
   		m.pop();//然后再出队
   		flag++;//报数增加
   	}
   	if (m.size() == 1)//当剩下最后一人时，就是没有被淘汰的编号
   	{
   		cout << m.front() << endl;
   		break;
   	}
   }
}
int main()
{
   int n;
   cin >> n;
   init(n);
   print(n);
}
           

补充：

用户可自行规定，比如一到三轮着报数，报道2或者3的人淘汰，只需要在源程序上稍作修改即可。报数的问题相比较约瑟夫问题简单较多。

评测结果：

法二：

解题方法：

这个题你把他反过来想，他问的就是最后一个人，也就是最后一个被淘汰的人

你不如，从第一个人开始找，然后涨到那么多人，他的位置就是最后一个人的位置

转载于：https://blog.csdn.net/a1439775520/article/details/105853821/

源程序

#include<iostream>
using namespace std;
int main()
{
	int n;
	cin >> n;
	int sum = 0;
	for (int i = 2; i <= n; i++)
		sum = (sum + 2) % i;
	cout << sum+1  << endl;
}
           

评测结果：

1. 可以发现两个解题方法，空间复杂度相差较多，法二更优化，但是相对比较难理解，两种方法可自行选取使用。
2. 最后，由报数问题可以引申出约瑟夫环的问题，后面我会对约瑟夫环问题进行讲解，感兴趣的可以关注一下。