Algorytm Hornera (Zamiana Systemów Liczbowych)

Podstawą na każdym egzaminie maturalnym z informatyki są systemy liczbowe. Często spotkasz zadania, w których musisz odczytać liczbę zapisaną w systemie binarnym (np. 1101) lub szesnastkowym i zamienić ją na system dziesiętny, z którym pracuje nam się najwygodniej.

Możemy to robić klasycznie, mnożąc każdą cyfrę przez potęgę podstawy systemu od końca. Wymaga to jednak ciągłego obliczania potęg. Dużo łatwiejszą i bardzo chętnie punktowaną na maturze (jako tzw. algorytm optymalny) jest metoda Schematu Hornera.

Jak działa Schemat Hornera?

Algorytm ten pozwala nam całkowicie pozbyć się potęgowania. Działa w oparciu o prostą iterację (od lewej do prawej) na cyfrach z tekstu.

Dla liczby zapisanej jako napis S w systemie o podstawie P:

1. Zaczynamy od stworzenia zmiennej wynik = 0.
2. Bierzemy pierwszą cyfrę z napisu (od lewej strony).
3. Aktualizujemy wynik: wynik = wynik * P + wartosc_cyfry.
4. Bierzemy kolejną cyfrę i powtarzamy krok 3, aż skończą nam się cyfry.

Dzięki temu liczba operacji w komputerze jest minimalna. Przechodzimy napis dokładnie raz z lewej do prawej (Złożoność O(D), gdzie D to długość napisu).

Implementacja krok po kroku

Kluczem w tego typu zadaniach jest operowanie na stringach (napisach). Wynika to z faktu, że liczby w systemach binarnych bywają tak potężne, że przekraczają standardowe zasięgi typów liczbowych w C++, a system szesnastkowy wymaga używania liter (A, B, C, D, E, F). W Pythonie zadanie jest banalnie proste, a sam Python posiada wbudowaną opcję konwersji używając int(napis, podstawa). Często jednak w kluczu odpowiedzi CKE proszą nas o napisanie własnej funkcji. W C++ musimy pamiętać o kodach ASCII, aby zamienić znak char (np. '1') na odpowiadającą mu liczbę typu int. Najprościej zrobić to odejmując od danego znaku kod ASCII znaku '0'.

Python

def horner(napis, podstawa):
    wynik = 0
    
    # Przechodzimy pętlą przez każdy znak napisu (od lewej)
    for znak in napis:
        # Zamieniamy znak (który jest stringiem) na cyfrę
        # np. "1" zamienia się na cyfrę 1
        cyfra = int(znak)
        
        # Schemat Hornera:
        wynik = wynik * podstawa + cyfra
        
    return wynik

# Testowanie - zamiana 1101 (bin) na dziesiętny
print(horner("1101", 2)) # Wyświetli 13

C++

#include <iostream>
#include <string>
using namespace std;

int horner(string napis, int podstawa) {
    int wynik = 0;
    
    // Pętla po całej długości napisu (od lewej do prawej)
    for (int i = 0; i < napis.length(); i++) {
        // Zamiana znaku ASCII na cyfrę całkowitą
        // Znak '1' ma kod 49, a '0' ma 48. Więc 49 - 48 = 1.
        int cyfra = napis[i] - '0';
        
        // Schemat Hornera
        wynik = wynik * podstawa + cyfra;
    }
    
    return wynik;
}

int main() {
    // 1101 binarne to 13 w dziesiętnym
    cout << horner("1101", 2) << endl;
    return 0;
}

[!TIP] Dla dociekliwych: A co z systemem szesnastkowym (Hex)? Skrypt zaprezentowany wyżej poradzi sobie super z systemem binarnym, trójkowym, czy ósemkowym. Co jednak jeśli mamy litery od 'A' do 'F' w systemie szesnastkowym? Wtedy do zmiennej cyfra musimy przypisać trochę inną logikę. Jeśli nasz znak mieści się w przedziale od 'A' do 'Z', to odejmujemy od niego kod ASCII literki 'A' i dodajemy 10 (ponieważ 'A' w systemie 16-kowym odpowiada dziesiątce). W C++ wygląda to tak: if(napis[i] >= 'A' && napis[i] <= 'Z') { cyfra = napis[i] - 'A' + 10; }