Вычисление наибольшего общего делителя двух целых неотрицательных чисел

Delphi , Синтаксис , Математика

Автор: Fenik
WEB-сайт: http://delphibase.endimus.com

{ **** UBPFD *********** by delphibase.endimus.com ****
>> 
Зависимости: System
Автор:       Fenik, chook_nu@uraltc.ru, Новоуральск
Copyright:   Turbo Pascal / С.А. Немнюгин. - СПб: Издательство "Питер", 2000.
Дата:        27 октября 2002 г.
***************************************************** }

function GCD(const m, n: LongWord): LongWord;
{Вычисление наибольшего общего делителя
 двух неотрицательных целых чисел.
 Если какое-то из чисел = 0, то функция возвратит 0.
 Взято из учебника:
 Turbo Pascal / С.А. Немнюгин. - СПб: Издательство "Питер", 2000.}
var
  p, n1, m1: LongWord;
begin
  if (n = 0) or (m = 0) then
    Result := 0
  else
  begin
    if m < n then
    begin
      n1 := m;
      m1 := n;
    end
    else
    begin
      n1 := n;
      m1 := m;
    end;
    while n1 > 0 do
    begin
      p := m1 mod n1;
      m1 := n1;
      n1 := p;
    end;
    Result := m1;
  end;
end;

Пример использования:

p := GCD(54, 36); {p := 18}

Вот перевод текста на русский язык:

Это реализация алгоритма Евклида в Delphi для поиска наибольшего общего делителя (НОД) двух неотрицательных целых чисел. Вот разбивка кода:

Подпись функции

function GCD(const m, n: LongWord): LongWord;

Функция GCD принимает два параметра типа LongWord, m и n, которые являются неотрицательными целыми числами, для которых мы хотим найти НОД.

Имплементация Если ни m, ни n не равно 0, функция возвращает 0 немедленно, поскольку НОД числа с 0 undefined.

if (n = 0) or (m = 0) then
  Result := 0

Если ни m, ни n не равно 0, функция продолжает обменять их, если необходимо, чтобы m было больше или равно n.

if m < n then
begin
  n1 := m;
  m1 := n;
end
else
begin
  n1 := n;
  m1 := m;
end;

Затем функция вступает в цикл, который продолжается до тех пор, пока n1 не равно 0. В каждом итерации она выполняет следующие шаги: 1. Вычисляет остаток от деления m1 на n1 с помощью оператора модуля (p := m1 mod n1;). 2. Обновляет m1 до равенства n1, а n1 до предыдущего значения p.

while n1 > 0 do
begin
  p := m1 mod n1;
  m1 := n1;
  n1 := p;
end;

Наконец, функция возвращает НОД, который хранится в m1 на этом этапе.

Result := m1;

Пример использования

p := GCD(54, 36); {p := 18}

Это код для расчета НОД чисел 54 и 36, который действительно равен 18.

В целом, эта реализация - это прямой и эффективный способ вычисления НОД двух неотрицательных целых чисел с помощью алгоритма Евклида.

Вычисление наибольшего общего делителя двух целых неотрицательных чисел с помощью алгоритма Евклида, представленного в виде функции на языке Delphi.

Комментарии и вопросы

Получайте свежие новости и обновления по Object Pascal, Delphi и Lazarus прямо в свой смартфон. Подпишитесь на наш Telegram-канал delphi_kansoftware и будьте в курсе последних тенденций в разработке под Linux, Windows, Android и iOS

:: Главная :: Математика ::