我正在编写一个解决这个益智游戏的程序:给出了一些数字和一个目标数字,你使用 n 个数字和运算符 +、-、*、/和 () 来计算目标数字。例如,给定 2,3,5,7 和目标编号 10,解决方案是 (2+3)*(7-5)=10
, 3*5-(7 -2)=10
,以此类推。
要注意的是,如果我天真地实现它,我会得到一堆相同的解决方案,比如 (2+3)*(7-5)=10
和 (3+ 2)*(7-5)=10
, 3*5-(7-2)=10
and 5*3-(7-2)=10
和 3*5-7+2=10
和 3*5+2-7=10
等等。所以我想检测那些相同的解决方案并修剪它们。
我目前使用随机生成的双数来检测相同的解决方案。我所做的基本上是将这些随机数替换为解决方案,并检查是否有任何一对随机数计算出相同的数字。我必须在我搜索的每个节点执行检测,所以它必须很快,我现在使用 hashset。
现在的问题是计算带来的错误。因为即使是相同的解决方案也不会计算出完全相同的值,所以我目前在将计算值存储在哈希集中时将其四舍五入到一个精度。但是,这似乎效果不佳,并且每次针对同一问题给出不同数量的解决方案。有时随机数不好,会修剪一些完全不同的解决方案。有时计算值位于舍入函数的边缘,它会输出两个(或多个)相同的解。有更好的方法吗?
编辑: “相同”是指两个或多个解决方案(f(w,x,y,z,...) 和 g(w,x,y,z,...))计算出相同的数字,无论原始数字是多少数字(w,x,y,z ...)是。对于更多示例,4/3*1/2 和 1*4/3/2 以及 (1/2)/(3/4) 是相同的,但是 4/3/1/2 和 4/(3*1)/2 不是因为如果您将 1 更改为其他数字,它们将不会产生相同的结果。
最佳答案
如果在比较表达式之前“规范化”它们会更容易。一种方法是在操作可交换时进行排序,因此 3+2
变为 2+3
而 2+3
保持原样。当然,您还需要为带括号的组建立排序,例如 3+(2*1)
...是否变为 (1*2)+3
还是 3+(1*2)
?顺序是什么不一定重要,只要它是总顺序即可。
关于c++ - 在 C++ 中检测相同表达式的好方法,我们在Stack Overflow上找到一个类似的问题: https://stackoverflow.com/questions/32762771/