有N(n<100)个小朋友,这N个小朋友围坐成一圈,从任意一位小朋友开始报数,第一位报1,当数字为3时,该小朋友出列,继续从1开始报数,以此循环下去,剩余最后一人为队长。
算法核心思路:
设置一个动态数组,便于进行元素的添加和删减
设置一个计数器p,指针j指向对应数组的元素,
当p加一时,j就向右移动一个元素;
当p为3的倍数时,就删除j所指向的元素,
当j指向数组的最后一个元素时(在此之后j会一直指向最后一个元素),在数组末尾添加数组未被删除的第一个元素;
继续p+1;j+1;
此时j又指向了数组的最后一个元素,在数组末尾添加数组未被删除的的第二个元素,
以此下去,最终推送的必然是剩下的最后未被删除过的一个元素,此时j所指向的元素的值就会等于添加的元素的值。二者相邻。
#include <vector>
#include <iostream>
using namespace std;
int main()
{
int n;
int p = 2, j = 1;//这里取这个值是为了便于在while处进行判断
int t = 0;//t在添加元素处需要运用到
cin >> n;
vector<int>a;
for (int i = 1; i <= n; i++)a.push_back(i);
if (n == 1)cout << a.back();
while(a.back()!=a[j])//直到最后一位与前一位相等时说明此时只剩下最后一个未被删除的数了
{
p++;
j++;
if (p % 3 == 0)
{
auto b = a.erase(a.begin() + j );
j--;
}
if (j==a.size()-1)
{
a.push_back(a[t++]); //添加过之后c就不是最后一项了,必须再经过一次循环j++后才会指向最后一项
}
}
cout <<a.back() << endl;
return 0;
}