c - 我需要一个关于这个方程的解释

Question

 while(v!=0)
{
        temp=u%v;
        u=v;
        v=temp;
}

我无法理解这个等式。为什么有 u=v 和 v=temp。这个方程如何找到最大公约数。温度是什么意思？

标签： c

Answer 1

该算法被称为“欧几里得算法”（参见维基百科）。

让成为和的x最大公约数 (gcd) 。uvu > v

然后x也是 gcdv和u-v。

在算法中，您不断从较大的数字中减去较小的数字，直到其中一个成为 gcd x。

取模的temp = u % v平均值（尽可能多地减去）uvvu

所以在这一步之后，你的数字比你开始的要小temp，v它们有相同的 gcd。较小的值现在在temp, 所以temp < v，否则你可以继续减去。

为了能够重用代码，您必须确保较大的值在 inu而较小的值在 in v，sov变成你的 newu和temp变成你的 new v。

要打破循环v( temp) 必须成为0. 要达到0，u必须是v模运算前的倍数。数字及其倍数的 gcd 是数字本身，因此在这种情况下v存储到。u

由于一直以来数字的 gcdx没有改变，我们终于有了u == x.

此方案temp通常用于交换两个值。

    temp=a;
    a=b;
    b=temp;