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

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

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

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

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

    questioner
    Участник

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

  • #2528

    Согласно алгоритма Евклида для двух чисел:

    • вычисления завершаются если числа равны – в этом случае наибольший общий делитель совпадает со значением этих чисел;
    • если числа не равны – надо выбрать из них большее и заменить его разностью чисел.

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

    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).

    Вложения:

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