Можно ли перейти от (a, b) к (c, d)

Question

Проблема заключалась в том, чтобы вывести, можно ли двигаться из заданной точки (a,b) к цели (c,d)

Мы ограничены только положительными координатами

Возможны следующие два хода

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

Например, (1,1) до (5,4) - это True Вы можете сделать следующее: 3-й ход 3 раза, (1,1) -> (1,2) -> (1,3) -> (1,4) 1-й ход 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

а) Охватывает ли мое решение все возможные случаи. Я не могу проверить наверняка, так как у меня нет тестовых случаев, но я думаю, что все учел.

б) Какова временная сложность моего решения? Я думаю, что это экспоненциально, но не могу сказать наверняка.

в) Есть ли лучшее решение для этого (с точки зрения сложности времени). Можем ли мы использовать динамическое программирование?

Спасибо за любой вклад.

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), если c > d и (c, d - c), если c < d, останавливается, когда вы нажимаете на матч, когда c == d, когда c < a или d < b.

Вариант этого, описанный в комментарии Пола Ханкина, - O(log n), хотя я не собираюсь пытаться это доказать.Эта версия O(n), где n больше c и d.Последовательные числа Фибоначчи, вероятно, сделают большинство шагов.

Конечно, все это бессмысленно, если вы можете иметь отрицательные числа, поскольку первое правило, примененное к (-17, 31), также даст (14, 31), и вы вернетесь кэкспоненциальный.

Answer 2

Ответы:

a.Да, он охватывает все дела.

b.Его сложность экспоненциальна, поскольку из каждого состояния он пытается перейти во все остальные состояния.

c.Да, вы можете использовать динамическое программирование, запоминая dp [a] [b];

Initialie dp [] [] все до -1;

def move(a,b,c,d):
    // memoizing is here.
    if dp[a][b] != -1
        return dp[a][b];
    dp[a][b] = INF; // INF = 100000000;
    if a==c and b==d:
        return dp[a][b] = True
    elif a>c and b>d:
        return dp[a][b] = False
    else:
        ans = False
        if a < c:
            if move(a+b,b,c,d):
                return dp[a][b] = True
        if b < d:
            if move(a,b+a,c,d):
                return dp[a][b] = True
    return dp[a][b] = False

При использовании динамического программирования сложность уменьшается до O (c * d)