题解 | #24点游戏算法#

using System; using System.Collections.Generic;

namespace HuaWeiTest { class Pongam

{
    private static int[] arr=new int[4];
    private static int[] visited= new int[4];
    static void Main(string[] arge)
    {
        
        string CF;
        while ((CF = Console.ReadLine()) != null)
        {
            var cfLine = CF.Split(' ');
            arr = Array.ConvertAll<string, int>(cfLine, s => int.Parse(s));
            var result = false;
            if (canGet24(0, 0))
            {
                Console.WriteLine("true");
            }
            else
            {
                Console.WriteLine("false");
            }
        }

    }
    private static bool canGet24(int cnt, double tmpres)
    {
        
        if (cnt == 4 && tmpres == 24)
        {//如果用了4个了，且结果已经是24了，那就说明24运算成功。
            return true;
        }
        if (cnt == 0)
        {//对于还没开始运算的情况，接收的第一个数值直接作为tmpres
            for (int i = 0; i < 4; i++)
            {
                visited[i] = 1;
                if (canGet24(1, arr[i]))
                {
                    return true;
                }
                visited[i] = 0;//每一轮循环都要把访问记录恢复
            }
            return false;//所有数字都试过了还没有得到24，说明不可能再得到。
        }

        if (cnt == 1 || cnt == 3 || cnt == 2)
        {
            for (int i = 0; i < 4; i++)
            {
                if (visited[i] == 0)
                {
                    visited[i] = 1;
                    if (canGet24(cnt + 1, tmpres + arr[i]) || canGet24(cnt + 1, tmpres * arr[i]) ||//加和乘计算
                       canGet24(cnt + 1, tmpres - arr[i]) || canGet24(cnt + 1, arr[i] - tmpres))
                    {//减法计算
                        return true;
                    }
                    if (tmpres != 0 && canGet24(cnt + 1, arr[i] / tmpres) ||
                       arr[i] != 0 && canGet24(cnt + 1, tmpres / arr[i]))
                    {//除法计算
                        return true;
                    }
                    visited[i] = 0;
                }
            }
        }//不是1~4的返回false
        return false;
    }
    //以下函数用于返回两个数进行任何运算后可能的值，以列表形式返回。

}

}