Ответ в теме: Вычисление многочлена по схеме Горнера на Prolog

      Комментарии к записи Ответ в теме: Вычисление многочлена по схеме Горнера на Prolog отключены
#2117

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

polynome_gorner([], _X, 0):-!.
polynome_gorner([An], _X, An):-!.
polynome_gorner([A|TailMultipliers], X, B):-
polynome_gorner(TailMultipliers, X, NextB),
B is A + NextB*X.

Первое правило обрабатывает случай, когда на вход подан пустой список, т.е. в многочлене нет ни одного ненулевого коэффициента. В схеме Горнера такой случай не рассматривается, однако многочлен при этом равен нулю вне зависимости от значения переменной.
Второе правило соответствует случаю, когда у многочлена есть один коэффициент, очевидно, что в этом случае значением многочлена будет значение соответствующего коэффициента. Это же правило соответствует первому шару алгоритма в схеме Горнера.
Остальные шаги алгоритма реализуются рекурсивно- третьим правилом. При этом исходный список разделяется на первый коэффициент и хвост. Хвост обрабатывается рекурсивно (вычисляется значение bn по Горнеру). После того, как результат получен можно вычислить предыдущее значение.