我试图学习有关算法设计的更多信息,并且给自己带来了创建一个简单的游戏的挑战,该游戏向用户提供数字数组,目标数字和一系列运算符(加,减,乘,除) ,也许平方根等等)。我需要做的是确定是否可以使用数组中的可用数字来确定目标数字。
我对从哪里开始感到有些困惑。在不同轮次的游戏,不同的运营商可以是可用的,例如+, -, *, and /,+ and -仅+ and *,或所有除+等
+, -, *, and /
+ and -
+ and *
+
我的意思是说,对于每种运算符组合(无论有多少,无论是20个还是其他),我实际上都需要一个单独的算法?如果是这样,那么我是否需要遍历网格中的每个数字,对数组中的每个其他数字执行每个可用的运算符?这似乎太乱了,但是我不确定是否还有其他选择。此选项也不会遵循通过多个操作的任何特定路径(例如,如果我想进行操作7,那么12 + 5 - 10如果这些是数组中唯一可用的数字,则可以这样做)。
7
12 + 5 - 10
谁能给我一些从哪里开始这类问题的指点?
您面临的是Partition Problem的更广泛的问题,即NP- Complete。
分区问题是:给定n数字,将它们分成两个(不同的)组A,B使sum(A) = sum(B)。现在,很容易看出,如果您遇到+,-运算符和目标编号0的问题,这基本上是相同的问题,并且从分区问题到问题的减少都很大。
n
A
B
sum(A) = sum(B)
由此我们可以得出结论,您的问题也是NP-Hard,并且 您的问题没有已知的多项式解 。
替代方法是:
很抱歉,如果这是个坏消息-但至少您不会寻找(大多数计算机科学家认为)不存在的东西