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。2 つの整数には常に GCD があります。したがって、関数のロジックは、ある条件下でreturn nil.

このreturn nil状態を見ると、いつc1 == c2（whileループを抜けるか）発生しています。同時に、whileループ内で value を返しますif c1 == c2。この 2 つのケースは論理的に矛盾しています。つまり、条件の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 ループに置き換え、再帰的な関数呼び出しで発生するように、2 番目の引数が 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 に答える