给定整数N和一组操作，以最少的步数将N减小为1 [英] Given an integer N and a set of operations, reduce N to 1 in the least amount of steps

问题描述

对于给定的整数N，我们可以使用以下运算：

On a given integer N we can use the following operations:

1. 如果N可以除以3：除以3。 / li>
   
2. 如果N可以除以2：除以2。


3. 减去1。

如何找到以最少的步骤达到1的策略？

How can I find a strategy to reach 1 in the least number of steps?

推荐答案

如mbeckish所述，您可以将其视为BFS遍历，与自下而上的DP方法相比，它在时间和空间上的复杂性要好得多。您还可以在遍历中应用种类的分支定界（B& B）启发式，以便在我们之前已经看到过标记值的节点上修剪树的分支。与实际的B& B启发式方法不同，这不会削减最佳解决方案，因为它不包含关于最佳解决方案可能在哪里的任何有根据的猜测。我将给出一个直观的示例，并将算法减少到0以更好地说明。

As mbeckish mentioned you can treat this as a BFS traversal, which has significantly better time and space complexity than a bottom up DP approach. You can also apply a branch and bound (B&B) heuristic of sorts in the traversal such that you prune the branches of the tree at nodes that we've already seen the labeled value before. Unlike an actual B&B heuristic, this will not prune off the optimal solution since it does not involve any educated guesses of where the optimal solution might be. I'll give a visual example and have the algorithm reduce down to 0 to better illustrate.

这是一整套将10减少到0的运算树：

Here is a full tree of operations reducing 10 to 0:

   --------10---------
   5         -----9----
---4---     -3-      ------8------  
2    -3-    1 2    --4--         7        
1    1 2    0 1    2  -3-   -----6------   
0    0 1      0    1  1 2   2   -3-    5   
       0           0  0 1   1   1 2  --4-- 
                        0   0   0 1  2  -3-
                                  0  1  1 2
                                     0  0 1
                                          0 

由于我们正在执行BFS，因此实际上我们会像下面那样停在第一个零，而不是构建树的更深部分：

Since we're doing BFS, we'll actually stop at the first zero like follows and not build the deeper parts of the tree:

   --------10------
   5         -----9--------
---4---     -3-     ------8------  
2    -3-    1 2     4           7        
1    1 2    0 

但是，通过B& B启发式方法，我们可以进一步减少分支数量这（这在大量数字上有很大的不同）：

However we can reduce the number of branches further by the B&B heuristic to look like this (and this makes a huge difference on massive numbers):

   --------10------
   5         -----9--------
   4         3            8
   2         1            7
             0 

时间复杂度： O（log n） 空间复杂度： O（log n） ^{（我认为）}

下面是输入1 googol（10 ^ 100）的python 3代码，在我的计算机上运行大约需要8秒钟，大约需要350 MB的RAM。您也可以在 https://repl.it/B3Oq/76

Below is python 3 code with input of 1 googol (10^100) which takes about 8 seconds to run on my computer and around ~350 MB of RAM. You can also run it online at https://repl.it/B3Oq/76

from collections import deque

def number_of_steps(i):
    Q = deque()
    seen_before = set()
    steps = 0
    Q.append((i, steps))
    while True:
        j, steps = Q.popleft()
        if j == 1:
            return steps
        if j % 3 == 0:
            branch(Q, seen_before, steps, j // 3)
        if j % 2 == 0:
            branch(Q, seen_before, steps, j // 2)
        branch(Q, seen_before, steps,  j - 1)

def branch(Q, seen_before, steps, k):
    if k not in seen_before:
        seen_before.add(k)
        Q.append((k, steps + 1))

import time
n = 10**100
print('input:', n)
start = time.time()
steps = number_of_steps(n)
end = time.time()
print('runtime (seconds):', end - start)
print('number of steps:', steps)

这篇关于给定整数N和一组操作，以最少的步数将N减小为1的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！