热门标签
热门文章
- 1循序渐进之（五）空间域图像增强之自适应直方图均衡化（AHE）
- 2CentOS 7 升级内核后 kdump 不能启动_systemctl status kdump.service报错initdir not set
- 3[centos7]linux-101-软硬件查看_centos7如何查看光驱
- 4【MATLAB第35期】基于MATLAB的2023年改进的进化算法优化LSTM时间序列预测模型思路_2023进化算法最新
- 5互联网发展简史(2)从ARPANET到Internet_阿帕网怎么变成internet
- 6人工智能-深度学习项目100项
- 7WIFI基础入门--802.11--用户身份验证--7_802.11 aka
- 8使用WPF MaterialDesignInXamlToolkit-3.2.0挖坑之路
- 9搭建Vgg16训练CIFAR10数据集_cif10vgg
- 10如何在HTML界面上显示特殊字符（如尖括号等）_code软件怎么写尖括号
当前位置: article > 正文
C++/Qt 计算24点_c++算24点
作者：菜鸟追梦旅行 | 2024-02-06 19:50:13
赞
踩
c++算24点
C++/Qt 计算24点
游戏的算法可描述如下：4个1-10的数字，用加、减、乘、除和括号把数子算成24，每个数字都必须使用到，且只能用一次。
用C++写会更加的方便：
在这本书中要求了表达式中数字的顺序不能改变，所以在7.7节 中提供的算法不具有普遍适应性，但是算法的思路还是很简单并且清晰。不需要多动脑袋。在他的基础上，可以轻易的扩展成一般的算法。
一些比较难的24点计算
-
1 3 9 10
-
1 4 5 6
-
1 5 5 5
-
2 7 10 10
-
3 3 7 7
-
3 3 8 8
1、用递归分治算法思路及设计
【1】最开始是4个数，A、B、C、D。
【2】从4个数中选择两个数，例如 A 和 B 。
【3】将两个数进行运算，R1 = A OP B
【4】运算结果 R1 和 剩余的数字进行运算，R1、C、D
【5】从三个数中选择任意两个数进行运算
【6】继续运算，只至一个数字
【7】用递归方法，计算结果是否为24 ，很容易，但是要输出一条完整的表达式，很复杂，因为其简单的计算思路，值得笔记下来。表达式应该还有需要深思的地方…
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include <string> #include <map> using namespace std; string ops[] = { "#","+","-","*","/","-","/" }; map <string, vector<string> > maps; static int counts = 3; string num_string( double n ) { char buf[10]; sprintf( buf, "%g", n ); return string( buf ); } double cal( double x, double y, int op ) { switch( op ) { case 1:return x + y; case 2:return x - y; case 3:return x * y; case 4: { if( y == 0 ) return -1000; return x / y; } default: return -1000; } } void findKeys( map <string, vector<string> > &m, string &v ) { map <string, vector<string> >::iterator it; it = m.find( v ); if( it != m.end() && counts > 0 ) { counts--; cout << "("; for( int i = 0; i < 3; i++ ) { findKeys( m, it->second[i] ); } cout << ")"; } else { cout << v; } } bool is24( vector<double> a ) { bool find = false; if( a.size() == 1 ) return fabs( a[0] - 24 ) < 10E-5; for( int i = 0; i < a.size(); i++ ) { vector<double> b( a ); b.erase( b.begin() + i ); for( int j = 0; j < b.size(); j++ ) { vector<double> c( b ); c.erase( c.begin() + j ); for( int op = 1; op <= 4; op++ ) { vector<double> d( c ); double r = cal( a[i], b[j], op ); if( r < 0 ) continue; else d.push_back( r ); if( is24( d ) ) { find = true; vector<string> res; res.push_back( num_string( a[i] ) ); res.push_back( ops[op] ); res.push_back( num_string( b[j] ) ); maps[num_string( r )] = res; return true; } } } } return false; } int main() { vector<double> a( 4, 0 ); while( cin >> a[0] >> a[1] >> a[2] >> a[3] ) { maps.clear(); counts = 3; if( is24( a ) ) { cout << "true" << endl; string s( "24" ); findKeys( maps, s); cout << " = 24" << endl; } else cout << "false" << endl; } }
- 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
2、暴力穷举法
【1】四个数， 穷举 A、B、C、D
【2】三个符号，穷举 ＋、－、×、÷
【3】两种模式
【3.1】组成表达式，（（A OP1 B） OP2 C ） OP3 D
【3.2】组成表达式，（A OP1 B） OP3 （C OP2 D）
【4】注意：减法和除法两个数字交换顺序后，会有不同结果，所以四则运算要分成6种。
对于减法，要检查是否为负数；对于除法，还要检查除数是否为0。
此时每一个数字和符号都已确定，可直接组合成完整的表达式。
#define _CRT_SECURE_NO_WARNINGS #include<iostream> #include<vector> #include <string> #include <map> using namespace std; string ops[] = { "#","+","-","*","/","-","/" }; string num_string( double n ) { char buf[10]; sprintf( buf, "%g", n ); return string( buf ); } double cal( double x, double y, int op ) { switch( op ) { case 1:return x + y; case 2:return x - y; case 3:return x * y; case 4: { if( y == 0 ) return -1000; return x / y; } case 5: return y - x; case 6: { if( x == 0 ) return -1000; return y / x; } default: return -1000; } } bool findString( vector<string> &vec, const string &str ) { for( const string var : vec ) { if( var == str ) return true; } return false; } bool is24( vector<double> a ) { vector < string > results; bool find = false; string res; //可以考虑使用逆波兰表达式，脱去括号，求得最终的表达式，加入表达式集，去除相同的部分 for( int A = 0; A < 4; A++ ) { for( int B = 0; B < 4; B++ ) { if( B == A ) continue; for( int C = 0; C < 4; C++ ) { if( C == A || C == B ) continue; for( int D = 0; D < 4; D++ ) { if( D == A || D == B || D == C ) continue; for( int op1 = 1; op1 <= 4; op1++ ) for( int op2 = 1; op2 <= 6; op2++ ) for( int op3 = 1; op3 <= 6; op3++ ) { double r1 = cal( a[A], a[B], op1 ); // (A op1 B) || (B op1 A) if( r1 < 0 ) continue; double r21 = cal( r1, a[C], op2 ); // (r1 op2 C) || (C op2 r1) double r31 = cal( r21, a[D], op3 ); // (r21 op2 D) || (D op2 r21) if( fabs( r31 - 24 ) < 10E-5 && ( r21 >= 0 ) ) { //cout << "r31\n"; find = true; if( op1 < 5 ) res = "(" + num_string( a[A] ) + ops[op1] + num_string( a[B] ) + ")"; else res = "(" + num_string( a[B] ) + ops[op1] + num_string( a[A] ) + ")"; if( op2 < 5 ) res = "(" + res + ops[op2] + num_string( a[C] ) + ")"; else res = "(" + num_string( a[C] ) + ops[op2] + res + ")"; if( op3 < 5 ) res = res + ops[op3] + num_string( a[D] ); else res = num_string ( a[D] ) + ops[op3] + res; //检查是否有同样的表达式 if( !findString( results, res ) ) results.push_back( res ); else continue; cout << res << "= 24" << endl; } double r22 = cal( a[C], a[D], op2 ); // (C op2 D) || (D op2 C) double r32 = cal( r1, r22, op3 ); // (r1 op2 r22) || (r22 op2 r1) if( fabs( r32 - 24 ) < 10E-5 && ( r22 >= 0 ) ) { find = true; string temp; if( op1 < 5 ) res = "(" + num_string( a[A] ) + ops[op1] + num_string( a[B] ) + ")"; else res = "(" + num_string( a[B] ) + ops[op1] + num_string( a[A] ) + ")"; if( op2 < 5 ) temp = "(" + num_string( a[C] ) + ops[op2] + num_string( a[D] ) + ")"; else temp = "(" + num_string( a[D] ) + ops[op2] + num_string( a[C] ) + ")"; if( op3 < 5 ) res = res + ops[op3] + temp; else res = temp + ops[op3] + res; //检查是否有同样的表达式 if( !findString( results, res ) ) results.push_back( res ); else continue; cout << res << "= 24" << endl; } } } } } } if( !find ) { cout << "Sorry ,无法计算\n"; return false; } else return true; } int main() { vector<double> a( 4, 0 ); while( cin >> a[0] >> a[1] >> a[2] >> a[3] ) { is24( a ); } }
- 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
3、Qt 图片
#include "Widget.h" #include <QtWidgets> QString ops[] = { "#","+","-","*","/","-","/" }; int num[] = { 0,1,7,5,10 }; int idx = 0; Widget::Widget(QWidget *parent) : QWidget(parent) { QPalette palette; palette.setColor(QPalette::Window,Qt::red); QHBoxLayout *labsLayout = new QHBoxLayout; for (int i = 0; i < 4; ++i) { labs[i] = new QLabel; labs[i]->setAutoFillBackground(true); labs[i]->setPalette(palette); labs[i]->setFrameStyle(QFrame::Panel ); labs[i]->setAlignment(Qt::AlignCenter); labs[i]->setMinimumHeight(50); labs[i]->setMargin(10); labsLayout->addWidget(labs[i]); } QGridLayout *btnsLayout = new QGridLayout; for (int i = 0; i < 10; ++i) { QPushButton *btn = new QPushButton(QString::number(i+1)); connect(btn,&QPushButton::clicked,[=](){ labs[idx]->setText(btn->text()); idx +=1; if(idx==1){ for (int i = 1; i < 4; ++i) { labs[i]->setText(""); } edit->clear(); } if(idx==4){ idx %= 4; get24(); } }); btnsLayout->addWidget(btn,i/5,i%5); } edit = new QTextEdit; edit->setReadOnly(true); QVBoxLayout *mainLayout = new QVBoxLayout(this); mainLayout->addLayout(labsLayout); mainLayout->addWidget(edit); mainLayout->addLayout(btnsLayout); } double Widget::cal(double x, double y, int op) { switch( op ) { case 1:return x + y; case 2:return x - y; case 3:return x * y; case 4: { if( y == 0 ) return -1000; return x / y; } case 5: return y - x; case 6: { if( x == 0 ) return -1000; return y / x; } default: return -1000; } } bool Widget::findString(QVector<QString> &vec, const QString &str) { for( const QString var : vec ) { if( var == str ) return true; } return false; } void Widget::get24() { num[1] = labs[0]->text().toInt(); num[2] = labs[1]->text().toInt(); num[3] = labs[2]->text().toInt(); num[4] = labs[3]->text().toInt(); QVector < QString > results; bool find = false; QString res; //可以考虑使用逆波兰表达式，脱去括号，求得最终的表达式，加入表达式集，去除相同的部分 for( int A = 1; A <= 4; A++ ) { for( int B = 1; B <= 4; B++ ) { if( B == A ) continue; for( int C = 1; C <= 4; C++ ) { if( C == A || C == B ) continue; for( int D = 1; D <= 4; D++ ) { if( D == A || D == B || D == C ) continue; for( int op1 = 1; op1 <= 4; op1++ ) for( int op2 = 1; op2 <= 6; op2++ ) for( int op3 = 1; op3 <= 6; op3++ ) { double r1 = cal( num[A], num[B], op1 ); // (A op1 B) || (B op1 A) if( r1 < 0 ) continue; double r21 = cal( r1, num[C], op2 ); // (r1 op2 C) || (C op2 r1) double r31 = cal( r21, num[D], op3 ); // (r21 op2 D) || (D op2 r21) // if( r31 == 24 && ( r21 >= 0 ) ) if( qAbs(r31 - 24)<10E-5 && ( r21 >= 0 ) ) { //cout << "r31\n"; find = true; if( op1 < 5 ) res = "(" + QString::number( num[A] ) + ops[op1] + QString::number( num[B] ) + ")"; else res = "(" + QString::number( num[B] ) + ops[op1] + QString::number( num[A] ) + ")"; if( op2 < 5 ) res = "(" + res + ops[op2] + QString::number( num[C] ) + ")"; else res = "(" + QString::number( num[C] ) + ops[op2] + res + ")"; if( op3 < 5 ) res = res + ops[op3] + QString::number( num[D] ); else res = QString::number( num[D] ) + ops[op3] + res; //检查是否有同样的表达式 if( !findString( results, res ) ) results.push_back( res ); else continue; // qDebug() << res << "= 24" ; edit->append(res+" = 24"); } double r22 = cal( num[C], num[D], op2 ); // (C op2 D) || (D op2 C) double r32 = cal( r1, r22, op3 ); // (r1 op2 r22) || (r22 op2 r1) if( qAbs(r32 - 24)<10E-5 && ( r22 >= 0 ) ) { find = true; QString temp; if( op1 < 5 ) res = "(" + QString::number( num[A] ) + ops[op1] + QString::number( num[B] ) + ")"; else res = "(" + QString::number( num[B] ) + ops[op1] + QString::number( num[A] ) + ")"; if( op2 < 5 ) temp = "(" + QString::number( num[C] ) + ops[op2] + QString::number( num[D] ) + ")"; else temp = "(" + QString::number( num[D] ) + ops[op2] + QString::number( num[C] ) + ")"; if( op3 < 5 ) res = res + ops[op3] + temp; else res = temp + ops[op3] + res; //检查是否有同样的表达式 if( !findString( results, res ) ) results.push_back( res ); else continue; // qDebug() << res << "= 24"; edit->append(res+" = 24"); } } } } } } if( !find ) edit->append("Sorry ,无法计算") ; else edit->moveCursor(QTextCursor::Start); }
- 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
有感兴趣的 可以直接下载 0 积分
https://download.csdn.net/download/hitzsf/85750810, 0积分下载
声明：本文内容由网友自发贡献，不代表【wpsshop博客】立场，版权归原作者所有，本站不承担相应法律责任。如您发现有侵权的内容，请联系我们。转载请注明出处：https://www.wpsshop.cn/w/菜鸟追梦旅行/article/detail/64321
推荐阅读
相关标签
