資源限制
時間限制：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;
}
評測結果：
- 可以發現兩個解題方法，空間復雜度相差較多，法二更優化，但是相對比較難理解，兩種方法可自行選取使用，
- 最后，由報數問題可以引申出約瑟夫環的問題，后面我會對約瑟夫環問題進行講解，感興趣的可以關注一下，
轉載請註明出處，本文鏈接：https://www.uj5u.com/ruanti/254099.html
標籤：其他