24点游戏
一、题目说明
完成24点游戏，从扑克中每次取出4张牌。使用加减乘除，第一个能得出24者为赢。（其中，J代表11，Q代表12，K代表13，A代表1），按照要求编程解决24点游戏。
基本要求：
随机生成4个代表扑克牌牌面的数字字母，程序自动列出所有可能算出24的表达式，用擅长的语言（C/C++/Java或其他均可）实现程序解决问题。
1.程序风格良好(使用自定义注释模板)
2.列出表达式无重复。
二、具体实现
1、基本思路
基本思路就是穷举4个数组成的所有可能计算式，计算结果。
(1) 将4个整数放入数组中，
(2) 在数组中取两个数字的排列，共有 P(4,2) 种排列。对每一个排列，
(2.1) 对 + - * / 每一个运算符，
(2.1.1) 根据此排列的两个数字和运算符，计算结果
(2.1.2) 改表数组：将此排列的两个数字从数组中去除掉，将 2.1.1 计算的结果放入数组中
(2.1.3) 对新的数组，重复步骤 2
(2.1.4) 恢复数组：将此排列的两个数字加入数组中，将 2.1.1 计算的结果从数组中去除掉
可见这是一个递归过程。步骤(2)就是递归函数。当数组中只剩下一个数字的时候，这就是表达式的最终结果，此时递归结束。
2、代码
#include <iostream>
#include <string>
#include <math.h>
#include <time.h>
#include <stdlib.h>
using namespace std;
const double LING = 1E-6;
const int COUNT_OF_NUMBER = 4;
const int VOLUE = 24;
double number[COUNT_OF_NUMBER];
string expression[COUNT_OF_NUMBER];//存放每一步产生的表达式
bool m_judge = false; //判断是否有解。
int count=0;//累积有多少结果
void Find(int n)
{
if (n == 1)
{
/*计算结果满足24输出*/
if ( fabs(number[0] - VOLUE) <= LING )
{
cout << expression[0] << endl;//输出满足条件的算式
m_judge = true;
count++;
}
else
{ }
}
for(int i=0; i < n; i++)
{
for (int j = i + 1; j < n; j++)/*生成两个数的排列*/
{
double a, b;
a = number[i];
b = number[j];
number[j] = number[n - 1];
string expressiona, expressionb;
expressiona = expression[i];
expressionb = expression[j];
expression[j] = expression[n - 1];
expression[i]= '('+ expressiona + '+' + expressionb + ')';
number[i] = a + b;
Find(n-1);
expression[i]='('+ expressiona+ '-' + expressionb + ')';
number[i] = a - b;
Find(n-1);
expression[i] = '('+ expressionb + '-' + expressiona + ')';
number[i] = b -a;
Find(n-1);
expression[i]= '('+ expressiona +'*'+ expressionb + ')';
number[i]=a*b;
Find(n-1);
if (b != 0)
{
expression[i] ='('+expressiona+'/' + expressionb + ')';
number[i] = a / b;
Find(n-1);
}
if (a != 0)
{
expression[i]='('+expressionb + '/'+ expressiona + ')';
number[i] = b / a;
Find(n-1);
}
number[i] =a;//恢复整个数组
number[j]=b;
expression[i] = expressiona;
expression[j] = expressionb;
}
}
}
int main()
{
// 随机生成4个数
srand((unsigned)(time(NULL)));
for(int i=0;i<COUNT_OF_NUMBER;i++)
{
char ch[20];
number[i]=rand()%13+1;
itoa(number[i],ch, 10); //itoa()函数的作用是把第一个参数(数值)传送(转换)到第二个参数(字符串)中去，第三个参数(int型)是该数值在字符串里以什么进制存放。
expression[i] = ch;
}
cout<<"随机生成的4张扑克牌："<<endl;
for(int i=0;i<COUNT_OF_NUMBER;i++)
{
cout<<number[i]<<" ";
}
cout<<endl;
Find(COUNT_OF_NUMBER);//寻找满足24点的算式
if(m_judge==true)
{
cout << "\n成功！" << endl;
cout<<"总共的计算方法共有： "<<count<<endl;
}
else
{
cout << "失败！" << endl;
}
return 0;
}
函数Find()就是递归函数
expression[]存储每一步的算式，number[]存储4个操作数，i次循环中，expression[i]，number[i]完成实际的计算步骤，两个数的运算结果存入number[i]中，已完成的计算步骤存入expression[i]中。在进行下一层递归时，需要恢复expression[]、number[]，故数据变化前需要保存至expressiona/expressionb、a/b，便于下一层递归调用前，将整个数组恢复
其次，用n控制结果的输出，n=1时，表明4个操作数已经全部参与运算，此时计算结果number[0]既是整个算式结果，判断是否为24，将算式输出。