是否可以从（a，b）移至（c，d）

Question

问题是输出是否可以从给定点移动(a,b)到目标(c,d)

我们仅限于积极的座标

可能有以下两个动作

(a,b) -> (a+b,b)
(a,b) -> (a,b+a)

例如，(1,1)to (5,4)is True 您可以执行以下操作：使用2nd move 3次，(1,1) -> (1,2) -> (1,3) -> (1,4)使用1st move 1次，(1,4) -> (5,4)

我想出了以下递归方法

def move(a,b,c,d):
    if a==c and b==d:
        return True
    elif a>c or b>d:
        return False
    else:
        ans = False
        if a < c:
            if move(a+b,b,c,d):
                return True
        if b < d:
            if move(a,b+a,c,d):
                return True
    return False

a）我的解决方案是否涵盖所有可能的情况？由于我没有测试用例，因此无法确定，但是我认为我确实考虑了所有因素。

b）我的解决方案的时间复杂度是多少？我认为它是指数的，但不能确定。

c）是否有更好的解决方案（在时间复杂度方面）。我们可以使用动态编程吗？

感谢您的投入。

Answer 1

如果所有数字都必须为正，那么我相信有一个更快的解决方案。

尝试查找是否可以到达(a, b)，例如(14, 31)，我们可以注意到要达到正数的唯一方法(14, 31)是将第二条规则应用于(14, 17)。唯一的方法(14, 17)是将第二个规则应用到(14, 3)。唯一的方法(14, 3)是将第一个规则应用于(11, 3)。唯一的方法(11, 3)是将第一个规则应用于(8, 3)，依此类推。因此，唯一可以达到的值(14, 31)是

(14, 31) # Final
(14, 17) # Rule 2
(14, 3)  # Rule 2
(11, 3)  # Rule 1
(8, 3)   # Rule 1
(5, 3)   # Rule 1
(2, 3)   # Rule 1
(2, 1)   # Rule 2
(1, 1)   # Rule 1

因此，算法非常简单。循环播放(c, d)，用(c - d, d)if c > d和(c, d - c)if 替换它c < d，当您打比赛，when c == d，when c < a或时停止d < b。

保罗·汉金（Paul Hankin）在评论中描述了此方法的一种变体O(log n)，尽管我不会尝试对其进行证明。这个版本是O(n)，这里n是大c和d。连续的斐波那契数字可能会采取最多的步骤。

当然，如果您可以有负数，那么所有这些都是没有意义的，因为应用到的第一个规则(-17, 31)也会产生结果，(14, 31)并且您将返回指数级。