算法学习001-圆桌问题中小学算法思维学习信奥算法解析 c++实现

算法学习001-圆桌问题

一、题目要求

1、编程实现

2、输入输出

二、算法分析

三、程序编写

四、程序说明

五、运行结果

六、考点分析

七、推荐资料

算法学习001-圆桌问题

一、题目要求

1、编程实现

圆桌边围坐着2n个人，其中n个人是好人，另外n个人是坏人。从第一个人开始数，数到第m个人，立即赶走该人；然后从被赶走的人之后开始数，再将数到的第m个人赶走，依此方法不断赶走围坐在圆桌边的人

预先应该如何安排这些好人与坏人的座位，才能使得在赶走n个人之后圆桌边围坐的剩余的n个人全是好人

2、输入输出

输入描述：多组数据，每组数据输入：n,m <= 32767

输出描述：对于每一组数据，输出2n个大写字母，G是好人，B是坏人，50个字母为一行，不允许出现空白字符，相邻数据间留有一个空行

输入样例：

2 3

2 4

输出样例：

GBBG

BGGB

二、算法分析

本题的解题思路有多种
这里使用动态数组的方式实现
首先实现一个2n的动态数组并进行编号
接着依次赶走n个坏人，要注意是圆桌所以需要赶走的坏人要考虑循环处理
然后再次对2n个编号进行遍历，和动态数组中留下来的编号一致的就是好人
否则就是坏人，按要求输出对应字母即可

三、程序编写

#include<bits/stdc++.h>
using namespace std;
int main()
{
	vector <int> table;
	int n,m;
	while(cin >> n >> m)
	{
		table.clear();
		for(int i=0;i<2*n;i++) table.push_back(i); 	//初始化
		int pos = 0;								//记录当前位置
		for(int i=0;i<n;i++)						//赶走的n个人
		{
			pos = (pos+m-1) % table.size();			//圆桌是一个环 取余处理
			table.erase(table.begin() + pos);		//赶走一个坏人 table人数减1
		}
		int j = 0;
		for(int i=0;i<2*n;i++)						//打印字母
		{
			if(!(i%50) && i) cout << endl;			//50个一行
			if(j < table.size() && i == table[j])	//留下的都是好人
			{
				j++;
				cout << 'G';
			}
			else
				cout << 'B';
		}
		cout << endl << endl;		
	}
	return 0;
}

四、程序说明

程序首先声明了一个vector<int>类型的table变量，用来存储圆桌上的人
然后在一个循环中读取输入的n和m
每次循环都会先清空table，然后通过for循环将2*n个人的编号依次加入到table中
接下来，声明一个变量pos用来记录当前位置，初始值为0
然后使用一个for循环从0到n-1，每次循环都会更新pos的值为(pos+m-1) % table.size()，这一步相当于将pos向后移动m个位置
接着，使用table.erase(table.begin() + pos)函数将table中的第pos个人删除，相当于赶走了一个坏人
最后，通过table.size()来获取table中剩余的人数，并将table中的人与循环变量i对比，如果相等则表示该人是好人，打印字符'G'，否则打印字符'B'。
并且每打印50个字符会换行。程序最后两个endl是为了输出格式的美观。
最后返回0，程序结束

本文作者：小兔子编程作者首页：https://blog.csdn.net/frank2102