Laczenie algorytmow na tekstach z algorytmami sortowania w projektach programistycznych
ð Podstawa programowa: II.1+I.2b-cSzyfr Cezara to jeden z najprostszych szyfrow podstawieniowych. Polega na przesunieciu kazdej litery w tekscie o stala liczbe pozycji w alfabecie.
# Szyfrowanie szyfrem Cezara
def szyfruj_cezar(tekst, przesuniecie):
wynik = ""
for znak in tekst:
if 'a' <= znak <= 'z':
nowy = chr((ord(znak) - ord('a') + przesuniecie) % 26 + ord('a'))
wynik += nowy
elif 'A' <= znak <= 'Z':
nowy = chr((ord(znak) - ord('A') + przesuniecie) % 26 + ord('A'))
wynik += nowy
else:
wynik += znak
return wynik
# Deszyfrowanie to szyfrowanie z przeciwnym przesunieciem
def deszyfruj_cezar(tekst, przesuniecie):
return szyfruj_cezar(tekst, -przesuniecie)Sortowanie babelkowe (ang. bubble sort) polega na wielokrotnym porownywaniu par sasiadujacych elementow i zamianie ich miejscami, jesli sa w zlej kolejnosci.
# 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 listaW praktyce programistycznej rzadko uzywamy algorytmow w izolacji. Prawdziwe projekty lacza wiele algorytmow w jedna calosci. Na dzisiejszej lekcji polaczymy operacje na tekstach z sortowaniem.
Jednym z waznych algorytmow tekstowych jest analiza czestotliwosci wystepowania znakow. Mozna ja polaczyc z sortowaniem, aby znalezc najczesciej lub najrzadziej wystepujace znaki.
# Analiza czestotliwosci znakow + sortowanie
def analiza_czestotliwosci(tekst):
# Zliczanie znakow
czestotliwosc = {}
for znak in tekst.lower():
if znak.isalpha():
czestotliwosc[znak] = czestotliwosc.get(znak, 0) + 1
# Zamiana na liste par (znak, liczba)
pary = list(czestotliwosc.items())
# Sortowanie babelkowe po czestotliwosci (malejaco)
n = len(pary)
for i in range(n - 1):
for j in range(n - 1 - i):
if pary[j][1] < pary[j + 1][1]:
pary[j], pary[j + 1] = pary[j + 1], pary[j]
return pary
tekst = "programowanie algorytmow tekstowych i sortowania"
wynik = analiza_czestotliwosci(tekst)
for znak, liczba in wynik:
print(f"'{znak}': {liczba} wystapien")# Sortowanie slow w zdaniu alfabetycznie
def sortuj_slowa(tekst):
slowa = tekst.split()
# Sortowanie babelkowe slow
n = len(slowa)
for i in range(n - 1):
for j in range(n - 1 - i):
if slowa[j].lower() > slowa[j + 1].lower():
slowa[j], slowa[j + 1] = slowa[j + 1], slowa[j]
return " ".join(slowa)
zdanie = "Python jest jezykiem programowania"
print(sortuj_slowa(zdanie))
# Wynik: jest jezykiem programowania PythonAnaliza czestotliwosci znakow pozwala zlamac szyfr Cezara bez znajomosci klucza. W jezyku polskim najczesciej wystepuje litera "a", wiec mozna znalezc przesuniecie:
def zlam_cezara(szyfrogramm):
# Znajdz najczesciej wystepujaca litere
czest = analiza_czestotliwosci(szyfrogramm)
if not czest:
return szyfrogramm
najczestsza = czest[0][0] # najczesciej wystepujaca litera
# Zakladamy, ze odpowiada literze 'a'
przesuniecie = (ord(najczestsza) - ord('a')) % 26
return deszyfruj_cezar(szyfrogramm, przesuniecie)Napisz program, ktory: (a) przyjmuje liste 5 wiadomosci od uzytkownika, (b) szyfruje kazda szyfrem Cezara z przesunieciem 3, (c) sortuje zaszyfrowane wiadomosci alfabetycznie, (d) wypisuje posortowana liste.
def szyfruj_cezar(tekst, przesuniecie):
wynik = ""
for znak in tekst:
if 'a' <= znak <= 'z':
wynik += chr((ord(znak) - ord('a') + przesuniecie) % 26 + ord('a'))
elif 'A' <= znak <= 'Z':
wynik += chr((ord(znak) - ord('A') + przesuniecie) % 26 + ord('A'))
else:
wynik += znak
return wynik
def sortuj_babelkowo(lista):
n = len(lista)
for i in range(n - 1):
for j in range(n - 1 - i):
if lista[j].lower() > lista[j + 1].lower():
lista[j], lista[j + 1] = lista[j + 1], lista[j]
return lista
# Glowny program
wiadomosci = []
for i in range(5):
w = input(f"Podaj wiadomosc {i+1}: ")
wiadomosci.append(w)
zaszyfrowane = [szyfruj_cezar(w, 3) for w in wiadomosci]
posortowane = sortuj_babelkowo(zaszyfrowane)
print("\nPosortowane zaszyfrowane wiadomosci:")
for w in posortowane:
print(f" {w}")Napisz program, ktory wczytuje tekst od uzytkownika, zlicza wystapienia kazdej litery, a nastepnie sortuje wyniki malejaco wedlug czestotliwosci. Wyswietl wynik w postaci rankingu.
def ranking_liter(tekst):
# Zliczanie
czestotliwosc = {}
for znak in tekst.lower():
if znak.isalpha():
czestotliwosc[znak] = czestotliwosc.get(znak, 0) + 1
# Konwersja do listy
pary = list(czestotliwosc.items())
# Sortowanie babelkowe malejaco po wartosci
n = len(pary)
for i in range(n - 1):
for j in range(n - 1 - i):
if pary[j][1] < pary[j + 1][1]:
pary[j], pary[j + 1] = pary[j + 1], pary[j]
return pary
tekst = input("Podaj tekst do analizy: ")
ranking = ranking_liter(tekst)
print("\n=== RANKING CZESTOTLIWOSCI LITER ===")
for pozycja, (znak, liczba) in enumerate(ranking, 1):
pasek = "#" * liczba
print(f"{pozycja:>2}. '{znak}': {liczba:>3} {pasek}")Napisz program, ktory wczytuje zdanie, dzieli je na slowa, a nastepnie sortuje slowa wedlug dlugosci (od najkrotszego do najdluzszego). Uzyj sortowania babelkowego.
def sortuj_wg_dlugosci(zdanie):
slowa = zdanie.split()
n = len(slowa)
for i in range(n - 1):
for j in range(n - 1 - i):
if len(slowa[j]) > len(slowa[j + 1]):
slowa[j], slowa[j + 1] = slowa[j + 1], slowa[j]
return slowa
zdanie = input("Podaj zdanie: ")
posortowane = sortuj_wg_dlugosci(zdanie)
print("\nSlowa posortowane wg dlugosci:")
for slowo in posortowane:
print(f" '{slowo}' ({len(slowo)} znakow)")Napisz program, ktory otrzymuje zaszyfrowany tekst (szyfr Cezara z nieznanym przesunieciem). Program powinien: (a) wygenerowac wszystkie 26 mozliwych odszyfrowanych wersji, (b) posortowac je alfabetycznie, (c) wskazac najbardziej prawdopodobna wersje na podstawie analizy czestotliwosci.
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
def ocena_tekstu(tekst):
"""Liczy ile popularnych polskich liter jest w tekscie"""
popularne = "aioeznrswtcypkdml"
punkty = 0
for z in tekst.lower():
if z in popularne:
punkty += 1
return punkty
szyfr = input("Podaj zaszyfrowany tekst: ")
wersje = []
for klucz in range(26):
odszyfrowany = szyfruj_cezar(szyfr, -klucz)
punkty = ocena_tekstu(odszyfrowany)
wersje.append((klucz, odszyfrowany, punkty))
# Sortowanie babelkowe wg punktow (malejaco)
n = len(wersje)
for i in range(n - 1):
for j in range(n - 1 - i):
if wersje[j][2] < wersje[j + 1][2]:
wersje[j], wersje[j + 1] = wersje[j + 1], wersje[j]
print("\n=== WYNIKI (od najbardziej prawdopodobnego) ===")
for klucz, tekst, pkt in wersje[:5]:
print(f"Klucz {klucz:>2}: {tekst} (punkty: {pkt})")