算法的正确性和逻辑：最少一步

Question

问题陈述：

对于正整数，您可以执行以下 3 个步骤中的任何一个。

从中减去 1。 ( n = n - 1 )
如果它能被 2 整除，则除以 2。（如果 n % 2 == 0，则 n = n / 2）
如果它能被 3 整除，则除以 3。（如果 n % 3 == 0，则 n = n / 3）

给定一个正整数 n，你的任务是找到使 n 等于 1 的最小步数。

我的递归解法（C++）比较了 N 能被 3 整除的所有 3 种情况，而一般的解法只比较了 2，但仍然给出了正确的解法。

int min_steps(int N){ 
        if(N==1) return 0;    
        else{
                if(N%3==0){
                       if(N%2==0) 
                          return (1+min(min_steps(N/3),min_steps(N/2),min_steps(N-1)));
                       else
                          return(1+min(min_steps(N/3),min_steps(N-1)));
                }
                else if(N%2==0){
                        return(1+min(min_steps(N/2),min_steps(N-1)));
                }
                else
                        return(1+min_steps(N-1));
        }
}

但一般的解决办法是，

int min_steps(int N){ 
        if(N==1) return 0;    
        else{
                if(N%3==0){
                        return(1+min(min_steps(N/3),min_steps(N-1)));
                }
                else if(N%2==0){
                        return(1+min(min_steps(N/2),min_steps(N-1)));
                }
                else
                        return(1+min_steps(N-1));
        }
}

我的问题是，为什么我们不比较所有 3 种情况，但仍然得出正确的解决方案。我无法遵循通用解决方案的算法。任何让我理解的帮助将不胜感激。

Answer 1

如果n能被3整除和能被2整除，那么除以[=11也没关系=]，然后在下一步中按 2，或者先按 2，然后在下一步中按 3。

示例：18 = 3*3*2

a) 18/3 = 6、6/3 = 2、2/2 = 1 或

b) 18/2 = 9、9/2 = #!?#、9/3 = 3、3/3 = 1 或...

Answer 2

"general solution" 不正确。有时除以 2 再减 1 是最优的，而通用解决方案代码不允许这样做。

"general solution" 为 642 生成了不正确的结果。

642 -> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 2 -> 1

但是，这是最优的，比短了一个：

642 -> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1

可以看到一般解是从除以3开始，最优解是从除以2然后减去1...这正是被删除的情况。

虽然它与您的问题没有直接关系，但这是我用来查找反例的代码（尽管自从我编写它后已经整理得很好）。它使用您提供的两种算法，但会记住它们以实现指数级速度增长。它还使用了从 min_steps 返回两个结果的技巧：不仅是最短路径的长度，还有该路径的第一步。这使得在不编写太多额外代码的情况下重建路径非常方便。

def memoize(f):
    """Simple memoization decorator"""
    def mf(n, div2, cache={}):
        if (n, div2) not in cache:
            cache[n, div2] = f(n, div2)
        return cache[(n, div2)]
    return mf

@memoize
def min_steps(n, div2):
    """Returns the number of steps and the next number in the solution.

    If div2 is false, the function doesn't consider solutions
    which involve dividing n by 2 if n is divisible by 3.
    """
    if n == 1:
        return 0, None
    best = min_steps(n - 1, div2)[0] + 1, n-1
    if n % 3 == 0:
        best = min(best, (min_steps(n // 3, div2)[0] + 1, n//3))
    if n % 2 == 0 and (div2 or n%3):
        best = min(best, (min_steps(n // 2, div2)[0] + 1, n//2))
    return best

def path(n, div2):
    """Generates an optimal path starting from n.

    The argument div2 has the same meaning as in min_steps.
    """
    while n:
        yield n
        _, n = min_steps(n, div2)

# Search for values of n for which the two methods of finding
# an optimal path give different results.
for i in xrange(1, 1000):
    ms1, _ = min_steps(i, True)
    ms2, _ = min_steps(i, False)
    if ms1 != ms2:
        print i, ms1, ms2
        print ' -> '.join(map(str, path(i, True)))
        print ' -> '.join(map(str, path(i, False)))

这是输出，包括运行次：

$ time python minsteps.py 
642 10 11
642 -> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1
642 -> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 2 -> 1
643 11 12
643 -> 642 -> 321 -> 320 -> 160 -> 80 -> 40 -> 20 -> 10 -> 9 -> 3 -> 1
643 -> 642 -> 214 -> 107 -> 106 -> 53 -> 52 -> 26 -> 13 -> 12 -> 4 -> 2 -> 1

real    0m0.009s
user    0m0.009s
sys 0m0.000s

算法的正确性和逻辑：最少一步

Correctness and Logic of algorithm: minimum steps to one

c++

algorithm

logic

correctness