Наибольший общий делитель двух и трех чисел на Prolog

Программирование Помощь с решением задач на Prolog Общие вопросы Наибольший общий делитель двух и трех чисел на Prolog

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

  • Автор
    Сообщения
  • #2527
    @questioner

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

  • #2528
    @admin

    Перед разбором реализации на Пролог рекомендую посмотреть «Алгоритм Евклида (наибольший общий делитель)«.

    Было бы удобно, если наибольшее двух чисел всегда было первым, однако может получаться и иная ситуация — в этом случае можно не искать среди чисел максимальное (это не удобно, т.к. его же придется заменять разностью), а вызывать правило с другим порядком аргументов:

    greatest_common_divisor(A, B, Divisor):-
      B > A, !, greatest_common_divisor(B, A, Divisor).
    greatest_common_divisor(A, B, Divisor):-
      A > B, !, Difference is A - B,
      greatest_common_divisor(Difference, B, Divisor).
    greatest_common_divisor(Divisor, Divisor, Divisor).

    Для вычисления НОД трех чисел достаточно вычислить НОД двух чисел, а затем — НОД результата и третьего числа:

    greatest_common_divisor3(A, B, C, Divisor):-
      greatest_common_divisor(A, B, DivisorAB),
      greatest_common_divisor3(C, DivisorAB, Divisor).

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