【Josephus环问题】

（一） 问题描述

1. 功能要求：建立一个循环表，声明入队出队算法，然后在主函数中使用
2. 输入输出要求：用c++的方式正确输入输出；
3. 测试数据样例 n=10;k=3;

(二)算法结构分析与设计

1. 算法中抽象数据类型定义：定义了出对入队方法
2. 算法主要思路：在主函数体外声明定义了一个循环列表和一个出队入队函数，然后在main()函数里用for循环实现入队出队操作

#include
#include
#include
using namespace std;
#define MAXSIZE 100
typedef struct
{
	int data[MAXSIZE];
	int front1, rear;
	int num;
}CS;             //定义了一个循环队列
CS* Init_S()
{
	CS* q;
	q = (CS*)malloc(sizeof(CS));
	q->front1 = q->rear = MAXSIZE - 1;
	q->num = 0;
	return q;
}                    //构建一个空的循环列表
void AddQ(CS* q, int x)
{
	if (q->num == MAXSIZE)
	{
		cout << "队满";
		return;
	}
	else
	{
		q->rear = (q->rear + 1) % MAXSIZE;
		q->data[q->rear] = x;
		q->num++;
		return;
	}
}                //循环队入队
void DeleteQ(CS* q, int& x)
{
	if (q->num == 0)
	{
		printf("队空");
		return;
	}
	else
	{
		q->front1 = (q->front1 + 1) % MAXSIZE;         //引用传递的作用:改变main()中变量的值
		x = q->data[q->front1];            //相当于存储被删掉的元素
		q->num--;
	}
}            //出队操作
int main()
{
	int n, k;
	int i = 1, a;
	cin >> n;
	cin >> k;
	CS* p = Init_S();            //得定义一个变量
	for (i = 1;i <= n;i++)
	{
		AddQ(p, i);
	}
	i = 1;
	while (n > 1)
	{
		DeleteQ(p, a);           //先进行遍历，如果是3的倍数输出出队，否则入队
		if (i % k == 0)
		{
			n--;
			i++;
			cout << a << " ";
			continue;
		}
		else
		{
			AddQ(p, a);               
			i++;
		}
	}
	return 0;
}