Как найти наибольший общий делитель

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

Автор: http://www.swissdelphicenter.ch

{
  The greatest common factor, or GCF, is the greatest factor
  that divides two numbers.
 }

uses
  math;

// Find the greatest common factor of two integers

function TForm1.GCF(A, B: Integer): Integer;
var
  Lfactor: Integer;
begin
  // Return -1 if either value is zero or negative
  if (A < 1) or (B < 1) then
  begin
    Result := -1;
    Exit;
  end;
  // if A = B then this is the GCF
  if A = B then
  begin
    Result := A;
    Exit;
  end;
  Result := 1;
  for Lfactor := trunc(max(A, B) / 2) downto 2 do
  begin
    if (frac(A / Lfactor) = 0) and (frac(B / Lfactor) = 0) then
    begin
      Result := Lfactor;
      Exit; // GCF has been found. No need to continue
    end;
  end;
end;

// Example:

procedure TForm1.Button1Click(Sender: TObject);
var
  Res: Integer;
begin
  Res := GCF(120, 30);
  ShowMessage(Inttostr(Res));
end;

{******************}

// Find the greatest common factor of an array of integers

function TForm1.GCFarray(A: array of Integer): Integer;
var
  Llength, Lindex, Lfactor: Integer;
begin
  Llength := Length(A);

  // Return -1 if any value is zero or negative
  for Lindex := 0 to Llength - 1 do
  begin
    if A[Lindex] < 1 then
    begin
      Result := -1;
      Exit;
    end;
  end;

  // if all elements are equal then this is the GCF
  Lindex := 1;
  while (Lindex < Llength) and (A[Lindex] = A[0]) do
    Inc(Lindex);
  if Lindex = Llength then
  begin
    Result := A[0];
    Exit;
  end;

  Result := 1;

  for Lfactor := trunc(ArrayMax(A) / 2) downto 2 do
  begin
    Lindex := 0;
    while (Lindex < Llength) and
      (frac(A[Lindex] / Lfactor) = 0) do
      Inc(Lindex);
    if Lindex = Llength then
    begin
      Result := Lfactor;
      Exit; // GCF has been found. No need to continue
    end;
  end;
end;

// find the maximum value in an array of integers

function TForm1.ArrayMax(Aarray: array of Integer): Integer;
var
  Lpos: Integer;
begin
  Result := 0;
  for Lpos := 0 to Length(Aarray) - 1 do
    if Aarray[Lpos] > Result then
      Result := Aarray[Lpos];
end;

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

Программа Delphi для расчета наибольшего общего делителя (НОД) двух целых чисел и массива целых чисел. НОД - это наибольший положительный целый, который делит оба числа без остатка.

Вот разбивка кода:

1. Функция GCF принимает два параметра-целых числа A и B, и возвращает их НОД.
2. Если любое из чисел A или B меньше 1, функция возвращает -1, указывая на недопустимый ввод.
3. Если A равно B, функция возвращает A как НОД.
4. Функция затем итерирует от max(A, B) / 2 до 2, проверяя, делится ли оба числа каждым целым числом в этом диапазоне. Когда она находит делимое, которое работает для обоих чисел, она возвращает это делимое как НОД.
5. Функция GCFarray принимает массив целых чисел в качестве входных данных и возвращает НОД всех элементов в массиве.
6. Если любое из чисел в массиве меньше 1, функция возвращает -1, указывая на недопустимый ввод.
7. Если все элементы равны, функция возвращает это общее значение как НОД.
8. Функция затем итерирует от ArrayMax(A) / 2 до 2, проверяя, делится ли каждый элемент массива каждым целым числом в этом диапазоне. Когда она находит делимое, которое работает для всех элементов, она возвращает это делимое как НОД.
9. Функция ArrayMax принимает массив целых чисел и возвращает максимальное значение в массиве.

В примере кода обработчик события клика кнопки вызывает функцию GCF с аргументами 120 и 30, отображая результат в сообщении. Результат - 60, который является НОД 120 и 30.

Некоторые предложения по улучшению:

• Вместо использования frac(A / Lfactor) = 0 для проверки делит ли число другое, вы можете использовать оператор модуля (A mod Lfactor = 0). Это более эффективно и легче для чтения.
• В функции GCFarray вы можете использовать переменную цикла вместо повторного чтения элементов массива в каждой итерации. Например, вы можете использовать Lindex := 1; while (Lindex < Llength) and (A[Lindex] = A[0]) do Inc(Lindex);.
• Вы можете добавить более комментариев для объяснения цели каждого функции и переменной.
• Рассмотрите добавление обработки ошибок для случаев, когда входной массив пуст или содержит нецелые значения.

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

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

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

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

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