1561 - 围圈报数
N 个人围成一圈顺序编号，从1 号开始按1、2、3 顺序报数，报3 者退出圈外，其余的人再从1、2、3 开始报数，报3 的人再退出圈外，依次类推。请按退出顺序输出每个退出人的原序号。要求使用环行链表编程。
Input
输入第一行为整数m表示有m组测试数据，接下来m行每行一个整数N，N不超过50。
Output
输出m行，每行表示题目所求，用空格隔开。
Examples
Input
1 4
Output
3 2 4 1
Solution C
#include<stdio.h> #include<stdlib.h> typedef struct Node { int data; struct Node *next; }Node; int main() { int m,n; scanf("%d",&n); for(int l=1;l<=n;l++) { scanf("%d",&m); int k=1; Node *c,*s,*r,*p; c=(Node *)malloc(sizeof(Node)); c->next=NULL; r=c; p=c; for(int j=1;j<=m;j++) { s=(Node *)malloc(sizeof(Node)); s->data=k++; r->next=s; r=r->next; } r->next=p->next; p=p->next; int count=1; while(p->next->data!=p->data) { if(count%3==0) { printf("%d ",p->data); p->data=p->next->data; p->next=p->next->next; count++; continue; } p=p->next; count++; } printf("%d\n",p->data); /*for(int i=0;i<=m+10;i++) { printf("%d ",p->data); p=p->next; printf("\n"); }*/ } //system("pause"); return 0; }
Solution C++
#include <iostream> #include <malloc.h> #include <cstdio> using namespace std; typedef struct node { int num; struct node *next; } LNode; int main() { //freopen("test.in", "r", stdin); //freopen("test.out", "w", stdout); int t; cin >> t; while (t--) { LNode *head,*p,*q; int N; cin>>N; p=(LNode*)(malloc(sizeof(LNode))); p->num=1; head=p; for(int i=1; i<N; i++) { p->next=(LNode*)(malloc(sizeof(LNode))); p=p->next; p->num=i+1; } p->next=head; p=head; while(p->next!=p) { q=p->next; p=q->next; q->next=p->next; cout<<p->num<<" "; delete p; p=q->next; } cout<<p->num<<endl; delete p; } return 0; }