ACM计算机程序设计大赛试题解答

试题 1 n 个人围成一圈, 并依次编号 1～n，。从编号为 1 的人开始，按顺时针方向每隔一人选出一个， 剩下的人重新围成一圈，如此循环直到剩下两人，这剩下的两人就是幸运儿。如果你想成为最后两个 幸运儿，请问开始时应该站在什么位置？（设 3<=n<=50） 输入：开始时的人数 n 输出：第 1行是选出顺序，第 2 行是两名幸运儿的开始位置（按升序排列），位置编号之间用一个空格 分开。

#include
#include
int na[51]b[51];
int j=1;

void main（）
{
	clock_t startend;	
	FILE *fp1*fp2;	
	int i=0kts=1q;
	int c[25];	
	start=clock（）;

	//文件输入n	
	fp1=fopen（“试题一输入.txt““r“）;
	
	if（fp1==NULL）
	{
		printf（“Cann‘t open this test!\n“）;
		//exit（0）;
	}

	/*c[1]=fgetc（fp1）;	
	c[2]=fgetc（fp1）;		
	fclose（fp1）;

	n=10*（c[1]-48）+（c[2]-48）;*/
	
	fscanf（fp1“%d“&n）;
	printf（“n=%d“n）;

	/*printf（“请输入n的值（3<=n<=50）:“）;         //键盘输入n
	scanf（“%d“&n）;
	while（n>50||n<3） 
	{
		printf（“\nn的值超界！\n请重新输入：“）;
		scanf（“%d“&n）;
	}*/

	printf（“\n“）;                            //打印 n
	for（i=1;i<=n;i++）
	{	
		a[i]=i;	
		printf（“%d “a[i]）;
	}

	printf（“\n“）;

	q=a[n];  	//q 标记被选一圈之前的没有被选出之中的最后一个值 
	printf（“\n新加入排好的数为:\n“）;
	for（t=1i=2;i<=n;i+=2j++t++）
	{
		b[j]=a[i];                           //b[]存放被选出的顺序
		c[t]=a[i-1];                         //c[]暂存没有被选出的
		printf（“%d “b[j]）;		
	}
	if（b[j-1]!=q）c[t++]=q;                  
	printf（“\n剩下的数为:\n“q）;
	for（i=1;i	{ 
		a[i]=c[i];
		printf（“%d “c[i]）;                  //把c[]中的数存入a[]，使之成为一新数列
	}
	k=t-1;	                                
	printf（“a[k]=%d\n“a[k]）;                //输出被选一圈之后的没有被选出之中的最后一个值a[k]
	
		while（k>2）                           
		{ 	/*判断一次挑选前后的最后一个值，如果相等则下一次挑选
			  从最后一个开始，否则从第一个开始*/
			if（a[k]==q）	                               
			{  
				q=a[k];
				printf（“\n进入一:\n新加入排好的数为：\n“）;
				for（t=1i=1;i<=k;i+=2j++t++）
				{
					b[j]=a[i];
					c[t]=a[i+1];
					printf（“%d “b[j]）;
				}				
				if（b[j-1]==q）t=t-1;
				
				printf（“\nq1=%d\n剩下的数为：\n“q）;
				for（i=1;i				{
					a[i]=c[i];
					printf（“%d “a[i]）;
				}				
				k=t-1; 
				printf（“\nk=%d\n“k）;
				if（k<2）	c[2]=b[j-1];			
				printf（“q2=%d\n“q）;
			}

			else 
			{
				q=a[k];
				printf（“\n进入二:\n新加入排好的数为：\n“）;
				for（t=1i=2;i<=k;i+=2j++t++）
				{
					b[j]=a[i];
					c[t]=a[i-1];
					printf（“%d “b[j]）;					
				}
				
				if（b[j-1]!=q）c[t++]=a[k];

				printf（“\n剩下的数为：\n“）;				
				for（i=1;i				{ 
					a[i]=c[i];
					printf（“%d “a[i]）;					
				}
				printf（“\nt=%d\n“t）;
				
				k=t-1;
				printf（“\nk=%d\n“k）;
				if（k<2）c[2]=b[j-1];				
				printf（“\nq=%da[k]=%d\n“qa[k]）;
			}
			s=s*2;			
		}

		fp2=fopen（“试题一的输出.txt““w“）;
		if（fp2==NULL）
		{
			printf（“cann‘t open this test!\n“）;
			//exit（0）;
		}
		printf（“\n选出的顺序：\n“）;	
		for（i=1;i<=n-2;i++）
		{
			printf（“%d “b[i]）;
			fprintf（fp2“%d “b[i]）;
		}

	printf（“\n两个幸运儿的开始位置：\n“）;
	printf（“%d %d \n“c[1]c[2]）;
	fprintf（fp2“\n%d %d“c[1]c[2]）;
	end=clock（）;	
	printf（“time=%d\n“end-start）;
}

 属性            大小     日期    时间   名称
----------- ---------  ---------- -----  ----

     文件          2  2006-07-18 16:48  新建文件夹\试题一输入.txt

     文件        416  2006-07-19 08:11  新建文件夹\2005.01.txt

     文件       2932  2006-07-18 16:46  新建文件夹\试题一.cpp

     目录          0  2006-07-20 09:58  新建文件夹

----------- ---------  ---------- -----  ----

                 3350                    4