Algoritmo de Horner para polinómios
As funções mais simples em matemática são os polinómios. Um polinómio é uma função com a forma Como é fácil de ver para calcular o valor do polinómio num ponto é apenas necessário fazer umas quantas multiplicações e somas. A maneira mais eficiente de calcular o valor do polinómio num ponto, isto é, efectuando o menor número de produtos e somas, é conseguido através do algoritmo de Horner. Consiste em factorizar o polinómio na seguinte forma:
A maneira mais simples de pensar numa implementação computacional é considerar a sucessão onde o resultado final é
Mais geralmente pode por-se com
Apesar da sua forma simples e definida por recurrência a sucessão de valores é mais clara e simples quando construída de uma forma imperativa do que a sua versão funcional. Se não veja-se. A implementação funcional fica:
(defun horner-eval (x coef) (accumulate (lambda (a b) (+ a (* b x))) 0 coef)) (defun accumulate (op initial sequence) (if (not sequence) initial (funcall op (car sequence) (accumulate op initial (cdr sequence)))))
enquanto a versão imperativa do mesmo algoritmo tem a forma:
(defun polyval (x coef) (let ((coefx coef) (px 0)) (while coefx (setq px (+ (* x px) (car coefx))) (setq coefx (cdr coefx))) px))Palavras chave/keywords: algoritmo, Horner, Lisp, Emacs
Criado/Created: NaN
Última actualização/Last updated: 10-10-2022 [14:26]
(c) Tiago Charters de Azevedo