Использование стека для поиска наибольшего общего делителя

Question

Я пытаюсь реализовать алогорифм, чтобы найти наибольший общий делитель, используя стек: я не могу сформулировать правильный ответ на основе моей логики ниже. Пожалуйста помоги. Вот мой код:

def d8(a,b) 
if (a==b) 
    return a 
end 
s = Stack.new 
s.push(b) 
s.push(a) 

c1 = s.pop 
c2 = s.pop 

while c1!=c2 
    if s.count>0 
     c1 = s.pop 
     c2 = s.pop 
    end 

    if c1== c2 
     return c1 
    elsif c1>c2 
     c1 = c1-c2 
     s.push(c2) 
     s.push(c1) 
    else 
     c2 = c2 -c1 
     s.push(c2) 
     s.push(c1) 
    end 
end 
    return nil 
end 

Answer 1

GCD не может быть nil. У двух целых чисел всегда есть GCD. Таким образом, логика в функции уже неверна только потому, что при некотором условии она имеет return nil.

Глядя на это return nil состояние, это происходит, когда c1 == c2 (он выйдет из петли while). В то же время внутри цикла while вы возвращаете значение if c1 == c2. Эти два случая находятся в логическом противоречии. Другими словами, вы выходите из цикла while в состоянии c1 == c2 и считаете это условие недопустимым до того, как ваше условие if c1 == c2 может вызвать и обработать условие как действительное и вернуть правильный ответ.

Упрощая логика немного, вы получите:

def d8(a,b) 
    return a if a == b # Just a simpler way of doing a small if statement 

    s = Stack.new # "Stack" must be a gem, not std Ruby; "Array" will work here 
    s.push(b) 
    s.push(a) 

    #c1 = s.pop  # These two statements aren't really needed because of the first 
    #c2 = s.pop  # "if" condition in the while loop 

    while c1 != c2 
    if s.count > 0 
     c1 = s.pop 
     c2 = s.pop 
    end 

    # if c1 == c2 isn't needed because the `while` condition takes care of it 
    if c1 > c2 
     c1 = c1 - c2 
    else 
     c2 = c2 - c1 
    end 

    # These pushes are the same at the end of both if conditions, so they 
    # can be pulled out 
    s.push(c2) 
    s.push(c1) 
    end 

    return c1 # This return occurs when c1 == c2 
end 

Это будет работать, но это становится все более очевидным, что использование стека является излишним и не служит никакой цели вообще в алгоритме. s.count > 0 всегда будет true, и вы выпадаете переменные сразу после того, как вы их нажимаете (в основном, нет-op). Так что это эквивалентно:

def d8(a,b) 
    return a if a == b 

    c1 = a 
    c2 = b 

    while c1 != c2 
    if c1 > c2 
     c1 = c1 - c2 
    else 
     c2 = c2 - c1 
    end 
    end 

    return c1 
end