24点C++程序实现 编程之美1.16

解法1，对于任意输入的四个数字，给出一个24点的解法，若无解，则没有输出。

原理参照下图（编程之美原书）

代码如下，仅供参考

// 1.16.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

#include<string>

#include "stdio.h"

#include <math.h>

using namespace std;

const int CardsNumber = ;//24点有四张卡

const double ErrorThreshold=1E-;//由于舍入误差，需要加入一个误差阈值，误差在一定范围之内为，判断相等

const int ResultValue = ;

#define N 4

string result[CardsNumber]={"","","",""};

double number[CardsNumber]={,,,};

bool PointsGame(int n)

{

    if(n == )

    {

        //如果结果为24

        //由于舍入误差，应允许一定范围内的误差

        if( fabs(number[]-ResultValue)<ErrorThreshold)

        {

            cout<<result[]<<endl;

            //cout<<'1'<<endl;

            return true;

        }

        else

        {

            return false;

        }

    }

    for(int i= ;i<n ;i++)

    {

        for(int j=i+;j<n;j++)

        {

            double a,b;

            string expa,expb;

            a=number[i];

            b=number[j];

            number[j]=number[n-];

            expa=result[i];

            expb=result[j];

            result[j]=result[n-];

            result[i]='('+ expa +'+'+expb+')';

            number[i]=a+b;

            if(PointsGame(n-))

                return true;

            result[i]='('+ expa +'-' + expb +')';

            number[i]=a-b;

            if(PointsGame(n-))

                return true;

            result[i]='('+ expa + '*' + expb +')';

            number[i]=a*b;

            if(PointsGame(n-))

                return true;

            if(b!=)

            {result[i]='('+expa +'/'+ expb +')';

            number[i]=a/b;

            if(PointsGame(n-))

                return true;

            }

            number[i]=a;

            number[j]=b;

            result[i]=expa;

            result[j]=expb;

        }

    }

    return false;

}

int _tmain(int argc, _TCHAR* argv[])

{

    PointsGame();

    return ;

}

解法2，可以返回，输入4个数字的情况下，一共有多少不同的解。

原理如下图（编程之美原书）

书中没有给出代码，分享下我的代码：

// 1.16.cpp : Defines the entry point for the console application.

//

#include "stdafx.h"

#include <iostream>

#include<string>

#include "stdio.h"

#include <math.h>

using namespace std;

const int CardsNumber = ;

const double ErrorThreshold=1E-;

const int ResultValue = ;

#define N 4

class doubleSet//以double数字为内容的集合

{

public:

    doubleSet()

    {

        length=;

    }

    doubleSet(double p[],int n)

    {

        length=n;

        for(int i=;i<n;i++)

        {

            content[i]=p[i];

        }

    }

    bool IsEmpty()

    {

        if(length== || length>)

            return true;

        else

            return false;

    }

    void Display()//显示该集合

    {

        //content[length]='\0';

        for(int i=;i<length;i++)

            printf("%f     ",content[i]);

        for(int i=;i<length;i++)

            cout<<content[i]<<endl;

    }

    int GetLength()

    {

        return length;

    }

    double* Getcontent()

    {

        return content;

    }

    static doubleSet Union(doubleSet set1,doubleSet set2)  //两个集合求交集

    {

        int num1=set1.length;

        int num2=set2.length;

        if(num1==)

            return set2;

        else if(num2==)

            return set1;

        double *p1=set1.content;

        double *p2=set2.content;

        bool Repeat=;

        for(int i=;i<num2;i++)

        {

            for(int j=;j<num1;j++)

            {

                if( *(p2+i)==*(p1+j))

                {

                    Repeat=;

                    break;

                }

            }

            if(Repeat==)

            {

                Repeat=;

            }

            else

            {

            num1++;

            *(p1+num1-)=*(p2+i);

            }

        }

        set1.length=num1;

        for(int i=;i<num1;i++)

            set1.content[i]=p1[i];

        return set1;

    }

private:

    int length;//length表示集合的长度

    double content[];//content代表集合中的内容

};

doubleSet fun(int i);

doubleSet S[];  //定义16个double数字集合

int Mycheck( doubleSet set)//check   最后有多少个结果为24

{

    int num=;

    double *content=set.Getcontent();

    for(int i=;i<set.GetLength();i++)

    {

        if(fabs(content[i]-ResultValue)<ErrorThreshold)

        {

            num++;

        }

    }

    cout<<num<<endl;

    return num;

}

doubleSet Fork(doubleSet set1,doubleSet set2)//通过加减乘除合并两个数字集合为一个数字集合

{

    if(set2.IsEmpty())

        return set1;

     if(set1.IsEmpty())

        return set2;

    doubleSet ret;

    int retLen=;

     double RetContent[];//因为函数结束后，会释放局部变量，所以设置为静态的

    //切记不要返回局部变量指着。

    double *content1=set1.Getcontent();

    double *content2=set2.Getcontent();

    for(int i=;i<set1.GetLength();i++)

    {

        for(int j=;j<set2.GetLength();j++)

        {

            *(RetContent+retLen++)=content1[i]+content2[j];

            *(RetContent+retLen++)=content1[i]-content2[j];

            *(RetContent+retLen++)=content2[j]-content1[i];

            *(RetContent+retLen++)=content1[i]*content2[j];

            if(content2[j]!=)

                *(RetContent+retLen++)=content1[i]/content2[j];

            if(content1[i]!=)

                *(RetContent+retLen++)=content2[j]/content1[i];

        }

    }

    return doubleSet(RetContent,retLen);

}

void TheGame(doubleSet set)

{

    //把i化为 2进制的数，第j位数为1的代表出现第j个数。

    int n=set.GetLength();

    //for(int i=1;i<=pow(2,n);i++)

    double *content1=    set.Getcontent();

    static double temp[][];

    for(int i=;i<n;i++)//先构造2的指数倍

    {

         temp[i][] = content1[i];

        S[static_cast<int>(pow(2.0,i))]=doubleSet(temp[i],);

    }

    for(int i=;i<=pow(2.0,n)-;i++)

        S[i]=fun(i);//fun返回该集合数字，通过四则运算可以返回的所有结果

    Mycheck( S[static_cast<int>  (pow(2.0,n)-)  ] );

}

doubleSet fun(int i)

{

    if(!S[i].IsEmpty())

        return S[i];

    for(int x=;x<i;x++)

    {

        if((x&i)==x)

            S[i]=doubleSet::Union(S[i],Fork(fun(x),fun(i-x)));

    }

    return S[i];

}

int _tmain(int argc, _TCHAR* argv[])

{

    double a[]={,,,};

    doubleSet set1=doubleSet(a,);

    TheGame(set1);

    return ;

}

注：本文主要参考编程之美，1.16节给出的理论，主要目的是把代码贴出来给大家分享。

本文的图都来自《编程之美》

本人水平有限，怀着分享学习的态度发表此文，欢迎大家批评，交流。感谢您的阅读。
欢迎转载本文，转载时请附上本文地址：http://www.cnblogs.com/Dzhouqi/p/3362259.html
另外：欢迎访问我的博客 http://www.cnblogs.com/Dzhouqi/