НОК двух чисел через сложение

      Комментарии к записи НОК двух чисел через сложение отключены

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

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

    Нужно вычислить наименьшее общее кратное (НОК) двух целых положительных чисел на Prolog. Решить нужно через сложение, т.е. у нас есть два числа – A и B. Мы можем последовательно вычислять 2*A, 3*A, ... N*A такие числа будут гарантированны кратны числу A, остается лишь дождаться пока очередное число станет кратно числу B.

    predicates
      lcm(integer, integer, integer)
      lcm(integer, integer, integer, integer)
      max(integer, integer, integer)
    clauses
      max(A, B, A):- A > B, !.
      max(_A, B, B).
      
      lcm(A, B, LCM):-
      	lcm(A, B, 0, LCM).
      
      lcm(A, B, Buf, Buf):-
      	Buf <> 0, 
      	Buf mod A = 0,
      	Buf mod B = 0, !.
      lcm(A, B, Buf, LCM):-
      	max(A, B, Max),
      	BufWithMax = Buf + Max,
      	lcm(A, B, BufWithMax, LCM).
    goal
      lcm(5, 3, LCM).

    lcm_prolog

    Основная функция lcm вызывает вспомогательную, принимающую четыре аргумента (дополнительный аргумент — буфер для накопления результата). При этом вызове в качестве начального значения буфера передается ноль.

    Вспомогательная функция завершает работу если очередное число (в буфере) не равно нулю и является делителем обоих чисел. В противном случае из двух чисел выбирается наибольшее и его значение прибавляется к буферу. Новое значение буфера обрабатывается рекурсивно.

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