MyException - 我的异常网
当前位置:我的异常网» 编程 » 天勤OJ 标题1386: 围圈报数

天勤OJ 标题1386: 围圈报数

www.MyException.Cn  网友分享于:2013-02-20  浏览:3次
天勤OJ 题目1386: 围圈报数
题目描述
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;
}



文章评论

软件开发程序错误异常ExceptionCopyright © 2009-2015 MyException 版权所有