---
title: "围圈报数"
created: 2025-11-28
tags:
  - 算法
---

# 围圈报数

## 题目 [围圈报数](https://www.acwing.com/problem/content/description/3562/)

![[image-6a74b20f.png]]

## 思路分析

构建一个循环链表。

`void init() {`

`for (int i = 1; i < n; i ++ )`

`ne[ ++ idx] = i + 1;`

`ne[ ++ idx] = 1;`

`}`

具体操作过程如下图所示：

![[image-eaed3393.png]]

构建完成循环链表后，每次报数为 3的人退出圈外，即进行链表的删除操作。那么我们如何去找报数为 3的那个人呢？ 我们设 start为我们的开始结点。则报数为
3的那个人一定是 `ne[ne[start]]`，并且更新 start的位置。

具体操作过程如下图所示：

![[image-00ae9f5f.png]]

## 代码实现

```cpp
#include<bits/stdc++.h>

using namespace std;

const int N=55;

int ne[N],idx;

int T,n;

void init()

{

    memset(ne,0,(n+1)*4);

    idx=0;

    for(int i=1;i<n;i++)

        ne[++idx]=i+1;

    ne[++idx]=1;

}

void del(int x){

    ne[x]=ne[ne[x]];

}

int main()

{

    cin>>T;

    while(T--){

        cin>>n;

        init();

        int start=1;

        for(int i=1;i<=n;i++){

            int now=ne[ne[start]];

            cout<<now<<" ";

            del(ne[start]);

            start=ne[ne[start]];

        }

        cout<<endl;

    }

    return 0;

}
```

```cpp
#include<bits/stdc++.h>

using namespace std;

int T,n;

int main()

{

    cin>>T;

    while(T--){

        cin>>n;

        list<int> nums;

        for(int i=1;i<=n;i++){

            nums.push_back(i);

        }

        auto it=nums.begin();

        int k=3-1;

        while(nums.size()){

            while(k--){

                it++;

                if(it==nums.end())

                    it=nums.begin();

            }

            cout<<*it<<" ";

            it=nums.erase(it);

            if(it==nums.end())

                it=nums.begin();

            k=3-1;

        }

        cout<<endl;

    }

    return 0;

}
```

## 同类题型

## 视频讲解

---
⬅️ [[区块反转|区块反转]] 🏠 [[00-刷题理模型]] ➡️ [[2-Learning/02-算法/03-刷题理模型/链表相关问题/圆圈中最后剩下的数字|圆圈中最后剩下的数字]]