目录
一、单向约瑟夫环
1.问题描述
2.list类函数用法
(1)list构造
(2)list iterator迭代器
(3)list容量
(4)list元素访问
(5)list增删查改
(6)list算法操作
3.代码演示
4.结果演示
二、双向约瑟夫环
1.问题描述
2.代码演示
3.结果演示
一、单向约瑟夫环
1.问题描述
约瑟夫生者死者游戏的大意是:30个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免遇难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第一个人开始,依次报数,数到第9人,便把他投入大海中,然后从他的下一个人数起,数到第9人,再将他投入大海,如此循环,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。
为了解决这一问题,可以用长度为30的数组作为线性存储结构,并把该数组看成是一个首尾相接的环形结构,那么每投入大海一个乘客,就要在该数组的相应位置做一个删除标记,该单元以后就不再作为计数单元。这样做不仅算法较为复杂,而且效率低,还要移动大量的元素。用单循环链表解决这一问题,实现的方法相对要简单得多。首先要定义链表结点,单循环链表的结点结构与一般的结点结构完全相同,只是数据域用一个整数来表示位置;然后将它们组成具有30个结点的单循环链表。接下来从位置为1的结点开始数,数到第8个结点,就将下一个结点从循环链表中删去,然后再从删去结点的下一个结点开始数起,数到第8个结点,再将其下一个结点删去,如此进行下去,直到剩下15个结点为止。
为了不失一般性,将30改为一个任意输入的正整数n,而报数上限(原为9)也为一个任选的正整数m。并且我们知道C++中有STL库可以调用list类进行链表的各种操作,所以代码就能变得很精炼。下面先来介绍一下list类的函数用法。
2.list类函数用法
(1)list构造
构造函数 | 接口说明 |
---|
list() | 构造空的list |
list (size_type n, const value_type& val = value_type()) | 构造的list中包含n个值为val的元素 |
list (const list& x) | 拷贝构造函数 |
list (InputIterator first, InputIterator last) | 用[first, last)区间中的元素构造list |
(2)list iterator迭代器
这里的迭代器理解成一个指针,该指针指向list中的某个节点。
函数声明 | 接口类型 |
---|
begin() | 返回第一个元素的迭代器 |
end() | 返回最后一个元素下一个元素的迭代器 |
rbegin() | 返回第一个元素的reverse_iterator,即end位置 |
rend() | 返回最后一个元素下一个位置的reverse_iterator,即begin位置 |
(3)list容量
函数声明 | 接口说明 |
---|
empty() | 检测list是否为空,是返回true,否则返回false |
size() | 返回list中有效节点的个数 |
(4)list元素访问
函数申明 | 接口说明 |
---|
front() | 返回list的第一个节点中值的引用 |
back() | 返回list最后一个节点中值的引用 |
(5)list增删查改
函数声明 | 接口说明 |
---|
push_back() | 尾插 |
push_front() | 头插 |
pop_back() | 尾删 |
pop_front() | 头删 |
insert() | 在pos位置插入值为val的元素 |
erase() | 删除pos位置的元素 |
swap() | 交换两个元素 |
clear() | 清空list中的有效元素 |
(6)list算法操作
函数声明 | 接口说明 |
---|
remove() | 删除指定值的元素 |
reverse() | 反转链表 |
unique() | 去重 |
merge() | 合并两个有序链表 |
sort() | 链表排序 |
3.代码演示
#include<iostream>
#include<list> //list容器的头文件
using namespace std;
int main()
{
int m, n, count=1;//计数器
cout<<"请输入总人数n\n";
cin >> n;
cout<<"请输入数到m退出的数m\n";
cin >> m;
list <int> l;//创建链表
for(int i=1;i<=n;i++)
{
l.push_back(i);
}//对n个元素标号
list<int>::iterator iter = l.begin(); //设置一个迭代器指向头部
cout << "船上的人的编号为:" << endl;
for(iter = l.begin(); iter != l.end(); iter++)
{
cout << *iter << " ";
}
cout << endl;
iter = l.begin(); //让迭代器指向第一个元素
while(l.size() > (n/2))//链表人数如果等于一半人,那么删除操作结束
{
for(int i = 0 ; i < m-1; i++) //迭代器位移m-1次,表示数到m
{
if(iter == --l.end())//如果迭代器指向了链表最后一个元素,即l.end()的前一位,则返回到第一个节点处
{
iter = l.begin();
}
else
{
iter++;//如果迭代器没有指向最后一个元素,那么就正常自增
}
}
cout << "第" << count << "次离开的人的序号是" << *iter << endl;
if(iter != --l.end()) //如果不是最后一个元素,正常删除即可
{
iter = l.erase(iter); //erase()函数返回的是删除元素下一位,这里是防止下一位是end()的情况
}
else
{
l.pop_back(); //如果是最后一个元素的话,直接调用pop_back函数尾删,并且迭代器直接返回到链表第一个节点
iter = l.begin();
}
count++;
}
cout << "船上还剩下的人为:" << endl;
for(iter = l.begin(); iter != l.end(); iter++)
{
cout << *iter << " ";
}
cout << endl;
return 0;
}
4.结果演示
二、双向约瑟夫环
1.问题描述
约瑟夫双向生死游戏是在约瑟夫生者死者游戏的基础上,正向计数后反向计数,然后再正向计数。具体描述如下:30个旅客同乘一条船,因为严重超载,加上风高浪大,危险万分;因此船长告诉乘客,只有将全船一半的旅客投入海中,其余人才能幸免遇难。无奈,大家只得同意这种办法,并议定30个人围成一圈,由第一个人开始,顺时针依次报数,数到第9人,便把他投入大海中,然后从他的下一个人数起,逆时针数到第5人,将他投入大海,然后从他逆时针的下一个人数起,顺时针数到第9人,再将他投入大海,如此循环,直到剩下15个乘客为止。问哪些位置是将被扔下大海的位置。
本游戏的数学建模如下:假设n个旅客排成一个环形,依次顺序编号1,2,…,n。从某个指定的第1号开始,沿环计数,数到第m个人就让其出列,然后从第m+1个人反向计数到m-k+1个人,让其出列,然后从m-k个人开始重新正向沿环计数,再数m个人后让其出列,然后再反向数k 个人后让其出列。这个过程一直进行到剩下q个旅客为止。
本游戏的要求用户输入的内容包括:
1. 旅客的个数,也就是n的值;
2. 正向离开旅客的间隔数,也就是m的值;
3. 反向离开旅客的间隔数,也就是k的值;
4. 所有旅客的序号作为一组数据要求存放在某种数据结构中。
本游戏要求输出的内容是包括
1. 离开旅客的序号;
2. 剩余旅客的序号;
所以,根据上面的模型分析及输入输出参数分析,可以定义一种数据结构后进行算法实现。
约瑟夫双向生死游戏如果用单循环链表作为线性存储结构,就只能正向计数结点,反向计数比较困难,算法较为复杂,而且效率低。用双向循环链表解决这一问题,实现的方法相对要简单得多。
为了不失一般性,将30改为一个任意输入的正整数n,而正向报数上限(原为9)也为一个任选的正整数m,正向报数上限(原为5)也为一个任选的正整数k。
2.代码演示
#include<iostream>
#include<list>//list容器的头文件
using namespace std;
int main()
{
int m, n, k, count=1;//计数器
cout<<"请输入总人数n\n";
cin >> n;
cout<<"请输入顺时针报数的数m:\n";
cin >> m;
cout<<"请输入逆时针报数的数k:\n";
cin >> k;
list <int> l;//创建链表
for(int i=1;i<=n;i++)
{
l.push_back(i);
}//对n个元素标号
list<int>::iterator iter = l.begin(); //设置一个迭代器指向头部
cout << "船上的人的序号为:" << endl;
for(iter = l.begin(); iter != l.end(); iter++)
{
cout << *iter << " ";
}
cout << endl;
iter = l.begin(); //让迭代器指向第一个元素
while(l.size() > (n / 2))//链表人数如果等于一半人,那么删除操作结束
{
for(int i = 0 ; i < m-1; i++) //迭代器向后位移m-1次,表示数到m
{
if(iter == --l.end())//如果迭代器指向了链表最后一个元素,即l.end()的前一位,则返回到第一个节点处
{
iter = l.begin();
}
else
{
iter++;//如果迭代器没有指向最后一个元素,那么就正常自增
}
}
iter++; //顺时针数完从他的后一个开始逆时针报数
for(int i = 0 ; i < k-1; i++) //迭代器向前位移k-1次,表示数到k
{
if(iter == l.begin())//如果迭代器指向了链表的头结点,即l.begin,则返回到尾节点处
{
iter = --l.end();
}
else
{
iter--;//如果迭代器没有指向头结点,那么就正常自减
}
}
cout << "第" << count << "次离开的人的序号是" << *iter << endl;
if(iter != --l.end()) //如果不是最后一个元素,正常删除即可
{
iter = l.erase(iter); //erase()函数返回的是删除元素下一位,这里是防止下一位是end()的情况
iter--; //(删除完后下一轮要从前一个元素开始正向报数)
}
else
{
l.pop_back(); //如果是最后一个元素的话,直接调用pop_back函数尾删,并且迭代器直接返回到链表尾节点
iter = l.end(); //(删除完后下一轮要从前一个元素开始正向报数)
}
count++;
}
cout << "船上还剩下的人为:" << endl;
for(iter = l.begin(); iter != l.end(); iter++)
{
cout << *iter << " ";
}
cout << endl;
return 0;
}
3.结果演示
本文内容由网友自发贡献,版权归原作者所有,本站不承担相应法律责任。如您发现有涉嫌抄袭侵权的内容,请联系:hwhale#tublm.com(使用前将#替换为@)