Минимальные ходы, чтобы достичь к

Question

Учитывая два числа m и n, за один ход вы можете получить две новые пары:

• m+n, n
• m, n+m

Давайте изначально установим m = n = 1 находим минимальное количество ходов, чтобы хотя бы одно из чисел равнялось k

, гарантированно, что есть решение (то есть существует последовательность ходов, которая приводит к k)

Например: дано k = 5 минимальное количество ходов, так что m или n равно k равно 3

1, 1
1, 2
3, 2
3, 5

Всего 3 хода.

Я нашел решение, использующее рекурсию в python, но, похоже, оно не работает с большим числом (т. Е. 10 ^ 6)

def calc(m, n, k):
    if n > k or m > k:
        return 10**6
    elif n == k or m == k:
        return 0
    else:
        return min(1+calc(m+n, n, k), 1+calc(m, m+n, k))

k = int(input())
print(calc(1, 1, k))

Как я могу улучшить производительность, так что она работает для больших чисел?

Answer 1

Мы можем сделать намного лучше, чем в очереди, даже используя грубую силу, пробуя каждое возможное n при установке m на k. Вот код JavaScript, очень близкий к синтаксису Python:

function g(m, n, memo){
  const key = m + ',' + n;
  
  if (memo[key])
    return memo[key];
  
  if (m == 1 || n == 1)
    return Math.max(m, n) - 1;
    
  if (m == 0 || n == 0)
    return Infinity;
  
  let answer;
  
  if (m > n)
    answer = Math.floor(m / n) + g(m % n, n, memo);
  else
    answer = Math.floor(n / m) + g(m, n % m, memo);
    
  memo[key] = answer;
  return answer;
}

function f(k, memo={}){
  if (k == 1)
    return 0;
  let best = Infinity;
  for (let n=1; n<=Math.floor(k/2); n++)
    best = Math.min(best, g(k, n, memo));
  return best;
}

var memo = {};
var ks = [1, 2, 5, 6, 10, 100, 1000, 100000];
  
for (let k of ks)
  console.log(`${ k }: ${ f(k, memo) }`);

Answer 2

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

Переформулируйте задачу: вы начинаете с двух чисел, характеризуемых как 1 * m + 0 * n, 0 * m + 1 * п. Используйте сокращение (1, 0) и (0, 1). Вы ищете кратчайший путь к любому решению линейного диофантова уравнения

a*m + b*n = k

, где (a, b) достигается из начальных значений (1, 1) aka ((1 , 0), (0, 1)).

Итак ... начиная с (1, 1), как вы можете охарактеризовать пути, которые вы достигаете из различных перестановок двоичного расширения. На каждом шаге у вас есть два варианта: a + = b или b + = a. Ваш существующий алгоритм уже распознает это двоичное дерево поиска.

Эти графовые переходы - ребра вдоль решетки - можно охарактеризовать, с помощью которых (a, b) пары вы можете достичь на данном шаге. Достаточно ли намёка, чтобы вас продвигать? Эта характеристика является ключом к преобразованию этой проблемы в нечто, близкое к прямым вычислениям.

Answer 3

нерекурсивный алгоритм на основе очереди приоритетов (с использованием кучи)

State: (sum_, m, n, path)
    sum_ is current sum (i.e. m + n)
    m and n are the first and second numbers
    path is the sequence of (m, n) pairs to get to the current sum

В каждом шаге есть два возможных хода

1. Замените первое число на сумму
2. Замените второе число на сумму

Таким образом, каждое состояние генерирует два новых состояния. Приоритеты для штатов:

1. ходы: штаты с меньшим числом имеют более высокий приоритет
2. сумма: штаты с более высокими суммами имеют более высокий приоритет

Мы используем приоритетную очередь (в данном случае кучу) для обработки состояний по приоритету.

Код

def calc1(k):
  if k < 1:
    return None, None  # No solution

  m, n, moves = 1, 1, 0
  if m == k or n == k:
    return moves, [(m, n)]

  h = []  # Priority queue (heap)

  path = [(m, n)]
  sum_ = m + n
  # Python's heapq acts as a min queue.
  # We can order thing by max by using -value rather than value
  # Thus Tuple (moves+1, -sum_, ...) prioritizes by 1) min moves, and 2) max sum
  heappush(h, (moves+1, -sum_, sum_, n, path))
  heappush(h, (moves+1, -sum_, m, sum_, path))

  while h:
    # Get state with lowest sum
    moves, sum_, m, n, path = heappop(h)

    sum_ = - sum_

    if sum_ == k:
      return moves, path  # Found solution

    if sum_ < k:
      sum_ = m + n  # new sum
      # Replace first number with sum
      heappush(h, (moves+1, -sum_, sum_, n, path + [(sum_, n)]))
      # Replace second number with sum
      heappush(h, (moves+1, -sum_, m, sum_, path + [(m, sum_)]))

    # else:
    #  so just continues since sum_ > k

  # Exhausted all options, so no solution
  return None, None

Тест

Тестовый код

for k in [5, 100, 1000]:
  moves, path = calc1(k)
  print(f'k: {k}, Moves: {moves}, Path: {path}')

Выход

k: 5, Moves: 3, Path: [(1, 1), (2, 3), (2, 5)]
k: 100, Moves: 10, Path: [(1, 1), (2, 3), (5, 3), (8, 3), (8, 11),
                         (8, 19), (27, 19), (27, 46), (27, 73), (27, 100)]
k: 1000, Moves: 15, Path: [(1, 1), (2, 3), (5, 3), (8, 3), (8, 11),
                          (19, 11), (19, 30), (49, 30), (79, 30), (79, 109), 
                          (188, 109), (297, 109), (297, 406), (297, 703), (297, 1000)]

Улучшение производительности

Выполнение двух настроек для повышения производительности

1. Не включая путь, просто количество шагов (обеспечивает 3-кратное ускорение для k = 10000
2. Не используется симметрия c (предоставляется 2x дополнительно с k = 10 000

Симметрично c парами, означают пары m, n, которые одинаковы вперед и назад, такие как (1, 2) и (2, 1) .
Нам не нужно переходить на оба эти параметра, поскольку они будут предоставлять одинаковое количество шагов решения.

Улучшенный код

def calc(k):
  if k < 1:
    return None, None

  m, n, moves = 1, 1, 0
  if m == k or n == k:
    return moves

  h = []    # Priority queue (heap)

  sum_ = m + n
  heappush(h, (moves+1, -sum_, sum_, n))

  while h:
    moves, sum_, m, n = heappop(h)
    sum_ = - sum_

    if sum_ == k:
      return moves

    if sum_ < k:
      sum_ = m + n
      steps = [(sum_, n), (m, sum_)]
      heappush(h, (moves+1, -sum_, *steps[0]))
      if steps[0] != steps[-1]: # not same tuple in reverse (i.e. not symmetric)
        heappush(h, (moves+1, -sum_, *steps[1]))

* 10 67 * Производительность

Tested up to k = 100, 000 which took ~2 minutes.

Обновление

Преобразование решения с помощью @ גלעדברקן с JavaScript на Python для проверки

def g(m, n, memo):
  key = (m, n)

  if key in memo:
    return memo[key]

  if m == 1 or n == 1:
    memo[key] = max(m, n) - 1

  elif m == 0 or n == 0:
    memo[key] = float("inf")

  elif m > n:
    memo[key]  = (m // n) + g(m % n, n, memo)

  else:
    memo[key]  = (n // m) + g(m, n % m, memo)

  return memo[key] 

def f(k, memo={}):
  if k == 1:
    return 0

  return min(g(k, n, memo) for n in range((k // 2) + 1))

Производительность @ גלעדברקן Код

Completed 100K in ~1 second 

This is 120X faster than my above heap based solution.

Answer 4

По умолчанию в Python для рекурсивной функции предел рекурсии установлен на 10 ^ 4. Вы можете изменить его, используя sys модуль:

import sys 
sys.setrecursionlimit(10**6)