Как найти НОД для массива чисел на Паскале: исправление ошибки в логике

Delphi , Синтаксис , Массивы

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

В представленном примере кода из контекста есть несколько ошибок, которые необходимо исправить для корректной работы функции нахождения НОД:

program GreatestCommonDivisor;
type mas = array[1..100] of integer;
var n : integer;
M : mas;
Rf : text;
procedure Skaityti;
var i : integer;
Df : text;
begin
Assign(Df,'duom1.txt');
Reset(Df);
Readln(Df,n);
for i := 1 to n do
  Read(Df,M[i]);
Close(Df);
end;
function GCD(M : array of integer): integer;
var i, min, m : integer;
begin
  Result := M[1];
  for m := 1 to High(M) do
    if Result > M[m] then
      Result := M[m];
  var temp := Result;
  while true do
  begin
    var flag := true;
    for m := 1 to High(M) do
      if M[m] mod temp <> 0 then
      begin
        flag := false;
        break;
      end;
    if flag then
      Exit;
    temp := temp - 1;
  end;
  GCD := temp;
end;
begin
  Skaityti;
  Assign(Rf,'rez.txt');
  for i := 1 to n do
    Writeln(Rf, GCD(M), ' ', M[i] div GCD(M));
  Close(Rf);
end.

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

Вот исправленная версия функции GCD с использованием алгоритма Евклида:

function GCD(arr: array of integer): integer;
var i, temp, first, second: integer;
begin
  first := arr[Low(arr)];
  second := arr[High(arr)];
  while second <> 0 do
  begin
    temp := second;
    second := first mod second;
    first := temp;
  end;
  GCD := first;
end;

Для работы с массивом чисел, эту функцию нужно обернуть в цикл, который будет последовательно применять её ко всем парам чисел в массиве:

function ArrayGCD(const Arr: TArray<Integer>): Integer;
var i, j, temp: Integer;
begin
  if Length(Arr) < 2 then
    Exit(Arr[0]);
  Result := GCD(Arr[1], Arr[2]);
  for i := 3 to Length(Arr) do
    Result := GCD(Result, Arr[i]);
end;

Теперь, чтобы использовать функцию ArrayGCD, достаточно передать ей массив чисел:

var numbers: TArray<Integer>;
numbers := [10, 20, 5, 14, 16];
Writeln('Главный общий делитель: ', ArrayGCD(numbers));

Таким образом, исправив логику нахождения НОД, мы сможем корректно решать задачу нахождения наибольшего общего делителя для массива чисел, написанного на языке Pascal.

Создано по материалам из источника по ссылке.

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

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

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

:: Главная :: Массивы ::