4

这是家庭作业！请不要给我解决方案，只是一个提示！

问题是应用从 N 开始的一系列运算来找到 M。输入是 6 个数字：A、B、C、D、N、M，其中 A 对应于加法，B 对应于减法，C 对应于乘法，D 对应于分配。这是一个例子：

10 4 2 3
21 32

我们将尝试使用这些操作从 21 开始找到数字 32

ADD 10     // "A" number
SUB 4      // "B" number
MUL By 2   // "C" number
DIV By 3   // "D" number

可能的答案是：

32 = ((((21 * 2) + 10) - 4) / 3) * 2

1如果有操作序列，则程序输出，否则0。有人可以给我一个提示如何解决这个问题吗？

4

4 回答 4

2

您可以进行某种图形搜索，但有四个数字和四个可能的操作来执行这些数字，每个节点将有 16 个分支，并且它可能会很快变大。

于 2013-04-03T10:51:19.600 回答
1

似乎最大的问题将是确定是否没有答案。如果 GCD(A, B) 为 1，则答案为 1，因为这意味着有一个序列ADD AandSUB B操作将源值递增或递减 1，所以如果你重复这个序列足够多次，你将达到任何数字从任何其他号码。如果它不是 1，并且您的 DIV 操作将值四舍五入，则搜索您是否可以target mod GCD(A,B)使用所有 4 个操作达到值。该值应该相当小，因此您可以进行上述图形搜索，通过 AND 相等分支裁剪下一步的结果，这些mod LCM(A,B)分支产生模 GCD(A,B) 操作的相等值。所以，如果你会达到一个等于target mod GCD(A,B)，您可以输出 1，如果没有达到，则输出 0。图游走最终将停止，因为(0, LCM(A,B)-1)区间中有固定数量的不同值，如果编程正确，将满足内存和时间要求。

是的，您必须注意特殊情况，例如 A=0、B=0、C=1 或 D=1。例如，序列0 3 1 3 81 5将产生 1，而0 3 1 3 81 29产生 0。 编辑：修改了裁剪中的模数，并发布了正确的 A 和 B 缩写函数。

于 2013-04-03T14:14:32.600 回答
0

如果您使用多态函子进行操作并继续尝试，您可以用蛮力解决这个问题。不过，您需要一个良好的中断标准（例如将应用操作的数量限制为 10 或类似的东西）。

关于函子的答案：C++ 函子 - 及其用途

多态性应该可以在网络上找到。

例子：

class operation {
public:
    enum TYPE { ADD = 0, SUB };

    virtual int operator()(int left, int right) = 0;
}

class add : public operation {
public:
    int operator()(int left, int right) {
        return left + right;
    }
}

class sub : public operation {
public:
    int operator()(int left, int right) {
        return left - right;
    }
}

int main() {
    std::vector<operation*> foo;
    foo[0] = new add();
    foo[1] = new sub();
    foo[2] = new add();


    int bar = 21;
    for (auto& op : foo) {
        bar = (*op)(bar, 2);
        std::cout << bar << std::endl;
    }
}

这些类是函子。使用这样的构造，您可以将算法或基本操作视为变量，您可以分配或随机化或随机化或任何您喜欢的。由于从操作中继承了所有相同的接口，他们都知道是什么()意思，但行为不同。

拥有这样的东西可以让您存储和回溯使用过的操作，并通过排列进行简单的循环。当你这样做时，你应该知道，你应该限制每组可能的最大操作组合的数量，否则你会遇到无限循环/递归。

于 2013-04-03T10:39:54.183 回答
0

此答案基于 math.stackexchange 上此问题的公认答案：

https://math.stackexchange.com/questions/354625/how-to-compose-given-add-sub-mult-div-functions-to-map-an-integer-m-to-n

给定六个输入（a、b、c、d、M、N）

  • a：我们可以添加的数字
  • b：我们可以减去的数字
  • c：我们可以乘的数
  • d：我们可以除的数
  • M：起始编号
  • N：结束编号

我假设它们都是整数，并且a> 0，b> 0，c可以是正数或负数，d不等于0。

然后有一种方法可以通过应用 add、sub、mult、div 将 M 转换为 N，

当且仅当

存在整数 m 和 n 使得

M*(c^m) 等价于 N*(d^n) 所有 mod gcd(a,b)

因此，首先要做的是找到 a 和 b 的最大公约数（我推荐这里描述的欧几里德算法。将 gcd 称为“g”。

mod应用于双方以验证相等性。

因此，开始列出左侧对于不同 m 可以取的可能值：

(M*( Pow(c,m) )) % g

然后，开始列出右侧对于不同 n 可以取的可能值：

(N*( Pow(d,n) )) % g

您将希望从零开始 m 和 n 并逐步向上。

最终，双方将开始重复，因为您正在使用 mod。

如果您在任何时候找到匹配项，即左侧等于某个右侧，则返回 1。

否则，一旦您用尽了所有左手值和右手值，没有匹配项，则返回 0。

请注意，C++ 中的 mod 运算符 (%) 对于负数的行为确实与上述数学描述的不同。您需要将 mod 的结果调整为始终在 0 <= result < g 范围内

最后，这仅适用于除法根据正常数学进​​行的情况，即 3 / 2 = 1.5 等等。

在您的情况下，您需要稍微修改公式以接受整数除法。特别是等式的右手边处理除法。有点像下面的等式是如何工作的，我们可以取一个除法，把它移到另一边，它就变成了一个乘法。

x / 3 = 1

x = 1*3

每次对 d 执行电源时，您都需要允许 rhs 取多个值。例如，在上面的例子中，我们需要让 1*3 等于 3,4 或 5。

所以，如果 d = 3，那么

  • Pow(d,0) = 1。
  • Pow(d,1) = 3 或 4 或 5。
  • Pow(d,2) = 9 或 10 或 11 或 12 或 13 或 14 或 15 或 16 或 17

您将看到 9 = 3*3、12 = 4*3 和 15 = 5*3。因此，即使对于不同的 d 值，该模式也应该易于复制。

我还没有尝试过最后一部分，所以我不完全确定这是否完全涵盖了整数除法的所有情况，但我认为确实如此，尽管它有点乏味。

于 2013-04-11T07:33:53.983 回答