Bézout 的恒等式，找到满足 ax+by = gcd(a,b) 的整数 x 和 y

Question

以下代码中的 gcd 函数在 Steven Skiena 的编程挑战一书中给出，作为查找整数 x 和 y 的一种方法，使得 ax+by = gcd(a,b)。例如，假设 a = 34398 和 b = 2132（其 gcd = 26），下面代码要执行的算法应该 return 34398 × 15 + 2132 × −242 = 26。找到 x 的算法并且 y 基于基本情况 y = 1 和 x = 0，因为 a * 1+0*0 = gcd(a,0) 并且根据欧几里得算法 gcd(34398, 2132) 简化为 gcd(gcd(34398, 2132 ),0) 或 gcd(26,0)。可以逆向应用欧几里德算法得到34398×15+2132×−242=26.

#include <stdio.h>
#include <math.h>

int main() { 
    gcd(34398, 2132, 0, 1);

    /* Find the gcd(p,q) and x,y such that p*x + q*y = gcd(p,q) */
    long gcd(long p, long q, long *x, long *y)
    {
        long x1,y1; /* previous coefficients */
        long g; /* value of gcd(p, q) */

        if (q > p) return(gcd(q, p, y, x));

        if (q == 0) {
            *x = 1;
            *y = 0;
            return(p);
        }

        g = gcd(q, p % q, &x1, &y1);
        *x = y1;
        *y = (x1 - floor(p / q) * y1);
        return(g);
    }

    return 0;
}

你如何测试这段代码？所需的输入似乎是 p、q 和基本情况 x 和 y 值，但是当我运行下面的程序使用代码行 gcd(34398, 2132, 0, 1);有一条运行时间错误消息指出 'conflicting types for gcd'。

Answer 1

声明long gcd(long p, long q, long *x, long *y)说gcd的最后两个参数是指针。所以你必须将指针传递给现有的 long;您不能传递 0 和 1.

等值

为此，在 main 中定义两个 long 对象，也可能称为 x 和 y，例如 long x = 0, y = 1;。然后将指向这些对象的指针传递给 gcd，就像 gcd(34398, 2132, &x, &y);.

此外，您必须在使用前声明 gcd。

在 main 中定义 gcd 是对 C 标准的扩展。该扩展在嵌套函数需要来自其包含函数的特定上下文的情况下很有用。这里不需要，所以函数应该按普通方式定义。将 gcd 的整个定义从 main 内部移动到 main.

之前

没有理由在floor(p / q)中使用floor，因为p和q是整数类型，会进行整数除法。 floor 不会有小数部分要删除。如果 double 类型的精度低于 long 类型，它实际上会使结果出错。所以只需使用 p/q.

也没有理由在此代码中使用递归。在这种情况下，这是浪费而且不具有教学意义。（参考 the book Programming Challenges，作者说“Euclid 的算法是递归的……”然而，我有一个 2003 年 Euclid 的 Elements 的英文翻译，大约公元前 300 年。看看 Euclid 的 GCD 算法在第七册命题 1 和 2 中，我会说它是迭代的，而不是递归的。以现代人的眼光来看，它以其繁琐的方式描述了重复做事，而不是重新应用整个算法 de novo.)

Bézout 的恒等式，找到满足 ax+by = gcd(a,b) 的整数 x 和 y

Bézout's identity, finding integers x and y such that ax+by = gcd(a,b)

c

number-theory