生成所有加和为目标数的数学表达式的组合（Java作业/面试）

Question

生成所有加和为目标数的数学表达式的组合（Java作业/面试）

16

我曾经尝试在编程挑战中解决以下问题，但是在一小时内没有完成。我对算法的工作原理有一个想法，但是我不确定如何最好地实现它。下面是我的代码和问题。

pi的前12位数字为314159265358。我们可以将这些数字组成一个表达式，计算出27182（e的前5位数字），方法如下：

3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182

或者

3 + 1 - 415 * 92 + 65358 = 27182

注意输入数字的顺序不会改变，运算符（+、-、/ 或 *）只是简单地插入以创建表达式。

编写一个函数，接受数字列表和目标值，返回这些数字可以组成的所有表达式的方法，这些表达式求值为目标值。

例如：
f("314159265358", 27182) 应该打印：

3 + 1 - 415 * 92 + 65358 = 27182
3 * 1 + 4 * 159 + 26535 + 8 = 27182
3 / 1 + 4 * 159 + 26535 + 8 = 27182
3 * 14 * 15 + 9 + 26535 + 8 = 27182
3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8 = 27182

这个问题很难，因为你可以有任意数字组合，并且不是一次考虑一个数字。我不确定如何进行组合和递归步骤。请注意，解决方案中没有提供括号，但操作顺序是保留的。

我的目标是从某个数字开始。

{"3"}
then
{"31", "3+1", "3-1", "3*1" "3/1"}
then
{"314", "31+4", "3+1+4", "3-1-4", "31/4", "31*4", "31-4"} etc.

然后每次查看列表中的每个值，看它是否是目标值。如果是，将该字符串添加到结果列表中。

这是我的代码

public static List<String> combinations(String nums, int target)
    {

        List<String> tempResultList = new ArrayList<String>();
        List<String> realResultList = new ArrayList<String>();
        String originalNum = Character.toString(nums.charAt(0));


        for (int i = 0; i < nums.length(); i++)
        {
            if (i > 0)
            {
                originalNum += nums.charAt(i); //start off with a new number to decompose
            }
            tempResultList.add(originalNum);
            char[] originalNumCharArray = originalNum.toCharArray();
            for (int j = 0; j < originalNumCharArray.length; j++)
            {
                //go through every character to find the combinations?
                // maybe recursion here instead of iterative would be easier...
            }
            for (String s : tempResultList)
            {
                //try to evaluate
                int temp = 0;
               if (s.contains("*") || s.contains("/") || s.contains("+") || s.contains("-"))
               {
                  //evaluate expression
               } else {
                   //just a number
               }
                if (temp == target)
                {
                    realResultList.add(s);
                }

            }
         tempResultList.clear();
        }
        return realResultList;
    }

有人可以帮忙解决这个问题吗？希望回答中包含代码，因为我需要在生成可能性方面得到帮助。

- John61590

由于每个数字都要将要评估的表达式数量乘以5，这意味着在12个数字之后，您将有244140625个潜在解决方案。虽然这个数字并不是非常大，但它可能不是面试官们想要的。 - biziclop

我复制并粘贴了确切的问题。它是专门为筛选候选人而编写/实现的，因此当然很难。 - John61590

这个问题没问题，我尝试说的是他们可能在寻找比暴力破解更好的答案。 - biziclop

问题是通过网络表单给出的，所以我不知道。唯一可能的解决方案都涉及某种形式的暴力破解。 - John61590

实际上只有5^11或48,828,125种可能性。为了生成它们，可以将其视为字符串操纵：您有12个字符：314159265358，因此有11个位置可以插入空格（将数字连接成更大的数字）或4个运算符之一。在这些5个选择的11个位置上排列组合将生成所有可能性。 - m69 ''snarky and unwelcoming''

顺便提一下，你的结果列表缺少 3 + 1 * 4 * 159 + 26535 + 8 = 27182 和 3141 / 5 / 9 * 26 * 5 * 3 - 5 * 8 = 27182。 - m69 ''snarky and unwelcoming''

3个回答

2

首先，您需要一个可以输入表达式的方法。

3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8

并获得答案：

接下来，您需要创建一个树形结构。您的第一和第二层已经完成。

3
31, 3 + 1, 3 - 1, 3 * 1, 3 / 1

你的第三层缺少一些表达方式。

31 -> 314, 31 + 4, 31 - 4, 31 * 4, 31 / 4
3 + 1 -> 3 + 14, 3 + 1 + 4, 3 + 1 - 4, 3 + 1 * 4, 3 + 1 / 4
3 - 1 -> 3 - 14, 3 - 1 + 4, 3 - 1 - 4, 3 - 1 * 4, 3 - 1 / 4
3 * 1 -> 3 * 14, 3 * 1 + 4, 3 * 1 - 4, 3 * 1 * 4, 3 * 1 / 4
3 / 1 -> 3 / 14, 3 / 1 + 4, 3 / 1 - 4, 3 / 1 * 4, 3 / 1 / 4

当一个分割产生非整数时，您可以停止向树枝添加叶子。

正如您所见，树的每个层级的叶子数量将以快速的速率增加。

对于每个叶子，您必须附加下一个值，下一个添加、减去、乘以和除以的值。作为最后一个示例，这是第四层级的5个叶子：

3 * 1 + 4 -> 3 * 1 + 41, 3 * 1 + 4 + 1, 3 * 1 + 4 - 1, 3 * 1 + 4 * 1,
    3 * 1 + 4 / 1

你的代码必须为每个叶子生成5个表达式，直到使用完所有的输入数字。

当你使用完所有的输入数字时，请检查每个叶子方程式是否等于该值。

- Gilbert Le Blanc

1

对于每个叶子节点，您可以将到目前为止的结果存储起来，以停止重复评估相同的子表达式。 - biziclop

首先，您需要一个可以输入表达式的方法：3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8并得到答案：27182System.out.println(3141 * 5 / 9 * 26 / 5 * 3 - 5 * 8); 可以正确输出答案，无需使用括号。 - John61590

我需要帮助生成这些可能性。 - John61590

@John61590：我已经尽可能清楚地解释了解决方案。下一步是编写程序。创建一个数据类来保存表达式，并使用您的数据类实例作为节点（叶子）构建树形结构。 - Gilbert Le Blanc

1

为什么要防止非整数？考虑 list = 3525，target = 1。 - גלעד ברקן

显示剩余4条评论

0

我的JavaScript实现：
稍后将使用Web Worker改进代码

// was not allowed to use eval , so this is my replacement for the eval function.
function evaluate(expr) {
  return new Function('return '+expr)();
 }
 function calc(expr,input,target) { 
   if (input.length==1) { 
    // I'm not allowed to use eval, so I will use my function evaluate
    //if (eval(expr+input)==target) console.log(expr+input+"="+target);
    if (evaluate(expr+input)==target) document.body.innerHTML+=expr+input+"="+target+"<br>";
   }
   else { 
     for(var i=1;i<=input.length;i++) {
      var left=input.substring(0,i);
      var right=input.substring(i);
      ['+','-','*','/'].forEach(function(oper) {
         calc(expr+left+oper,right,target);
      },this);
     }
   }
 };
 function f(input,total) {
  calc("",input,total);
 }

- Sergio Fernandez

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Stefan Haustein · Accepted Answer

我认为没有必要建立一个树，你应该能够边计算边实现--你只需要稍微延迟加减运算的顺序，以便能够正确考虑优先级：

static void check(double sum, double previous, String digits, double target, String expr) {
   if (digits.length() == 0) {
     if (sum + previous == target) {
       System.out.println(expr + " = " + target);
     }
   } else {
     for (int i = 1; i <= digits.length(); i++) {
       double current = Double.parseDouble(digits.substring(0, i));
       String remaining = digits.substring(i);
       check(sum + previous, current, remaining, target, expr + " + " + current);
       check(sum, previous * current, remaining, target, expr + " * " + current);
       check(sum, previous / current, remaining, target, expr + " / " + current);
       check(sum + previous, -current, remaining, target, expr + " - " + current);
     }
   }
 }

 static void f(String digits, double target) {
   for (int i = 1; i <= digits.length(); i++) {
     String current = digits.substring(0, i);
     check(0, Double.parseDouble(current), digits.substring(i), target, current);
   }
 }