算法的正确性和逻辑性:最少步长为一 [英] Correctness and Logic of algorithm: minimum steps to one

问题描述

问题陈述:

对于正整数，您可以执行以下3个步骤之一.

On a positive integer, you can perform any one of the following 3 steps.

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

1. Subtract 1 from it. ( n = n - 1 )

如果将其除以2，再除以2.(如果n％2 == 0，则n = n/2)

If its divisible by 2, divide by 2. ( if n % 2 == 0 , then n = n / 2 )

如果将其除以3，则除以3.(如果n％3 == 0，则n = n/3)

If its divisible by 3, divide by 3. ( if n % 3 == 0 , then n = n / 3 )

给出一个正整数n，您的任务是找到将n减为1的最小步数.

Given a positive integer n and you task is find the minimum number of steps that takes n to one .

当N被3整除时，我的递归解决方案(在C ++中)比较了所有3种情况，而常规解决方案仅比较了2种，但仍给出了正确的解决方案.

My Recursive Solution (in C++) compares all the 3 cases when N is divisible by 3, while the general solution compares only 2, but still gives the correct solution.

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

但是一般的解决方法是，

But the general solution is,

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种情况，但仍然得出正确的解决方案.我无法遵循通用解决方案的算法.让我理解的任何帮助将不胜感激.

My question is, how come we don't compare all the 3 cases but still derive at the correct solution. I cannot follow the general solution's algorithm. Any help for letting me understand would be appreciated hugely.

推荐答案

一般解决方案"不正确.有时最好将其除以2再减去1，而一般的解决方案代码则不允许这样做.

The "general solution" is incorrect. Sometime's it's optimal to divide by 2 and then subtract 1, and the general solution code doesn't allow for that.

一般解决方案"对于642产生不正确的结果.

The "general solution" produces incorrect results for 642.

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

但是，这是最佳选择，它要短一些:

However, this is optimal, being one shorter:

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

您可以看到一般的解决方案是先除以3，最佳解决方案是先除以2再减去1 ...，这正是删除的情况.

You can see the general solution starts by dividing by 3, and the optimal solution starts by dividing by 2 and then subtracting 1... which is exactly the case that's been removed.

虽然它与您的问题没有直接关系，但是这是我用来查找反例的代码(尽管自从我编写它以来，它进行了大量的整理).它使用您提供的两种算法，但会记住它们，以实现指数级的速度增加.它还使用了从min_steps返回两个结果的技巧:不仅是最短路径的长度，而且是该路径的第一步.这使得在无需编写过多代码的情况下重构路径非常方便.

While it's not directly relevant to your question, here's the code I used to find the counter-example (albeit greatly tidied up since I wrote it). It uses the two algorithms you gave, but memoizes them for an exponential speed increase. It also uses a trick of returning two results from min_steps: not only the length of the shortest path, but also the first step in that path. This makes it extremely convenient to reconstruct the path without writing much extra code.

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

以下是输出，包括运行时:

Here's the output, including run-times:

$ 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

这篇关于算法的正确性和逻辑性:最少步长为一的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！