24点是一种老少皆宜的游戏,它的具体玩法如下:
给玩家4张牌,每张牌的面值都在1---13之间,允许其中有数值相同的牌。采用加、减、乘、除四则运算,允许中间运算存在小数,并且可以使用括号,但每张牌只能使用一次,尝试构造一个多项式,使其运算结果为24.
输入:n1,n2,n3,n4。
输出:若能得到运算结果为24,则输出一个对应的计算表达式。
输入:11,8,3,5
输出:(11-8)*(3+5) = 24
分析与解法
最直接的想法就是采用穷举法,因为运算符号只有4种,每个数字只能使用一次,所以通过穷举4个数所有可能的表达式,并分别计算出各表达式的值,就可以得到答案。那么如何穷举所有可能的表达式呢?
先不考虑使用括号,可以做出如下分析:
每个数只能使用一次,对4个整数进行全排列,总共有4!=4*3*2*1=24中排列。4个数的四则运算中总共需要3个运算符,同一运算符可以重复出现,那么对于每一个排列,总共可有4*4*4中表达式。因此在不考虑括号的情况下,总共可以得到4!*4*4*4=1536中表达式。
接下来再考虑加上括号后的情况,对于4个数而言,总共会有以下5种加括号的方式:
(A(B(CD)))、(A((BC)D))、((AB)(CD))、((A(BC))D)、(((AB)C)D)。
所以需要遍历的表达式数最多有4!*4*4*4*5=7680种。即使采用逆波兰表达式,其总数也不变。
通过上面的分析,得到了一种解24点的基本思路,即遍历运算符、数字和括号的所有排列组合形式,接下来,我们将更加细致地讨论这种解法的一个具体实现。
假设给定的4个数组成的集合为A={1,2,3,4},定义函数f(A)为对集合A中的元素进行所有可能的四则混合运算所得到的值。
首先从集合A中任意取出两个数,如取出1和2,A=A-{1,2},对取出来的数分别进行不同的四则运算,1+2=3,1-2=-1,1/2=0.5,1*2=2,将得到的结果再分别加入集合A,可得到B={3,3,4},C={-1,3,4},D={0.5,3,4},E={2,3,4}四个新的集合,那么f(A)= f(B)+f(C)+f(D)+f(E),通过以上的计算就达到了分而治之的目的,问题规模就从4个数降到了3个数,成了3个数的4个子问题之和。综上所述,可以得到递归解法如下:
将给定的4个数放入数组Array中,将其作为参数传入函数f中,伪代码如下所示:
f(Array)
{
if(Array.Length < 2)
{
if(得到的最终结果为)
输出表达式
else 输出无法构造符合要求的表达式
}
foreach(从数组中任取两个数的组合)
{
foreach(运算符(+, -, *, /))
{
1、计算该组合在此运算符下的结果
2、将该组合中的两个数从原数组中移除,并将步骤的计算结果放入数组
3、对新数组递归调用f。如果找到一个表达式则返回
4、将步骤的计算结果移除,并将该组合中的两个数重新放回数组中对应的位置
}
}
}
具体代码如下所示:
#include "iostream"
#include "cmath"
#include "string"
using namespace std;
const double Threshold = 1E-6; //容差值
const int CardsNumber = 4;
const int ResultValue = 24;
double number[CardsNumber]; //输入的4个整数
string result[CardsNumber]; //保存表达式
bool PointsGame(int n)
{
if(n == 1)
{
//由于浮点数运算会有精度误差,所以用一个很小的数1E-6来做容差值
if(fabs(number[0] - ResultValue) < Threshold)
{
cout << result[0] << " == 24" << endl;
return true;
}
else
{
return false;
}
}
for(int i = 0; i < n; i++)
{
for(int j = i + 1; j < n; j++) //从数组中任取两个数的组合
{
double a, b;
string expa, expb;
a = number[i];
b = number[j];
number[j] = number[n-1]; //任取两个数并将其结果放入数组后,原数组的个数减少一个
expa = result[i]; //保存表达式中的数字
expb = result[j];
result[j] = result[n-1];
result[i] = '(' + expa + '+' + expb + ')'; //任取的两个数在“+”运算符下的结果
number[i] = a + b; //将该运算符下的运算结果放入数组中
if(PointsGame(n - 1))
return true;
result[i] = '(' + expa + '-' + expb + ')'; //任取的两个数在“-”运算符下的结果
number[i] = a - b;
if(PointsGame(n - 1))
return true;
result[i] = '(' + expb + '-' + expa + ')'; //任取的两个数在“-”运算符下的结果
number[i] = b - a;
if(PointsGame(n - 1))
return true;
result[i] = '(' + expa + '*' + expb + ')'; //任取的两个数在“*”运算符下的结果
number[i] = a * b;
if(PointsGame(n - 1))
return true;
if(b != 0)
{
result[i] = '(' + expa + '/' + expb + ')'; //任取的两个数在“/”运算符下的结果
number[i] = a / b;
if(PointsGame(n - 1))
return true;
}
if(a != 0)
{
result[i] = '(' + expb + '/' + expa + ')'; //任取的两个数在“/”运算符下的结果
number[i] = b / a;
if(PointsGame(n - 1))
return true;
}
number[i] = a; //将刚开始任取的两个数重新放回数组中对应的位置
number[j] = b;
result[i] = expa;
result[j] = expb;
}
}
return false;
}
int main(void)
{
int i,x;
for(i = 0; i < CardsNumber; i++)
{
char buffer[20];
cout << "Please input the " << i+1 << "th number:";
cin >> x;
number[i] = x; //保存输入的4个整数的浮点型数组
itoa(x, buffer, 10); //把输入的4个整数按10进制转化为字符串
result[i] = buffer;
}
if(PointsGame(CardsNumber) )
{
cout << "Success." << endl;
}
else
{
cout << "Fail." << endl;
}
system("pause");
return 0;
}
运行效果图如下:
分享到:
相关推荐
这是一个二十四点小程序,功能分成二十四点游戏和二十四点计算器两个部分。目标及其实现如下。 1. 目标:控制台输入4个数字,产生一组解 实现:【24点计算机---一个结果】 2. 目标:测试所有二十四点问题,给出...
24点游戏代码(完整的有界面),可以下载参考,代码简单易懂,希望你们喜欢
c++ 24点游戏源码 c++ 24点游戏源码 c++ 24点游戏源码 c++ 24点游戏源码 c++ 24点游戏源码
本Console版本的24点游戏包含其解搜索的解决方案
基于Java的Android应用程序开发-24点游戏源码+详细项目说明.zip 基于Java的Android应用程序开发-24点游戏源码+详细项目说明.zip 基于Java的Android应用程序开发-24点游戏源码+详细项目说明.zip 【项目介绍】 该资源...
基于Android平台的24点游戏设计与实现需求分析.pdf基于Android平台的24点游戏设计与实现需求分析.pdf基于Android平台的24点游戏设计与实现需求分析.pdf基于Android平台的24点游戏设计与实现需求分析.pdf基于Android...
使用python+pysimplegui开发的二十四点游戏
用C语言实现24点游戏的代码
24点游戏,C++编写的24点游戏,C++编写的24点游戏。
24点游戏程序设计.doc
既可以实现24点游戏,也可以实现其他数值的游戏
用VC++设计的一个24点小游戏,包含了设计过程和大部分主要的源代码。
24点游戏大家都应该玩过,我做的一个在手机玩的,比较简单,显示四张牌,并且给出答案,界面比较简单,很容易实现。
scratch图形化少儿编程24点小游戏
C语言实现24点游戏源码 游戏规则: 从键盘输入任意1-13的4个数,然后用算术运算符“+、一、*、/”将这四个数组成一一个算术表达式(可加括号,每个数字只能使用1次),使得该式的运算结果为24,每输入一次表达式,系统...
24点游戏开发,包含程序源代码、可执行文件,下载即可使用。
C语言原程序二十四点游戏的编程思路与基本算法 C语言原程序二十四点游戏的编程思路与基本算法
用c语言实现控制台下的24点游戏,实现了24点游戏的基本功能,还有改进的地方
MFC 24点游戏 基于对话框实现的 主要是24点算法以及判定无解的情况
24点游戏求解,关键之一是组合的生成(包括允许重复选取和不允许),其次是将三次运算作为算法的核心。本程序最后运行得到的1820种情况的答案,也同时上传,供大家参考。不当之处,请指正。