試題 算法訓練 報數

資源限制

時間限制：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. 最後，由報數問題可以引申出約瑟夫環的問題，後面我會對約瑟夫環問題進行講解，感興趣的可以關注一下。