Возможный путь от к координатам - PullRequest
Новая
       9

Возможный путь от к координатам

3 голосов
/ 04 апреля 2019

У меня недавно было собеседование, и мой алгоритм только прошел все тестовые случаи, кроме одного, и я не могу понять, почему. Проблема, которую мне нужно решить, была:

При заданной точке стояния (a, b) в 2D-сетке можно достичь точки назначения (x, y) или нет. Единственная операция, которую он может сделать, - это перейти в точку (a + b, b) или (a, a + b) из некоторой точки (a, b).

Я попытался решить это с помощью gcd. например Если gcd (a, b) = gcd (x, y), то это возможно, иначе нет. Интуиция была, если k будет gcd a & b. тогда k также разделит (a + b). Я использовал следующий алгоритм для расчета gcd: 

int gcd(int a, int b) {
    return b == 0 ? a : gcd(b, a % b);
}

РЕДАКТИРОВАТЬ: также числа a, b, x и y все положительные целые числа.

Ответы [ 2 ]

1 голос
/ 04 апреля 2019

GCD (3,7) = GCD (7,3), но ни один из них недоступен для другого. Ваше состояние необходимо, но не достаточно.

Обратите внимание, что для каждой точки существует уникальный возможный предшественник. То есть для точки (a, b), если a> b, то предшественником является (a-b, b), в противном случае предшественником является (a, b-a).

0 голосов
/ 04 апреля 2019

Теперь у вас есть 2 вопроса к сообщению:

  1. Как мне решить алгоритм?
    Photon ссылка охватывает это хорошо.
  2. Почему не работает GCD?

GCD является необходимым, но не достаточным условием.

Верно, если a = b, то (x, y) достижимотогда и только тогда, когда GCD (x, y) = a = b.Однако это не распространяется на все проблемные пары.Тривиальный контрпример пытается достичь (1, N) из (N, 1), где N> 1.Другой (2, 3) => (4, 5).

Итак, давайте перейдем к качественной части: «Я не могу понять ...».Я подозреваю, что проблема в том, что вы видите сходство между алгоритмом Евклида и вашим шагом добавления.Более того, алгоритм «назад» в ссылке предполагает применение алгоритма Евклида.

Он может, в некотором смысле, но не так просто и универсально, как вы пытались его использовать.Думайте о проблеме как о графике на целочисленной решетке в декартовой плоскости.Разрешенные операции (направленные ребра) определяют, как вы можете перемещаться из одной точки в другую.

Ключевой термин здесь направлен : как только вы «переместились» из начальной точки в однукоторый определяет GCD в вашей системе, вы не имеете свободу повторять эти шаги.Вы перемещаетесь либо вперед или назад через пространство графика.

Например, хотя ваши обратные переходы позволяют вам переходить от (4, 1) к (1, 1) или от (1, 4) к (1, 1), вы не можете использовать это, чтобы завершить путь от (4, 1) до (1, 4): половина этих движений в направлении не разрешена.

Это помогает рассеять путаницу?

...