Horner
======

.. warning:: Per a resoldre aquest exercici **no es poden fer servir
             iteracions (ni** ``for`` **ni** ``while`` **)**, només
             funcions recursives.

.. py:module:: horner

La classe :py:class:`polinomi.Polinomi` (idèntica a la d'aquest `exercici <http://gie.cs.upc.edu/inf/temes/recursivitat/Polinomi_amb_m%C3%A9s_coeficients_no_nuls/index.html>`_) està especificada així:

.. py:class:: polinomi.Polinomi()

   Representa un polinomi que inicialment serà el polinomi nul amb
   tots els coeficients iguals a zero.

   Mètode:

   .. py:method:: grau()

      Retorna el grau del polinomi

   Operacions:

   +--------------------------+---------------------------------+
   | Operació                 | Resultat                        |
   +==========================+=================================+
   | ``p[g]``                 | retorna  el valor que té el     |
   |                          | coeficient de grau *g* del      |
   |                          | polinomi *p*                    |
   +--------------------------+---------------------------------+
   | ``p[g] = val``           | assigna el valor *val*  al      |
   |                          | coeficient de grau *g* del      |
   |                          | polinomi *p*                    |
   +--------------------------+---------------------------------+
   | ``p == v``               | retorna True si els polinomis   |
   |                          | *p* i *v* són iguals i False    |
   |                          | altrament                       |
   +--------------------------+---------------------------------+


Disposeu d'una implementació de la classe
:py:class:`polinomi.Polinomi` al fitxer :download:`polinomi.py`.


En el mòdul :file:`horner.py` dissenyeu la funció recursiva
següent:

.. py:function:: horner(p, x)

   Retorna el valor del polinomi 
   :py:class:`~polinomi.Polinomi` *p* corresponent al valor *x*.

   Per exemple:

   .. literalinclude:: test-horner.txt
      :language: python
      :start-after: --ini-enunciat
      :end-before: --fi-enunciat



L'avaluació del polinomi s'implementarà seguint el mètode de Horner. Donat un polinomi :math:`p(x)` de grau :math:`n`:

.. math::
   p(x) = \sum_{i=0}^n a_i x^i = a_0 + a_1 x + a_2 x^2 + a_3 x^3 + \cdots + a_n x^n

Es pot avaluar generant una seqüència de valors :math:`v_nv_{n-1}\ldots v_1v_0` de la següent forma:

.. math::
   \begin{align}
 v_n & = a_n \\
 v_{n-1} & = a_{n-1} + v_n x \\
 \quad\quad\quad & ~~~ \vdots \\
 v_1 & = a_1 + v_2 x \\
 v_0 & = a_0 + v_1 x.
 \end{align}


Essent finalment :math:`v_0 = p(x)` el valor del polinomi en :math:`x`.

.. note::

   Disposeu de jocs de prova al fitxer :download:`test-horner.txt`.

.. rubric:: Solució

Disposeu d'una solució al fitxer :download:`horner.py
<solucio/horner.py>`.