Синтаксис:

              g = gcd(m, n)
              [g, c, d] = gcd(m, n)

Описание:

Функция g = gcd(m, n) вычисляет наибольший общий делитель двух целых чисел m и n. Принято, что gcd(0, 0) = 0.

Функция [g, c, d] = gcd(m, n) кроме наибольшего общего делителя вычисляет два множителя c и d, таких, что выполняется соотношение g = = m*c + n*d.

Для массивов чисел эту функцию применять нельзя.

Алгоритм:

             if round(a) ~= a | round(b) ~= b
                error(‘Входные аргументы должны быть целыми числами.')
             end
             u = [1 0 abs(a)];
             v = [0 1 abs(b)];
             while v(3)
                 q = floor( u(3) / v(3) );
                 t = u - v*q;
                 u = v;
                 v = t;
             end
             c = u(1) * sign(a);
             d = u(2) * sign(b);
             g = u(3);

Пример:

             [g, c, d] = gcd(45, 36);
             [g c d] ans = 9     1    -1

Сопутствующие функции: ABS, FLOOR, ROUND, SIGN.

Наши баннеры