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

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

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

Просмотр 2 сообщений - с 1 по 2 (из 2 всего)
  • Автор
    Сообщения
  • #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).

    Вложения:
    Вы должны войти для просмотра вложений.
Просмотр 2 сообщений - с 1 по 2 (из 2 всего)

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