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

本文介绍了是否可以从（a，b）移至（c，d）的处理方法，对大家解决问题具有一定的参考价值，需要的朋友们下面随着小编来一起学习吧！ 问题描述

问题是输出是否可以从给定点（a，b）移至目标（c，d）

The problem was to output whether it is possible to move from a given point (a,b) to target (c,d)

我们仅限于正坐标

以下两个步骤是可能

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

例如，（1,1） 到（5,4）是 True 您可以执行以下操作：使用2次移动3次，（1,1）-> （1,2）-> （1,3）-> （1,4）使用第一步移动1次（1,4）-> （5,4） 我想出了以下递归方法

For instance, (1,1) to (5,4) is True You can do the following: Using 2nd move 3 times, (1,1) -> (1,2) -> (1,3) -> (1,4) Using 1st move 1 time (1,4) -> (5,4) I came up with the following recursive method

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）我的解决方案是否涵盖所有可能的情况。由于我没有测试用例，因此无法确定，但是我认为我确实考虑到了所有问题。

a) Does my solution cover all the possible cases. I am unable to verify for sure since I do not have test cases, but I think I did take everything into account.

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

b) What is the time complexity of my solution? I think it is exponential but can't say for sure.

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

c) Is there a better solution to this (in terms of time complexity). Can we use dynamic programming?

谢谢您的任何输入。

推荐答案

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

If all the numbers have to be positive, then I believe there is a much quicker solution.

试图找出我们是否可以从中获得收益（a，b）表示为（14，31），我们可以注意到，只有正数才能达到（14，31）将第二条规则应用于（14，17）。到达（14，17）的唯一方法是将第二条规则应用于（14，3）。到达（14，3）的唯一方法是将第一个规则应用于（11，3）。 （11，3）的唯一方法是将第一个规则应用于（8，3），依此类推上。因此，唯一可以达到（14，31）的值是

Trying to find if we can get from (a, b) to, say (14, 31), we can note that the only way with positive numbers to reach (14, 31) is to apply the second rule to (14, 17). The only way to get to (14, 17) is to apply the second rule to (14, 3). The only way to get to (14, 3) is to apply the first rule to (11, 3). The only way to (11, 3) is to apply the first rule to (8, 3), and so on. So the only values that can reach (14, 31) are

(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 和（c，d-c）如果 c< d ，当您打比赛时停止，当 c == d ，当 c< a 或 d< b 。

So an algorithm is pretty simple. Loop on (c, d), replacing it with (c - d, d) if c > d and with (c, d - c) if c < d, stopping when you hit a match, when c == d, when c < a or d < b.

Paul Hankin在评论中描述的一个变体是 O（log n），尽管我不会尝试证明这一点。此版本为 O（n），其中 n 是 c 和 d 。连续的斐波那契数可能会采取最多的步骤。

A variant of this described in a comment by Paul Hankin is O(log n), although I'm not going to try to prove it. This version is O(n), where n is the larger of c and d. Consecutive Fibonacci numbers will probably take the most steps.

当然，如果您可以有负数，那么这一切都是没有意义的，因为第一个规则适用于 （-17，31）也会产生（14，31），您将返回指数级。

Of course all this is meaningless if you can have negative numbers, since the first rule applied to (-17, 31) would also yield (14, 31) and you're back to exponential.