Exponenta Banner

gCD

Наибольший общий делитель

свернуть все на странице

Синтаксис

G = gcd(A,B)
[G,U,V] = gcd(A,B)

Описание

пример

G = gcd(A,B) возвращает наибольшие общие делители элементов A и B. Элементы в G являются всегда неотрицательными, и gcd(0,0) возвращает 0. Этот синтаксис поддерживает входные параметры любого числового типа.

пример

[G,U,V] = gcd(A,B) также возвращает коэффициенты Bézout, U и V, которые удовлетворяют: A.*U + B.*V = G. Коэффициенты Bézout полезны для решения диофантовых уравнений. Этот синтаксис поддерживает двойные, одни входные параметры, и целого числа со знаком.

Примеры

свернуть все

Скрипт Open Live Script
A = [-5 17; 10 0];
B = [-15 3; 100 0];
G = gcd(A,B)
G = 2×2

     5     1
    10     0

gcd возвращает положительные значения, даже когда входные параметры отрицательны.

Скрипт Open Live Script
A = uint16([255 511 15]);
B = uint16([15 127 1023]);
G = gcd(A,B)
G = 1x3 uint16 row vector

   15    1    3
Скрипт Open Live Script

Решите диофантовое уравнение, 30x+56y=8 для x и y.

Найдите наибольший общий делитель и пару коэффициентов Bézout для 30 и 56.

[g,u,v] = gcd(30,56)
g = 2

u = -13

v = 7

u и v удовлетворяют идентичность Безута, (30*u) + (56*v) = g.

Перепишите идентичность Безута так, чтобы она больше походила на исходное уравнение. Сделайте это путем умножения 4. Используйте ==, чтобы проверить, что обе стороны уравнения равны.

(30*u*4) + (56*v*4) == g*4
ans = logical
   1

Вычислите значения x и y это решает проблему. 

x = u*4
x = -52

y = v*4
y = 28

Входные параметры

свернуть все

Входные значения, заданные как скаляры, векторы или массивы действительных целочисленных значений. A и B могут быть любым числовым типом, и они могут иметь различные типы в рамках определенных ограничений:

  • Если A или B имеют тип single, то другой может иметь тип single или double.

  • Если A или B принадлежат целочисленному классу, то другой должен принадлежать тому же классу, или это должно быть скалярное значение double.

A и B должны быть одного размера, или нужно быть скаляром.

Пример: [20 -3 13],[10 6 7]

Пример: int16([100 -30 200]),int16([20 15 9])

Пример: int16([100 -30 200]),20

Типы данных: single | double | int8 | int16 | int32 | int64 | uint8 | uint16 | uint32 | uint64

Выходные аргументы

свернуть все

Наибольший общий делитель, возвращенный как массив действительных неотрицательных целочисленных значений. G одного размера как A и B, и значения в G являются всегда действительными и неотрицательными. G возвращен как тот же тип как A и B. Если A и B имеют различные типы, то G возвращен как недвойной тип.

Коэффициенты Bézout, возвращенные как массивы действительных целочисленных значений, которые удовлетворяют уравнению, A.*U + B.*V = G. Тип данных U и V является тем же типом как тот из A и B. Если A и B имеют различные типы, то U и V возвращены как недвойной тип.

Алгоритмы

g = gcd(A,B) вычисляется с помощью Алгоритма Евклида. [1]

[g,u,v] = gcd(A,B) вычисляется с помощью расширенного Алгоритма Евклида. [1]

Ссылки

[1] Knuth, D. “Алгоритмы A и X.” Искусство программирования, издания 2, разделяют 4.5.2. Чтение, MA: Аддисон-Уэсли, 1973.

Расширенные возможности

Генерация кода C/C++
Генерация кода C и C++ с помощью MATLAB® Coder™.

Смотрите также

Представлено до R2006a

Документация MATLAB
Поддержка