多人围成一圈报数问题！

男娘i 2022-05-14 08:03 197阅读 0赞

题目（摘自谭浩强的C语言）:有n个人围成一圈，顺序排号。从第一个人开始报数(从1到3报数)，凡报到3的人退出圈子，问最后留下的是原来第几号的那个人。

解法思路：首先不要将思维局限在一圈人，可以先将n个人看做一排，即作为一个数组，为这个数组的每一个元素(即人)编号，第0个人就编号1，以此类推。有了编号之后可以这样：让第一个人开始报数，到第三个人喊3的时候，将其编号重置为0，并且将喊的那个数重置0(即让下一个人喊的时候又从1开始)，如此这么循环（循环的条件就是留下的人至少为一个）。有一点要注意的就是，当指针访问到最后一个人的时候，由于题目要求是围成一圈，而我们这里是一排，所以要重置指针，使其指向排头。

代码如下：

#include <stdio.h>
    void main()
    {
    	int num[50],n,*p,j,loop,i,m,k;
    	printf("请输入这一圈人的数量:\n");
    	scanf("%d",&n);
    	p=num;
    	//开始给这些人编号
    	for (j=0;j<n;j++)
    	{
    		*(p+j)=j+1;
    	}
        i=0;//i用于计数,即让指针后移
        m=0;//m记录退出圈子的人数
        k=0;//k报数1,2,3
        while(m<n-1)//当退出的人数不大于总人数时，即留下的人数至少是一个人
    		        //这句不能写成m<n,因为假设有8人，当退出了6人时，此时还是进行人数退出，即m++，
    				//这时是7<8，剩下的一个人自己喊1，2,3那么他也就退出了，将不会有输出
    	{
    		if (*(p+i)!=0)//如果这个人的头上编号不是0就开始报数加1，这里采用的方法是报数为3的人头上编号重置为0
    		{
    			k++;
    		}
    		if (k==3)
    		{    k=0;    //报数清零，即下一个人从1开始报数
    		    *(p+i)=0;//将报数为3的人编号重置为0
    			 m++;    //退出人数加1
    		}
    		i++;      //指针后移
    		if (i==n)//这句很关键，如果到了队尾，就要使指针重新指向对头
    			//并且它只能放在i++后面，因为只有i++了才有可能i==n
    		{
    			i=0;
    		}
    		
    		
    	}
    	printf("现在剩下的人是:");
    	for (loop=0;loop<n;loop++)
    	{
    		if (num[loop]!=0)
    		{
    			printf("%2d号\n",num[loop]);
    		}
    	}
    	
    }

![1354199746_3295.jpg][]

用链表实现上面的算法：

#include <stdio.h>
    #define N 13    //定义人数
    struct person
    {
    	int num;//人编号
    	int next;
    }link[N+1];//数组长为N+1方便编号
    void main()
    {
    	int i,h;//数组编号
    	int count=0;//记录退出人数
    	//编号
    	for (i=1;i<=N;i++)
    	{
    		if(i==N)
    		link[N].next=1;//最后一个人的地址编号指向第一个人
    		else
    		link[i].next=i+1;//前一个人指向后一个人
    		link[i].num=i;   //编号
    	}	
    	h=N;
    	printf("离开的人是:");
    	while(count<N-1)
    	{int i=0;	
    	 while(i!=3)
    	 { h=link[h].next;
    	   if(link[h].num)//即link[ link[h].next ].num
    		   i++;
    	 }
    	 printf("%3d",link[h].num);
    	 link[h].num=0;//喊3的人编码赋值为0
    	 count++;
    	}
    	printf("最后剩下的人是:\n");
    	for(i=1;i<=N;i++)
    	{
    		if(link[i].num!=0)
    			printf("%d",link[i].num);
    	}
    }

[1354199746_3295.jpg]: https://img-my.csdn.net/uploads/201211/29/1354199746_3295.jpg