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 <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

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303

.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);
}

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261