Lekcja 15: Algorytmy - powtorzenie i utrwalenie (systemy liczbowe, NWD)

Systemy liczbowe

W informatyce kluczowe sa cztery systemy liczbowe. Komputer operuje na bitach (systemie dwojkowym), ale programisci czesto uzywaja systemu osemkowego i szesnastkowego jako wygodnego skrotu.

Konwersja DEC na BIN (metoda dzielenia przez 2)

Przyklad: 42(10) na BIN
42 / 2 = 21 reszta 0
21 / 2 = 10 reszta 1
10 / 2 = 5  reszta 0
5  / 2 = 2  reszta 1
2  / 2 = 1  reszta 0
1  / 2 = 0  reszta 1

Czytamy reszty od dolu: 42(10) = 101010(2)

Sprawdzenie: 1*32 + 0*16 + 1*8 + 0*4 + 1*2 + 0*1 = 32+8+2 = 42 ✓

Konwersja BIN na HEX

Grupujemy bity po 4 (od prawej) i zamieniamy na cyfry HEX:
1010 1100 0011(2)
 A    C    3
= AC3(16)

Tabela konwersji (4 bity -> HEX):
0000=0  0001=1  0010=2  0011=3
0100=4  0101=5  0110=6  0111=7
1000=8  1001=9  1010=A  1011=B
1100=C  1101=D  1110=E  1111=F

Implementacja w Pythonie

def dec_na_bin(n):
    """Konwersja dziesietna na dwojkowa"""
    if n == 0:
        return "0"
    wynik = ""
    while n > 0:
        wynik = str(n % 2) + wynik
        n //= 2
    return wynik

def dec_na_hex(n):
    """Konwersja dziesietna na szesnastkowa"""
    if n == 0:
        return "0"
    hex_cyfry = "0123456789ABCDEF"
    wynik = ""
    while n > 0:
        wynik = hex_cyfry[n % 16] + wynik
        n //= 16
    return wynik

def dowolna_na_dec(tekst, baza):
    """Konwersja z dowolnej bazy na dziesietna"""
    cyfry = "0123456789ABCDEF"
    wynik = 0
    for znak in tekst.upper():
        wynik = wynik * baza + cyfry.index(znak)
    return wynik

# Testy
print(f"42 DEC = {dec_na_bin(42)} BIN")        # 101010
print(f"42 DEC = {dec_na_hex(42)} HEX")        # 2A
print(f"101010 BIN = {dowolna_na_dec('101010', 2)} DEC")  # 42
print(f"2A HEX = {dowolna_na_dec('2A', 16)} DEC")        # 42

# Wbudowane funkcje Pythona:
print(bin(42))     # 0b101010
print(oct(42))     # 0o52
print(hex(42))     # 0x2a
print(int('101010', 2))   # 42
print(int('2A', 16))      # 42

Algorytm Euklidesa - NWD

Najwiekszy Wspolny Dzielnik (NWD) dwoch liczb to najwieksza liczba, ktora dzieli obie bez reszty. Algorytm Euklidesa (ok. 300 p.n.e.) to jeden z najstarszych znanych algorytmow i wciaz jeden z najelegantszych.

# NWD - wersja iteracyjna
def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# NWD - wersja rekurencyjna
def nwd_rek(a, b):
    if b == 0:
        return a
    return nwd_rek(b, a % b)

# Najmniejsza Wspolna Wielokrotnosc
def nww(a, b):
    return a * b // nwd(a, b)

# Testy
print(f"NWD(48, 18) = {nwd(48, 18)}")   # 6
print(f"NWD(100, 75) = {nwd(100, 75)}") # 25
print(f"NWW(12, 8) = {nww(12, 8)}")     # 24

# Rozszerzony algorytm Euklidesa
# Znajduje x, y takie ze: a*x + b*y = NWD(a,b)
def nwd_rozszerzony(a, b):
    if b == 0:
        return a, 1, 0
    d, x, y = nwd_rozszerzony(b, a % b)
    return d, y, x - (a // b) * y

d, x, y = nwd_rozszerzony(48, 18)
print(f"NWD(48,18) = {d}, 48*{x} + 18*{y} = {48*x + 18*y}")

Badanie pierwszosci liczb

Liczba pierwsza to liczba naturalna wieksza od 1, ktora dzieli sie tylko przez 1 i przez siebie. Badanie pierwszosci ma ogromne znaczenie w kryptografii (np. RSA).

# Metoda naiwna - O(n)
def czy_pierwsza_naiwna(n):
    if n < 2:
        return False
    for i in range(2, n):
        if n % i == 0:
            return False
    return True

# Metoda zoptymalizowana - O(sqrt(n))
def czy_pierwsza(n):
    if n < 2:
        return False
    if n < 4:
        return True
    if n % 2 == 0 or n % 3 == 0:
        return False
    i = 5
    while i * i <= n:
        if n % i == 0 or n % (i + 2) == 0:
            return False
        i += 6
    return True

# Sito Eratostenesa - znajdz WSZYSTKIE liczby pierwsze do n
def sito_eratostenesa(n):
    jest_pierwsza = [True] * (n + 1)
    jest_pierwsza[0] = jest_pierwsza[1] = False

    i = 2
    while i * i <= n:
        if jest_pierwsza[i]:
            for j in range(i * i, n + 1, i):
                jest_pierwsza[j] = False
        i += 1

    return [i for i in range(n + 1) if jest_pierwsza[i]]

# Testy
print(f"17 pierwsza? {czy_pierwsza(17)}")    # True
print(f"21 pierwsza? {czy_pierwsza(21)}")    # False
print(f"Pierwsze do 50: {sito_eratostenesa(50)}")
# [2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47]

# Rozklad na czynniki pierwsze
def rozklad(n):
    czynniki = []
    d = 2
    while d * d <= n:
        while n % d == 0:
            czynniki.append(d)
            n //= d
        d += 1
    if n > 1:
        czynniki.append(n)
    return czynniki

print(f"Rozklad 360 = {rozklad(360)}")  # [2, 2, 2, 3, 3, 5]