Java实现24点游戏算法详解

24点游戏算法详解

先附上源码

问题描述:任意输入四个整数,通过运算整合(使用加减乘除和括号),使结果为24,如果有解法,输出所有解法并进行技术。如果没有解法,输出失败。

说说思路

这个算法必然是穷举法尽可能的得到所有的组合,那,怎么开始组合呢?

我的思路是,从左到右,并且 + – * /的顺序开始

例:

现在是 a b c d四个值

先a+b看作一个整体,先 (a+b)+c+d运算,可行输出,计数+1

不可行就改变为(a+b)+c-d运算,

再不可行改变为(a+b)+c*d,以此类推,一直往外解括号

然后 a+c、a+d、b+c、b+d、c+d

依次遍历完所有的可能性

算法复杂度为O(n^2)

关于其中的一些坑和技术想法都写在了源码的注释中