Перемножение многочленов на Prolog

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

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

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

    questioner
    Участник

    Написать функцию, вычисляющую произведение многочленов, заданных в виде списков коэффициентов.

  • #2128

    Даны два полинома, заданным списками Left и Right с длинами RightLength и LeftLength, соответственно.
    Нужно вычислить их произведение, в результате получится новый полином Product, с длиной ProductLength. Для этого, согласно формуле, нужно выделять элементы с заданными индексами из исходный списков, однако индексы изменяются от 0 до ProductLength, т.е. для части индексов в исходных списках будет отсутствовать элемент.

    Есть три варианта решить проблему:

    • выделять функцией nth0 элементы непосредственно из исходных списков и вычислять их произведение. При отсутствии элемента функция завершится неудачей — в этом случае результат умножения текущего элемента можно считать равным нулю;
    • выделять части исходных списков, а затем их обрабатывать. Это чуть-чуть более эффективно и удобно. Кроме того, можно заметить, что согласно формуле выполняется скалярное умножение векторов, но часть, вырезанная из правового списка перед умножением переворачивается. Самой сложной частью при этом будет выделение частей исходных списков, т.к. по прежнему часть элементов в исходных списках будет отсутствовать. Нужно также учитывать то, что исходные списки могут быть разной длины;
    • исходные списки можно дополнить нулями до ProductLength — это не изменит значения полиномов, однако значительно упростит выделение части списка для вычисления скалярного произведения. Теперь элементы с нужными индексами всегда есть в списке, поэтому для вычисления K-того элемента произведения достаточно получить первые K элементов из исходных списков, перевернуть второй и вычислить их скалярное произведение.

    %% product two polynoms
    polynom_product(Left, Right, Product):-
      length(Left, LeftLength),
      length(Right, RightLength),
      ProductLength is LeftLength + RightLength,
      supplementToLength(Left, ProductLength, SupplementedLeft),
      supplementToLength(Right, ProductLength, SupplementedRight),
      polynom_product(SupplementedLeft, SupplementedRight, 1, ProductLength, Product).

    Функцией length вычисляется длина исходных списков, длина результата. Умножаемые полиномы дополняются незначащими нулями и передаются вспомогательной функции для расчета всех элементов от 1 до ProductLength.

    %% supplement polynom to fixed length by zero coefficients
    supplementToLength([], 0, []):-!.
    supplementToLength([], Length, [0|Supplement]):-
      NextLength is Length - 1, 
      supplementToLength([], NextLength, Supplement), !.
    supplementToLength([Head|Tail], Length, [Head|TailSupplement]):-
      supplementToLength(Tail, Length, TailSupplement).

    Функция дополнения списка нулями до заданной длины завершает работу если длина равна нулю и исходный список пуст.
    Если исходный список пуст, но длина не равна нулю — нужно добавить вернуть список из Length нулей, поэтому рекурсивно уменьшается длина и новое значение обрабатывается рекурсивно. К полученному результату дописывается ноль. Если же исходный список не пуст, то мы должны убрать первый элемент (Head), сохранив его в стеке, остальные элементы обработать рекурсивно, а затем дописать Head к результату.

    Вспомогательная функция перебирает все значения от 1 до ProductLength и для каждого из них инициализирует вычисление K-того элемента:

    %% calculate each of 1..length product elements 
    %% length is size of result polynom
    %% left and right polynoms must be supplemented to length
    polynom_product(_Left, _Right, ProductIndex, ProductIndex, []):-!.
    polynom_product(Left, Right, ProductIndex, ProductLength, [ProductHead|ProductTail]):-
      product_element_calculation(Left, Right, ProductIndex, ProductHead), 
      NextProductIndex is ProductIndex + 1, 
      polynom_product(Left, Right, NextProductIndex, ProductLength, ProductTail).

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

    %% calculate single product element
    %% by select part of list and calculate their scalar multiplication
    product_element_calculation(Left, Right, ProductIndex, ProductElement):-
      get_first_elements(Left, ProductIndex, LeftPart),
      get_first_elements(Right, ProductIndex, RightPart),
      reverse(RightPart, ReverseRightPart),
      scalar_multiplication(LeftPart, ReverseRightPart, ProductElement), !.

    При вычисления элемента полинома-результата достаточно выделить из обоих списков первые K элементов, второй из них перевернуть и выполнить скалярное произведение частей.

    Для выделения первых K элементов можно использовать встроенные функции append и length:

    %% get first elements of list
    get_first_elements(List, PartLength, Part):-
      append(Part, _OtherElements, List), 
      length(Part, PartLength), !.

    Функция append при таком использовании разделяет исходный список List на две части произвольным образом (всеми доступными вариантами). Функция length задает ограничение — первая часть списка должна иметь заданную длину.

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