Chceš se vypracovat až k výdělku 160.000 Kč/měsíc? Důležité je začít. Staň se programátorem díky rekvalifikačnímu kurzu! Začni dnes!
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í.

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.

Koupit tento kurz

Koupit všechny aktuálně dostupné lekce s funkcí odevzdávání úloh za pouhých 100 Kč
Aktuální stav konta 0 Kč
Koupí tohoto balíčku získáš přístup ke všem 14 článkům (14 lekcí) tohoto kurzu.

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.

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

Č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