Klasyczne Algorytmy Liczbowe

Wstęp: Kręgosłup Matury z Informatyki

Wchodzimy w najważniejszy etap przygotowań. Arkusze CKE z programowania niemal zawsze opierają się na analizie właściwości liczb. Poniższe algorytmy to absolutne "pewniaki" – nie ma tu miejsca na zastanawianie się, jak je napisać. Musisz potrafić zakodować je z pamięci, rozumieć, jak działają, i wiedzieć, jak zoptymalizować je tak, by program wykonał się w wyznaczonym czasie.

🧮 Spis treści: Algorytmy Liczbowe

1 Cyfry liczby i Palindromy
2 Liczby Pierwsze i Rozkład na Czynniki

3 NWD i NWW (Algorytm Euklidesa)
4 Systemy Liczbowe i Schemat Hornera

Badanie właściwości: Cyfry i Palindromy

Ogromna część zadań rozpoczyna się od analizy pojedynczych cyfr danej liczby. Na przykład: "Znajdź liczby, których suma cyfr wynosi 12" lub "Sprawdź, czy liczba nie zawiera cyfry 0".

Metoda 1: Matematycznie (% i //)

Tradycyjne i najszybsze w działaniu podejście. Rozbijamy liczbę w pętli while, dopóki jest większa od zera.

n % 10 – zawsze zwraca ostatnią cyfrę.
n // 10 – odcina ostatnią cyfrę (zmienia np. 123 na 12).

def suma_cyfr(n):
    suma = 0
    while n > 0:
        cyfra = n % 10
        suma += cyfra
        n = n // 10
    return suma

Metoda 2: "Na skróty" (Tekstowo)

Ponieważ programujemy w Pythonie, możemy zamienić liczbę na tekst (string), a tekst traktować jak listę znaków. To ogromne ułatwienie dla maturzystów.

def ile_trojek(n):
    # Zamieniamy liczbę np. 1337 na tekst "1337"
    tekst = str(n)

    # Używamy wbudowanej metody .count()
    return tekst.count('3')

# Przekształcenie do int, by zsumować
suma_c = sum([int(x) for x in str(1234)])

🔄

Liczby Palindromiczne

Palindrom to słowo lub liczba, która czytana od lewej do prawej, jak i od prawej do lewej, jest dokładnie taka sama (np. 12321, 44, 8). Na egzaminie bardzo często sprawdza się to w różnych systemach liczbowych.

Sposób Pythona (Zalecany) s = str(liczba)
if s == s[::-1]:
print("Palindrom!")

Sposób matematyczny (CKE Teoria) n = liczba
odw = 0
while n > 0:
odw = (odw * 10) + (n % 10)
n //= 10

Uwaga: CKE w zadaniach wprost z algorytmiki (Część I) może zapytać, jak odwrócić liczbę bez używania stringów. Wykorzystuje się do tego pokazany po prawej wzór: "poprzednia odwrócona razy 10 plus nowa cyfra".

Teoria Liczb: Pierwszość i Czynniki

Liczba pierwsza to taka, która dzieli się tylko przez 1 i samą siebie (uwaga: 0 i 1 nie są liczbami pierwszymi!). Sprawdzenie tego w Pythonie jest proste, jednak CKE zawsze narzuca takie pliki testowe, które zmuszą Twój komputer do kapitulacji, jeśli nie użyjesz odpowiedniej optymalizacji matematycznej.

Algorytm Naiwny (0 pkt za wydajność)

Początkujący uczniowie piszą pętlę, która sprawdza wszystkie dzielniki od $2$ aż do $n-1$. Dla liczby rzędu dziesięciu miliardów, taka pętla wykona się 10 miliardów razy. Program "zawiśnie" na egzaminie.

# ZBYT WOLNE! NIE UŻYWAJ TEGO NA MATURZE!
def czy_pierwsza_wolna(n):
    if n < 2: return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

Złoty Standard (Optymalizacja do

\sqrt{n}

)⭐

Dzielniki zawsze występują w parach. Jeśli liczba dzieli się przez

a

, to wynikiem jest

b

(

a \times b = n

). Wystarczy sprawdzić dzielniki tylko do pierwiastka z $n$ . Jeśli do tego momentu nic nie znajdziemy, to drugi dzielnik z pary też nie istnieje!

def czy_pierwsza(n):
    if n < 2: return False
    # range idzie do pierwiastka (+1 żeby domknąć przedział)
    for i in range(2, int(n**0.5) + 1):
        if n % i == 0:
            return False
    return True

Rozkład na czynniki pierwsze (Faktoryzacja)

Każdą liczbę złożoną można przedstawić jako iloczyn liczb pierwszych (np.

12 = 2 \times 2 \times 3

). Na egzaminie często musisz znaleźć te czynniki lub policzyć ich ilość. Klasyczny algorytm używa do tego zagnieżdżonej pętli while.

def czynniki(n):
    lista_czynnikow = []
    k = 2 # Zaczynamy od najmniejszej liczby 1.

    # Dzielimy, dopóki z liczby nie zostanie 1
    while n > 1:
        # Dopóki się dzieli bez reszty przez k
        while n % k == 0:
            lista_czynnikow.append(k)
            n //= k # Zmniejszamy n!
        k += 1 # Sprawdzamy kolejny dzielnik

    return lista_czynnikow

Jak to działa w praktyce?

Wyobraź sobie liczbę 12:

k = 2. 12 dzieli się przez 2. Zapisujemy 2. Liczba to teraz 6.
6 dzieli się przez 2. Zapisujemy 2. Liczba to teraz 3.
3 nie dzieli się przez 2. Zwiększamy k na 3.
3 dzieli się przez 3. Zapisujemy 3. Liczba spada do 1. Główna pętla się kończy.

Wynik: [2, 2, 3]

🛑

Haczyk CKE: Potęgowanie w Pythonie

Matematyczny zapis pierwiastka $\sqrt(n)$ to inaczej podniesienie liczby do potęgi $\frac,1,2,$ (czyli $0.5$). W Pythonie do potęgowania NIE UŻYWAMY znaku karety ^ (to operacja bitowa XOR!). Potęgowanie zapisujemy podwójną gwiazdką: n**0.5. Błąd w tym znaku doprowadzi do natychmiastowego oblania zadania.

NWD i NWW: Algorytm Euklidesa

Największy Wspólny Dzielnik (NWD) to największa liczba, która dzieli dwie podane liczby bez reszty. Jest on kluczem do skracania ułamków i znajdowania cykli. Z kolei Najmniejsza Wspólna Wielokrotność (NWW) przydaje się przy wspólnym mianowniku. Na maturze musisz znać dwa sposoby zapisu tego algorytmu.

Wersja z Odejmowaniem (Teoria CKE)

Klasyczna, powolna wersja wymyślona przez starożytnych Greków. Polega na odejmowaniu mniejszej liczby od większej, aż obie staną się równe. Rzadko używamy jej w praktyce, ale bardzo często pojawia się w arkuszach z teorii (jako schemat blokowy do analizy).

def nwd_odejmowanie(a, b):
    # Wykonuj dopóki liczby są różne
    while a != b:
        if a > b:
            a = a - b
        else:
            b = b - a
    # Gdy są równe, obojętnie co zwrócisz
    return a

Wersja z Modulo (Praktyka)⚡

Zamiast odejmować wielokrotnie, możemy od razu obliczyć resztę z dzielenia (%). Ta wersja jest błyskawiczna i to ją musisz stosować w zadaniach z programowania (Część II), aby nie przekroczyć czasu wykonywania.

def nwd_modulo(a, b):
    # Dopóki b nie jest zerem
    while b > 0:
        # a przyjmuje wartość b
        # b przyjmuje resztę z dzielenia a przez b
        a, b = b, a % b
    return a

Pro tip: W Pythonie przypisanie wielokrotne a, b = b, a % b zwalnia nas z konieczności tworzenia zmiennej pomocniczej temp!

NWW (Najmniejsza Wspólna Wielokrotność)

Gdy znasz już NWD, obliczenie NWW to czysta matematyka. Wystarczy pomnożyć przez siebie obie liczby i podzielić wynik przez ich NWD. Wzór to: $NWW = \frac{a \cdot b}{NWD(a,b)}$ .

def nww(a, b):
# Używamy // aby wynik na pewno był liczbą całkowitą (int)
return (a * b) // nwd_modulo(a, b)

🔑

Legalny Cheat: Wbudowana biblioteka Math

Na maturze CKE interesuje tylko Twój wynik w pliku wyniki.txt (oraz to, by kod działał). Nie musisz pisać NWD z pamięci! Python posiada tę funkcję wbudowaną w standardową bibliotekę matematyczną. Użycie jej to ogromna oszczędność czasu i gwarancja bezbłędności.

import math

wynik_nwd = math.gcd(24, 36) # Zwróci 12
wynik_nww = math.lcm(24, 36) # Zwróci 72 (Uwaga: math.lcm dostępne od Pythona 3.9)

Systemy Liczbowe i Schemat Hornera

Nasz mózg przyzwyczaił się do systemu dziesiętnego (podstawa 10), ale komputery "myślą" w systemie binarnym (podstawa 2). Na maturze bardzo często spotkasz się również z systemem ósemkowym (8) i szesnastkowym (16). Musisz umieć swobodnie przeliczać wartości między tymi światami na dwa sposoby: pythonowym (szybkim) oraz algorytmicznym (wymaganym w teorii).

Z dowolnego na Dziesiętny (Oszustwo Pythona)⚡

Jeśli w Części Praktycznej (programowanie) masz za zadanie wczytać liczbę binarną z pliku i zamienić ją na "naszą", użyj potężnej funkcji int(). Jako drugi argument przyjmuje ona podstawę systemu, z jakiego przeliczasz!

# int(tekst, podstawa)
binarna = "1010"
dziesietna = int(binarna, 2) # Wynik: 10

# Działa dla każdego systemu od 2 do 36!
osemkowa = "17"
dziesietna2 = int(osemkowa, 8) # Wynik: 15

# System szesnastkowy (zawiera litery A-F)
szesnastkowa = "FF"
dziesietna3 = int(szesnastkowa, 16) # Wynik: 255

Z dowolnego na Dziesiętny: Schemat Hornera

To must-have na część teoretyczną. Algorytm Hornera pozwala błyskawicznie przeliczyć system na dziesiętny poprzez cykliczne mnożenie dotychczasowego wyniku przez podstawę i dodawanie kolejnej cyfry.

def horner(liczba_str, podstawa):
    wynik = 0
    for cyfra in liczba_str:
        # Zamieniamy znak (str) na wartość (int)
        wartosc = int(cyfra)
        # Kluczowy wzór Hornera:
        wynik = wynik * podstawa + wartosc
    return wynik

Wyobraź sobie "101" binarne:
Krok 1: $0 \cdot 2 + 1 = 1$
Krok 2: $1 \cdot 2 + 0 = 2$
Krok 3: $2 \cdot 2 + 1 = 5$ (Gotowe!)

Z Dziesiętnego na Dowolny (Algorytm dzielenia)

Aby zamienić naszą liczbę dziesiętną na inny system, musimy wielokrotnie dzielić ją przez nową podstawę i zapisywać reszty z dzielenia. Wynik to złączone reszty odczytane od tyłu.

def na_inny_system(n, podstawa):
    if n == 0: return "0"
    wynik = ""

    while n > 0:
        # 1. Oblicz resztę
        reszta = n % podstawa
        # 2. Doklej resztę NA POCZĄTEK tekstu
        # (dzięki temu czytamy od tyłu!)
        wynik = str(reszta) + wynik
        # 3. Podziel liczbę (odrzuć resztę)
        n = n // podstawa

    return wynik

Wbudowane funkcje Pythona:

Python potrafi automatycznie konwertować liczby dziesiętne na te najpopularniejsze systemy. Wynik jest stringiem z technicznym przedrostkiem.

bin(10) zwraca "0b1010" (binarny).
oct(15) zwraca "0o17" (ósemkowy).
hex(255) zwraca "0xff" (szesnastkowy).

Tip: Użyj slicingu [2:], aby pozbyć się przedrostków!
Npr. bin(10)[2:] da czyste "1010".

Algorytmy Liczbowe Zaliczone! 🥇

Znasz już najważniejsze narzędzia, za pomocą których rozwiązuje się lwią część matury z programowania. Umiesz rozkładać liczby na czynniki, szukać palindromów i przeliczać systemy.

Przejdź do: Algorytmy Tekstowe i Szyfrowanie ➡️

Teoria opanowana? Czas na sprawdzenie wiedzy!

Szybkie Quizy CKE

Praktyka i Arkusze