[pta-- use queues to solve the problem of monkeys choosing kings]

Problem description

A group of monkeys are going to choose a new monkey king . The choice of the new monkey king is ： Give Way N There are only monkeys in a circle , The sequence number from a certain position is 1~N Number . From 1 We'll start counting on the , From 1 To report for duty 3, Where to report 3 That's the monkey who quit the circle , And then from the next monkey next to the same number . And so on and on , The last monkey left is the monkey king . What's the original Monkey King number ？

Input format ：

Enter a positive integer on a line N（≤1000）.

Output format ：

Output the number of monkey king in one line .

sample input ：

11

sample output ：

7

analysis

We know that queues have the characteristics of first in, first out , If you put the first position of the queue back in the queue , Then the number of the first position becomes the last number of the new queue , Thus, a closed loop can be formed . Therefore, using queues can better solve this kind of problem .

According to the problem description , A group of monkeys form a circle , Every time the third monkey is eliminated , The last one is the king to choose . According to example analysis , We can create a queue first , take 11 Monkeys are put into the queue in turn , Then just look at the first three monkeys in the queue , Remove the first two monkeys from the original queue , Then put it back in the queue , After the third monkey is removed, there is no need to care , Thus cycle , When there is only one element left in the queue , Out of the loop , This element is the number to choose .

for the first time ：

The second time ：

third time ：

  The fourth time ：

The fifth time ： 

The sixth time ：

In turn, cycle , Finally, there is only one element left ：

That is to say 7, namely 7 It's the monkey king .

c++ The code is as follows ：

#include<iostream>
#include<queue>
using namespace std;
int main() {
	int n;
	cin>>n;
	queue<int> que;
	for (int i = 1; i <= n; i++) {
		que.push(i);
	}
	while (1) {
		if (que.size() == 1) break;
		for (int i = 1; i < 3; i++) {
			int t = que.front();
			que.pop();
			que.push(t);
		}
		que.pop();
	}
	cout<<que.front();
}