时间戳

首页 > 解决方案 > 达到 k 的最小步数

python - 达到 k 的最小步数

问题描述

给定两个数字m和n，一步可以得到两个新对：

让我们最初设置m = n = 1找到最小的移动次数，以便至少有一个数字等于k

保证有一个解决方案（即存在一系列导致 k 的移动）

例如：给定k = 5 最小移动次数，使得mor n 等于k3

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))

如何提高性能以使其适用于大数字？

标签： pythonalgorithm

解决方案

基于优先队列的非递归算法（使用堆）

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. sum：总和较高的国家优先级较高

我们使用优先级队列（在本例中为堆）按优先级处理状态。

代码

from heapq import heappush, heappop

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. 不包括路径，仅包括步数（为 k = 10,000 提供 3 倍加速
  2. 不使用对称对（在 k = 10, 000 时额外提供 2x

对称对是指 m, n 的前向和后向相同的对，例如 (1, 2) 和 (2, 1)。
我们不需要在这两个上进行分支，因为它们将提供相同的解决方案步数。

改进的代码

from heapq import heappush, heappop

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]))

表现

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.

推荐阅读