I_R_W14_M30_C++ Schemat Hornera - efektywna metoda obliczania wartości wielomianów
W informatyce liczy się nie tylko to, co obliczamy, ale przede wszystkim jak to robimy**. Schemat Hornera** jest świetnym przykładem metody, która pozwala wykonywać obliczenia szybciej, efektywniej i z mniejszym ryzykiem błędów. W tym rozdziale poznasz sposób przekształcania wielomianów, który od lat stanowi podstawę optymalnych obliczeń numerycznych i pokazuje, jak myśleć algorytmicznie. Zobaczysz, jak dzięki kilku prostym krokom można znacząco przyspieszyć działanie programu i dlaczego schemat Hornera jest tak ważny w praktyce programistycznej.
Schemat Hornera pozwala obliczać wartość wielomianu. Dzięki niemu można ograniczyć liczbę operacji mnożenia, co w informatyce pozwala zaoszczędzić czas oraz zasoby. W tym e‑materiale poznasz dwie wersje algorytmu obliczania wartości wielomianu z wykorzystaniem schematu Hornera: iteracyjną i rekurencyjną.
Horner nie był pierwszy…
Choć schemat nosi nazwisko Williama George’a Hornera (1774–1837), metoda była znana kilka stuleci wcześniej. Stosowali ją już chińscy matematycy, m.in. Qin Jiushaow XIII wieku. Horner jedynie ją spopularyzował - i to jego nazwisko zostało w historii.
Ćwiczenia na rozgrzewkę
Stwórz mini komiks: „Horner na ratunek!”
Kadr 1 Uczeń siedzi nad kartką pełną potęg i mnożeń. Uczeń: „Serio? Mam to wszystko liczyć po kolei? To potrwa wieki…”
Kadr 2 Nagle zza kartki wychyla się sympatyczny matematyk w cylindrze. Horner: „Pozwól, że się przedstawię: Horner. Schemat Horner.”
Uczeń: „A pan skąd się tu wziął?”
Kadr 3
Horner: „Widzę, że męczysz się z wielomianem. A ja mam sposób, żeby policzyć go szybciej niż myślisz.”
Uczeń: „Szybciej? Ile razy szybciej?”
Horner: „Tyle, że zdążysz jeszcze na przerwę.”
Kadr 4 Horner pokazuje schemat Hornera, a liczby „spływają” po nim jak po zjeżdżalni. Horner: „Zamiast liczyć każdy wyraz osobno, przepuszczamy wszystko przez jedną maszynkę.”
Uczeń: „Ooo! To działa jak matematyczny ekspres!”
Kadr 5 Uczeń zadowolony, kartka czysta, wynik gotowy. Uczeń: „To było… zaskakująco proste.”
Horner: „Wiem. Dlatego mnie lubią.”
Wyjaśnisz, jak działa schemat Hornera zapisany iteracyjnie i rekurencyjnie.
Przeanalizujesz obie wersje algorytmu obliczającego wartość wielomianu z wykorzystaniem schematu Hornera zapisane za pomocą pseudokodu.
Wykorzystasz schemat Hornera do wykonania ćwiczeń.