c++ - 算法的正确性和逻辑 : minimum steps to one

Question

问题陈述:

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

1. 从中减去 1。 ( n = n - 1 )

2. 如果它能被 2 整除，则除以 2。(如果 n % 2 == 0 ，则 n = n/2 )

3. 如果它能被 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

“通用解决方案”不正确。有时最好先除以 2 再减去 1，但通用解决方案代码不允许这样做。

“通用解决方案”为 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