0

我正在尝试实现一个算法来使用堆栈找到最大公约数：我无法根据下面的逻辑制定正确的答案。请帮忙。这是我的代码：

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
4

2 回答 2

3

GCD 不能nil。两个整数总是有一个 GCD。所以函数中的逻辑已经不正确，因为在某些情况下它有一个return nil.

查看这种return nil情况，它正在发生时c1 == c2（它将退出while循环）。同时，在while循环内部，您返回一个 value 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，并且您在推送变量后立即弹出变量（基本上是无操作）。所以这相当于：

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
于 2013-10-04T11:22:17.893 回答
0

它的Java代码将是

public static int gcd (int p, int q) {
        StackGeneric<Integer> stack = new StackGeneric<Integer>();
        int temp;

        stack.push(p);
        stack.push(q);

        while (true) {
            q = stack.pop();
            p = stack.pop();
            if (q == 0) {
                break;
            }
            temp = q;
            q = p % q;
            p = temp;
            stack.push(p);
            stack.push(q);
        }
        return p;
    }

用while循环替换递归解决方案中的函数调用并迭代它直到第二个参数变为0，就像递归函数调用一样

    public static int gcd (int p, int q) {
        if (q == 0) {
            return p;
        }
        return gcd(q, p % q);
    }
于 2019-08-29T11:40:20.480 回答