1.16 24点游戏

题目描述：

给定4个数，允许使用加、减、乘、除，允许中间存在小数，可以使用括号，使其计算结果为24； 

解法一：

穷举法，每个数字一次，运算符号4种，所以可以穷举4个数所有可能的表达式；

1）不考虑括号情况
  4个数全排列：4！=24种
  需要三个运算符，且运算符可以重复：4*4*4=64
  总计：1536
2）考虑括号
   四个数有五种加括号方式：
((AB)C)D 、(AB)(CD) 、(A(BC))D 、 A((BC)D) 、A(B(CD))
四个运算数五种不同加括号方式的由来。这是一个经典的Catalan数问题。
前几个Catalan数为：C(0)=1，C(1)=1，C(2)=2，C(3)=5，C(4)=14，C(5)=42。
对于4个数，中间有3个位置，可以在任何一个位置一分为二，
被分开的两半各自的加括号方案再拼凑起来就得到一种4个数的加括号方案：
一个数时：(A)，一种
两个数：g(2)=g(1)g(1)，所以是(A)(B)=(AB)，一种
三个数：g(3)=g(1)g(2)+g(2)g(1)=(A)(BC)+(AB)(C)，两种
四个数：g(4)=g(1)g(3)+g(2)g(2)+g(3)g(1)
                 =(A)[(B)(CD)+(BC)(D)]+(AB)(CD)+[(A)(BC)+(AB)(C)](D)
                 =A(B(CD)) + A((BC)D) + (AB)(CD) + (A(BC))D + ((AB)C)D

共有五种。 

#include<iostream> 
#include<cmath>
#include<stdio.h> 
#include<stdlib.h>
using namespace std;

const double Threshold = 1E-6;
const int CardsNumber = 4;
const int ResultValue = 24;
double number[CardsNumber];
string result[CardsNumber];

bool PointsGame(int n)
{
     if(n == 1)
     {
          // 由于浮点数运算会有精度误差，所以用一个很小的数1E-6来做容差值
          if(fabs(number[0]-ResultValue)<Threshold)//结果等于24
          {
               cout <<result[0]<< 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()
{
    int x;
    for(int i = 0;i<CardsNumber;i++)
    {
         char buffer[20];
         cout << "the " << i << "th number:";
         cin >> x;
         number[i] = x;
         itoa(x,buffer,10);
         result[i] = buffer;
    }
    if(PointsGame(CardsNumber))
    {
         cout << "Success." << endl;
    }
    else
    {
         cout << "Fail." << endl;
    }
}