Schemat Hornera i szybkie potęgowanie

Schemat Hornera i szybkie potęgowanie to dwa algorytmy, które podstawa programowa informatyki w zakresie rozszerzonym wymienia z nazwy: obliczanie wartości wielomianu za pomocą schematu Hornera oraz szybkie potęgowanie liczb w wersji iteracyjnej i rekurencyjnej. Oba pokazują, jak sprytne przekształcenie wzoru zmniejsza liczbę mnożeń — i oba wracają w zadaniach maturalnych, w których trzeba przeanalizować gotowy kod albo napisać własną implementację.

W pierwszej części zapisujesz wielomian w postaci Hornera, na przykład $4x^3 - 2x^2 + 5x - 3 = ((4x - 2)x + 5)x - 3$, i obliczasz jego wartość krok po kroku. Liczysz mnożenia: schemat Hornera potrzebuje ich dokładnie tyle, ile wynosi stopień wielomianu, podczas gdy liczenie każdej potęgi osobno wymaga ich znacznie więcej. Widzisz też, że ten sam schemat zamienia liczbę z systemu o podstawie $p$ na dziesiętny — cyfry są współczynnikami, a $x$ to podstawa. Krótki program w Pythonie z pętlą w = w · x + c pokazuje, jak mało kodu potrzeba, i przypomina o współczynnikach równych zeru.

Druga część to szybkie potęgowanie. Poznajesz wzór rekurencyjny: dla parzystego wykładnika $a^n=(a^{n\mathrm{/}2}{)}^2$, dla nieparzystego $a^n=a\cdot a^{n-1}$. Śledzisz funkcję rekurencyjną w C++ i liczysz jej wywołania, porównujesz liczbę mnożeń z metodą naiwną i uzasadniasz złożoność $O(\log n)$. Wersję iteracyjną łączysz z zapisem dwójkowym wykładnika: $13 = 1101_2$, więc $a^{13}=a^8\cdot a^4\cdot a$. Na koniec liczysz potęgę modulo, biorąc resztę po każdym mnożeniu — tak, by liczby nie rosły ponad miarę.

Materiał oferuje cztery formy pracy. Quiz zawiera zadania rachunkowe i analizę programów z wyjaśnieniem każdego kroku. Fiszki utrwalają postać Hornera, wzory rekurencyjne, złożoności i związek z systemem dwójkowym. Egzamin ustny w formie rozmowy z egzaminatorem sprawdza, czy umiesz objaśnić oba algorytmy i uzasadnić ich efektywność. Praca pisemna do wydruku zawiera zadania otwarte: obliczenia krok po kroku i zapis algorytmów w pseudokodzie lub w wybranym języku programowania (C++, Python lub Java).

Wszystkie zadania są oryginalnymi ćwiczeniami do samodzielnej nauki, a wyniki programów zostały sprawdzone przez ich uruchomienie.

• Zapisujesz wielomian w postaci Hornera i obliczasz jego wartość z n mnożeniami.
• Stosujesz schemat Hornera do zamiany liczby z systemu o podstawie p na dziesiętny.
• Stosujesz wzór rekurencyjny szybkiego potęgowania i liczysz wywołania funkcji.
• Łączysz wersję iteracyjną szybkiego potęgowania z zapisem dwójkowym wykładnika.
• Obliczasz potęgi modulo i uzasadniasz złożoność O(log n).

Materiał ćwiczeniowy przygotowany przez Zestly.