Chính xác và logic của thuật toán: các bước tối thiểu cho một

Question

Báo cáo vấn đề:

Trên số nguyên dương, bạn có thể thực hiện bất kỳ một trong 3 bước sau đây.

1. Subtract 1 từ nó. (N = n - 1)

2. Nếu chia nó cho 2, chia cho 2. (nếu n% 2 == 0 thì n = n/2)

3. Nếu chia hết cho mình bằng 3, chia bởi 3. (nếu n% 3 == 0 thì n = n/3)

cho một số nguyên dương n và bạn nhiệm vụ là tìm số tối thiểu là bước mà mất n để một.

Giải pháp đệ quy của tôi (bằng C++) so sánh tất cả 3 trường hợp khi N chia hết cho 3, trong khi giải pháp chung chỉ so sánh 2, nhưng vẫn đưa ra giải pháp đúng.

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

Nhưng giải pháp chung là,

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

Câu hỏi của tôi là, làm thế nào chúng ta không so sánh tất cả 3 trường hợp, nhưng vẫn lấy được tại các giải pháp đúng. Tôi không thể làm theo thuật toán của giải pháp chung. Bất kỳ sự giúp đỡ nào cho tôi hiểu sẽ được đánh giá rất cao.

Answer 1

Các "giải pháp chung" là không chính xác. Đôi khi nó là tối ưu để chia cho 2 và sau đó trừ đi 1, và mã giải pháp chung không cho phép điều đó.

Các "giải pháp chung" tạo ra kết quả không chính xác cho 642.

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

Tuy nhiên, điều này là tối ưu, là một trong ngắn:

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

Bạn có thể xem giải pháp chung bắt đầu bằng cách chia cho 3 và giải pháp tối ưu bắt đầu bằng cách chia cho 2 và sau đó trừ đi 1 ... chính xác là trường hợp đã bị xóa.

Mặc dù nó không liên quan trực tiếp đến câu hỏi của bạn, đây là mã tôi đã sử dụng để tìm ví dụ phản đối (mặc dù đã được dọn dẹp rất nhiều kể từ khi tôi viết nó). Nó sử dụng hai thuật toán bạn đã cung cấp, nhưng ghi nhớ chúng để tăng tốc độ theo cấp số mũ.Nó cũng sử dụng một thủ thuật trả về hai kết quả từ min_steps: không chỉ chiều dài của đường đi ngắn nhất, mà còn là bước đầu tiên trong đường dẫn đó. Điều này làm cho nó cực kỳ thuận tiện để tái tạo lại đường dẫn mà không cần viết nhiều mã bổ sung.

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

Dưới đây là đầu ra, bao gồm chạy lần:

$ 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 

Answer 2

Nếu n là chia hết cho 3và chia 2, sau đó nó không quan trọng nếu bạn chia 3 đầu tiên và sau đó bởi 2 trong bước tiếp theo, hoặc bằng cách 2 đầu tiên và sau đó bởi 3 trong bước tiếp theo.

Ví dụ: 18 = 3*3*2

a) 18/3 = 6, 6/3 = 2, 2/2 = 1, hoặc

b) 18/2 = 9, 9/2 = #!?#, 9/3 = 3, 3/3 = 1, hoặc ...