题目描述
N 个人围成一圈顺序编号，从1 号开始按1、2、3 顺序报数，报3 者退出圈外，其余的人再从1、2、3 开始报数，报3 的人再退出圈外，依次类推。请按退出顺序输出每个退出人的原序号。要求使用环行链表编程。
输入
输入第一行为整数m表示有m组测试数据，接下来m行每行一个整数N，N不超过50。
输出
输出m行，每行表示题目所求，用空格隔开。
样例输入
1
4
样例输出
3 2 4 1
提示 [+]
*** 提示已隐藏，点击上方 [+] 可显示 ***
来源
北京理工大学计算机专业2001年研究生复试上机试题
分析：问题的关键有两点：
一是围成了一个圈，那么报数的时候就要考虑到循环遍历。（直到全部退出圈外）
二是被删除的人的表示问题：
1 如果是数组实现的话，那么就应该是对删除的人做标记，表示其已经被删除，否则你就需要每删除一个人，就要将所有后面的人的位 置都向前挪一位；
2 如果是链表实现的话，那么你删除的时候直接删除表示该人的节点。
解答：下面的代码使用数组实现，比较简单。但是思路应该比较清晰了。
/********************************** 日期：2013-2-14* 作者：SJF0115* 题号: 天勤OJ 题目1386: 围圈报数* 来源：http://acmclub.com/problem.php?id=1386* 结果：AC* 来源：北京理工大学计算机专业2001年研究生复试上机试题* 总结：**********************************/#include<stdio.h>#include<string.h>#include<stdlib.h>#define ID = 3;//报3 者退出圈外int main(){ int n,i,j,people,index,count; int DeleteID[51]; while(scanf("%d",&n) != EOF){ for(i = 0;i < n;i++){ int Flag[51] = {0};//标记1为删除 count = 0;//统计删除的人数 index = 1; scanf("%d",&people); for(j = 0;j < people;j++){ //报3 者退出圈外 if(index % 3 == 0 && Flag[j] == 0){ //删除 Flag[j] = 1; //重新报数 index = 1; //标记删除的人数 DeleteID[count] = j+1; count++; } //报数 删除的不用报（Flag[j] = 1已删除不用报数） if(Flag[j] == 0){ index++; } //下一圈报数 if(j == people-1){ j = -1; } //全部退出 if(count == people){ break; } }//for //输出每个退出人的原序号 for(j = 0;j < count;j++){ if(j == count - 1){ printf("%d\n",DeleteID[j]); } else{ printf("%d ",DeleteID[j]); } } }//for }//while return 0;}数组 第二种方法
/********************************** 日期：2013-2-14* 作者：SJF0115* 题号: 天勤OJ 题目1386: 围圈报数* 来源：http://acmclub.com/problem.php?id=1386* 结果：AC* 来源：北京理工大学计算机专业2001年研究生复试上机试题* 总结：先将所有人进行编号，如果被删除就将其编号设置为0。 循环直到队列中只剩0个人**********************************/#include<stdio.h>#include<string.h>#include<stdlib.h>int main(){ int n,i,j,people,index,remain; const int ID = 3;//报3 者退出圈外 int DeleteID[51]; while(scanf("%d",&n) != EOF){ for(i = 0;i < n;i++){ scanf("%d",&people); int Flag[51] = {0};//标记1为删除 index = 0; remain = people; while(remain >= 1){ for(j = 0;j < people;j++){ //对没有标记为1的报数 if(Flag[j] == 0){ //报数 index ++; //报ID者退出圈外 if(index == ID){ //退出圈外 Flag[j] = 1; //重新报数 index = 0; DeleteID[remain-1] = j+1; remain --; }//if }//if }//for }//while //输出每个退出人的原序号 for(j = people-1;j >= 0;j--){ if(j == 0){ printf("%d\n",DeleteID[j]); } else{ printf("%d ",DeleteID[j]); } } }//for }//while return 0;}