24点游戏算法分析
一：题目分析
从扑克中每次取出4张牌。使用加减乘除，第一个能得出24者为赢。（其中，J代表11，Q代表12，K代表13，A代表1），按照要求编程解决24点游戏。 基本要求： 随机生成4个代表扑克牌牌面的数字字母，程序自动列出所有可能算出24的表达式 其中一种算法是把多元运算转化为两元运算，先从四个数中取出两个数进行运算，然后把运算结果和第三个数进行运算，再把结果与第四个数进行运算
(1) 将4个整数放入数组中
(2) 在数组中取两个数字的排列，共有 P(4,2) 种排列。对每一个排列，对 – * / 每一个运算符，
(2.1.1) 根据此排列的两个数字和运算符，计算结果
(2.1.2) 改表数组：将此排列的两个数字从数组中去除掉，将 2.1.1 计算的结果放入数组中
(2.1.3) 对新的数组，重复步骤 2
(2.1.4) 恢复数组：将此排列的两个数字加入数组中，将 2.1.1 计算的结果从数组中去除掉可见这是一个递归过程。步骤 2 就是递归函数。当数组中只剩下一个数字的时候，这就是表达式的最终结果，此时递归结束。
另一种算法是将有关于a，b，c，d的所有表达式在函数中写出来，通过对abcd的排序作为函数的参数调用24次函数，计算表达式等于24的结果。这种算法很容易漏掉某一种表达式，因此第一种算法较好，二报告对一种算法进行分析。
两种算法都不能查重。
二：流程图
Find函数中加法
Find函数
void Find(int n)
{
if (n == 1)
{
if ( fabs(number[0] - VOLUE) <= LING )//fabs()求绝对值,找到和为24的表达式并输出
{
cout << expression[0] << "\t\t"; //输出表达式
m_judge = true;
count ++;
if((count % 1)==0) //使输出时每行一个表达式
cout<<endl;
}
}
for(int i=0; i < n; i++)//查找
{
for (int j = i + 1; j < n; j++)//与其后面的查找进行计算
{
double a, b;
string expressiona, expressionb;//字符串，存放表达式
a = number[i];
b = number[j];
number[j] = number[n - 1];
expressiona = expression[i];
expressionb = expression[j];
expression[j] = expression[n - 1];
expression[i]= '('+ expressiona + '+' + expressionb + ')';//表达式为（a+b）
number[i] = a + b;
Find(n-1); //递归
expression[i]='('+ expressiona+ '-' + expressionb + ')';//表达式为（a-b）
number[i] = a - b;
Find(n-1);
expression[i] = '('+expressionb + '-' + expressiona + ')';//表达式为（b-a）
number[i] = b -a;
Find(n-1);
expression[i]= '('+ expressiona +'*'+ expressionb+ ')';//表达式为（a*b）
number[i]=a*b;
Find(n-1);
if (b != 0)
{
expression[i] ='('+expressiona+'/' + expressionb + ')';//表达式为（a/b）
number[i] = a / b;
Find(n-1);
}
if (a != 0)
{
expression[i]='('+expressionb + '/'+ expressiona + ')';//表达式为（b/a）
number[i] = b / a;
Find(n-1);
}
number[i] =a;
number[j]=b;
expression[i] = expressiona;
expression[j] = expressionb;
}
}
}
#include <iostream>
#include <string>
#include <math.h>
#include<stdlib.h>
#include<time.h>
using namespace std;
const double LING = 1E-6;
const int CONT = 4;
int live=3;
const int VOLUE = 24;
double number[4]; //存放4个数
string expression[4];
bool m_judge = false; //判断是否有解。
int count = 0;
void Find(int n)
{
if (n == 1)
{
if ( fabs(number[0] - VOLUE) <= LING ) //fabs()求绝对值,找到和为24的表达式并输出
{
cout << expression[0] << "\t\t"; //输出表达式
m_judge = true;
count ++;
if((count % 1)==0) //使输出时每行一个表达式
cout<<endl;
}
}
for(int i=0; i < n; i++)//查找
{
for (int j = i + 1; j < n; j++) //与其后面的查找进行计算
{
double a, b;
string expressiona, expressionb; //字符串，存放表达式
a = number[i];
b = number[j];
number[j] = number[n - 1];
expressiona = expression[i];
expressionb = expression[j];
expression[j] = expression[n - 1];
expression[i]= '('+ expressiona + '+' + expressionb + ')';//表达式为（a+b）
number[i] = a + b;
Find(n-1); //递归
expression[i]='('+ expressiona+ '-' + expressionb + ')';//表达式为（a-b）
number[i] = a - b;
Find(n-1);
expression[i] = '('+expressionb + '-' + expressiona + ')';//表达式为（b-a）
number[i] = b -a;
Find(n-1);
expression[i]= '('+ expressiona +'*'+ expressionb+ ')';//表达式为（a*b）
number[i]=a*b;
Find(n-1);
if (b != 0)
{
expression[i] ='('+expressiona+'/' + expressionb + ')';//表达式为（a/b）
number[i] = a / b;
Find(n-1);
}
if (a != 0)
{
expression[i]='('+expressionb + '/'+ expressiona + ')';//表达式为（b/a）
number[i] = b / a;
Find(n-1);
}
number[i] =a;
number[j]=b;
expression[i] = expressiona;
expression[j] = expressionb;
}
}
}
int main()
{
srand((unsigned)time(NULL));
number[0]=rand()%12+1;
number[1]=rand()%12+1;
number[2]=rand()%12+1;
number[3]=rand()%12+1;
cout<<"随机生成的四个数为"<<endl;
cout<< number[0]<<endl;
cout<< number[1]<<endl;
cout<< number[2]<<endl;
cout<< number[3]<<endl;
for (int i = 0; i < CONT; i++)
{char ch[20];
itoa(number[i],ch, 10); //itoa()函数的作用是把第一个参数(数值)传送(转换)到第二个参数(字符串)中去，第三个参数(int型)是该数值在字符串里以什么进制存放。
expression[i] = ch;
}
cout<<endl;
Find(CONT) ;
if(m_judge==true)
{cout << "\n成功！" << endl;
cout<<"总共的计算方法共有： "<<count<<endl;
}
else
{
cout << "不可组成24点" << endl;
}
return 0;}
心得体会
当拿到这个题目是，我首先想到的是我提到的第二种算法，即把所有关于a,b,c,d的表达式全部列出来，用if，else的方法逐一比较，成功组成24的输出，但这种方法很笨，很容易丢失某一种排序方式或者某种方法。所以我在网上搜集资料，我发现了我这次提交的程序，这个程序把4个数的表达式拆分为2目运算，通过递归，把a,b,c,d 所有的情况全部计算，并且这种算法避免了对（）的使用，大大的降低了缺失的可能性。
这次的代码主要是在网上找的，我只是做了一些修改，因为我自己可能真的想不出来这种算法。我看了这个算法很久，大体上看懂来了，这个程序是通过递归把所有的情况全部计算，在通过函数中对结果的比较，找到符合的表达式。对递归这种算法，我也懂，不过在这个程序中，我不知道在函数递归后，函数体中的循环是怎么变化的，n随着递归每次减一，但控制循环的i，j是不变的，当随着递归的进行，n会变为1，此时函数中的循环会停止，那么在第一个递归语句后的其余代码是什么时候执行，这点我不是很懂。
这次的作业，我写的不是很多，大多时间都在思考这个程序，收获很多，比我自己写简单但繁琐的第二种算法收获的更多。