约瑟夫环

/*
 *   问题描述:已知n个人（以编号1，2，3...n分别表示）围坐在一张圆桌周围。
 *   从编号为k的人开始报数，数到m的那个人出列；他的下一个人又从1开始报
 *   数，数到m的那个人又出列；依此规律重复下去，直到圆桌周围的人全部出列。
*/
#include<stdio.h>
#include<stdlib.h>
#include<malloc.h>

/*
 * 约瑟夫环结点结构
*/
typedef struct
{
	int data;       //约瑟夫环结点的编号

	int tag;        //标记元素是否已输出(未输出为1，输出为0)

}ring;

/*
 *  创建元素类型为ring的数组，存储约瑟夫环的编号，以及输出标记
 *
 *  sum为约瑟夫环的元素个数
*/
void create_ring(ring **r, int sum)
{
	int i;
	
	if( NULL == (*r = (ring *)malloc(sizeof(sum * sizeof(ring)))) )
		exit(0);

	for(i = 0; i < sum; i++)
	{
		(*r)[i].data = i + 1;
		(*r)[i].tag = 1;
	}

}

/*
 * step为约瑟夫环中元素输出的间隔
 *
 * begin为刚刚开始报数的那个人的编号
*/
void deal_ring(ring *r, int begin, int step, int sum)
{
	int i, p, count;

	p = begin - 1;
	count = 0;

	while(count < sum)
	{
		for(i = 1; i < step; i++)
		{
			p = (++p) % sum;

			if(0 == r[p].tag)     //如果下标p所在的元素已输出,则i退回一步
				--i;
			if(count == sum)     
				break;
		}

		printf("%-4d",r[p].data);
		r[p].tag = 0;

		p = (++p) % sum; 
		count++;
	}
}

int main()
{
	int sum, begin, step;
	ring *r;

	printf("输入约瑟夫环的大小: ");
	scanf("%d",&sum);
	
	printf("输入第一个报数人的编号: ");
	scanf("%d",&begin);

	printf("输入出列间隔: ");
	scanf("%d",&step);

	create_ring(&r, sum);

	deal_ring(r,begin,step,sum);

	return 0;
}