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

      Комментарии к записи Ответ в теме: Наибольший общий делитель двух и трех чисел на Prolog отключены
#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).

Вложения: