写一个算法来决定是否一个目标数字可以用一组其他数字和具体的运营商达成？ [英] Writing an algorithm to decide whether a target number can be reached with a set of other numbers and specific operators?

问题描述

我想更多地了解算法设计，我已经给自己定下了创建一个简单的游戏，presents用户数的数组，一个目标数量，以及一系列运营商的挑战（加，减，乘，除，也许平方根而这种更高版本）。我需要做的是决定是否有可能利用现有的数字数组中，这个目标数字。

I'm trying to learn more about algorithm design, and I've set myself the challenge of creating a simple game that presents users with an array of numbers, a target number, and a range of operators (plus, minus, multiply, divide, perhaps square root and such later). What I need to do is decide whether or not it's possible to make that target number using the available numbers in the array.

我在哪里开始与这个有点难倒。在不同轮次的比赛中，不同的运营商可能会使用，如 +， - ，*，和/ ， +和 - ，只有 +和* ，或所有除 + 等。

I'm a little stumped on where to begin with this. In different rounds of the game, different operators may be available, such as +, -, *, and /, + and -, only + and *, or all except +, etc.

难道我说得对，我会有效地需要一个单独的算法，运营商的每一种组合（然而，许多有，20或其他）？如果是的话，我会再需要遍历网格中的每一个号码，对方号码阵列中执行每个可用的运营商？这似乎过于凌乱，但我真的不知道还有什么其他的选择有。此选项也不会跟进多个操作的具体路径（例如，如果我要拍 7 ，我可以这样做 12 + 5 - 10 如果这些人在阵列中提供给我的唯一编号）。

Am I right in saying that I would effectively need a separate algorithm for each combination of operators (however many there are, 20 or whatever)? And if so, will I then need to iterate through each number in the grid, performing each available operator on each other number in the array? That seems overly messy, but I'm not really sure what other options there are. This option also doesn't follow any specific path through multiple operations (for instance if I wanted to make 7, I may do 12 + 5 - 10 if those were the only numbers available to me in the array).

任何人都可以给我从哪里开始这类问题的一些指针？

Could anyone give me some pointers on where to begin with this kind of problem?

推荐答案

您所面临的划分问题的一个更普遍的问题，这是 NP完全。

该分区的问题是：由于 N 的数字，他们分成两个（不同）组 A 和 B ，使得和（A）= SUM（B）。现在，很容易看到，如果你有+问题 - 运营商和目标数0 - 这是基本相同的问题，有一个immidiate减少从划分问题，您的问题

The Partition Problem is: Given n numbers, split them into two (distinct) groups A and B such that sum(A) = sum(B). Now, it is easy to see that if you have a problem with +,- operators and target number 0 - this is basically the same problem, and there is an immidiate reduction from Partition Problem to your problem.

由此我们可以得出结论：你的问题是 NP难以及，和不存在已知的多项式的解决方案为您的问题

From this we can conclude your problem is NP-Hard as well, and there is no known polynomial solution for your problem.

替代方案是：

1. 蛮力（所建议的@Sayakiss）
2. 根据不同的运营商 - 你也许可以使用一些​​分支定界技术
。
3. 对于划分问题有伪多项式动态规划解决方案，可能在这里被用作好吧，至少对于一些情况。

1. Brute Force (As suggested by @Sayakiss)
2. Depending on the operators - you might be able to use some branch and bound techniques.
3. For Partition Problem there is pseudo-polynomial Dynamic Programming solution, that might be utilized in here as well, at least for some of the cases.

很抱歉，如果这是个坏消息 - 但至少你会不会寻找的东西（大多数计算机科学家认为）是不存在的。

Sorry if it's bad news -but at least you won't be looking for something that (most computer scientists believe) is not there

这篇关于写一个算法来决定是否一个目标数字可以用一组其他数字和具体的运营商达成？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！