{"id":8122,"date":"2023-05-12T06:00:46","date_gmt":"2023-05-12T04:00:46","guid":{"rendered":"http:\/\/www.glc.us.es\/~jalonso\/exercitium\/?p=8122"},"modified":"2023-05-04T11:01:42","modified_gmt":"2023-05-04T09:01:42","slug":"12-may-23","status":"publish","type":"post","link":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/12-may-23\/","title":{"rendered":"TAD de los polinomios: M\u00e9todo de Horner del valor de un polinomio"},"content":{"rendered":"

El m\u00e9todo de Horner para calcular el valor de un polinomio se basa en representarlo de una forma forma alernativa. Por ejemplo, para calcular el valor de<\/p>\n

\n   a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f\n<\/pre>\n
se representa como<\/p>\n
\n  (((((0 * x + a) * x + b) * x + c) * x + d) * x + e) * x + f\n<\/pre>\n
y se eval\u00faa de dentro hacia afuera; es decir,<\/p>\n
\n  v(0) = 0\n  v(1) = v(0)*x+a = 0*x+a = a\n  v(2) = v(1)*x+b = a*x+b\n  v(3) = v(2)*x+c = (a*x+b)*x+c = a*x^2+b*x+c\n  v(4) = v(3)*x+d = (a*x^2+b*x+c)*x+d = a*x^3+b*x^2+c*x+d\n  v(5) = v(4)*x+e = (a*x^3+b*x^2+c*x+d)*x+e = a*x^4+b*x^3+c*x^2+d*x+e\n  v(6) = v(5)*x+f = (a*x^4+b*x^3+c*x^2+d*x+e)*x+f = a*x^5+b*x^4+c*x^3+d*x^2+e*x+f\n<\/pre>\n
Usando el tipo abstracto de los polinomios<\/a>, definir la funci\u00f3n<\/p>\n
\n   horner :: (Num a, Eq a) => Polinomio a -> a -> a\n<\/pre>\n
tal que horner p x<\/code> es el valor del polinomio p<\/code> al sustituir su variable por el n\u00famero x<\/code>. Por ejemplo,<\/p>\n
\n   \u03bb> pol1 = consPol 5 1 (consPol 2 5 (consPol 1 4 polCero))\n   \u03bb> pol1\n   x^5 + 5*x^2 + 4*x\n   \u03bb> horner pol1 0\n   0\n   \u03bb> horner pol1 1\n   10\n   \u03bb> horner pol1 1.5\n   24.84375\n   \u03bb> import Data.Ratio\n   \u03bb> horner pol1 (3%2)\n   795 % 32\n<\/pre>\n
Soluciones<\/b><\/p>\n
A continuaci\u00f3n se muestran las soluciones en Haskell<\/a> y las soluciones en Python<\/a>.<\/p>\n
<\/a>
\nSoluciones en Haskell<\/b><\/p>\n
\nimport TAD.Polinomio (Polinomio, polCero, consPol)\nimport Pol_Transformaciones_polinomios_densas (polinomioAdensa)\n\n-- 1\u00aa soluci\u00f3n\n-- ===========\n\nhorner :: (Num a, Eq a) => Polinomio a -> a -> a\nhorner p x = hornerAux (polinomioAdensa p) 0\n  where hornerAux [] v     = v\n        hornerAux (a:as) v = hornerAux as (v*x+a)\n\n-- El c\u00e1lculo de (horner pol1 2) es el siguiente\n--    horner pol1 2\n--    = hornerAux [1,0,0,5,4,0] 0\n--    = hornerAux   [0,0,5,4,0] ( 0*2+1) = hornerAux   [0,0,5,4,0] 1\n--    = hornerAux     [0,5,4,0] ( 1*2+0) = hornerAux     [0,5,4,0] 2\n--    = hornerAux       [5,4,0] ( 2*2+0) = hornerAux       [5,4,0] 4\n--    = hornerAux         [4,0] ( 4*2+5) = hornerAux         [4,0] 13\n--    = hornerAux           [0] (13*2+4) = hornerAux           [0] 30\n--    = hornerAux            [] (30*2+0) = hornerAux            [] 60\n\n-- 2\u00aa soluci\u00f3n\n-- ===========\n\nhorner2 :: (Num a, Eq a) => Polinomio a -> a -> a\nhorner2 p x = foldl (\\a b -> a*x + b) 0 (polinomioAdensa p)\n<\/pre>\n
<\/a>
\nSoluciones en Python<\/b><\/p>\n
\nfrom functools import reduce\n\nfrom src.Pol_Transformaciones_polinomios_densas import polinomioAdensa\nfrom src.TAD.Polinomio import Polinomio, consPol, polCero\n\n# 1\u00aa soluci\u00f3n\n# ===========\n\ndef horner(p: Polinomio[float], x: float) -> float:\n    def hornerAux(ys: list[float], v: float) -> float:\n        if not ys:\n            return v\n        return hornerAux(ys[1:], v * x + ys[0])\n\n    return hornerAux(polinomioAdensa(p), 0)\n\n# El c\u00e1lculo de horner(pol1, 2) es el siguiente\n#    horner pol1 2\n#    = hornerAux [1,0,0,5,4,0] 0\n#    = hornerAux   [0,0,5,4,0] ( 0*2+1) = hornerAux   [0,0,5,4,0] 1\n#    = hornerAux     [0,5,4,0] ( 1*2+0) = hornerAux     [0,5,4,0] 2\n#    = hornerAux       [5,4,0] ( 2*2+0) = hornerAux       [5,4,0] 4\n#    = hornerAux         [4,0] ( 4*2+5) = hornerAux         [4,0] 13\n#    = hornerAux           [0] (13*2+4) = hornerAux           [0] 30\n#    = hornerAux            [] (30*2+0) = hornerAux            [] 60\n\n# 2\u00aa soluci\u00f3n\n# ===========\n\ndef horner2(p: Polinomio[float], x: float) -> float:\n    return reduce(lambda a, b: a * x + b, polinomioAdensa(p) , 0.0)\n<\/pre>\n","protected":false},"excerpt":{"rendered":"
El m\u00e9todo de Horner para calcular el valor de un polinomio se basa en representarlo de una forma forma alernativa. Por ejemplo, para calcular el valor de a*x^5 + b*x^4 + c*x^3 + d*x^2 + e*x + f se representa como (((((0 * x + a) * x + b) * x + c) *…<\/p>\n","protected":false},"author":1,"featured_media":0,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"jetpack_post_was_ever_published":false,"_kad_post_transparent":"","_kad_post_title":"","_kad_post_layout":"","_kad_post_sidebar_id":"","_kad_post_content_style":"","_kad_post_vertical_padding":"","_kad_post_feature":"","_kad_post_feature_position":"","_kad_post_header":false,"_kad_post_footer":false,"_jetpack_newsletter_access":"","_jetpack_dont_email_post_to_subs":false,"_jetpack_newsletter_tier_id":0,"_jetpack_memberships_contains_paywalled_content":false,"footnotes":"","_jetpack_memberships_contains_paid_content":false},"categories":[581],"tags":[265],"jetpack_featured_media_url":"","jetpack_sharing_enabled":true,"_links":{"self":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8122"}],"collection":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/comments?post=8122"}],"version-history":[{"count":1,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8122\/revisions"}],"predecessor-version":[{"id":8123,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/posts\/8122\/revisions\/8123"}],"wp:attachment":[{"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/media?parent=8122"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/categories?post=8122"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.glc.us.es\/~jalonso\/exercitium\/wp-json\/wp\/v2\/tags?post=8122"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}