Lekcja 29 - Powtorzenie wiadomosci

📚

Teoria - podsumowanie

▼

1. Myslenie komputacyjne

Cztery filary myslenia komputacyjnego:

Dekompozycja - rozbijanie problemu na mniejsze czesci
Rozpoznawanie wzorcow - znajdowanie podobienst i powtarzalnosci
Abstrakcja - skupienie na istotnych elementach, pominiecie szczegolow
Algorytmizacja - tworzenie krokowego rozwiazania problemu

2. Systemy liczbowe

                    Kluczowe systemy:

                    Binarny (dwojkowy) - podstawa 2 (cyfry: 0, 1) - uzywany przez komputery

                    Osemkowy (oktalny) - podstawa 8 (cyfry: 0-7)

                    Dziesietny (decymalny) - podstawa 10 (cyfry: 0-9) - uzywany na co dzien

                    Szesnastkowy (heksadecymalny) - podstawa 16 (cyfry: 0-9, A-F) - kolory, adresy pamięci

# Konwersje w Pythonie
liczba = 42
print(f"Dziesietnie: {liczba}")
print(f"Binarnie:    {bin(liczba)}")     # 0b101010
print(f"Osemkowo:    {oct(liczba)}")     # 0o52
print(f"Szesnastkowo:{hex(liczba)}")     # 0x2a

# Konwersja reczna: dziesietny -> binarny
def dec_to_bin(n):
    if n == 0:
        return "0"
    wynik = ""
    while n > 0:
        wynik = str(n % 2) + wynik
        n = n // 2
    return wynik

3. Algorytmy na liczbach

NWD - Algorytm Euklidesa

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

# NWW obliczamy przez NWD
def nww(a, b):
    return a * b // nwd(a, b)

Sprawdzanie pierwszosci

import math

def czy_pierwsza(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

Ciag Fibonacciego (iteracyjnie)

def fibonacci(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for i in range(2, n + 1):
        a, b = b, a + b
    return b

4. Algorytmy na tekstach

Szyfr Cezara

def szyfruj_cezar(tekst, klucz):
    wynik = ""
    for z in tekst:
        if 'a' <= z <= 'z':
            wynik += chr((ord(z) - ord('a') + klucz) % 26 + ord('a'))
        elif 'A' <= z <= 'Z':
            wynik += chr((ord(z) - ord('A') + klucz) % 26 + ord('A'))
        else:
            wynik += z
    return wynik

Wyszukiwanie wzorca (naiwne)

def szukaj_wzorca(tekst, wzorzec):
    pozycje = []
    for i in range(len(tekst) - len(wzorzec) + 1):
        if tekst[i:i+len(wzorzec)] == wzorzec:
            pozycje.append(i)
    return pozycje

5. Algorytmy sortowania

Sortowanie babelkowe

def sortowanie_babelkowe(lista):
    n = len(lista)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if lista[j] > lista[j + 1]:
                lista[j], lista[j + 1] = lista[j + 1], lista[j]
    return lista

Sortowanie przez wstawianie

def sortowanie_przez_wstawianie(lista):
    for i in range(1, len(lista)):
        klucz = lista[i]
        j = i - 1
        while j >= 0 and lista[j] > klucz:
            lista[j + 1] = lista[j]
            j -= 1
        lista[j + 1] = klucz
    return lista

6. Podstawy Pythona - sciagawka

# Zmienne i typy danych
x = 10          # int
y = 3.14        # float
tekst = "abc"   # str
lista = [1,2,3] # list
prawda = True   # bool

# Instrukcja warunkowa
if x > 0:
    print("Dodatnia")
elif x == 0:
    print("Zero")
else:
    print("Ujemna")

# Petle
for i in range(10):     # petla for (0..9)
    print(i)

while x > 0:            # petla while
    x -= 1

# Funkcje
def suma(a, b):
    return a + b

# Lista - operacje
lista.append(4)         # dodaj element
lista.pop()             # usun ostatni
len(lista)              # dlugosc
lista[0]                # pierwszy element
lista[-1]               # ostatni element
lista[1:3]              # wycinek (indeks 1 i 2)

                    Porownanie zlozonosci algorytmow:

                    Sortowanie babelkowe: O(n^2) - wolne dla duzych danych

                    Sortowanie przez wstawianie: O(n^2), ale szybsze dla prawie posortowanych

                    NWD Euklidesa: O(log n) - bardzo szybki

                    Fibonacci iteracyjny: O(n) - szybki

                    Fibonacci rekurencyjny: O(2^n) - bardzo wolny!

                    Sprawdzanie pierwszosci: O(sqrt(n)) - efektywny

✏️

Zadania - powtorzenie

▼

Latwe

Zadanie 1: Konwersje systemow liczbowych

Napisz program, ktory wczytuje liczbe dziesietna od uzytkownika i wyswietla ja w systemie binarnym, osemkowym i szesnastkowym. Zaimplementuj konwersje na binarny samodzielnie (bez uzycia bin()).

Pokaz rozwiazanie

def na_binarny(n):
    if n == 0:
        return "0"
    wynik = ""
    liczba = abs(n)
    while liczba > 0:
        wynik = str(liczba % 2) + wynik
        liczba //= 2
    return ("-" if n < 0 else "") + wynik

def na_osemkowy(n):
    if n == 0:
        return "0"
    wynik = ""
    liczba = abs(n)
    while liczba > 0:
        wynik = str(liczba % 8) + wynik
        liczba //= 8
    return ("-" if n < 0 else "") + wynik

def na_szesnastkowy(n):
    if n == 0:
        return "0"
    hex_cyfry = "0123456789ABCDEF"
    wynik = ""
    liczba = abs(n)
    while liczba > 0:
        wynik = hex_cyfry[liczba % 16] + wynik
        liczba //= 16
    return ("-" if n < 0 else "") + wynik

n = int(input("Podaj liczbe dziesietna: "))
print(f"Dziesietnie:   {n}")
print(f"Binarnie:      {na_binarny(n)}")
print(f"Osemkowo:      {na_osemkowy(n)}")
print(f"Szesnastkowo:  {na_szesnastkowy(n)}")

# Weryfikacja z wbudowanymi funkcjami:
print(f"\nSprawdzenie: bin={bin(n)}, oct={oct(n)}, hex={hex(n)}")

Srednie

Zadanie 2: Wielofunkcyjny kalkulator algorytmiczny

Napisz program z menu, ktory oferuje nastepujace funkcje: (1) NWD i NWW dwoch liczb, (2) sprawdzanie pierwszosci, (3) n-ty wyraz ciagu Fibonacciego, (4) szyfr Cezara (szyfrowanie/deszyfrowanie). Uzytkownik wybiera opcje z menu.

Pokaz rozwiazanie

import math

def nwd(a, b):
    while b != 0:
        a, b = b, a % b
    return a

def nww(a, b):
    return a * b // nwd(a, b)

def czy_pierwsza(n):
    if n < 2:
        return False
    for i in range(2, int(math.sqrt(n)) + 1):
        if n % i == 0:
            return False
    return True

def fibonacci(n):
    if n <= 1:
        return n
    a, b = 0, 1
    for i in range(2, n + 1):
        a, b = b, a + b
    return b

def szyfruj_cezar(tekst, klucz):
    wynik = ""
    for z in tekst:
        if 'a' <= z <= 'z':
            wynik += chr((ord(z) - ord('a') + klucz) % 26 + ord('a'))
        elif 'A' <= z <= 'Z':
            wynik += chr((ord(z) - ord('A') + klucz) % 26 + ord('A'))
        else:
            wynik += z
    return wynik

while True:
    print("\n=== KALKULATOR ALGORYTMICZNY ===")
    print("1. NWD i NWW")
    print("2. Sprawdz pierwszosc")
    print("3. Ciag Fibonacciego")
    print("4. Szyfr Cezara")
    print("0. Wyjscie")

    wybor = input("\nWybierz opcje: ")

    if wybor == "1":
        a = int(input("Podaj a: "))
        b = int(input("Podaj b: "))
        print(f"NWD({a}, {b}) = {nwd(a, b)}")
        print(f"NWW({a}, {b}) = {nww(a, b)}")

    elif wybor == "2":
        n = int(input("Podaj liczbe: "))
        if czy_pierwsza(n):
            print(f"{n} jest liczba pierwsza!")
        else:
            print(f"{n} NIE jest liczba pierwsza.")

    elif wybor == "3":
        n = int(input("Ktory wyraz ciagu? n = "))
        print(f"F({n}) = {fibonacci(n)}")

    elif wybor == "4":
        tekst = input("Podaj tekst: ")
        klucz = int(input("Podaj klucz (przesuniecie): "))
        tryb = input("(s)zyfruj czy (d)eszyfruj? ")
        if tryb == 'd':
            klucz = -klucz
        print(f"Wynik: {szyfruj_cezar(tekst, klucz)}")

    elif wybor == "0":
        print("Do widzenia!")
        break
    else:
        print("Nieznana opcja!")

Srednie

Zadanie 3: Sortowanie i analiza danych

Napisz program, ktory: (a) generuje losowa liste 20 liczb z zakresu 1-100, (b) wyswietla liste przed sortowaniem, (c) sortuje ja babelkowo i przez wstawianie (osobno), (d) liczy liczbe zamian/porownan dla kazdej metody, (e) wyswietla wyniki porownania.

Pokaz rozwiazanie

import random

def babelkowe_z_licznikiem(lista):
    tab = lista.copy()
    porownania = 0
    zamiany = 0
    n = len(tab)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            porownania += 1
            if tab[j] > tab[j + 1]:
                tab[j], tab[j + 1] = tab[j + 1], tab[j]
                zamiany += 1
    return tab, porownania, zamiany

def wstawianie_z_licznikiem(lista):
    tab = lista.copy()
    porownania = 0
    przesuniecia = 0
    for i in range(1, len(tab)):
        klucz = tab[i]
        j = i - 1
        while j >= 0:
            porownania += 1
            if tab[j] > klucz:
                tab[j + 1] = tab[j]
                przesuniecia += 1
                j -= 1
            else:
                break
        tab[j + 1] = klucz
    return tab, porownania, przesuniecia

# Generuj dane
dane = [random.randint(1, 100) for _ in range(20)]
print(f"Dane wejsciowe: {dane}\n")

# Sortowanie babelkowe
wynik_b, por_b, zam_b = babelkowe_z_licznikiem(dane)
print(f"Babelkowe:    {wynik_b}")
print(f"  Porownania: {por_b}, Zamiany: {zam_b}")

# Sortowanie przez wstawianie
wynik_w, por_w, prz_w = wstawianie_z_licznikiem(dane)
print(f"\nWstawianie:   {wynik_w}")
print(f"  Porownania: {por_w}, Przesuniecia: {prz_w}")

# Porownanie
print(f"\n=== POROWNANIE ===")
print(f"Babelkowe:   {por_b} porownan, {zam_b} zamian")
print(f"Wstawianie:  {por_w} porownan, {prz_w} przesuniec")
if por_b > por_w:
    print("Wstawianie bylo efektywniejsze!")
else:
    print("Babelkowe bylo efektywniejsze (lub rowne)!")

Trudne

Zadanie 4: Projekt - analizator tekstu

Napisz rozbudowany analizator tekstu w Pythonie, ktory: (a) wczytuje tekst od uzytkownika, (b) liczy: znaki, slowa, zdania, (c) wyznacza najczesciej wystepujaca litere, (d) sortuje slowa alfabetycznie, (e) szyfryje tekst szyfrem Cezara, (f) wyswietla pelen raport.

Pokaz rozwiazanie

def analizuj_tekst(tekst):
    print("=" * 50)
    print("       ANALIZATOR TEKSTU v1.0")
    print("=" * 50)

    # 1. Statystyki podstawowe
    znaki = len(tekst)
    znaki_bez_spacji = len(tekst.replace(" ", ""))
    slowa = tekst.split()
    liczba_slow = len(slowa)
    zdania = tekst.count('.') + tekst.count('!') + tekst.count('?')
    if zdania == 0:
        zdania = 1

    print(f"\n--- Statystyki ---")
    print(f"Znakow (ze spacjami):  {znaki}")
    print(f"Znakow (bez spacji):   {znaki_bez_spacji}")
    print(f"Slow:                  {liczba_slow}")
    print(f"Zdan:                  {zdania}")
    print(f"Sr. dlugosc slowa:     {znaki_bez_spacji/max(liczba_slow,1):.1f}")

    # 2. Czestotliwosc liter
    czest = {}
    for z in tekst.lower():
        if z.isalpha():
            czest[z] = czest.get(z, 0) + 1

    pary = list(czest.items())
    # Sortowanie babelkowe malejaco
    for i in range(len(pary) - 1):
        for j in range(len(pary) - 1 - i):
            if pary[j][1] < pary[j+1][1]:
                pary[j], pary[j+1] = pary[j+1], pary[j]

    print(f"\n--- Top 5 najczestszych liter ---")
    for i, (litera, ile) in enumerate(pary[:5]):
        procent = ile / max(znaki_bez_spacji, 1) * 100
        pasek = "#" * ile
        print(f"  {i+1}. '{litera}': {ile} ({procent:.1f}%) {pasek}")

    # 3. Sortowanie slow
    slowa_sort = slowa.copy()
    n = len(slowa_sort)
    for i in range(n - 1):
        for j in range(n - 1 - i):
            if slowa_sort[j].lower() > slowa_sort[j+1].lower():
                slowa_sort[j], slowa_sort[j+1] = slowa_sort[j+1], slowa_sort[j]

    print(f"\n--- Slowa posortowane ---")
    print(", ".join(slowa_sort))

    # 4. Szyfrowanie
    klucz = 3
    zaszyfrowany = ""
    for z in tekst:
        if 'a' <= z <= 'z':
            zaszyfrowany += chr((ord(z)-ord('a')+klucz)%26+ord('a'))
        elif 'A' <= z <= 'Z':
            zaszyfrowany += chr((ord(z)-ord('A')+klucz)%26+ord('A'))
        else:
            zaszyfrowany += z

    print(f"\n--- Szyfr Cezara (klucz={klucz}) ---")
    print(f"Oryginal:     {tekst}")
    print(f"Zaszyfrowany: {zaszyfrowany}")

    print("\n" + "=" * 50)

# Program glowny
tekst = input("Podaj tekst do analizy:\n> ")
analizuj_tekst(tekst)

🎥

Materialy wideo

▼

1. Wprowadzenie do algorytmów

Programowanie Ilona Bednarska

Przykłady Algorytmów

V LO Olsztyn

🎧

Podcasty

▼

✔️

Quiz - sprawdz sie!

▼

📜

Podstawa programowa

▼

Lekcja 29: Powtorzenie wiadomosci - algorytmy i programowanie

Teoria - podsumowanie

1. Myslenie komputacyjne

2. Systemy liczbowe

3. Algorytmy na liczbach

NWD - Algorytm Euklidesa

Sprawdzanie pierwszosci

Ciag Fibonacciego (iteracyjnie)

4. Algorytmy na tekstach

Szyfr Cezara

Wyszukiwanie wzorca (naiwne)

5. Algorytmy sortowania

Sortowanie babelkowe

Sortowanie przez wstawianie

6. Podstawy Pythona - sciagawka

Zadania - powtorzenie

Zadanie 1: Konwersje systemow liczbowych

Zadanie 2: Wielofunkcyjny kalkulator algorytmiczny

Zadanie 3: Sortowanie i analiza danych

Zadanie 4: Projekt - analizator tekstu

Materialy wideo

Podcasty

Porozmawiajmy o IT - Jak zaczac programowac?

Just Join IT - Sciezki kariery programisty

Quiz - sprawdz sie!

Pytanie 1: Algorytm to:

Pytanie 2: Zlozonosc obliczeniowa O(n) oznacza:

Pytanie 3: Ktore zdanie o Pythonie jest PRAWDZIWE?

Podstawa programowa