首页
学习
活动
专区
圈层
工具
发布
首页
学习
活动
专区
圈层
工具
MCP广场
社区首页 >问答首页 >C++ -如何迭代数组的所有组合以强制执行

C++ -如何迭代数组的所有组合以强制执行
EN

Stack Overflow用户
提问于 2020-10-24 09:57:05
回答 1查看 494关注 0票数 0

我有一个练习,发现所有的1-9的可能的总和加起来是100,规则是每个数字必须使用一次和顺序,并且允许的运算符是+/-并把数字相加在一起。1+2+3-4+5+6+ 78 +9= 100

我已经编写了计算它的逻辑,我有一个由9个元素组成的数组,它代表可以放置运算符的所有位置,1是+,2是-,3是将数字相加在一起。上面示例的运算符字符串为{1,1,1,2,1,1,1,3,1}。

所以我真正的问题是如何迭代这个运算符数组并生成每一个可能的数字组合。

所以我从{1,1,1,1,1,1,1}开始

直到数组都是3s

代码语言:javascript
运行
复制
111111111
111111112
111111113
111111121
111111122
111111123
111111131

我在去年左右已经为这个函数编写了一个函数,但是它使用了很多if on语句,这使得函数变得不灵活,我想要建议什么是正确的程序,因为我想改进我的编码。

EN

回答 1

Stack Overflow用户

回答已采纳

发布于 2020-10-24 11:23:06

这次行动是如此公平,以至于问题是关于家庭作业的。

我做了一个练习,找出所有可能的1-9,加起来是100。

因此,我并没有给出这个练习的完整解决方案,但是为了实现这一点,不需要添加太多的内容。

给出了9个参数(数字1…)( 9)二进制运算符的参数。

二进制运算符需要左参数和右参数。因此,我得出结论,有8个位置可以选择一个二进制运算符。

这对+-来说很容易,但是添加数字又如何呢?

这是一项我称之为“级联”的行动。实际上,将“串联”表示为简单的算术表达式很容易:

代码语言:javascript
运行
复制
lr: 10 * l + r

“级联”问题解决后,就不再那么复杂了。

我的第一个想法是使用像函子或函数指针之类的东西,但是没有函子或函数指针就不难解决。

为此,我定义了操作的枚举:

代码语言:javascript
运行
复制
enum Op { Add, Sub, Cat, NOps};

以及用于这些操作的compute()函数:

代码语言:javascript
运行
复制
int compute(Op op, int l, int r)
{
  switch (op) {
    case Add: return l + r;
    case Sub: return l - r;
    case Cat: return l * 10 + r;
  }
  // ...unreachable for the humans eyes but not for the compiler...
  assert(false); return 0;
}

下一个拼图是一个函数,它计算一个完整方程的结果。方程由N个参数(数字)和N-1运算符定义.

在实现这个过程中,我意识到“级联”必须具有更高的优先级。否则,计算函数将无法正常工作。

示例:

代码语言:javascript
运行
复制
12 + 23 = 35 

如果不考虑“级联”的更高优先级,这将导致:

代码语言:javascript
运行
复制
12 + 23 = ((12) + 2)3 = (14)3 = 143

对于这个问题的简单解决方案,计算函数应该运行两次:

  1. 解决所有连接
  2. 解决所有其他操作。
代码语言:javascript
运行
复制
int compute(std::vector<int> args, std::vector<Op> &ops)
{
  assert(args.size() == ops.size() + 1);
  // perform cat()
  std::vector<int> args2;
  args2.push_back(args[0]);
  for (size_t i = 0, n = ops.size(); i < n; ++i) {
    if (ops[i] == Cat) {
      int l = args2.back(); args2.pop_back();
      args2.push_back(compute(Cat, l, args[i + 1]));
    } else args2.push_back(args[i + 1]);
  }
  // perform add() and sub()
  int result = args2[0];
  for (size_t i = 0, j = 1, n = ops.size(); i < n; ++i) {
    const Op op = ops[i];
    if (op != Cat) result = compute(op, result, args2[j++]);
  }
  return result;
}

最后一个缺失的部分是里程计-like迭代std::vector<Op> &ops中的值。最简单的方法(虽然不是最优雅的)是相应数量的嵌套for循环。

所以,我们在这里:

代码语言:javascript
运行
复制
#include <cassert>
#include <iostream>
#include <vector>

enum Op { Add, Sub, Cat, NOps};

int compute(Op op, int l, int r)
{
  switch (op) {
    case Add: return l + r;
    case Sub: return l - r;
    case Cat: return l * 10 + r;
  }
  // ...unreachable for the humans eyes but not for the compiler...
  assert(false); return 0;
}

/* Attention!
 * cat() must have higher precedence then add() and sub()
 */

int compute(std::vector<int> args, std::vector<Op> &ops)
{
  assert(args.size() == ops.size() + 1);
  // perform cat()
  std::vector<int> args2;
  args2.push_back(args[0]);
  for (size_t i = 0, n = ops.size(); i < n; ++i) {
    if (ops[i] == Cat) {
      int l = args2.back(); args2.pop_back();
      args2.push_back(compute(Cat, l, args[i + 1]));
    } else args2.push_back(args[i + 1]);
  }
  // perform add() and sub()
  int result = args2[0];
  for (size_t i = 0, j = 1, n = ops.size(); i < n; ++i) {
    const Op op = ops[i];
    if (op != Cat) result = compute(op, result, args2[j++]);
  }
  return result;
}

const char* toString(Op op)
{
  static const char* texts[] = { " + ", " - ", "" };
  return texts[op];
}

int main()
{
  std::vector<int> args = { 1, 2, 3, 4 };
  std::vector<Op> ops(args.size() - 1);
  for (int op2 = 0; op2 < NOps; ++op2) {
    ops[2] = (Op)op2;
    for (int op1 = 0; op1 < NOps; ++op1) {
      ops[1] = (Op)op1;
      for (int op0 = 0; op0 < NOps; ++op0) {
        ops[0] = (Op)op0;
        // print equation
        std::cout << args[0];
        for (size_t i = 0, n = ops.size(); i < n; ++i) {
          std::cout << toString(ops[i]) << args[i + 1];
        }
        std::cout << " = " << compute(args, ops) << '\n';
      }
    }
  }
}

输出:

代码语言:javascript
运行
复制
1 + 2 + 3 + 4 = 10
1 - 2 + 3 + 4 = 6
12 + 3 + 4 = 19
1 + 2 - 3 + 4 = 4
1 - 2 - 3 + 4 = 0
12 - 3 + 4 = 13
1 + 23 + 4 = 28
1 - 23 + 4 = -18
123 + 4 = 127
1 + 2 + 3 - 4 = 2
1 - 2 + 3 - 4 = -2
12 + 3 - 4 = 11
1 + 2 - 3 - 4 = -4
1 - 2 - 3 - 4 = -8
12 - 3 - 4 = 5
1 + 23 - 4 = 20
1 - 23 - 4 = -26
123 - 4 = 119
1 + 2 + 34 = 37
1 - 2 + 34 = 33
12 + 34 = 46
1 + 2 - 34 = -31
1 - 2 - 34 = -35
12 - 34 = -22
1 + 234 = 235
1 - 234 = -233
1234 = 1234

coliru现场演示

注:

我只使用了4位而不是9位数字,因为我认为这足以显示原理,并且应该很容易被OP扩展(以及添加计算结果的测试是否可以接受)。

票数 0
EN
页面原文内容由Stack Overflow提供。腾讯云小微IT领域专用引擎提供翻译支持
原文链接:

https://stackoverflow.com/questions/64512118

复制
相关文章

相似问题

领券
问题归档专栏文章快讯文章归档关键词归档开发者手册归档开发者手册 Section 归档