Какое минимальное количество шагов можно получить от (a, b) до (0, 0), если вы можете либо удвоить одно число, либо добавить или вычесть любое число из обоих чисел?

Question

Предположим, что это худший вариант развития событий. Добавление любого числа (может быть отрицательным), но должно быть для обоих чисел. Только один может быть удвоен от (а, б). Это можно сделать столько раз, сколько необходимо.

Какое минимальное количество шагов, чтобы добраться до (0, 0)?

Answer 1

Это всегда можно сделать в три этапа.

Первый шаг: добавьте число x, чтобы одно число было в два раза больше другого числа:

 a + x = 2 (b + x)
a - 2b = x

Затем удвойте второе число (что делает оба числа равными) и, наконец, вычтите все (сделав его (0, 0)).

Вы можете сохранить шаги, если оба числа уже равны нулю (0 шагов), оба числа равны (1 шаг) или x равен нулю (два шага).