Hledáme nové posily do ITnetwork týmu. Podívej se na volné pozice a přidej se do nejagilnější firmy na trhu - Více informací.
Pouze tento týden sleva až 80 % na e-learning týkající se Swiftu. Zároveň využij výhodnou slevovou akci až 30 % zdarma při nákupu e-learningu - více informací.
discount 30 + hiring

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 c0cn 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

Znalosti v hodnotě stovek tisíc získáš za pár korun

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.

Omezená nabídka: Nauč se vše a ušetři

Koupit lekce a funkce postupně a po jednom 40 bodů
Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za exkluzivní cenu 34 bodů (85 Kč)
Na svém účtu máš aktuálně 0 bodů
Koupí tohoto výhodného balíčku získáš přístup ke všem 23 lekcím s kontrolou a certifikací a ještě navíc ušetříš 15 Kč. Nabídka je omezená pouze pro první lekce z kurzu a obsahuje exkluzivní slevu 15%.
34 bodů získáš za přidání svého článku na síť nebo odpovídá 100 Kč 85 Kč

Pozor, pokud si koupíš pouze tuto lekci, ztratíš nárok na speciální slevu 15% na balíček všech lekcí.

Koupit jen lekci 10 bodů
Na svém účtu máš aktuálně 0 bodů
10 bodů získáš za přidání svého článku na síť nebo odpovídá 25 Kč

Obsah článku spadá pod licenci Premium, koupí článku souhlasíš se smluvními podmínkami.

Co od nás v dalších lekcích dostaneš?
  • 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.

Body 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íť.

Článek pro vás napsal Drahomír Hanák
Avatar
Autor v současné době studuje Informatiku. Zajímá se o programování, matematiku a grafiku.
Aktivity