dhu编程练习

8 圆桌问题

1.问题描述
目的：使用C++模板设计循环链表的抽象数据类型（ADT）。并在此基础上，使用循环链表ADT的基本操作，设计并实现单链表的简单算法设计。

内容：（1）请使用模板设计循环链表的抽象数据类型。（由于该环境目前仅支持单文件的编译，故将所有内容都集中在一个源文件内。在实际的设计中，推荐将抽象类及对应的派生类分别放在单独的头文件中。参考网盘中的单链表ADT原型文件，自行设计循环链表的ADT。）

（2）ADT的简单应用：使用该ADT设计并实现循环链表应用场合的一些简单算法设计。

圆桌上围坐着2n个人。其中n个人是好人，另外n个人是坏人。如果从第一个人开始数数，数到第m个人，则立即处死该人；然后从被处死的人之后开始数数，再将数到的第m个人处死……依此方法不断处死围坐在圆桌上的人。试问预先应如何安排这些好人与坏人的座位，能使得在处死n个人之后，圆桌上围坐的剩余的n个人全是好人。
2.输入说明
输入：好人和坏人的人数n（<=32767）、步长m（<=50）；
3.输出说明
输出2n个大写字母，‘G’表示好人，‘B’表示坏人，50个字母为一行。
4.范例
输入说明
52 6
输出说明
BGGBGBGGBBBBGGGGBBBGBGGBGBBGGBBGBGBBGGGBBBGBGGBBGG
BBGBBGGGGBBBBGGBGGBBGBBGGBGBBGGBBBGGBGGBBGGGBBGBGG
GBGB

5.代码

#include<iostream>
using namespace std;
//约瑟夫问题(圆桌问题)-----使用循环链表
//定义结点
struct node
{
    
	char num;
	int  isGood; //判断是否为好人，isGood==1为好人
	struct node *next;
};

struct node *create(int n ,char num[])//创建带头结点的循环单链表

{
    

	int i;

	struct node *current;//当前插入位置指针

	struct node *tail;//尾指针

	struct node *head;//头指针

	head = (struct node*)malloc(sizeof(struct node));//头结点

	head->next = NULL;

	current = head;//当前位置指针指向头结点

	tail = head;//尾指针也指向头结点

	for (i = 0; i < n; i++)

	{
    
			struct node *p;

			p = (struct node*)malloc(sizeof(struct node));

			p->num = num[i];

			p->isGood = 1;//初始化

			p->next = current->next;

			current->next = p;

			current = p;
	}
	current->next = head;//保证循环链表性质，尾指针指向头结点
	return head;
}

void  arraylist(struct node *head, int n,int m)//n为人数，m为步长 
{
    
	//注：每次数到了步长，则将isGood设置为-1
	struct node *p = head->next;
	int count = 1;
	int len = n;//每淘汰一个bad，就len--
	while (len>0)
	{
    
		if (count == m)//数到步长
		{
    
			if (p->isGood != -1)//是好人
			{
    
				p->isGood = -1;//放坏人
				count = 1;
				len--;
		    }
				p = p->next;
		}

		else if (count < m)
		{
    
			if (p->isGood != -1)//是好人
			{
    
               count++;
			}
			   p = p->next;
		}

		if (p == head)//保证循环链表
			p = p->next;
	}

	//接下来根据isGood进行赋值处理

	struct node *q= head->next;
	int cnt = 1;
	while (q != head)
	{
    
		if (q->isGood == -1)
		{
    
			q->num = 'B';
		}
		if (cnt == 50)
		{
    
			cout << q->num << endl;
			cnt = 1;//这边注意输出格式为50个一行
		}
		else
		{
    
          cout << q->num;
		  cnt++;
		}
		q = q->next;
	}	
}



int main()

{
    
	int n, m;//n为人数，m为步长 n<=32767
	cin >> n >> m;
	int len = 2 * n;
	char arr[70000];//此处arr[len]编译不能通过
	for (int i = 0; i < len; i++)
	{
    
		arr[i] = 'G';//初始化均为好人
	}

	struct node * list = create(len, arr); //注意总链表长度为len，即2*n
	arraylist(list, n, m);//这里保证最后的人数为n个好人
	return 0;
}