[编程题]围圈报数
- 热度指数：6904 时间限制：C/C++ 1秒，其他语言2秒 空间限制：C/C++ 32M，其他语言64M
- 算法知识视频讲解
N 个人围成一圈顺序编号，从1 号开始按1、2、3 顺序报数，报3 者退出圈外，其余的人再从1、2、3 开始报数，报3 的人再退出圈外，依次类推。请按退出顺序输出每个退出人的原序号。要求使用环行链表编程。
输入描述:
输入第一行为整数m表示有m组测试数据，接下来m行每行一个整数N，N不超过50。
输出描述:
输出m行，每行表示题目所求，用空格隔开。
示例1
输入
1 4
输出
3 2 4 1
#include <cstdio>
#include <cstring>
#include <algorithm>
#include <string>
#include <iostream>
#include <stack>
#include <cmath>
#include <map>
#include <vector>
using namespace std;
struct node{
int id;
node* next;
};
typedef node* LNode;
int main()
{
int T;
int n;
while(cin >> T)
{
for(int j = 0;j<T;j++)
{
cin >> n;
LNode head = (node*)malloc(sizeof(node));
head->id = -1; head->next = head;
LNode pre = head;
for(int i = 0 ;i<n;i++)
{
LNode t = (node*)malloc(sizeof(node));
t->id = i+1;
t->next = NULL;
pre->next = t;
pre = t;
}
pre->next = head;
pre = head;
LNode now = head->next;
vector<int> v;
v.clear();
for(int i = 0;i<n;i++)
{
int _count = (now->id == -1) ? 0 : 1;
while(_count < 3)
{
pre = now;
now = now->next;
if(now->id == -1)
{
pre = now;
now = now->next;
}
_count++;
}
v.push_back(now->id);
now = now->next;
pre->next = now;
}
for(int i = 0 ;i<n;i++)
{
cout << v[i];
if(i == n-1)
cout << endl;
else cout << " ";
}
}
}
}
发表于 2019-02-22 13:51:05
回复(0)
使用一个循环单链表做就很简单了，一开始设置count为1，每次读完以后count+1，当count是3的倍数（count%3=0)时删除这个节点。因为要删除某一个节点，如果只是设置一个current指针找到了要删的节点，还得从头开始找上一个节点。因此除了设置一个current指针指向当前节点，还需要设置一个last指针指向上一个节点
每次循环，按道理last和current都会取到next（除了删除时是last不动，current后移一个），这里我用的是带有头结点的循环单链表，current取了next以后可能会变成head，此时直接让current取head->next（第一个数据节点），让last取head，也就是再移动一次。
//
// 242围圈报数.cpp
// 牛客考研机试题
//
// Created by TuGang's Mac on 2021/5/2.
// Copyright © 2021 TuGang's Mac. All rights reserved.
//
#define maxSize 50
#include <stdio.h>
#include <iostream>
#include <vector>
using namespace std;
struct loopLList{
//循环单链表,带有头结点
int num;
loopLList* next;
loopLList(){next=NULL;}
loopLList(int n){
next=NULL;
num=n;
}
};
vector<int> out_order(loopLList* head){
vector<int> result;
int count=1;
loopLList* current=head->next;
loopLList* last=head;//上一个节点，方便做删除用
while (last!=current) {
//循环终止条件:last==current，此时只剩一个头结点
if (count%3==0) {
//报到3的人出圈
result.push_back(current->num);
//删掉这个节点
loopLList* p=current;
last->next=p->next;
current=current->next;
if(current==head){
//折回一圈，current变成head
last=head;
current=head->next;
}
delete p;
++count;
}
else{
++count;
last=last->next;
current=current->next;
if(current==head){
//折回一圈，current变成head
last=head;
current=head->next;
}
}
}
return result;
}
int main(){
//初始化链表
int m;cin>>m;//输入m次
int n;//
for (int i=1; i<=m; ++i) {
cin>>n;//输入总人数
//开始编号
loopLList* head=new loopLList();
loopLList* first=head;
for (int j=1; j<=n; ++j) {
//结点编号
loopLList* node=new loopLList(j);
//初始化链表
first->next=node;
if (j==n) {
//最后一个结点next指向head
node->next=head;
}
//这样first相当于一个尾结点，可以重复使用
first=first->next;
}
vector<int> result=out_order(head);
for (int k=0; k<result.size(); ++k) {
cout<<result[k]<<" ";
}
//删除head结点
delete head;
cout<<endl;//进入下一次循环
}
}
发表于 2021-05-02 22:14:17
回复(0)
#include <iostream>
#include <queue>
using namespace std;
int main()
{
int m,n,i;
cin>>m;
while(m--)
{
cin>>n;
queue<int> a;
if(n==1) printf("1");
else if(n==2) printf("1 2");
else{
printf("3");
for(i=4;i<=n;i++)
a.push(i);
a.push(1);
a.push(2);
i=1;
while(!a.empty())
{
if(i%3==0)
{
printf(" %d",a.front());
a.pop();
}
else{
a.push(a.front());
a.pop();
}
i++;
}
}
printf("\n");
}
return 0;
}
发表于 2021-03-24 11:17:13
回复(0)
静态链表模拟一下
#include<bits/stdc++.h>
using namespace std;
int Next[100];
void solve(int N){
for(int i=0;i<N;i++)Next[i]=(i+1)%N;
int p=0;
for(int i=0;i<N;i++){
p=Next[p];
printf("%d%c",Next[p]+1,i+1==N?'\n':' ');
Next[p]=Next[Next[p]];
p=Next[p];
}
}
int main()
{
int T,N;
scanf("%d",&T);
while(T--){
scanf("%d",&N);
solve(N);
}
return 0;
}
发表于 2021-02-07 17:02:08
回复(0)
#include<stdio.h>
int main()
{
int m,n,i,j,k,num;
scanf("%d",&m);
while(m--)
{
int a[100];
scanf("%d",&n);
for(i=0;i<n;i++)
a[i]=i+1;//初始编号
i=0;//数组下标
k=0;//1--3计数
num=0;//退出的人数
while(num!=n-1)//==n-1的时候只剩下一个人
{
if(a[i]!=0) k++; //数组==0的时候不再参与报数
if(k==3)
{
printf("%d ",a[i]);
a[i]=0;
num++;
k=0;
}
i++;
if(i==n)//报数到末尾
i=0;
}
i=0;
while(a[i]==0) i++;
printf("%d\n",a[i]);//输出最后一个数
}
return 0;
}
发表于 2020-05-09 16:15:38
回复(0)
使用STL中list容器实现算法
值得注意的是：list 并不是从最后一个元素指向第一元素，而是从最后一个元素的下一位置指向第一个元素。
#include <iostream>
#include <list>
#include <vector>
using namespace std;
int main(){
list<int> clist;
vector<int> array;
int m, N;
cin >> m;
for (int k = 0; k < m; k++) {
clist.clear();
array.clear();
cin >> N;
for (int i = 1; i <= N; i++){
clist.push_back(i);
}
list<int>::iterator it = clist.begin();
while(N){
for (int j = 1; j < 3; j++){
it++;
if(it == clist.end()){
it = clist.begin();
}
}
array.push_back(*it);
it = clist.erase(it);
N--;
if(it == clist.end()){
it = clist.begin();
}
}
for (int i = 0;i<array.size();i++){
cout << array[i] << " ";
}
cout << endl;
}
return 0;
}
发表于 2020-02-09 20:05:54
回复(0)
#include<iostream>
using namespace std;
typedef struct node{
int num;
struct node *next;
}node;
node *creat(int n){
node *head;
head=(node*)malloc(sizeof(node));
head->num=1;
head->next=head;//成环
for(int i=n;i>=2;i--){
node *p;
p=(node*)malloc(sizeof(node));
p->num=i;
p->next=head->next;
head->next=p;
}
return head;
}
int main(){
int m,n;
while(cin>>m){
for(int j=0;j<m;j++){
cin>>n;
node *L=creat(n);
node *p=L,*pre=NULL;//注意这里 每一轮pre都要初始化，不然while循环只能进行一次
int count=1;
while(pre->next!=pre){
pre=p;
p=p->next;
count++;
if(count==3){
pre->next=p->next;
cout<<p->num<<" ";
free(p);
p=pre->next;
count=1;//重新开始计数
}
}
cout<<pre->num<<endl;
}
}
return 0;
}
发表于 2019-03-11 15:54:03
回复(1)
Python实现
class ListNode(object):
def __init__(self, x):
self.x = x
self.next = None
for _ in range(int(input())):
num = int(input())
head = ListNode(1)
temp = head
for i in range(2, num + 1):
temp.next = ListNode(i)
temp = temp.next
temp.next = head
temp = head
res = []
while temp.x != temp.next.x:
temp = temp.next
res.append(temp.next.x)
temp.next = temp.next.next
temp = temp.next
res.append(temp.x)
print(' '.join(map(str, res)))
发表于 2019-02-27 11:23:01
回复(0)
题目要求使用环形链表。其实很简单，就是处理好节点的删除就好了。以下是C++代码实现。核心程序不多，在init是构造环形链表。主要语句是main里面的一句while，这里的head就是当前要准备退出的，接下来删除它即可。
while((head = head->next)&&--k);
#include<iostream>
#include<cstdio>
#include<cstdlib>
using namespace std;
typedef struct Node{
int index;
struct Node *next;
struct Node *pre;
}Node,*Nodeptr;
Nodeptr init(int n){
Nodeptr head = (Nodeptr)malloc(sizeof(Node));
Nodeptr p = head;
head->index = 1;
for(int i = 2;i<=n;i++){
Nodeptr node = (Nodeptr)malloc(sizeof(Node));
node->index = i;
p->next = node;
node->pre = p;
p = node;
}
p->next = head;
head->pre = p;
return head;
}
int main(void){
int m;
cin>>m;
int n;
for(int i = 0;i<m;i++){
cin>>n;
Nodeptr head = init(n);
Nodeptr p;
while(n){
int k = 2;
while((head = head->next)&&--k);
cout<<head->index<<" ";
head->next->pre = head->pre;
head->pre->next = head->next;
p = head;
head = head->next;
free(p);
n--;
}
cout<<endl;
}
return 0;
}
发表于 2019-05-23 12:08:03
回复(1)
应题目要求，使用的是单项循环链表实现的。因为我自己理不出来这其中的数据之间的计算表达式，所以用的是指针移动的方式实现的。
先是一个Init函数，对每一个N初始化构造出一个单项循环链表，把1——N按顺序填充进去。
然后就是用指针进行移动，找到对应节点，输出数据后将节点删除。
因为这题目里只报到3，所以我觉得还是很好理解和实现的，但是如果报的数大的话，每次指针移动就会很麻烦了，我的方法就不太适合了
#include <iostream>
#include <cstdio>
#include <cstdlib>
using namespace std;
//结点类型定义
typedef struct LNode{
int data;
struct LNode *next;
}LNode,*Link;
//初始化单向链表
Link InitList(int N){
Link head=(Link)malloc(sizeof(LNode));//头节点
Link p=head;
head->data=1;
for(int i=2;i<=N;i++){
Link node=(Link)malloc(sizeof(LNode));//新节点
node->data=i;
p->next=node;
p=p->next;
}
p->next=head;
return head;
}
int main(){
int m,N;
cin>>m;
for(int i=0;i<m;i++){
cin>>N;
Link L=InitList(N);
Link p=L;
while(N){
Link q=p->next->next;//q指针指向要输出的节点
cout<<q->data<<" ";//输出数据，记得加空格
p=p->next;//p指针后移，便于删除节点
p->next=q->next;
free(q);//删除节点
p=p->next;//p移动到下一个报数起点（即报1的位置）
N--;//记录链表中剩余数据
}
cout<<endl;
}
return 0;
}
发表于 2019-12-31 21:39:18
回复(0)
数组模拟实现循环链表
#include <iostream>
using namespace std;
const int N = 55;
int head, nail, ne[N], e[N], idx;
void init() {
head = -1;
nail = 0;
idx = 0;
}
void insert(int &head, int x) {
e[idx] = x;
if (head == -1)
head = idx;
ne[nail] = idx;
ne[idx] = head;
nail = idx ++;
}
void print() {
int cnt = 1;
int p = head, q = nail;
while (p != q) {
if (cnt % 3 == 0) {
cout << e[p] << " ";
ne[q] = ne[p];
p = ne[q];
} else {
p = ne[p];
q = ne[q];
}
cnt ++;
}
cout << e[p];
}
int main() {
int n, m;
cin >> m;
while (m--) {
init();
cin >> n;
for (int i = 1; i <= n; i ++) insert(head, i);
print();
cout << endl;
}
return 0;
}
发表于 2025-02-08 11:55:14
回复(0)
先构造循环链表。定义一个变量i由于统计当前遍历到第几个节点，如果 i 能被3整除就输出当前节点编号并删除此节点。当循环链表中只剩下一个节点时，最后再单独输出它。
#include <cstdlib>
#include <iostream>
using namespace std;
struct LinkNode {
int number;
LinkNode* next{nullptr};
LinkNode(int value): number(value) {}
};
void initial(LinkNode* head, LinkNode* node) {//构造循环链表
if (head->next == nullptr) { // 如果链表为空
head->next = node;
node->next = head; // 新节点指向头节点，形成循环
} else {
auto p = head;
while (p->next != head) { // 找到最后一个节点
p = p->next;
}
p->next = node; // 将新节点连接到最后一个节点
node->next = head; // 新节点指向头节点，形成循环
}
}
LinkNode* del(LinkNode* head, LinkNode* p) {//删除指定节点
auto temp = head;
while (temp->next != p) {
temp = temp->next;
}
temp->next = temp->next->next;
if(head ==p){//如果删除的节点是头节点
head = temp->next;//重置头节点
return head;
}
return head;
}
int main() {
int m;cin>>m;
while (m--) {
int n;
cin >> n;
auto* head = new LinkNode(1);//构造头节点，编号为1
head->next = head;
if(n>=2){
for (int i = 2; i <= n; i++) {
initial(head, new LinkNode(i));//构造循环链表
}
}
int i = 1;//用于判断当前是第几个节点
auto p = head;
while (p ->next != p) {//当链表中的元素数量大于1时
if (i % 3 == 0) {//如果报数为3的倍数
cout << p->number << " ";//打印当前节点
head = del(head, p);//删除当前节点
p = p->next;
i++;
}else{
p = p->next;
i++;
}
}
cout << p->number<<endl;//当链表只剩1个元素的时候，输出
}
}
发表于 2025-02-14 19:59:42
回复(0)
#include <iostream>
#include <queue>
using namespace std;
int main() {
int m;
cin>>m;
while(m--){
int n;
queue<int> q;
cin>>n;
for(int i=1;i<=n;i++) q.push(i);
int now=1;
while(!q.empty()){
if(now==3){
cout<<q.front()<<' ';
q.pop();
now=1;
}
else{
q.push(q.front());
q.pop();
now++;
}
}
cout<<endl;
}
}
编辑于 2024-03-25 18:41:04
回复(0)
import java.util.LinkedList;
import java.util.List;
import java.util.Scanner;
public class Main {
public static void main(String[] args) {
Scanner scanner = new Scanner(System.in);
while(scanner.hasNext()) {
int m = scanner.nextInt();
for (int i = 0; i < m; i++) {
int n = scanner.nextInt();
//按照输入顺序排序
List<Integer> myList = new LinkedList<Integer>();
for (int j = 1; j <= n; j++) {
myList.add(j);
}
while(!myList.isEmpty()) {
if(myList.size() >= 3) {
System.out.print(myList.get(2)+" ");
reSort(myList);
continue;
}else {
System.out.print(myList.remove(0)+" ");
}
}
//换行输出
System.out.println();
}
}
}
public static void reSort(List<Integer> myList) {
//重排List：实现将List的前两个元素插入到最后得到一个新的List
if (myList.size() >= 3) {
int list1 = myList.remove(0);
int list2 = myList.remove(0);
//删除原来List中第3个元素
myList.remove(0);
myList.add(list1);
myList.add(list2);
}
}
}
编辑于 2024-03-21 15:27:26
回复(0)
#include <iostream>
using namespace std;
typedef struct LNode{
int data;
struct LNode* next;
}* LinkList;
int main(){
int m;
cin >> m;
while(m--){
int n;
cin >> n;
LinkList head = new LNode;
head->data = -1;
head->next = head;
LNode* pre = head;
for(int i=1; i<=n; ++i){
LNode* t = new LNode;
pre->next = t;
t->data = i;
t->next = head;
pre = t;
}
int k = 1;
pre = head;
LNode* s=head->next;
while(head->next!=head){
if(k!=3){
if(s==head){
pre = s;
s = s->next;
}
pre = s;
s = s->next;
++k;
}else{
if(s==head){
pre = s;
s = s->next;
}
pre->next = s->next;
cout << s->data << ' ';
free(s);
s = pre->next;
k=1;
}
}
cout << endl;
}
}
编辑于 2024-03-15 15:17:42
回复(0)
#include <cstddef>
#include <cstdlib>
#include <iostream>
using namespace std;
struct Node {
int no;
struct Node* next;
};
int main() {
int m;
while (cin >> m) {
for (int i = 0; i < m; ++i) {
Node* pHead = NULL, * preP;
int num;
cin >> num;
if(num == 1){
cout << 1 << endl;
continue;
}
for (int j = 1; j <= num; ++j) {
Node* pNew = (Node*)malloc(sizeof(Node));
pNew->no = j;
if (pHead == NULL) {
pHead = pNew;
preP = pHead;
} else {
preP->next = pNew;
preP = pNew;
}
if (j == num) {
pNew->next = pHead;
} else {
pNew->next = NULL;
}
}
Node* pNew2 = pHead,* pPre2;
int count = 1;
while (pNew2 != NULL) {
count++;
if (count % 3 == 0) {
Node* pTemp = pNew2->next;
cout << pTemp->no << " ";
if (pTemp->next != pNew2) {
pNew2->next = pTemp->next;
} else {
pPre2 = pNew2;
pNew2->next = NULL;
}
free(pTemp);
count = 1;
}
pNew2 = pNew2->next;
}
cout << pPre2->no << endl;
}
}
}
// 64 位输出请用 printf("%lld")
发表于 2023-03-28 16:48:17
回复(0)
#include <iostream>
using namespace std;
typedef struct node{
int val;
struct node *next;
}Node;
/*创建初始换循环链表*/
Node *init(int n){
Node *q = (Node *)malloc(sizeof(Node));
q -> val = 1;
q -> next = NULL;
Node *head = q;
for(int i = 2 ; i<=n;i++){
Node *p = (Node *)malloc(sizeof(Node));
p->val = i;
p->next = NULL;
q->next = p;
q = p;
}
q->next = head;
return head;
}
/*逐个弹出报3的节点，在只剩一个节点时停止
此时head->next = head
*/
void pop(Node *head){
while(head -> next != head){
Node *temp = head->next->next;
cout << temp->val <<" ";
head -> next -> next = temp ->next;
head = temp ->next;
free(temp);
}
cout << head->val <<endl;
}
int main() {
int m;
cin >> m;
while(m--){
int x;
cin >> x;
Node *head = init(x);
pop(head);
}
}
// 64 位输出请用 printf("%lld")
发表于 2023-03-17 11:54:07
回复(0)
只用了数组的...
#include<stdio.h>
#include<stdlib.h>
#include<math.h>
#include<string.h>
#include<limits.h>
int main()
{
int n;
scanf("%d",&n);
while(n>0)
{
int num;
scanf("%d",&num);
int len=num;
int people[num];
for(int i=0;i<num;i++)
{
people[i]=i;
}
int index=0;
while(len>0)
{
//报数1
while(people[(index+num)%num]==-1)
index++;
index++;
//报数2
while(people[(index+num)%num]==-1)
index++;
index++;
//报数3
while(people[(index+num)%num]==-1)
index++;
printf("%d ",people[(index+num)%num]+1);
people[(index+num)%num]=-1;
index++;
len--;
}
printf("\n");
n--;
}
}
发表于 2022-03-17 14:28:08
回复(0)
#include<iostream>
using namespace std;
typedef struct Node
{
int data;
Node * next;
Node(int x)
{
data = x;
next = NULL;
}
}*LinkList;
void InitList(LinkList & list,int n)//初始化单循环链表,无头结点
{
Node * p,*q;
list = new Node(1);
q = p = list;
for(int i = 2;i <= n;i++)
{
Node * temp = new Node(i);
p->next = temp;
p = p->next;
}
p->next = q;
}
void count(LinkList list,int N)//计数并输出
{
Node * p = list;
while(N--)
{
Node * q = p->next->next;
cout << q->data << ' ';
p->next->next = q->next;
p = q->next;//p指向下次报数的位置
free(q);
}
cout << endl;
}
int main(void)
{
int m;
cin >> m;
while(m--)
{
int N;
cin >> N;
LinkList list;
InitList(list, N);
count(list, N);
}
return 0;
}
发表于 2022-02-07 17:35:19
回复(0)
问题信息
通过挑战的用户
查看代码-
2023-03-09 18:37:10
-
2023-02-27 12:18:10 -
2023-01-21 17:03:08 -
2022-10-19 21:37:23 -
2022-09-07 19:37:44
相关试题
-
扫描二维码，关注牛客网
- 意见反馈
-
下载牛客APP，随时随地刷题
扫一扫，把题目装进口袋
- 求职之前，先上牛客
-
扫描二维码，进入QQ群
扫描二维码，关注牛客公众号
- 公司地址：北京市朝阳区北苑路北美国际商务中心K1座一层-北京牛客科技有限公司
- 联系方式：010-60728802 投诉举报电话：010-57596212（朝阳人力社保局）
- 牛客科技© All rights reserved admin@nowcoder.com
- 京ICP备14055008号-4 增值电信业务经营许可证 营业执照 人力资源服务许可证
-
京公网安备
11010502036488号
