什么是约瑟夫环问题？
约瑟夫问题是个有名的问题：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_OBJECTpublic: 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);}