Разложение числа на слагаемые на Prolog

      Комментарии к записи Разложение числа на слагаемые на Prolog отключены

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

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

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

    questioner
    Участник

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

    Вложения:
  • #2123

    Обе задачи решаются рекурсивно. Пусть требуется разложить число Number на слагаемые без учета порядка их следования.
    После генерации первого слагаемого (Addend) задача уменьшается, т.к. теперь требуется разложить Number-Addend.
    Очевидно, в качестве слагаемого должны подставляться все числа в диапазоне от 1 до Number. Для генерации таких чисел можно использовать встроенную функцию between.

    number_partitions(0, []):-!.
    number_partitions(Number, [Addend|TailComprosition]):-
      between(1, Number, Addend),
      TailNumber is Number - Addend,
      number_partitions(TailNumber, TailComprosition).

    Если исходное число равно нулю, то разбивать на слагаемые нечего — результатом является пустой список. В противном случае выполняется генерация слагаемого, на основе которого вычисляется новое значение аргумента и выполняется рекурсивная обработка.

    При генерации композиций требуется учитывать порядок следования элементов. Для этого можно потребовать, чтобы каждое следующее слагаемое было меньше или равно предыдущему — это исключит одинаковые наборы слагаемых, отличающиеся лишь порядком следования элементов.

    number_compositions(Number, Composition):-
      number_compositions(Number, 1, Composition).

    Вспомогательная функция инициализирует начальное значение предыдущего слагаемого единицей.

    number_compositions(0, _PreviousAddend, []):-!.
    number_compositions(Number, PreviousAddend, [Addend|TailComprosition]):-
      between(PreviousAddend, Number, Addend),
      TailNumber is Number - Addend,
      number_compositions(TailNumber, Addend, TailComprosition).

    Генерация композиций отличается от разбиений лишь тем, что в качестве нижней границы функции between передается значение предыдущего слагаемого.

    Примеры разложения чисел приведены на снимках экрана.

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