【凤凰社】C# 24点游戏求解算法(修订1)

经常跟儿子玩24点,有时候比较难算的,算一会儿,两人算不出来,就收了,当作没法算。

以我的数学可以力,一般来说,算不出来的,大概率确实是算不出来的。

But遇到比较变态的,当作算不出来是可可以的,So一直想找一个直接可以解24点的程序。

可是网上找了一圈,一直没找到。

想着自己写一个,可是这里面的逻辑一直理不清楚,不知道这个算法应该怎么写。

下午坐在电脑前面想的时候,不知道为啥,像是突然开窍了。写着写着居然写出来了。

贴出来供有兴趣的朋友参考,有问题请指正。

修订1:增加(a,b),(c,d)的算法

using System;
using System.Collections.Generic;
using System.Diagnostics;
using System.Linq;

namespace Calc24Point
{
    internal class Program
    {
        private static void Main(string[] args)
        {
            while (true)
            {
                var a = int.Parse(Console.ReadLine());
                var b = int.Parse(Console.ReadLine());
                var c = int.Parse(Console.ReadLine());
                var d = int.Parse(Console.ReadLine());

                Console.Clear();
                Console.WriteLine($"{a}, {b}, {c}, {d}");
                Console.WriteLine("------------------------");

                var items = CalcHelper.CalcResult(a, b, c, d);
                if (items?.Any() == true)
                {
                    foreach (var item in items)
                    {
                        Console.WriteLine(item);
                    }
                }
                else
                {
                    Console.WriteLine("无解");
                }
                Console.WriteLine("------------------------");
            }
        }
    }

    public class CalcHelper
    {
        public static List<string> CalcResult(double a, double b, double c, double d)
        {
            List<string> myList = new List<string>();
            List<CalcInfo> items = MakeCalcs(a, b, c, d);
            foreach (var item in items)
            {
                var result = item.GetResult();
                if (double.IsNaN(result) == false && IsEqual(result, 24))
                {
                    var text = item.GetString();
                    if (myList.Contains(text) == false)
                    {
                        myList.Add(text);
                    }
                }
            }

            return myList;
        }

        private static bool IsEqual(double a, double b)
        {
            return Math.Abs(a - b) < 0.000001;
        }

        private static List<CalcInfo> MakeCalcs(double a, double b, double c, double d)
        {
            var items = new List<CalcInfo>();
            items.AddRange(MakeCalcs(a, (b, c, d)));
            items.AddRange(MakeCalcs(b, (a, c, d)));
            items.AddRange(MakeCalcs(c, (b, a, d)));
            items.AddRange(MakeCalcs(d, (b, c, a)));

            items.AddRange(MakeCalcs((a, b), (c, d)));
            items.AddRange(MakeCalcs((a, c), (b, d)));
            items.AddRange(MakeCalcs((a, d), (c, b)));

            return items;
        }

        private static IEnumerable<CalcInfo> MakeCalcs((double a, double b) p1, (double c, double d) p2)
        {
            foreach (CalcInfo item1 in MakeCalcs(p1.a, p1.b))
            {
                foreach (CalcInfo item2 in MakeCalcs(p2.c, p2.d))
                {
                    yield return new CalcInfo(item1, item2, EMode.加);
                    yield return new CalcInfo(item1, item2, EMode.减);
                    yield return new CalcInfo(item2, item1, EMode.减);
                    yield return new CalcInfo(item1, item2, EMode.乘);
                    yield return new CalcInfo(item1, item2, EMode.除);
                    yield return new CalcInfo(item2, item1, EMode.除);
                }
            }
        }

        private static IEnumerable<CalcInfo> MakeCalcs(double item1, (double b, double c, double d) p)
        {
            foreach (CalcInfo item2 in MakeCalcs(p.b, (p.c, p.d)))
            {
                yield return new CalcInfo(item1, item2, EMode.加);
                yield return new CalcInfo(item1, item2, EMode.减);
                yield return new CalcInfo(item2, item1, EMode.减);
                yield return new CalcInfo(item1, item2, EMode.乘);
                yield return new CalcInfo(item1, item2, EMode.除);
                yield return new CalcInfo(item2, item1, EMode.除);
            }

            foreach (CalcInfo item2 in MakeCalcs(p.c, (p.b, p.d)))
            {
                yield return new CalcInfo(item1, item2, EMode.加);
                yield return new CalcInfo(item1, item2, EMode.减);
                yield return new CalcInfo(item2, item1, EMode.减);
                yield return new CalcInfo(item1, item2, EMode.乘);
                yield return new CalcInfo(item1, item2, EMode.除);
                yield return new CalcInfo(item2, item1, EMode.除);
            }

            foreach (CalcInfo item2 in MakeCalcs(p.d, (p.b, p.c)))
            {
                yield return new CalcInfo(item1, item2, EMode.加);
                yield return new CalcInfo(item1, item2, EMode.减);
                yield return new CalcInfo(item2, item1, EMode.减);
                yield return new CalcInfo(item1, item2, EMode.乘);
                yield return new CalcInfo(item1, item2, EMode.除);
                yield return new CalcInfo(item2, item1, EMode.除);
            }
        }

        private static IEnumerable<CalcInfo> MakeCalcs(double item1, (double c, double d) p)
        {
            foreach (CalcInfo item2 in MakeCalcs(p.c, p.d))
            {
                yield return new CalcInfo(item1, item2, EMode.加);
                yield return new CalcInfo(item1, item2, EMode.减);
                yield return new CalcInfo(item2, item1, EMode.减);
                yield return new CalcInfo(item1, item2, EMode.乘);
                yield return new CalcInfo(item1, item2, EMode.除);
                yield return new CalcInfo(item2, item1, EMode.除);
            }
        }

        private static IEnumerable<CalcInfo> MakeCalcs(double item1, double item2)
        {
            yield return new CalcInfo(item1, item2, EMode.加);
            yield return new CalcInfo(item1, item2, EMode.减);
            yield return new CalcInfo(item2, item1, EMode.减);
            yield return new CalcInfo(item1, item2, EMode.乘);
            yield return new CalcInfo(item1, item2, EMode.除);
            yield return new CalcInfo(item2, item1, EMode.除);
        }
    }

    public class CalcInfo
    {
        public CalcInfo Items1 { get; set; }
        public CalcInfo Items2 { get; set; }
        public EMode? Mode { get; set; }
        public double Result { get; set; }

        public CalcInfo(double value)
        {
            Result = value;
        }

        public CalcInfo(double value1, double value2, EMode mode) : this(new CalcInfo(value1), new CalcInfo(value2), mode)
        {
        }

        public CalcInfo(double value1, CalcInfo value2, EMode mode) : this(new CalcInfo(value1), value2, mode)
        {
        }

        public CalcInfo(CalcInfo value1, double value2, EMode mode) : this(value1, new CalcInfo(value2), mode)
        {
        }

        public CalcInfo(CalcInfo value1, CalcInfo value2, EMode mode)
        {
            Items1 = value1;
            Items2 = value2;
            Mode = mode;
        }

        public double GetResult()
        {
            if (Mode == null)
            {
                return Result;
            }

            var item1 = Items1.GetResult();
            var item2 = Items2.GetResult();
            if (double.IsNaN(item1) || double.IsNaN(item1))
            {
                return double.NaN;
            }

            switch (Mode.Value)
            {
                case EMode.加:
                    return item1 + item2;
                case EMode.减:
                    return item1 - item2;
                case EMode.乘:
                    return item1 * item2;
                case EMode.除:
                    if (item2 == 0)
                    {
                        return double.NaN;
                    }

                    return item1 / item2;
                default:
                    Debug.Assert(false);
                    break;
            }

            return double.NaN;
        }

        public string GetString()
        {
            if (Mode == null)
            {
                return Result.ToString();
            }

            switch (Mode.Value)
            {
                case EMode.加:
                    return $"({Items1.GetString()} + {Items2.GetString()})";
                case EMode.减:
                    return $"({Items1.GetString()} - {Items2.GetString()})";
                case EMode.乘:
                    return $"({Items1.GetString()} * {Items2.GetString()})";
                case EMode.除:
                    return $"({Items1.GetString()} / {Items2.GetString()})";
                default:
                    Debug.Assert(false);
                    break;
            }

            return null;
        }
    }

    public enum EMode
    {
        加,
        减,
        乘,
        除,
    }
}

 


0 评论

回复