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

      Комментарии к записи Наибольший общий делитель на Prolog отключены

В этой теме 1 ответ, 2 участника, последнее обновление  Васильев Владимир Сергеевич 2 года/лет, 2 мес. назад.

  • Автор
    Сообщения
  • #2053

    questioner
    Участник

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

    Желательно решить без использования списков.

  • #2059

    Самый простой алгоритм вычисления наибольшего общего делителя двух чисел заключается в последовательном переборе всех возможных делителей в порядке убывания и их проверке. Первое число, оказавшееся делителем возвращается в качестве результата. Нижней границей перебора в любом случае окажется единица, верхней — одно из двух исходных чисел. Блок-схема такого алгоритма прикреплена.
    В качестве начального значения верхней границы может передаваться, наименьшее из двух исходных чисел, но на асимптотическую эффективность алгоритма это не окажет влияния. Вызов функции и инициализацию верхнего значения удобно вынести в отдельную функцию еще и потому, что в ней же возможно вычисление модулей чисел (приведенный алгоритм сработает только для положительных чисел).
    Реализация поиска наибольшего общего делителя на SWI Prolog:

    greatest_common_denominator(A, B, Denominator):-
      greatest_common_denominator(A, B, A, Denominator).
      
    greatest_common_denominator(A, B, Iterator, Iterator):-
      0 is A mod Iterator, 0 is B mod Iterator, !.
    greatest_common_denominator(A, B, Iterator, Denominator):-
      NextIterator is Iterator - 1,
      greatest_common_denominator(A, B, NextIterator, Denominator).

Для ответа в этой теме необходимо авторизоваться.