约瑟夫问题与STL容器动态数组vector(C++)"/>
详解约瑟夫问题与STL容器动态数组vector(C++)
目录
一、STL容器vector
1.前言
2.vector定义示例
3.vector常用操作
二、约瑟夫问题
问题描述
解题思路
完整代码
运行结果
一、STL容器vector
1.前言
数组是基本的数据结构,有静态数组与动态数组两大类。在算法竞赛中,有一个编码习惯:如果空间足够,优先考虑使用静态数组,而不用指针去管理动态数组,这样既简单且不易出错。但如果空间紧张,便可以使用STL库中的容器vector来建立一个动态数组,既节约空间且不易出错。
vector是STL的动态数组,在运行时能够根据运行时的需要来改变数组的大小,并且里面包含了很多关于数组的常用操作,我们只需调用即可,不用再自己编写,这样既节省时间,也不易出错。由于它是数组,所以其地址是连续的,所以查找非常迅速,可以在常数时间内完成,其算法的复杂度为O(n)。但是对其进行删除与插入操作时会造成内存块的复制。另外,如果数组后面空间不过偶,则需要重新申请一块足够大的内存。这些事数组存储结构所无法避免的,会影响vector的效率
2.vector定义示例
3.vector常用操作
二、约瑟夫问题
问题描述
约瑟夫问题也称为“圆桌问题”,具体描述如下:
圆桌边上围坐着2n个人。其中n个是好人,n个是坏人。现规定,从第一个人开始数,当数到第m个人时立即赶走此人;然后从被赶走的人之后继续开始数,再将数到第m个人立即赶走,如此反复,用这一方法不断赶走围坐在圆桌边上的人。
问:预先应该如何安排好人与坏人的座位,才能使得在赶走n个人之后围桌边围坐的人全是好人?
输入格式
多组数据,每组输入:n,m<=32767
输出格式
对于每一组数据,输出2n个大写字母。
“G”表示好人,“B”表示坏人。50个字母为一行
不允许出现空白字符,且相邻数据间留有一个空行
样例输入
2 3
2 4
样例输入
GBBG
BGGB
解题思路
因为圆桌上的人是不断变化的,故可以使用动态数组vector来模拟圆桌。圆桌是一个环模型,所以通过位置变量加上规定所数的数m再减去一(减去一是因为要对应数组的下标,其是从0开始的)然后对数组的大小取余,则余数位置即为要删除的元素,即坏人位置。最后遍历所有下标,根据数组中所剩元素(即剩下的好人)的下标来打印座位顺序。代码如下:
完整代码
//约瑟夫问题,即圆桌问题
#include<bits/stdc++.h>
using namespace std;
int main(){vector <int> table;//建立动态数组,模拟圆桌int n,m,i;//多组输入,只要有输入则循环将继续进行 while(cin>>n>>m){table.clear();//先清空数组 for(i=0;i<2*n;i++){table.push_back(i);//初始化动态数组 }int pos=0;//位置变量for(i=0;i<n;i++){pos=(pos+m-1)%table.size();//因为圆桌是一个环,,所以通过取余处理来得到坏人的位置下标 table.erase(table.begin()+pos);//删除坏人 } //开始打印预先座位顺序安排表int j=0;for(i=0;i<2*n;i++){if(!(i%50)&&i)cout<<endl;if(j<table.size()&&i==table[j]){cout<<"G";j++;}elsecout<<"B";} cout<<endl;}return 0;
}
运行结果
文章到此结束,如果有所收获,不妨点个赞哦~
更多推荐
详解约瑟夫问题与STL容器动态数组vector(C++)
发布评论