什么是约瑟夫环问题?
约瑟夫问题是个有名的问题:N个人围成一圈,从第一个开始报数,第M个将被杀掉,最后剩下一个,其余人都将被杀掉。例如N=6,M=5,被杀掉的顺序是:5,4,6,2,3。
分析:
(1)由于对于每个人只有死和活两种状态,因此可以用布尔型数组标记每个人的状态,可用true表示死,false表示活。
(2)开始时每个人都是活的,所以数组初值全部赋为false。
(3)模拟杀人过程,直到所有人都被杀死为止。
魔术
1、4张牌对折后撕开,就是8张,叠放在一起就是ABCDABCD。注意,ABCD四个数字是完全等价的。
2、根据名字字数,把顶上的牌放到下面,但怎么放都不会改变循环序列的相对位置。譬如2次,最后变成CDABCDAB;譬如3次,最后换成DABCDABC。但无论怎么操作,第4张和第8张牌都是一样的。
3、把顶上3张插到中间任意位置。这一步非常重要!因为操作完之后必然出现第1张和第8张牌是一样的!以名字两个字为例,可以写成BxxxxxxB(这里的x是其他和B不同的牌)。
4、拿掉顶上的牌放到一边,记为B。剩下的序列是xxxxxxB,一共7张牌。
5、南方人/北方人/不确定,分别拿顶上的1/2/3张牌插到中间,但是不会改变剩下7张牌是xxxxxxB的结果。
6、男生拿掉1张,女生拿掉2张。也就是男生剩下6张,女生剩下5张。分别是xxxxxB和xxxxB。
7、把最顶上的放到最底下,循环7次,男生和女生分别会是xxxxBx和xxBxx。
8、最后执行约瑟夫环过程!操作到最后只剩下1张。当牌数为6时(男生),剩下的就是第5张牌;当牌数为5时(女生),剩下的就是第3张牌。就是第4步拿掉的那张牌!
.h
#ifndef WIDGET_H
#define WIDGET_H
#include <QWidget>
#include <vector>
#include "brand.h"
#include <QPushButton>
#include <QRadioButton>
#include <QLineEdit>
#include <QLayout>
#include <QStackedWidget>
#include <QSplitter>
#include <QButtonGroup>
class Step: public QWidget
{
public:
Step(QWidget *parent = 0):QWidget(parent){
QVBoxLayout* vbox = new QVBoxLayout(this);
QHBoxLayout* hboxLabel = new QHBoxLayout;
hboxChoose = new QHBoxLayout;
QHBoxLayout* hboxBtn = new QHBoxLayout;
label = new QLabel(this);
hboxLabel->addStretch();
hboxLabel->addWidget(label);
hboxLabel->addStretch();
hboxBtn->addStretch();
vbox->addLayout(hboxLabel);
vbox->addLayout(hboxChoose);
vbox->addLayout(hboxBtn);
}
void SetText(QString text){
label->setText(text);
}
QHBoxLayout* GetChooseLayout(){
return hboxChoose;
}
virtual bool Check() {
return true;
}
private:
QLabel* label;
QHBoxLayout* hboxChoose;
};
class Start: public Step
{
public:
Start(QWidget *parent = 0):Step(parent)
{
SetText("请输入四个数字、字母或汉字");
edit = new QLineEdit(this);
edit->setPlaceholderText("请输入四个数字、字母或汉字");
GetChooseLayout()->addWidget(edit);
}
QString GetStr(){
return edit->text();
}
bool Check() {
return edit->text().size() == 4;
}
private:
QLineEdit* edit;
};
class First: public Step
{
public:
First(QWidget *parent = 0):Step(parent)
{
SetText("4张牌对折后撕开");
}
};
class Second: public Step
{
public:
Second(QWidget *parent = 0):Step(parent)
{
SetText("请输入您的名字");
edit = new QLineEdit(this);
edit->setPlaceholderText("请输入您的名字");
GetChooseLayout()->addWidget(edit);
}
int GetNumber(){
return edit->text().size();
}
bool Check() {
return edit->text().size() > 0;
}
private:
QLineEdit* edit;
};
class Third: public Step
{
public:
Third(QWidget *parent = 0):Step(parent)
{
SetText("把顶上3张插到中间任意位置");
radio = new QRadioButton("第一张后面",this);
radio1 = new QRadioButton("第二张后面",this);
radio2 = new QRadioButton("第三张后面",this);
radio3 = new QRadioButton("第四张后面",this);
GetChooseLayout()->addWidget(radio);
GetChooseLayout()->addWidget(radio1);
GetChooseLayout()->addWidget(radio2);
GetChooseLayout()->addWidget(radio3);
radio->setChecked(true);
}
int GetChoose(){
if(radio->isChecked())
return 1;
if(radio1->isChecked())
return 2;
if(radio2->isChecked())
return 3;
if(radio3->isChecked())
return 4;
return 1;
}
private:
QRadioButton* radio;
QRadioButton* radio1;
QRadioButton* radio2;
QRadioButton* radio3;
};
class Four: public Step
{
public:
Four(QWidget *parent = 0):Step(parent)
{
SetText("拿掉顶上的牌放到一边");
}
};
class Five: public Step
{
public:
Five(QWidget *parent = 0):Step(parent)
{
SetText("南方人/北方人/不确定,分别拿顶上的1/2/3张牌插到中间");
QVBoxLayout* vbox = new QVBoxLayout;
QHBoxLayout* hbox = new QHBoxLayout;
QHBoxLayout* hbox1 = new QHBoxLayout;
QButtonGroup* group = new QButtonGroup(this);
QButtonGroup* group1 = new QButtonGroup(this);
radio = new QRadioButton("南方人",this);
radio1 = new QRadioButton("北方人",this);
radio2 = new QRadioButton("不确定",this);
radio3 = new QRadioButton("第一张后面",this);
radio4 = new QRadioButton("第二张后面",this);
radio5 = new QRadioButton("第三张后面",this);
hbox->addWidget(radio);
hbox->addWidget(radio1);
hbox->addWidget(radio2);
hbox1->addWidget(radio3);
hbox1->addWidget(radio4);
hbox1->addWidget(radio5);
group->addButton(radio);
group->addButton(radio1);
group->addButton(radio2);
group1->addButton(radio3);
group1->addButton(radio4);
group1->addButton(radio5);
vbox->addLayout(hbox);
vbox->addLayout(hbox1);
GetChooseLayout()->addLayout(vbox);
radio2->setChecked(true);
radio3->setChecked(true);
}
int GetChoose(){
if(radio->isChecked())
return 1;
else if(radio1->isChecked())
return 2;
else if(radio2->isChecked())
return 3;
return 1;
}
int GetChoose1(){
if(radio3->isChecked())
return 1;
else if(radio4->isChecked())
return 2;
else if(radio5->isChecked())
return 3;
return 1;
}
private:
QRadioButton* radio;
QRadioButton* radio1;
QRadioButton* radio2;
QRadioButton* radio3;
QRadioButton* radio4;
QRadioButton* radio5;
};
class Six: public Step
{
public:
Six(QWidget *parent = 0):Step(parent)
{
SetText("男生拿掉1张,女生拿掉2张");
radio = new QRadioButton("男生",this);
radio1 = new QRadioButton("女生",this);
GetChooseLayout()->addWidget(radio);
GetChooseLayout()->addWidget(radio1);
radio->setChecked(true);
}
int GetChoose(){
if(radio->isChecked())
return 1;
if(radio1->isChecked())
return 2;
return 1;
}
private:
QRadioButton* radio;
QRadioButton* radio1;
};
class Seven: public Step
{
public:
Seven(QWidget *parent = 0):Step(parent)
{
SetText("把最顶上的放到最底下,循环7次");
}
};
class Last: public Step
{
public:
Last(QWidget *parent = 0):Step(parent){
SetText("好运留下来");
flag = 1;
}
void Init(){
SetText("好运留下来");
flag = 1;
}
void ChangeText(){
switch(flag){
case 0:
flag = 1;
SetText("好运留下来");
break;
case 1:
flag = 0;
SetText("烦恼都丢掉");
break;
default:
break;
}
}
int GetFlag(){
return flag;
}
private:
int flag;
};
class Widget : public QSplitter
{
Q_OBJECT
public:
Widget(QWidget *parent = 0);
~Widget();
private:
void StartGetData();
void FirstStep();
void SecondStep();
void ThridStep();
void FourStep();
void FiveStep();
void SixStep();
void SevenStep();
void LastStep();
void UpdateData();
protected slots:
void OnClicked(bool);
private:
std::vector<Brand*> m_vecBrand;
QString m_firstCard;
QLabel* label;
QPushButton* btn;
QStackedWidget* m_stackedWidget;
bool bOver;
};
#endif // WIDGET_H
.cpp
#pragma execution_character_set("utf-8")
#include "widget.h"
#include <QDebug>
Widget::Widget(QWidget *parent)
: QSplitter(parent)
{
setOrientation(Qt::Vertical);
label = new QLabel("qweqwe",this);
QWidget* widget = new QWidget(this);
m_stackedWidget = new QStackedWidget(this);
addWidget(label);
addWidget(widget);
setStretchFactor(1,2);
m_stackedWidget->addWidget(new Start);
m_stackedWidget->addWidget(new First);
m_stackedWidget->addWidget(new Second);
m_stackedWidget->addWidget(new Third);
m_stackedWidget->addWidget(new Four);
m_stackedWidget->addWidget(new Five);
m_stackedWidget->addWidget(new Six);
m_stackedWidget->addWidget(new Seven);
m_stackedWidget->addWidget(new Last);
QHBoxLayout* hbox = new QHBoxLayout;
QVBoxLayout* vbox = new QVBoxLayout;
btn = new QPushButton("下一步",this);
hbox->addStretch();
hbox->addWidget(btn);
vbox->addWidget(m_stackedWidget);
vbox->addLayout(hbox);
widget->setLayout(vbox);
connect(btn, SIGNAL(clicked(bool)), this, SLOT(OnClicked(bool)));
bOver = false;
}
Widget::~Widget()
{
}
void Widget::StartGetData()
{
Start* start = (Start*)m_stackedWidget->widget(0);
QString str = start->GetStr();
for(int i=0; i<str.length(); i++){
Brand* brand = new Brand(QString(str[i]));
m_vecBrand.push_back(brand);
}
}
void Widget::FirstStep()
{
Start* start = (Start*)m_stackedWidget->widget(0);
QString str = start->GetStr();
for(int i=0; i<str.length(); i++){
Brand* brand = new Brand(QString(str[i]));
m_vecBrand.push_back(brand);
}
}
void Widget::SecondStep()
{
Second* second = (Second*)m_stackedWidget->widget(2);
int number = second->GetNumber();
for(int i=0; i<number; i++){
Brand* brand = m_vecBrand[0];
m_vecBrand.erase(m_vecBrand.begin());
m_vecBrand.push_back(brand);
}
}
void Widget::ThridStep()
{
Third* third = (Third*)m_stackedWidget->widget(3);
int number = third->GetChoose();
Brand* brand = m_vecBrand[0];
Brand* brand1 = m_vecBrand[1];
Brand* brand2 = m_vecBrand[2];
m_vecBrand.erase(m_vecBrand.begin());
m_vecBrand.erase(m_vecBrand.begin());
m_vecBrand.erase(m_vecBrand.begin());
std::vector<Brand*> vecBrand;
for(int i=0; i<m_vecBrand.size(); i++){
vecBrand.push_back(m_vecBrand[i]);
if(number == i + 1){
vecBrand.push_back(brand);
vecBrand.push_back(brand1);
vecBrand.push_back(brand2);
}
}
m_vecBrand = vecBrand;
}
void Widget::FourStep()
{
m_firstCard = m_vecBrand[0]->GetStr();
setWindowTitle("当前选择牌为:"+ m_firstCard);
m_vecBrand.erase(m_vecBrand.begin());
}
void Widget::FiveStep()
{
Five* five = (Five*)m_stackedWidget->widget(5);
int number = five->GetChoose();
int number1 = five->GetChoose1();
std::vector<Brand*> vecBrand;
switch (number) {
case 1:
vecBrand.push_back(m_vecBrand[0]);
m_vecBrand.erase(m_vecBrand.begin());
break;
case 2:
vecBrand.push_back(m_vecBrand[0]);
vecBrand.push_back(m_vecBrand[1]);
m_vecBrand.erase(m_vecBrand.begin());
m_vecBrand.erase(m_vecBrand.begin());
break;
case 3:
vecBrand.push_back(m_vecBrand[0]);
vecBrand.push_back(m_vecBrand[1]);
vecBrand.push_back(m_vecBrand[2]);
m_vecBrand.erase(m_vecBrand.begin());
m_vecBrand.erase(m_vecBrand.begin());
m_vecBrand.erase(m_vecBrand.begin());
break;
default:
break;
}
std::vector<Brand*> vecBrand1;
for(int i=0; i<m_vecBrand.size(); i++){
vecBrand1.push_back(m_vecBrand[i]);
if(number1 == i + 1){
vecBrand1.insert(vecBrand1.end(), vecBrand.begin(), vecBrand.end());
}
}
m_vecBrand = vecBrand1;
}
void Widget::SixStep()
{
Six* six = (Six*)m_stackedWidget->widget(5);
int number = six->GetChoose();
switch (number) {
case 1:
m_vecBrand.erase(m_vecBrand.begin());
break;
case 2:
m_vecBrand.erase(m_vecBrand.begin());
m_vecBrand.erase(m_vecBrand.begin());
break;
default:
break;
}
}
void Widget::SevenStep()
{
for(int i=0; i<7; i++){
Brand* brand = m_vecBrand[0];
m_vecBrand.erase(m_vecBrand.begin());
m_vecBrand.push_back(brand);
}
}
void Widget::LastStep()
{
Last* last = (Last*)m_stackedWidget->widget(8);
int flag = last->GetFlag();
switch (flag) {
case 0:
m_vecBrand.erase(m_vecBrand.begin());
break;
case 1:
Brand* brand = m_vecBrand[0];
m_vecBrand.erase(m_vecBrand.begin());
m_vecBrand.push_back(brand);
break;
}
last->ChangeText();
}
void Widget::UpdateData()
{
QString str;
for(int i=0; i<m_vecBrand.size(); i++){
str+= m_vecBrand[i]->GetStr();
}
label->setText(str);
}
void Widget::OnClicked(bool)
{
if(bOver){
setWindowTitle("magic");
Last* last = (Last*)m_stackedWidget->widget(8);
last->Init();
bOver = false;
btn->setText("下一步");
m_stackedWidget->setCurrentIndex(0);
return;
}
Step* step = (Step*)m_stackedWidget->currentWidget();
if(!step->Check())
return;
if(m_vecBrand.size() == 1){
m_vecBrand.clear();
Last* last = (Last*)m_stackedWidget->widget(8);
last->SetText("之前的牌为:"+ m_firstCard+ " 对上否?");
bOver = true;
btn->setText("重新开始");
return;
}
switch (m_stackedWidget->currentIndex()) {
case 0://4张牌
StartGetData();
break;
case 1://对折撕开
FirstStep();
break;
case 2://根据名字字数,把顶上的牌放到下面
SecondStep();
break;
case 3://把顶上3张插到中间任意位置
ThridStep();
break;
case 4://拿掉顶上的牌放到一边
FourStep();
break;
case 5://南方人/北方人/不确定,分别拿顶上的1/2/3张牌插到中间
FiveStep();
break;
case 6://男生拿掉1张,女生拿掉2张
SixStep();
break;
case 7://把最顶上的放到最底下,循环7次
SevenStep();
break;
case 8://好运留下来 烦恼都丢掉
LastStep();
break;
default:
break;
}
UpdateData();
if(m_stackedWidget->currentIndex() + 1 < m_stackedWidget->count())
m_stackedWidget->setCurrentIndex(m_stackedWidget->currentIndex() + 1);
}