天天看点

报数游戏是这样的:有n个人围成一圈,按顺序从1到n编好号。从第一个人开始报数,报到m的人退出圈子;下一个人从1开始报数,报到m的人退出圈子。如此下去,如此反复到所有人出列。

报数游戏是这样的:有n个人围成一圈,按顺序从1到n编好号。从第一个人开始报数,报到m(<n)的人退出圈子;下一个人从1开始报数,报到m的人退出圈子。如此下去,如此反复到所有人出列。设n个人的编号分别为1,2,……n,打印出列的顺序。

【算法分析】

本题可以采用建立标志位的方法求解,但如果使用循环链的思想,则解题效率更高。n个人围城一圈,把一个人看成一个节点,n个人采用链接方式,即每一个节点有一个前继节点和后继节点,每一个节点有一个指针指向下一个节点,最后一个节点的指针指向第一个节点。这就是单链循环的数据结构。当m个人出列时,将m的前继节点指针指向m节点的后继指针节点,即把m节点驱出循环链。

1.建立循环链表

当用数组实现本体链式结构时,数组a【i】作为“指针”变量来使用,a[i]存放下一个节点的位置。

设立指针j指向当前节点,则移动节点过程为j=a[i],当数到m时,m节点出链,则a[j]=a[a[j]]。

2.设立指针,指向当前节点,设立计数器,计数数到多少人。

3.沿链移动指针,每移动一个节点,计数器的值加一,当计数器的值为m时,则m节点出链,计数器的值置为1.

4.重复3,直到n个节点出链为止。

【代码如下】

#include<iostream>
using namespace std;
const int n=10,m=4;//设有十个人,报到4的人出列 
int a[n+1],j=n,k=1,p=0;
int main()
{
	for(int i=1;i<n;i++)
		a[i]=i+1;   //建立链表 
	a[n]=1;   //第n个人指向第1个人  ,形成一个环 
	while(p<n)   //n个人均出列为止 
	{
		while(k<m)   //报数   计数器加一  
		{
			j=a[j];
			k++;
		}
		printf("%d",a[j]);  //数到m此人出列  计数器置一 
		p++;  //出列人数加一 
		a[j]=a[a[j]];
		k=1;
	}
	return 0;
}