equationgame.cs

一、前言 24点游戏是一个常见游戏

using System;
using System.Collections.Generic;
using System.Collections;
using System.Text;


/// <summary>
/// 游戏规则，给定一组整数、一组四则运算符和一个结果数，要求用上所有
/// 最笨情况，做全排列，全结合顺序，全运算符组合的搜索
/// 优化1：有相同数的，可以减少排列数
/// 优化2：加法和乘法有交换律
/// 优化3：备忘录法，记录n个数所能达到的计算结果，则可以直接查表
/// 潜在bug1：出现分数时，必须按分数形式保留结果，否则会有误差
/// </summary>
class EquationGame
{
    /// 备忘录,记录由哪组数，可以达到哪些值，对应的(1个)表达式是怎样
    public Dictionary<string, SortedList<Fraction, Expression>> memo = new Dictionary<string, SortedList<Fraction, Expression>>();
    ///记录哪个子数组和另外一个子数组是否交叉计算过
    public Hashtable hashTable = new Hashtable(); 
    public int[] array;//数组
    public int n;//数组大小
    public EquationGame(int[] array)
    {
        Array.Sort(array);
        this.array = array;
        this.n = array.Length;
    }

    public Expression GetOneExpression(int r)
    {
        //计算所有可能的最终结果，存入备忘录
        BuildAllPossbile(array);
        //查找最终结果为要求数的表达式
        string strAll = GetKeyString(array);
        Fraction fra = new Fraction(r);
        if (memo[strAll].ContainsKey(fra))
            return memo[strAll][fra];
        return null;
    }

    /// <summary>
    /// 构造由arr里面的每个数用一次运算的不同计算结果
    /// 并保留对应表达式，核心算法在这里
    /// </summary>
    void BuildAllPossbile(int[] arr)
    {
        string strKey = GetKeyString(arr);
        if (memo.ContainsKey(strKey) == true)
            return;//已存在，不用再计算
        SortedList<Fraction, Expression> list = new SortedList<Fraction, Expression>();
        if (arr.Length == 1)
        {//单个数直接添加
            Expression exp = new Expression(arr[0]);
            list.Add(new Fraction(arr[0]), exp);
        }

        //子串长度,根据组合公式C(n,r)=C(n,n-r)，只搜索到一半就完成
        for (int len = 1; len <= arr.Length / 2; len++)
        {
            //将arr分成两个数组，一个长度为len，一个为arr.Legnth-len，求所有可能的组合
            int[] a1 = new int[len];
            int[] a2 = new int[arr.Length - len];
            int[] select = new int[arr.Length];//当前组合选入a1的数在arr中的下标
            for (int i = 0; i < len; i++)
                select[i] = i;

            while (true)
            {
                //将选择映射到两个数组
                int c1 = 0, c2 = 0, si = 0;
                for (int i = 0; i < arr.Length; i++)
                {
                    if (select[si] == i)
                    {
                        a1[c1++] = arr[i];  //前半数组
                        si++;
                    }
                    else
                        a2[c2++] = arr[i];  //后半数组
                }

                string hKey = GetKeyString(a1) + ' ' + GetKeyString(a2);
                if (hashTable.Contains(hKey) == false)
                {//如果a1和a2没有计算过，则进行计算
                    hashTable.Add(hKey, null); 
                    BuildAllPossbile(a1);
                    BuildAllPossbile(a2);
                    CalculateAll(a1, a2, list);
                }
                //调整到下一个可能 比如5选2有
                //找下一个可调整位置
                int t = len - 1;
                while (t >= 0 && select[t] == arr.Length - len + t)
                    t--;
                if (t == -1) break;

                select[t]++;
                for (int j = t + 1; j < len - 1; j++)
                    select[j] = select[j - 1] + 1;
            }
        }
        memo[strKey] = list;
    }

    /// <summary>
    /// 计算a1和a2所有可能的运算结果，保存到list
    /// </summary>
    void CalculateAll(int[] a1, int[] a2, SortedList<Fraction, Expression> list)
    {
        SortedList<Fraction, Expression> list1 = memo[GetKeyString(a1)];
        SortedList<Fraction, Expression> list2 = memo[GetKeyString(a2)];
        Fraction fra;
        foreach (Fraction fra1 in list1.Keys)
            foreach (Fraction fra2 in list2.Keys)
                foreach (Operator opt in Operator.Operators)
                    for (int k = 0; k < 2; k++)
                    {
                        if (k == 1 && opt.Exchangable == true)//满足交换律只算一次
                            break;
                        if (k == 0)
                            fra = Fraction.Operate(fra1, fra2, opt);
                        else
                            fra = Fraction.Operate(fra2, fra1, opt);
                        if (fra == null) break;

                        //如果当前计算值不存在，才加入list，如果要求所有解，则是不相同就能加入list
                        if (list.ContainsKey(fra) == false)
                        {
                            //构造新的表达式加入进来
                            Expression exp = new Expression();
                            exp.Operator = opt;
                            if (k == 1)
                            {
                                exp.LChild = list2[fra2];
                                exp.RChild = list1[fra1];
                            }
                            else
                            {
                                exp.LChild = list1[fra1];
                                exp.RChild = list2[fra2];
                            }
                            list[fra] = exp;
                        }
                    }
    }

    /// <summary>
    /// 根据数组产生备忘录的索引字符串
    /// </summary>
    string GetKeyString(int[] arr)
    {
        StringBuilder sb = new StringBuilder();
        int index = 0;
        int last = arr.Length - 1;
        foreach (int num in arr)
        {
            sb.Append(num);
            if (index < last)
                sb.Append(',');
            index++;
        }
        return sb.ToString();
    }

    public List<Expression> GetAllExpresses(int r)
    {
        //计算所有可能的最终结果，存入备忘录
        BuildAllPossbile(array);
        //查找最终结果为要求数的表达式
        //将array拆分成所有可能的两组数运算的组合，
        //在第一组数中，找第二组数能够与其运算得到目标值r的情况
        return GetAllExpresses(array, new Fraction(r));
    }

    /// <summary>
    /// 求arr拆分之后，所有可能达到r的表达式的集合
    /// </summary>
    List<Expression> GetAllExpresses(int[] arr, Fraction r)
    {
        List<Expression> list = new List<Expression>();
        string strKey = GetKeyString(arr);
        if (memo.ContainsKey(strKey) == false) return list;//查表不可达到，直接放弃搜索
        if (arr.Length == 1)
        {
            if (new Fraction(arr[0]).CompareTo(r) == 0)
                list.Add(new Expression(arr[0])); 
            return list;
        }
        //子串长度,根据组合公式C(n,r)=C(n,n-r)，只搜索到一半就完成
        for (int len = 1; len <= arr.Length / 2; len++)
        {
            //将arr分成两个数组，一个长度为len，一个为arr.Legnth-len，求所有可能的组合
            int[] a1 = new int[len];
            int[] a2 = new int[arr.Length - len];
            int[] select = new int[arr.Length];//当前组合选入a1的数在arr中的下标
            for (int i = 0; i < len; i++)
                select[i] = i;

            while (true)
            {
                //将选择映射到两个数组
                int c1 = 0, c2 = 0, si = 0;
                for (int i = 0; i < arr.Length; i++)
                {
                    if (select[si] == i)
                    {
                        a1[c1++] = arr[i];  //前半数组
                        si++;
                    }
                    else
                        a2[c2++] = arr[i];  //后半数组
                }

                CalculateEqualFra(a1, a2, list, r);
                //调整到下一个可能 比如5选2有
                //找下一个可调整位置
                int t = len - 1;
                while (t >= 0 && select[t] == arr.Length - len + t)
                    t--;
                if (t == -1) break;

                select[t]++;
                for (int j = t + 1; j < len - 1; j++)
                    select[j] = select[j - 1] + 1;
            }
        }
        return list;
    }

    /// <summary>
    /// 计算a1和a2所有可能的运算结果，保存到list
    /// </summary>
    void CalculateEqualFra(int[] a1, int[] a2, List<Expression> list, Fraction r)
    {
        SortedList<Fraction, Expression> list1 = memo[GetKeyString(a1)];
        SortedList<Fraction, Expression> list2 = memo[GetKeyString(a2)];
        Fraction fra;
        foreach (Fraction fra1 in list1.Keys)
            foreach (Fraction fra2 in list2.Keys)
                foreach (Operator opt in Operator.Operators)
                    for (int k = 0; k < 2; k++)
                    {
                        if (k == 1 && opt.Exchangable == true)//满足交换律只算一次
                            break;
                        if (k == 0)
                            fra = Fraction.Operate(fra1, fra2, opt);
                        else
                            fra = Fraction.Operate(fra2, fra1, opt);
                        if (fra == null) break;

                        //如果计算值等于r，则加入list
                        if (fra.CompareTo(r) == 0)
                        {
                            //构造新的表达式加入进来
                            Expression exp = new Expression();
                            //递归的求子表达式有哪些情况
                            List<Expression> l1 = GetAllExpresses(a1, fra1);
                            List<Expression> l2 = GetAllExpresses(a2, fra2);
                            exp.Operator = opt;
                            //然后组合在一起
                            foreach (Expression exp1 in l1)
                                foreach (Expression exp2 in l2)
                                {
                                    if (k == 1)
                                    {
                                        exp.LChild = exp2;
                                        exp.RChild = exp1;
                                    }
                                    else
                                    {
                                        exp.LChild = exp1;
                                        exp.RChild = exp2;
                                    }

                                    if (list.Contains(exp) == false)
                                        list.Add(exp);
                                }
                        }
                    }
    }
}


//3
//3
//8
//8
//33     0    1   6    9
//38    -5   11   5   24
//338
//388
//3388


//338
//2338
//3338
//3348