Úloha: Dostaneme polynom $P(x)=ax^2+bx+c$, kde $a$, $b$, $c\in \ZZ$ jsou předem známé konstanty. Pro všechna $x\in\{1, 2,\dots, n\}$ bychom chtěli spočítat hodnotu polynomu. Například proto, abychom si mohli nakreslit graf funkce $P(x)$.

Řešení: (Hörnerovo schéma) Pro každé $x$ spočítáme hodnotu $P(x)$ Hörnerovým schématem. Hörnerovo schéma vychází z možnosti částečně povytýkat $x$. Dostaneme $P(x)= (((a)x + b)x +c)$. Uzávorkování nám dává návod, jak vyhodnotit polynom v bodě $x$. Budeme postupovat v cyklu, začneme od nejvnitřnější závorky. V každém kroku přenásobíme vnitřní závorku hodnotou $x$ a přičteme k ní odpovídající konstantu.

Pro vyhodnocení polynomu ve všech $x\in\{1,\dots, n\}$ budeme $2n$ krát násobit a $2n$ krát sčítat.

Řešení: (výpočet hodnoty na základě předchozí) Tentokrát zkusíme hodnotu $P(x+1)$ spočítat na základě předchozí hodnoty $P(x)$. Pro vypočtení $P(1)$ potřebujeme jen dvakrát sčítat. $P(x+1)= a(x+1)^2+b(x+1)+c = P(x) + (2a)x + (a+b)$. Pro výpočet $P(x+1)$ tedy úplně stačí, když k předchozí hodnotě $P(x)$ přičteme $(2a)x + (a+b)$. Označíme $Q(x)=(2a)x + (a+b)$. Zbývá ukázat, jak rychle spočítat hodnotu $Q(x)$. Spočteme ji stejným trikem. Pro výpočet $Q(1)$ nám stačí tři sčítání. Pro výpočet hodnoty $Q(x+1)$ na základě předchozí nám stačí jednou sčítat, protože $Q(x+1) = Q(x) + 2a$.

$\ARRAY{P}{1}:=a+b+c$; 
$\ARRAY{Q}{1}:=3a+b$ 
for $i=2$ to n do
	 $\ARRAY{P}{i}:=\ARRAY{P}{i-1}+\ARRAY{Q}{i-1}$
	 $\ARRAY{Q}{i}:=\ARRAY{Q}{i-1}+2a$

Takto vypočítáme hodnotu $P(x)$ ve všech bodech $x\in\{1,\dots, n\}$ pomocí pouhých $2n+5$ sčítání.1 Pokud by $a$, $b$, $c$ byly opravdu předem známé konstanty a ne proměnné, tak můžeme ušetřit i těch prvních $5$ sčítání tím, že si $P(1)$, $Q(1)$ předpočítáme.

Dokážete úlohu zobecnit pro vyhodnocování polynomu stupně $3$, stupně $4$ nebo obecně pro polynomy stupně $k$?