Самый короткий путь между двумя целыми числами путем добавления или вычитания

Ответ 1

Пусть начнется набор интересных наблюдений. Как отмечалось многими другими, цель состоит в том, чтобы найти некоторую линейную комбинацию 5x + 7y + 12z = b - a с целыми коэффициентами, для которой | x | + | y ​​| + | z | минимизируется. Но между этими тремя числами есть очень интересные связи:

• Если у нас когда-либо есть комбинация 5x + 7y + 12z, где x и y оба положительные или оба отрицательные, мы можем отменить некоторое количество x и y, чтобы добавить эквивалентное число 12s. Другими словами, ни одно оптимальное решение не имеет одинакового знака как для x, так и для y, потому что мы всегда можем сделать это решение лучше.
• Если у нас когда-либо есть комбинация 5x + 7y + 12z, где y и z имеют противоположные знаки, мы всегда можем удалить 7 и 12 и добавить 5 соответствующих знаков, чтобы получить лучшее решение. Аналогично, если x и z имеют противоположные знаки, мы всегда можем удалить 5 и 12 и добавить 7 соответствующего знака. Это означает, что нам никогда не нужно рассматривать какое-либо решение, где z имеет тот же знак, что и x или y, потому что это означает, что должно быть лучшее решение.

Подумайте о том, что (1) и (2) сообщаем нам. (1) говорит, что знаки на х и у не могут быть одинаковыми, поскольку мы всегда можем добиться большего. (2) говорит, что если x и z имеют противоположные знаки или если y и z имеют противоположные знаки, мы всегда можем добиться большего успеха. В совокупности это означает, что

Лемма: по крайней мере один из x, y или z должен быть равен нулю в оптимальном решении.

Чтобы увидеть это, если все три отличны от нуля, если x и y имеют один и тот же знак, тогда мы можем четко сделать решение лучше, заменив их на 12s. В противном случае x и y имеют противоположные знаки. Таким образом, если x и z имеют разные знаки, то в силу (2) мы можем заменить их меньшим числом 7, в противном случае y и z имеют разные знаки, а по (2) мы можем заменить их меньшим числом 5.

Хорошо, это действительно здорово! Это означает, что нам просто нужно решить эти три целочисленных уравнения и найти, какая из них имеет наименьшую сумму коэффициентов:

• 5x + 7y = b - a
• 5x + 12z = b - a
• 7y + 12z = b - a

К счастью, идентификатор Bezout, поскольку gcd (5, 7) = gcd (5, 12) = gcd (7, 12) = 1, все эти системы уравнений имеют решение для любого значения b - a.

Теперь посмотрим, как решить каждое из этих уравнений. К счастью, мы можем использовать некоторые симпатичные трюки, чтобы значительно сократить наше пространство поиска. Например, для 5x + 7y = b - a значение x не может быть вне [-6, +6], так как если бы мы могли просто заменить семь из 5 на пять 7. Это означает, что мы можем решить вышеупомянутое уравнение, выполнив следующее:

Для x = -6 - +6, см., если 5x + 7y = b - a имеет целочисленное решение, вычислив (b - a) - 5x и увидев, если он делится на семь. Если это так, количество шагов, необходимых для решения проблемы, задается | x | + | ((b - a) - 5x)/7 |.

Мы можем использовать аналогичные трюки для решения последних двух уравнений - для второго уравнения х варьируется от -11 до +11, а для третьего у - от -11 до +11. Затем мы можем просто взять лучший ответ из всех трех уравнений, чтобы узнать, что такое ответ.

Здесь некоторый псевдокод для записи наименьшего количества шагов. Это можно легко изменить, чтобы вернуть то, что эти шаги, просто записав, какое из решений было использовано, а затем расширило его на полный путь:

Let best = infinity

# Solve 5x + 7y = b - a
for x = -6 to +6:
    if ((b - a) - 5 * x) mod 7 = 0:
        best = min(best, |x| + |((b - a) - 5 * x) / 7|)

# Solve 5x + 12y = b - a
for x = -11 to +11:
    if ((b - a) - 5 * x) mod 12 = 0:
        best = min(best, |x| + |((b - a) - 5 * x) / 12|)

# Solve 7x + 12y = b - a
for x = -11 to +11:
    if ((b - a) - 7 * x) mod 12 = 0:
        best = min(best, |x| + |((b - a) - 7 * x) / 12|)

return best;

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

Надеюсь, это поможет!

Ответ 2

Проблема эквивалентна получению числа a-b. Или abs(a-b), так как он симметричен вокруг нуля. Я думаю, что это можно сделать легко с принятием динамического программирования . Например, самый быстрый способ получить 23 - это самый быстрый способ получить 23+5,23-5,23+7,23-7,23+12 или 23-12 плюс одну операцию. Если вы примените это пару раз в исходном состоянии (стоимость + 5, -5,.. равна 1, другие - бесконечны), вы получите ответ в O(a-b).

Ответ 3

Вам нужно решить 5x + 7y + 12z = b-a. такой, что | x | + | y ​​| + | z | является минимальным. Возможно, есть простой математический путь. Возможно, это помогает: http://mathforum.org/library/drmath/view/66870.html

Ответ 4

Я думаю, вы могли бы взглянуть на "Задача подмножества сумм" для идей.

Ответ 5

Предварительно вычислить операции, необходимые для первого минимального диапазона, после этого просто добавьте кратные +12.

Ответ 6

Предварительно вычислите все свои комманды операций в хэш-карту, а затем просто просмотрите ответ.

Шаг предварительной калькуляции потребует времени, но после его выполнения вы найдете ответы в пределах предварительно рассчитанного диапазона, которые являются 1 операцией поиска.

Вот небольшая демонстрация JavaScript:

// maximum depth of combos to try
var MAX = 6;
// possible operations
var ops = ["+-5", "+5", "+-7", "+7", "+-12", "+12"];
// initial hash map of operations->value
var all = {"+5":5, "+-5":-5, "+7":7, "+-7":-7, "+12":12, "+-12":-12};
var allcnt = 6; // count combos *not needed*
// initial hash map of values->operations, plus "0" so we can avoid it
var unique = {"0": "0", "5":"+5", "-5":"+-5", "7":"+7", "-7":"+-7", "12":"+12", "-12":"+-12" };
var ready = false;
// get all useful combinations of ops
function precalc() {
  var items = [];
  for(var p in all) {
     items.push(p);
  }
  for(var p=0; p<items.length; p++) {
    for(var i=0; i<ops.length; i++) {
      var k = items[p] + ops[i];
      var v = eval(k);
      if(unique[v] == null) {
        unique[v] = k;
        all[k] = v;
        allcnt++;
      }
    }
  }
}
// find an answer within the pre-calc'd depth
function find(a, b) {
  if(ready === false) {
    for(var i=0; i<MAX; i++) precalc();
    ready = true;
  }
  return unique[""+Math.abs(a-b)];
}
// test
find(-5,19);