Lekce 13 - Hornerovo schéma
V minulé lekci, Převod čísel mezi číselnými soustavami, jsme si ukázali algoritmy pro převod čísel mezi číselnými soustavami.
Hornerovo schéma je algoritmus pro efektivní výpočet mnohočlenu v daném bodě. Je užitečný například pro převod čísel do desítkové soustavy, nebo zjištění derivace mnohočlenu.
Mějme mnohočlen P(x), kde c0 až cn jsou reálné koeficienty odpovídajících členů polynomu. Chceme vypočítat hodnotu této funkce:
P(x) = c0 + c1 x + c2 x2 + c3 x3 + ... + cn-1 xn−1 + cn xn
Naivní algoritmus
Jeden z možných způsobů, jak takový mnohočlen spočítat pro danou hodnotu x, je vypočítat každý jeho člen zvlášť. To je poměrně náročné. Tento způsob totiž vyžaduje n násobení pro nejvyšší člen, n-1 pro druhý nejvyšší člen atd., až jedno násobení pro poslední člen polynomu. Budeme tedy potřebovat n + (n-1) + (n-2) ... 1 násobení. Členy této řady tvoří aritmetickou posloupnost, kde je diference 1 (každý následující člen posloupnosti se od předchozího liší o 1). To znamená, že budeme potřebovat (n2 + n) / 2 násobení a n sčítání, protože vypočítané členy musíme nakonec sečíst, abychom dostali požadovaný výsledek.
Popsaný algoritmus jde vylepšit použitím efektivnějšího způsobu výpočtu mocniny (třeba postupným násobením x od nejnižšího členu). Existuje ale lepší a jednoduší způsob, jak stejný problém vyřešit.
...konec náhledu článku...
Pokračuj dál
Došel jsi až sem a to je super! Věříme, že ti první lekce ukázaly něco nového a užitečného.
Chceš v kurzu pokračovat? Přejdi do prémiové sekce.
Koupit tento kurz
Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.
- Neomezený a trvalý přístup k jednotlivým lekcím.
- Kvalitní znalosti v oblasti IT.
- Dovednosti, které ti pomohou získat vysněnou a dobře placenou práci.
Popis článku
Požadovaný článek má následující obsah:
Hornerovo schéma je algoritmus pro efektivní výpočet hodnoty mnohočlenu příp. jeho derivace. Je užitečný mj. i pro převod čísla do desítkové soustavy.
Kredity získáš, když podpoříš naši síť. To můžeš udělat buď zasláním symbolické částky na podporu provozu nebo přidáním obsahu na síť.
