我有一个练习,发现所有的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
111111111
111111112
111111113
111111121
111111122
111111123
111111131
我在去年左右已经为这个函数编写了一个函数,但是它使用了很多if on语句,这使得函数变得不灵活,我想要建议什么是正确的程序,因为我想改进我的编码。
发布于 2020-10-24 11:23:06
这次行动是如此公平,以至于问题是关于家庭作业的。
我做了一个练习,找出所有可能的1-9,加起来是100。
因此,我并没有给出这个练习的完整解决方案,但是为了实现这一点,不需要添加太多的内容。
给出了9个参数(数字1…)( 9)二进制运算符的参数。
二进制运算符需要左参数和右参数。因此,我得出结论,有8个位置可以选择一个二进制运算符。
这对+
和-
来说很容易,但是添加数字又如何呢?
这是一项我称之为“级联”的行动。实际上,将“串联”表示为简单的算术表达式很容易:
lr: 10 * l + r
“级联”问题解决后,就不再那么复杂了。
我的第一个想法是使用像函子或函数指针之类的东西,但是没有函子或函数指针就不难解决。
为此,我定义了操作的枚举:
enum Op { Add, Sub, Cat, NOps};
以及用于这些操作的compute()
函数:
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运算符定义.
在实现这个过程中,我意识到“级联”必须具有更高的优先级。否则,计算函数将无法正常工作。
示例:
12 + 23 = 35
如果不考虑“级联”的更高优先级,这将导致:
12 + 23 = ((12) + 2)3 = (14)3 = 143
对于这个问题的简单解决方案,计算函数应该运行两次:
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
循环。
所以,我们在这里:
#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';
}
}
}
}
输出:
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扩展(以及添加计算结果的测试是否可以接受)。
https://stackoverflow.com/questions/64512118
复制相似问题