22

我正在处理一个家庭作业问题，它问我这个问题：

给定一组有限的数字和一个目标数字，找出该集合是否可用于使用基本数学运算（add、sub、mult、div）计算目标数字，并仅使用集合中的每个数字一次（所以我需要用尽集合）。这必须通过递归来完成。

所以，例如，如果我有一套

{1, 2, 3, 4}

和目标 10，然后我可以通过使用

((3 * 4) - 2)/1 = 10.

我试图用伪代码来表达算法，但到目前为止还没有走得太远。我认为图表是要走的路，但肯定会感谢您对此的帮助。谢谢。

4

7 回答 7

5

这并不意味着是最快的解决方案，而是一个有启发性的解决方案。

  • 它以后缀符号递归生成所有方程
  • 它还提供从后缀到中缀符号的翻译
  • 没有实际的算术计算，所以你必须自己实现
    • 小心除以零

使用 4 个操作数，4 个可能的运算符，它生成所有 7680 = 5 * 4！* 4^3 种可能的表达方式。

  • 5是加泰罗尼亚语（3）。Catalan(N) 是对 N+1 个操作数进行括号运算的方法数。
  • 4！因为 4 个操作数是可置换的
  • 4^3 因为这 3 个操作员各有 4 个选择

这肯定不能很好地扩展，因为 N 个操作数的表达式数量是 [1, 8, 192, 7680, 430080, 30965760, 2724986880, ...]。

一般来说，如果你有n+1操作数，并且必须插入n从k可能性中选择的运算符，那么就有(2n)!/n! k^n可能的方程。

祝你好运！

import java.util.*;

public class Expressions {
    static String operators = "+-/*";

    static String translate(String postfix) {
        Stack<String> expr = new Stack<String>();
        Scanner sc = new Scanner(postfix);
        while (sc.hasNext()) {
            String t = sc.next();
            if (operators.indexOf(t) == -1) {
                expr.push(t);
            } else {
                expr.push("(" + expr.pop() + t + expr.pop() + ")");
            }
        }
        return expr.pop();
    }

    static void brute(Integer[] numbers, int stackHeight, String eq) {
        if (stackHeight >= 2) {
            for (char op : operators.toCharArray()) {
                brute(numbers, stackHeight - 1, eq + " " + op);
            }
        }
        boolean allUsedUp = true;
        for (int i = 0; i < numbers.length; i++) {
            if (numbers[i] != null) {
                allUsedUp = false;
                Integer n = numbers[i];
                numbers[i] = null;
                brute(numbers, stackHeight + 1, eq + " " + n);
                numbers[i] = n;
            }
        }
        if (allUsedUp && stackHeight == 1) {
            System.out.println(eq + " === " + translate(eq));
        }
    }
    static void expression(Integer... numbers) {
        brute(numbers, 0, "");
    }

    public static void main(String args[]) {
        expression(1, 2, 3, 4);
    }
}
于 2010-03-07T02:54:12.213 回答
5

在考虑如何解决问题之前（比如用图表），看看问题真的很有帮助。如果您发现自己陷入困境并且似乎无法提出任何伪代码，那么很可能是有什么阻碍了您；其他一些尚未解决的问题或疑虑。在这种情况下，一个“棘手”问题的示例可能是“这个问题的递归究竟是什么？”

在阅读下一段之前，请先尝试回答这个问题。如果你知道什么是递归问题，那么编写一个递归方法来解决它可能不是很困难。

您想知道某个使用一组数字（每个数字仅使用一次）的表达式是否为您提供了目标值。有四个二元运算，每个都有一个逆运算。因此，换句话说，您想知道第一个数字是否与其他数字的某种表达式一起运算给了您目标。好吧，换句话说，您想知道“其他”数字的某些表达是否是[...]。如果没有，那么对第一个数字使用第一个操作并不能真正满足您的需求，因此请尝试其他操作。如果他们不工作，那么也许它就是不应该的。

编辑：我认为这是四个不带括号的运算符的中缀表达式，因为对原始问题的评论说括号是为了示例而添加的（为了清楚起见？）并且没有明确说明括号的使用。

于 2010-03-07T05:22:32.390 回答
4

好吧，你没有提到效率，所以我将发布一个非常强力的解决方案，如果你愿意的话，让你优化它。由于您可以使用括号，因此使用反向波兰表示法很容易强制它：

首先，如果你的集合有 n 个数字，你必须使用 n - 1 个运算符。因此，您的解决方案将由来自 {{your given set}、{*、/、+、-}} 的 2n - 1 个符号序列给出

st = a stack of length 2n - 1
n = numbers in your set
a = your set, to which you add *, /, +, -
v[i] = 1 if the NUMBER i has been used before, 0 otherwise

void go(int k)
{
  if ( k > 2n - 1 ) 
  {
    // eval st as described on Wikipedia. 
    // Careful though, it might not be valid, so you'll have to check that it is   
    // if it evals to your target value great, you can build your target from the given numbers. Otherwise, go on.

    return;
  }

  for ( each symbol x in a )
    if ( x isn't a number or x is a number but v[x] isn't 1 )
    {
      st[k] = x;
      if ( x is a number )
        v[x] = 1;

      go(k + 1);
    }
}
于 2010-03-06T12:56:27.523 回答
3

一般来说，当您需要递归地做某事时，从“底部”开始并向上思考会有所帮助。考虑：您有一组Sn个数字{a,b,c,...}和一组四个操作{+,-,*,/}。让我们调用在集合上运行的递归函数F(S)

  • 如果n是 1，那么F(S)就是那个数字。
  • 如果n为 2，F(S)则可以是八件事：
    • S从（2 个选项）中选择您的左手号码
    • 然后选择要应用的操作（4 个选项）
    • 你的右手号码将是集合中剩下的任何东西
  • 现在，您可以从n =2 的情况进行概括：
    • x从中选择一个数字S作为左侧操作数（n 个选项）
    • 选择要应用的操作
    • 你的右手号码将是F(S-x)

我会让你从这里拿走。:)

编辑：马克提出了有效的批评；上述方法不会得到绝对的一切。要解决该问题，您需要以稍微不同的方式考虑它：

  • 在每个步骤中，您首先选择一个操作（4 个选项），然后
  • 分成 S两组，用于左右手操作数，
  • 并递归地应用于F两个分区

不过，将一组的所有分区分成两部分本身并不是一件容易的事。

于 2010-03-06T12:53:44.210 回答
2

关于如何解决这个问题的最佳线索是您的老师/教授希望您使用递归这一事实。也就是说，这不是一个数学问题——它是一个搜索问题。

不要放弃太多（毕竟这是家庭作业），但您必须使用运算符、数字和包含剩余数字的列表来调用递归函数。递归函数将从列表中提取一个数字，并使用传入的操作将其与传入的数字（即您的运行总数）结合起来。获取运行总数并使用列表中的剩余项目再次调用自己（您必须在调用中迭代列表，但调用顺序是深度优先的）。对四个运算符中的每一个执行一次此操作，除非在前一阶段的搜索中取得了成功。

我更新了这个以使用列表而不是堆栈

当操作的结果是您的目标编号并且您的列表为空时，那么您已成功找到一组操作（那些追踪到成功叶子的路径的操作） - 设置成功标志并展开。请注意，运算符不在列表中，也不在调用中：函数本身总是遍历所有四个。您从成功的叶子“展开”运算符序列以获取序列的机制是返回当前运算符和附加到递归调用返回的值的数字（其中只有一个会成功，因为您在成功时停止 - 显然, 是要使用的）。如果没有一个成功，那么无论如何你返回什么都不重要。

更新当您必须考虑像 Daniel 发布的那样的表达式时，这要困难得多。你有数字和分组的组合（数字是因为 / 和 - 是顺序敏感的，即使没有分组和分组，因为它改变了优先级）。然后，当然，你也有操作的组合。很难管理 (4 + 3) * 2 和 4 + (3 * 2) 之间的差异，因为分组不会像运算符或数字那样递归（您可以在制作 (深度优先）递归调用）。

于 2010-03-06T13:27:44.997 回答
2

这里有一些 Python 代码可以帮助您入门：它只打印所有可能的表达式，而不必过多担心冗余。您需要对其进行修改以评估表达式并与目标数字进行比较，而不是简单地打印它们。

left基本思想是：给定一组数字 S ，以所有可能的方式将 S 划分为两个子集right（我们不关心 and 中的元素的顺序或元素left）right，使得leftandright都是非空的。现在对于这些分区中的每一个，找到所有组合元素的方法left（递归！），类似地 for right，并将两个结果值与所有可能的运算符组合。当一个集合只有一个元素时，递归会触底，在这种情况下，只有一个可能的值。

即使您不了解 Python，该expressions函数也应该相当容易理解；该splittings函数包含一些 Python 奇怪的东西，但它所做的只是将列表的所有分区查找l为左右部分。

def splittings(l):
    n = len(l)
    for i in xrange(2**n):
        left = [e for b, e in enumerate(l) if i & 2**b]
        right = [e for b, e in enumerate(l) if not i & 2**b]
        yield left, right

def expressions(l):
    if len(l) == 1:
        yield l[0]
    else:    
        for left, right in splittings(l):
            if not left or not right:
                continue
            for el in expressions(left):
                for er in expressions(right):
                    for operator in '+-*/':
                        yield '(' + el + operator + er + ')'

for x in expressions('1234'):
    print x
于 2010-03-06T17:13:53.177 回答
-1

普斯多代码：

Works(list, target)
for n in list
tmp=list.remove(n)
return Works(tmp,target+n) or Works(tmp,target-n) or Works(tmp, n-target) or ...

那么你只需要把基本情况放进去。我想我放弃了很多。

于 2010-03-07T05:37:48.537 回答