Powtorka z algorytmow tekstowych, sortowania i ciagow liczbowych
ð Podstawa programowa: I.2b-dNa lekcjach w klasach I i II poznawalismy rozne rodzaje algorytmow. Dzis przypomnimy sobie najwazniejsze z nich: algorytmy na tekstach, algorytmy sortowania oraz algorytmy na ciagach liczbowych.
Szyfr Cezara to jeden z najprostszych szyfrow podstawieniowych. Kazda litera tekstu jawnego jest zastepowana litera znajdujaca sie o stala liczbe pozycji dalej w alfabecie.
def szyfr_cezara(tekst, klucz):
wynik = ""
for znak in tekst:
if znak.isalpha():
baza = ord('A') if znak.isupper() else ord('a')
wynik += chr((ord(znak) - baza + klucz) % 26 + baza)
else:
wynik += znak
return wynik
# Szyfrowanie: przesuniecie o 3
print(szyfr_cezara("HELLO", 3)) # KHOOR
# Deszyfrowanie: przesuniecie o -3
print(szyfr_cezara("KHOOR", -3)) # HELLOWyszukiwanie wzorca w tekscie (pattern matching) polega na znalezieniu wszystkich wystapien krotszego ciagu znakow (wzorca) w dluzszym tekscie.
def wyszukaj_wzorzec(tekst, wzorzec):
pozycje = []
n = len(tekst)
m = len(wzorzec)
for i in range(n - m + 1):
if tekst[i:i+m] == wzorzec:
pozycje.append(i)
return pozycje
print(wyszukaj_wzorzec("ababcababd", "abab")) # [0, 5]Przypomnienie najwazniejszych metod sortowania:
# Sortowanie babelkowe
def bubble_sort(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 insertion_sort(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 listaCiag Fibonacciego: 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... Kazdy kolejny element jest suma dwoch poprzednich.
def fibonacci(n):
if n <= 0:
return 0
elif n == 1:
return 1
a, b = 0, 1
for _ in range(2, n + 1):
a, b = b, a + b
return b
# Wypisz pierwsze 10 wyrazow
for i in range(10):
print(fibonacci(i), end=" ") # 0 1 1 2 3 5 8 13 21 34Napisz program, ktory pobiera od uzytkownika tekst i klucz (liczbe calkowita), a nastepnie szyfruje tekst szyfrem Cezara. Program powinien rowniez oferowac mozliwosc deszyfrowania.
def szyfr_cezara(tekst, klucz):
wynik = ""
for znak in tekst:
if znak.isalpha():
baza = ord('A') if znak.isupper() else ord('a')
wynik += chr((ord(znak) - baza + klucz) % 26 + baza)
else:
wynik += znak
return wynik
tekst = input("Podaj tekst: ")
klucz = int(input("Podaj klucz: "))
wybor = input("(S)zyfruj czy (D)eszyfruj? ").upper()
if wybor == "S":
print("Zaszyfrowany:", szyfr_cezara(tekst, klucz))
else:
print("Odszyfrowany:", szyfr_cezara(tekst, -klucz))Zaimplementuj trzy algorytmy sortowania (babelkowe, przez wstawianie, przez wybieranie). Zmierz czas sortowania losowej tablicy 1000 elementow kazdym algorytmem. Ktory jest najszybszy w praktyce? Czy wynik jest zgodny z teoria?
import time
import random
def bubble_sort(lst):
lst = lst[:]
n = len(lst)
for i in range(n-1):
for j in range(n-1-i):
if lst[j] > lst[j+1]:
lst[j], lst[j+1] = lst[j+1], lst[j]
return lst
def insertion_sort(lst):
lst = lst[:]
for i in range(1, len(lst)):
k = lst[i]
j = i - 1
while j >= 0 and lst[j] > k:
lst[j+1] = lst[j]
j -= 1
lst[j+1] = k
return lst
def selection_sort(lst):
lst = lst[:]
n = len(lst)
for i in range(n):
min_idx = i
for j in range(i+1, n):
if lst[j] < lst[min_idx]:
min_idx = j
lst[i], lst[min_idx] = lst[min_idx], lst[i]
return lst
dane = [random.randint(1, 10000) for _ in range(1000)]
for nazwa, funkcja in [("Babelkowe", bubble_sort),
("Wstawianie", insertion_sort),
("Wybieranie", selection_sort)]:
start = time.time()
funkcja(dane)
czas = time.time() - start
print(f"{nazwa}: {czas:.4f} s")Zaimplementuj ciag Fibonacciego w trzech wersjach: iteracyjnej, rekurencyjnej i rekurencyjnej z memoizacja. Porownaj czas obliczenia F(30) i F(35) kazdym sposobem.
import time
from functools import lru_cache
def fib_iter(n):
if n <= 1: return n
a, b = 0, 1
for _ in range(2, n+1):
a, b = b, a+b
return b
def fib_rek(n):
if n <= 1: return n
return fib_rek(n-1) + fib_rek(n-2)
@lru_cache(maxsize=None)
def fib_memo(n):
if n <= 1: return n
return fib_memo(n-1) + fib_memo(n-2)
for n in [30, 35]:
print(f"\n--- F({n}) ---")
for nazwa, f in [("Iteracyjna", fib_iter),
("Rekurencyjna", fib_rek),
("Memoizacja", fib_memo)]:
start = time.time()
wynik = f(n)
czas = time.time() - start
print(f"{nazwa}: {wynik} ({czas:.4f} s)")Napisz program, ktory bez znajomosci klucza probuje zlamac szyfr Cezara metoda brute-force. Wypisz wynik deszyfrowania dla wszystkich 25 mozliwych kluczy. Dodaj analiza czestotliwosci liter (najczestsza litera w polskim to 'A', w angielskim 'E').
def deszyfruj(tekst, klucz):
wynik = ""
for z in tekst:
if z.isalpha():
baza = ord('A') if z.isupper() else ord('a')
wynik += chr((ord(z) - baza - klucz) % 26 + baza)
else:
wynik += z
return wynik
def analiza_czestotliwosci(tekst):
freq = {}
for z in tekst.upper():
if z.isalpha():
freq[z] = freq.get(z, 0) + 1
if not freq:
return None
return max(freq, key=freq.get)
szyfr = input("Podaj zaszyfrowany tekst: ")
print("\n--- Brute force (wszystkie klucze) ---")
for k in range(1, 26):
print(f"Klucz {k:2d}: {deszyfruj(szyfr, k)}")
# Analiza czestotliwosci
naj = analiza_czestotliwosci(szyfr)
if naj:
klucz_ang = (ord(naj) - ord('E')) % 26
klucz_pol = (ord(naj) - ord('A')) % 26
print(f"\nNajczestsza litera: {naj}")
print(f"Prawdopodobny klucz (ang): {klucz_ang} -> {deszyfruj(szyfr, klucz_ang)}")
print(f"Prawdopodobny klucz (pol): {klucz_pol} -> {deszyfruj(szyfr, klucz_pol)}")