Наименьшее общее кратное последовательности чисел

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

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

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

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

    questioner
    Участник

    Помогите решить задачу на Prolog — нужна функция, вычисляющая наименьшее общее кратное (НОК) последовательности чисел. Я находил алгоритм вычисления НОК через наибольший общий делитель, но как я понял, он работает только для двух чисел, а не для последовательности.

  • #2583

    Я думаю, что решение через НОД тоже может работать (надо проверить), но если нужно обойтись без него — то наименьшее общее кратное — это такое число LCD = k*max(List), что для любого элемента E из списка List выполняется LCD mod E = 0, при этом k = 1, 2, ... (должно быть минимальным). Такая формула связана с тем, что НОК не может быть меньше max(List), т.к. тогда оно не сможет быть кратно максимуму. С другой стороны — числа, кратные max(List)можно описать как k*max(List), где k — целое число. Отсюда может быть получен следующий алгоритм:

    1. вычислить Increment = max(List), V = Increment;
    2. если для любого элемента E списка List выполняется V mod E = 0 — вернуть V;
    3. V = V + Increment;
    4. переход на п. 2.
  • #2584

    В программе обрабатывается список целых чисел:

    domains
      elem_d = integer
      list_d = elem_d*

    Для ввода списка можно использовать функцию readlist.

    Для поиска наибольшего элемента списка в SWI Prolog можно использовать встроенную функцию max_list, однако, в Turbo и Visual Prolog ее необходимо реализовать вручную.

    Нам потребуется функция, проверяющая является ли число общим кратным списка чисел — для этого она перебирает числа пока список не окажется пустым и для каждого числа выполняет проверку кратности:

      is_lowest_common_denominator(_LCD, []):-!.
      is_lowest_common_denominator(LCD, [Head|Tail]):-
        0 = LCD mod Head, is_lowest_common_denominator(LCD, Tail).

    Функция поиска НОК вычисляет максимальный элемент списка и вызывает вспомогательную функцию, реализующую цикл приведенного выше алгоритма, передавая Max в качестве начального значения V и Increment:

      lowest_common_denominator(List, LCD):-
        max_list(List, Max), 
        lowest_common_denominator(List, Max, Max, LCD).

    Вспомогательная функция завершает работу если текущее значение V (переменная LCD) является НОК (для этого использует функцию is_lowest_common_denominator), а в противном случае увеличивает значение буфера на Increment и запускает рекурсивную обработку:

      lowest_common_denominator(List, _Increment, LCD, LCD):-
        is_lowest_common_denominator(LCD, List), !.
      lowest_common_denominator(List, Increment, Buffer, LCD):-
        BuffetWithIncrement = Buffer+Increment,
        lowest_common_denominator(List, Increment, BuffetWithIncrement, LCD).

    Для приведенных функций в разделе predicates должны быть следующим типом описаны типы данных:

    predicates
      is_lowest_common_denominator(elem_d, list_d)
      lowest_common_denominator(list_d, elem_d)
      lowest_common_denominator(list_d, elem_d, elem_d, elem_d)

    Точка входа в программу выполняет ввод списка целых чисел и вычисление их наименьшего общего кратного:

    goal
      readlist(List),
      lowest_common_denominator(List, LCD).

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