Qt C++春晚刘谦魔术约瑟夫环问题的模拟程序

什么是约瑟夫环问题？

约瑟夫问题是个有名的问题：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 #include #include "brand.h"#include #include #include #include #include #include #include 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 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);}