确定的最佳方法从(a,b)开始时是否可以到达对(c,d)

Question

每对(a,b)可以转换为(a + b,b)或(a,a + b).

给定函数bool isPossible(int a,int b,int c,int d),实现返回true或false的逻辑,具体取决于是否可以通过(a,b)到达目标对(c,d)

// (a,b) -> (a, a+b)
// (a,b) -> (a+b,b)
// 2,3 -> 2,5 | 5,3 -> 7,5 | 2, 7 | 5, 8 | 8, 3 -> 12, 5 | 7, 12 | 9, 7 | 2, 9 |5, 13|13,8 | 11, 3 | 8, 11
// a,b -> a,a+b | a+b, b -> a, 2a+b | 2a +b , a+b | a+b, a+2b | a+2b, b -> a, 3a + b | 3a + b , 2a +b |

更新:在此添加我的解决方案. 寻找其他优雅的解决方案会很有趣.

bool isPossible(int a,int b,int c,int d) {

    while(c>=a && d>=b) {
        if(a == c && b==d ) {
            return true;
        }
        int temp = c;
        c= c>d?c-d:c;
        d= d>=temp?d-temp:d;
    }
    return false;
}

更新:此解决方案似乎仅适用于a和b的正值.

Answer 1

您的解决方案基于这样的想法：最好向后走，即从 (c,d) 到 (a,b)。这是因为当你从 (a,b) 开始并向前走时，你对下一对有两种可能性，而当你从 (c,d) 开始并向后走时，你显然只有一种可能性 \xe2\x80\ x94 你需要用最大的值减去最小值。

\n\n

a当和均为b正值时确实如此。在这种情况下，a+b>a和a+b>b，因此给定一(c,d)对，很容易确定变换链中的哪一步是最后一步（这取决于是否c>d或d>c）。a然而，如果或可能为负，则这种推理会被b打破，因为在这种情况下，您不知道是否应该减去c，d反之亦然。这是您的方法中的一个根本问题，我没有看到克服它的简单方法。

\n\n

a如果我们只考虑和为正的情况b，那么我们可以将您的解决方案修改为更有效的解决方案。

\n\n

c考虑当远大于时的情况d。在这种情况下，您将多次减去dfrom c，直到 newc变得小于d。你最终会到达什么？显然是为了(c%d, d). 因此，您可以一步完成，得到与求最大公约数的欧几里得算法非常相似的代码。

\n\n

然而，通过从减法跳转到模除法，您实际上可能跳过了所需的对（即（a，b））。然而，这个问题很容易解决，因为其中一个数字不会改变，所以我们可以很容易地确定这种情况。

\n\n

代码将类似于以下内容（未经测试）

\n\n

while (c > 0 && d > 0) {  // similar to how Eucledian algorithm is written\n    if (c > d) {\n        int new_c = c % d;\n        if (b == d) {  // we should have seen (a,b) here\n            return (a % d == new_c && a >= new_c && a <= c);\n        }\n        c = new_c;\n    } else {\n        //  a symmetrical case follows\n        ...\n    }\n} \n

\n\n

该代码具有时间复杂度O(log(c + d))，而带有减法的代码可以在O(c+d).

\n\n\n\n

至于当a和/或b可以为负时的情况，这似乎是一个更困难的问题。

\n