代码之家 › 专栏 › 技术社区 › Maxpm

处理“所有组合”项目的最佳方法是什么?

algorithm performance

Maxpm · 技术社区 · 15 年前

我被分配了一个学校项目,在这个项目中,我需要使用整数尽可能多地提出整数。 2 3 4 以及操作人员 + - * / % . 然后我必须输出整数 cout 以及我如何得到答案。例如:

cout << "2 + 3 - 4 = " << 2 + 3 - 4;

每个整数只能使用一次 咳嗽 声明,不能有重复的答案。

其他人似乎都在使用“蛮力”方法(即复制和粘贴相同的语句,更改数字和运算符),但这似乎很难奏效。我想我应该试着一个接一个地循环浏览每个号码和接线员,检查是否已经找到答案,但我不确定最简单的方法是什么。

我想我可以使用嵌套循环,但是仍然存在检查是否已经找到答案的问题。我尝试将答案存储在向量中,但无法将向量传递给用户定义的函数,该函数检查向量中是否存在值。

3 回复 | 直到 13 年前

Cameron Skinner 15 年前

你可以用一个 map 或A hash_map 来自标准模板库(STL)。这些结构有效地存储键值对。在使用它们之前,请仔细阅读它们,但它们可能会为您提供一个良好的起点。提示:您计算的整数可能会成为好的键。

JoshMachine 15 年前

假设您可以使用集合(2,3,4)中的每个数字,只有一次有3个!排列这三个数字的方法。然后有2个地方做标记,总共有5个符号(+- */%)所以有5*5=25种方法。所以你总共有3个!*25个表达式。然后您可以创建一个哈希映射,其中键为数字,值为表达式。如果散列映射已经包含键,则跳过该表达式。

paxdiablo 15 年前

您可以尝试一些元编程,如下所示。它的优点是使用C本身来计算表达式,而不是使用自己的计算器(可能会出错):

#include <stdlib.h>
#include <iostream>
#include <fstream>
using namespace std;

int main (void) {
  int n1, n2, n3;
  const char *ops[] = {" + ", " - ", " * ", " / ", " % ", 0};
  const char **op1, **op2;
  ofstream of;

  of.open ("prog2.cpp", ios::out);

  of << "#include <iostream>\n";
  of << "using namespace std;\n";
  of << "#define IXCOUNT 49\n\n";
  of << "static int mkIdx (int tot) {\n";
  of << "  int ix = (IXCOUNT / 2) + tot;\n";
  of << "  if ((ix >= 0) && (ix < IXCOUNT)) return ix;\n";
  of << "  cout << \"Need more index space, "
     << "try \" << IXCOUNT + 1 + (ix - IXCOUNT) * 2 << \"\\n\";\n";
  of << "  return -1;\n";
  of << "}\n\n";
  of << "int main (void) {\n";
  of << "  int tot, ix, used[IXCOUNT];\n\n";
  of << "  for (ix = 0; ix < sizeof(used)/sizeof(*used); ix++)\n";
  of << "    used[ix] = 0;\n\n";

  for (n1 = 2; n1 <= 4; n1++) {
    for (n2 = 2; n2 <= 4; n2++) {
      if (n2 != n1) {
        for (n3 = 2; n3 <= 4; n3++) {
          if ((n3 != n1) && (n3 != n2)) {
            for (op1 = ops; *op1 != 0; op1++) {
              for (op2 = ops; *op2 != 0; op2++) {
                of << "    tot = " << n1 << *op1 << n2 << *op2 << n3 << ";\n";
                of << "    if ((ix = mkIdx (tot)) < 0) return ix;\n";
                of << "    if (!used[ix])\n";
                of << "      cout << " << n1 << " << \"" << *op1 << "\" << "
                   << n2 << " << \"" << *op2 << "\" << " << n3
                   << " << \" = \" << tot << \"\\n\";\n";
                of << "    used[ix] = 1;\n\n";
              }
            }
          }
        }
      }
    }
  }

  of << "    return 0;\n";
  of << "}\n";

  of.close();

  system ("g++ -o prog2 prog2.cpp ; ./prog2");
  return 0;
}

这给了你:

2 + 3 + 4 = 9
2 + 3 - 4 = 1
2 + 3 * 4 = 14
2 + 3 / 4 = 2
2 + 3 % 4 = 5
2 - 3 + 4 = 3
2 - 3 - 4 = -5
2 - 3 * 4 = -10
2 - 3 % 4 = -1
2 * 3 + 4 = 10
2 * 3 * 4 = 24
2 / 3 + 4 = 4
2 / 3 - 4 = -4
2 / 3 * 4 = 0
2 % 3 + 4 = 6
2 % 3 - 4 = -2
2 % 3 * 4 = 8
2 * 4 + 3 = 11
2 / 4 - 3 = -3

我不是完全但是,把这个作为一项任务交给别人是明智的。