Prezentacja multimedialna

Polecenie 1

Zapoznaj się z prezentacją przedstawiającą użycie stosu zaimplementowanego przy użyciu listy jednokierunkowej niecyklicznej w realizacji algorytmu konwersji zapisu infiksowego na odwrotną notację polskąD8zD8PhYJodwrotną notację polską. Algorytm zapisany w pseudokodzie znajdziesz w multimedium materiału Dynamiczne struktury danychDINsybcX5Dynamiczne struktury danych.

Specyfikacja problemu:

Dane:

wyrazenie – łańcuch znaków; zapis infiksowy wyrażenia arytmetycznego, w którym znak spacji występuje przed i po każdym operatorze

Wynik:

wyrażenie infiksowe wypisane w odwrotnej notacji polskiej

ReOuOtTJWFy5S1

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY 3.0.

Polecenie 2

Na podstawie informacji z sekcji „Przeczytaj” oraz powyższej prezentacji napisz i uruchom program konwertujący podane wyrażenie infiksowe na postfiksowe. W programie użyj stosu zaimplementowanego za pomocą omówionej w sekcji „Przeczytaj” klasy deque z modułu collections, a także funkcji czy_operator() oraz priorytet() wykorzystujących operator in.

Działanie programu przetestuj dla następującego wyrażenia: (31 + 4) * 7.

Specyfikacja problemu:

Dane:

wyrazenie – łańcuch znaków; zapis infiksowy wyrażenia arytmetycznego, w którym znak spacji występuje przed i po każdym operatorze

Wynik:

wyrażenie infiksowe wypisane w odwrotnej notacji polskiej.

Przykładowy wynik działania programu:

Wyrażenie infiksowe: (31 + 4) * 7
Wyrażenie postfiksowe: 31  4 +  7 *

R1A9kmLl87dM9

Linia 1. from collections import deque. Linia 3. def czy podkreślnik operator otwórz nawias okrągły znak zamknij nawias okrągły dwukropek. Linia 4. return znak in cudzysłów otwórz nawias okrągły zamknij nawias okrągły plus minus asterysk prawy ukośnik procent kareta cudzysłów. Linia 6. def priorytet otwórz nawias okrągły znak zamknij nawias okrągły dwukropek. Linia 7. if znak znak równości znak równości cudzysłów otwórz nawias okrągły cudzysłów dwukropek return 0. Linia 8. elif znak in cudzysłów plus minus cudzysłów dwukropek return 1. Linia 9. elif znak in cudzysłów asterysk prawy ukośnik procent cudzysłów dwukropek return 2. Linia 10. elif znak znak równości znak równości cudzysłów kareta cudzysłów dwukropek return 3. Linia 11. else dwukropek return minus 1. Linia 13. def konwertuj podkreślnik do podkreślnik onp otwórz nawias okrągły wyrazenie zamknij nawias okrągły dwukropek. Linia 14. stos znak równości deque otwórz nawias okrągły zamknij nawias okrągły. Linia 15. wynik znak równości cudzysłów cudzysłów. Linia 17. for znak in wyrazenie dwukropek. Linia 18. if znak znak równości znak równości cudzysłów cudzysłów or not czy podkreślnik operator otwórz nawias okrągły znak zamknij nawias okrągły dwukropek. Linia 19. wynik plus znak równości znak. Linia 20. elif znak znak równości znak równości cudzysłów otwórz nawias okrągły cudzysłów dwukropek. Linia 21. stos kropka append otwórz nawias okrągły znak zamknij nawias okrągły. Linia 22. elif znak znak równości znak równości cudzysłów zamknij nawias okrągły cudzysłów dwukropek. Linia 23. while stos otwórz nawias kwadratowy minus 1 zamknij nawias kwadratowy wykrzyknik znak równości cudzysłów otwórz nawias okrągły cudzysłów dwukropek. Linia 24. wynik plus znak równości cudzysłów cudzysłów plus stos kropka pop otwórz nawias okrągły zamknij nawias okrągły. Linia 25. stos kropka pop otwórz nawias okrągły zamknij nawias okrągły. Linia 26. else dwukropek. Linia 27. while stos and priorytet otwórz nawias okrągły stos otwórz nawias kwadratowy minus 1 zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias ostrokątny znak równości priorytet otwórz nawias okrągły znak zamknij nawias okrągły dwukropek. Linia 28. wynik plus znak równości stos kropka pop otwórz nawias okrągły zamknij nawias okrągły. Linia 29. stos kropka append otwórz nawias okrągły znak zamknij nawias okrągły. Linia 31. while stos dwukropek. Linia 32. wynik plus znak równości cudzysłów cudzysłów plus stos kropka pop otwórz nawias okrągły zamknij nawias okrągły. Linia 34. return wynik. Linia 36. wyrazenie znak równości cudzysłów otwórz nawias okrągły 31 plus 4 zamknij nawias okrągły asterysk 7 cudzysłów. Linia 37. print otwórz nawias okrągły cudzysłów Wyrażenie infiksowe dwukropek cudzysłów przecinek wyrazenie zamknij nawias okrągły. Linia 38. wynik znak równości konwertuj podkreślnik do podkreślnik onp otwórz nawias okrągły wyrazenie zamknij nawias okrągły. Linia 39. print otwórz nawias okrągły cudzysłów Wyrażenie postfiksowe dwukropek cudzysłów przecinek wynik zamknij nawias okrągły.

from collections import deque

def czy_operator(znak):
    return znak in "()+-*/%^"

def priorytet(znak):
    if znak == "(": return 0
    elif znak in "+-": return 1
    elif znak in "*/%": return 2
    elif znak == "^": return 3
    else: return -1

def konwertuj_do_onp(wyrazenie):
    stos = deque()
    wynik = ""

    for znak in wyrazenie:
        if znak == " " or not czy_operator(znak):
            wynik += znak
        elif znak == "(":
            stos.append(znak)
        elif znak == ")":
            while stos[-1] != "(":
                wynik += " " + stos.pop()
            stos.pop()
        else:
            while stos and priorytet(stos[-1]) >= priorytet(znak):
                wynik += stos.pop()
            stos.append(znak)

    while stos:
        wynik += " " + stos.pop()

    return wynik

wyrazenie = "(31 + 4) * 7"
print("Wyrażenie infiksowe:", wyrazenie)
wynik = konwertuj_do_onp(wyrazenie)
print("Wyrażenie postfiksowe:", wynik)

Polecenie 3

Zapoznaj się z prezentacją przedstawiającą użycie jednokierunkowej listy cyklicznej w symulacji problemu Flawiusza. Algorytm zapisany w pseudokodzie znajdziesz w multimedium materiału Dynamiczne struktury danychDINsybcX5Dynamiczne struktury danych.

Specyfikacja problemu:

Dane:

n – liczba całkowita; liczba elementów kręgu
k – liczba całkowita; liczba oznaczająca pierwszy eliminowany element oraz liczbę przejść do następnego eliminowanego elementu

Wynik:

wypisany numer elementu, który pozostał w kręgu.

RM35JzKivKflU1

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY 3.0.

Polecenie 4

Przyjmijmy, że do symulacji problemu Flawiusza używamy dwukierunkowej listy cyklicznej o znanym rozmiarze n. Zaimplementuj metody dodaj(), usun() oraz wypisz() uwzględniające dwukierunkowość listy. Po uruchomieniu program powinien wypisywać zawartość listy przed każdym usunięciem węzła, a na końcu pozycję węzła, który pozostał na liście.

Działanie programu przetestuj dla n = 8 i k = 3.

Specyfikacja problemu:

Dane:

n – liczba naturalna; rozmiar listy cyklicznej
k – liczba naturalna; liczba oznaczająca pierwszy eliminowany element oraz liczbę przejść do następnego eliminowanego elementu

Wynik:

zawartość listy przed każdym usunięciem węzła oraz pozycja węzła, który pozostał na liście

Przykładowy wynik działania programu:

1 2 3 4 5 6 7 8 
1 2 4 5 6 7 8 
1 2 4 5 7 8 
2 4 5 7 8 
2 4 7 8 
4 7 8 
4 7 
7

R1HVhjYLRgQ5f1

Linia 1. class Wezel dwukropek. Linia 2. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self przecinek pozycja zamknij nawias okrągły dwukropek. Linia 3. self kropka pozycja znak równości pozycja. Linia 4. self kropka nastepny znak równości None. Linia 5. self kropka poprzedni znak równości None. Linia 7. class Lista dwukropek. Linia 8. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 9. self kropka glowa znak równości None. Linia 11. def przejdz otwórz nawias okrągły self przecinek o podkreślnik ile przecinek wezel zamknij nawias okrągły dwukropek. Linia 12. pomocniczy znak równości wezel. Linia 13. if not wezel dwukropek. Linia 14. pomocniczy znak równości self kropka glowa. Linia 16. for i in range otwórz nawias okrągły o podkreślnik ile zamknij nawias okrągły dwukropek. Linia 17. pomocniczy znak równości pomocniczy kropka nastepny. Linia 19. return pomocniczy. Linia 21. def dodaj otwórz nawias okrągły self przecinek pozycja zamknij nawias okrągły dwukropek. Linia 22. nowy znak równości Wezel otwórz nawias okrągły pozycja zamknij nawias okrągły. Linia 24. if not self kropka glowa dwukropek. Linia 25. self kropka glowa znak równości nowy. Linia 26. self kropka glowa kropka nastepny znak równości self kropka glowa kropka poprzedni znak równości self kropka glowa. Linia 27. return. Linia 29. ostatni znak równości self kropka glowa kropka poprzedni. Linia 30. nowy kropka nastepny znak równości self kropka glowa. Linia 31. nowy kropka poprzedni znak równości ostatni. Linia 32. self kropka glowa kropka poprzedni znak równości nowy. Linia 33. ostatni kropka nastepny znak równości nowy. Linia 35. def usun otwórz nawias okrągły self przecinek wezel zamknij nawias okrągły dwukropek. Linia 36. wezel kropka nastepny kropka poprzedni znak równości wezel kropka poprzedni. Linia 37. wezel kropka poprzedni kropka nastepny znak równości wezel kropka nastepny. Linia 39. if wezel znak równości znak równości self kropka glowa dwukropek. Linia 40. if self kropka glowa kropka nastepny wykrzyknik znak równości self kropka glowa dwukropek. Linia 41. self kropka glowa znak równości self kropka glowa kropka nastepny. Linia 42. else dwukropek. Linia 43. self kropka glowa znak równości None. Linia 45. def wypisz otwórz nawias okrągły self przecinek n zamknij nawias okrągły dwukropek. Linia 46. pomocniczy znak równości self kropka glowa. Linia 47. while n dwukropek. Linia 48. print otwórz nawias okrągły pomocniczy kropka pozycja przecinek cudzysłów cudzysłów przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 49. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 50. n minus znak równości 1. Linia 51. print otwórz nawias okrągły zamknij nawias okrągły. Linia 54. lista znak równości Lista otwórz nawias okrągły zamknij nawias okrągły. Linia 55. n znak równości 8. Linia 56. k znak równości 3. Linia 58. for i in range otwórz nawias okrągły n zamknij nawias okrągły dwukropek. Linia 59. lista kropka dodaj otwórz nawias okrągły i plus 1 zamknij nawias okrągły. Linia 61. wezel znak równości lista kropka przejdz otwórz nawias okrągły k minus 1 przecinek None zamknij nawias okrągły. Linia 62. while wezel kropka nastepny wykrzyknik znak równości wezel dwukropek. Linia 63. lista kropka wypisz otwórz nawias okrągły n zamknij nawias okrągły. Linia 64. n minus znak równości 1. Linia 65. lista kropka usun otwórz nawias okrągły wezel zamknij nawias okrągły. Linia 66. wezel znak równości lista kropka przejdz otwórz nawias okrągły k przecinek wezel zamknij nawias okrągły. Linia 68. print otwórz nawias okrągły wezel kropka pozycja zamknij nawias okrągły.

class Wezel:
    def __init__(self, pozycja):
        self.pozycja = pozycja
        self.nastepny = None
        self.poprzedni = None

class Lista:
    def __init__(self):
        self.glowa = None

    def przejdz(self, o_ile, wezel):
        pomocniczy = wezel
        if not wezel:
            pomocniczy = self.glowa

        for i in range(o_ile):
            pomocniczy = pomocniczy.nastepny

        return pomocniczy

    def dodaj(self, pozycja):
        nowy = Wezel(pozycja)

        if not self.glowa:
            self.glowa = nowy
            self.glowa.nastepny = self.glowa.poprzedni = self.glowa
            return

        ostatni = self.glowa.poprzedni
        nowy.nastepny = self.glowa
        nowy.poprzedni = ostatni
        self.glowa.poprzedni = nowy
        ostatni.nastepny = nowy

    def usun(self, wezel):
        wezel.nastepny.poprzedni = wezel.poprzedni
        wezel.poprzedni.nastepny = wezel.nastepny

        if wezel == self.glowa:
            if self.glowa.nastepny != self.glowa:
                self.glowa = self.glowa.nastepny
            else:
                self.glowa = None

    def wypisz(self, n):
        pomocniczy = self.glowa
        while n:
            print(pomocniczy.pozycja, "", end="")
            pomocniczy = pomocniczy.nastepny;
            n -= 1
        print()


lista = Lista()
n = 8
k = 3

for i in range(n):
    lista.dodaj(i + 1)

wezel = lista.przejdz(k - 1, None)
while wezel.nastepny != wezel:
    lista.wypisz(n)
    n -= 1
    lista.usun(wezel)
    wezel = lista.przejdz(k, wezel)

print(wezel.pozycja)

Polecenie 5

Zapoznaj się z prezentacją przedstawiającą użycie niecyklicznej listy dwukierunkowej w algorytmie leksykograficznego sortowania wyrazów. Algorytm zapisany w pseudokodzie znajdziesz w multimedium materiału Dynamiczne struktury danychDINsybcX5Dynamiczne struktury danych.

Specyfikacja problemu:

Dane:

wyrazy – lista zawierająca ciągi znaków, wyrazy do uporządkowania

Wynik:

wypisane w porządku leksykograficznym wyrazy

R5KUbv9cJaGbm1

Źródło: Contentplus.pl Sp. z o.o., licencja: CC BY-SA 3.0.

Polecenie 6

Metoda wstaw() zaimplementowana w prezentacji dotyczącej sortowania leksykograficznego wykonuje w pętli while jedno porównanie, które wcześniej wykonywane jest w metodzie sortuj().

Zaimplementuj taką wersję tej metody, która nie wykona zbędnego porównania.

Działanie programu przetestuj dla wyrazów: "dynamiczne", "Struktury", "danych", "Python".

Specyfikacja problemu:

Dane:

wyrazy – lista zawierająca ciągi znaków – wyrazy do uporządkowania

Wynik:

wyrazy wypisane przed posortowaniem i po sortowaniu w porządku leksykograficznym

Przykładowy wynik działania programu:

dynamiczne Struktury danych Python 
danych dynamiczne Python Struktury

R1bwubhT9Kxlt

Linia 1. class Wezel dwukropek. Linia 2. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self przecinek wyraz zamknij nawias okrągły dwukropek. Linia 3. self kropka wyraz znak równości wyraz. Linia 4. self kropka nastepny znak równości None. Linia 5. self kropka poprzedni znak równości None. Linia 7. class Lista dwukropek. Linia 8. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 9. self kropka glowa znak równości self kropka ogon znak równości None. Linia 11. def dodaj otwórz nawias okrągły self przecinek wyraz zamknij nawias okrągły dwukropek. Linia 12. nowy znak równości Wezel otwórz nawias okrągły wyraz zamknij nawias okrągły. Linia 14. if not self kropka glowa dwukropek. Linia 15. self kropka glowa znak równości self kropka ogon znak równości nowy. Linia 16. else dwukropek. Linia 17. self kropka ogon kropka nastepny znak równości nowy. Linia 18. nowy kropka poprzedni znak równości self kropka ogon. Linia 19. self kropka ogon znak równości nowy. Linia 21. def usun otwórz nawias okrągły self przecinek wezel zamknij nawias okrągły dwukropek. Linia 22. if wezel znak równości znak równości self kropka glowa and self kropka glowa kropka nastepny wykrzyknik znak równości None dwukropek. Linia 23. self kropka glowa znak równości self kropka glowa kropka nastepny. Linia 24. self kropka glowa kropka poprzedni znak równości None. Linia 25. return. Linia 27. if wezel znak równości znak równości self kropka ogon dwukropek. Linia 28. wezel kropka poprzedni kropka nastepny znak równości None. Linia 29. self kropka ogon znak równości wezel kropka poprzedni. Linia 30. else dwukropek. Linia 31. wezel kropka poprzedni kropka nastepny znak równości wezel kropka nastepny. Linia 32. wezel kropka nastepny kropka poprzedni znak równości wezel kropka poprzedni. Linia 34. def porownaj otwórz nawias okrągły self przecinek wezel podkreślnik 1 przecinek wezel podkreślnik 2 zamknij nawias okrągły dwukropek. Linia 35. wyraz podkreślnik 1 znak równości wezel podkreślnik 1 kropka wyraz kropka lower otwórz nawias okrągły zamknij nawias okrągły. Linia 36. wyraz podkreślnik 2 znak równości wezel podkreślnik 2 kropka wyraz kropka lower otwórz nawias okrągły zamknij nawias okrągły. Linia 38. if wyraz podkreślnik 1 zamknij nawias ostrokątny wyraz podkreślnik 2 dwukropek. Linia 39. return 1. Linia 40. elif wyraz podkreślnik 1 otwórz nawias ostrokątny wyraz podkreślnik 2 dwukropek. Linia 41. return minus 1. Linia 42. else dwukropek. Linia 43. return 0. Linia 45. def sortuj otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 46. pomocniczy znak równości self kropka glowa. Linia 47. while True dwukropek. Linia 48. if pomocniczy kropka nastepny znak równości znak równości None dwukropek. Linia 49. break. Linia 51. if self kropka porownaj otwórz nawias okrągły pomocniczy przecinek pomocniczy kropka nastepny zamknij nawias okrągły zamknij nawias ostrokątny 0 dwukropek. Linia 52. self kropka usun otwórz nawias okrągły pomocniczy zamknij nawias okrągły. Linia 53. self kropka wstaw otwórz nawias okrągły pomocniczy zamknij nawias okrągły. Linia 54. pomocniczy znak równości self kropka glowa. Linia 55. else dwukropek. Linia 56. pomocniczy znak równości pomocniczy kropka nastepny. Linia 59. def wstaw otwórz nawias okrągły self przecinek wezel zamknij nawias okrągły dwukropek. Linia 60. pomocniczy znak równości wezel kropka nastepny. Linia 61. while pomocniczy wykrzyknik znak równości self kropka ogon and self kropka porownaj otwórz nawias okrągły wezel przecinek pomocniczy kropka nastepny zamknij nawias okrągły zamknij nawias ostrokątny znak równości 0 dwukropek. Linia 62. pomocniczy znak równości pomocniczy kropka nastepny. Linia 64. if pomocniczy znak równości znak równości self kropka ogon dwukropek. Linia 65. wezel kropka nastepny znak równości None. Linia 66. wezel kropka poprzedni znak równości self kropka ogon. Linia 67. self kropka ogon kropka nastepny znak równości wezel. Linia 68. self kropka ogon znak równości wezel. Linia 69. else dwukropek. Linia 70. wezel kropka poprzedni znak równości pomocniczy. Linia 71. wezel kropka nastepny znak równości pomocniczy kropka nastepny. Linia 72. pomocniczy kropka nastepny kropka poprzedni znak równości wezel. Linia 73. pomocniczy kropka nastepny znak równości wezel. Linia 75. def wypisz otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 76. pomocniczy znak równości self kropka glowa. Linia 77. while pomocniczy wykrzyknik znak równości None dwukropek. Linia 78. print otwórz nawias okrągły pomocniczy kropka wyraz przecinek cudzysłów cudzysłów przecinek end znak równości cudzysłów cudzysłów zamknij nawias okrągły. Linia 79. pomocniczy znak równości pomocniczy kropka nastepny średnik. Linia 80. print otwórz nawias okrągły zamknij nawias okrągły. Linia 83. dane znak równości otwórz nawias kwadratowy cudzysłów dynamiczne cudzysłów przecinek cudzysłów Struktury cudzysłów przecinek cudzysłów danych cudzysłów przecinek cudzysłów Python cudzysłów zamknij nawias kwadratowy. Linia 85. lista znak równości Lista otwórz nawias okrągły zamknij nawias okrągły. Linia 86. for wyraz in dane dwukropek. Linia 87. lista kropka dodaj otwórz nawias okrągły wyraz zamknij nawias okrągły. Linia 89. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły. Linia 90. lista kropka sortuj otwórz nawias okrągły zamknij nawias okrągły. Linia 91. lista kropka wypisz otwórz nawias okrągły zamknij nawias okrągły.

class Wezel:
    def __init__(self, wyraz):
        self.wyraz = wyraz
        self.nastepny = None
        self.poprzedni = None

class Lista:
    def __init__(self):
        self.glowa = self.ogon = None

    def dodaj(self, wyraz):
        nowy = Wezel(wyraz)

        if not self.glowa:
            self.glowa = self.ogon = nowy
        else:
            self.ogon.nastepny = nowy
            nowy.poprzedni = self.ogon
            self.ogon = nowy

    def usun(self, wezel):
        if wezel == self.glowa and self.glowa.nastepny != None:
            self.glowa = self.glowa.nastepny
            self.glowa.poprzedni = None
            return

        if wezel == self.ogon:
            wezel.poprzedni.nastepny = None
            self.ogon = wezel.poprzedni
        else:
            wezel.poprzedni.nastepny = wezel.nastepny
            wezel.nastepny.poprzedni = wezel.poprzedni

    def porownaj(self, wezel_1, wezel_2):
        wyraz_1 = wezel_1.wyraz.lower()
        wyraz_2 = wezel_2.wyraz.lower()

        if wyraz_1 > wyraz_2:
            return 1
        elif wyraz_1 < wyraz_2:
            return -1
        else:
            return 0

    def sortuj(self):
        pomocniczy = self.glowa
        while True:
            if pomocniczy.nastepny == None:
                break

            if self.porownaj(pomocniczy, pomocniczy.nastepny) > 0:
                self.usun(pomocniczy)
                self.wstaw(pomocniczy)
                pomocniczy = self.glowa
            else:
                pomocniczy = pomocniczy.nastepny


    def wstaw(self, wezel):
        pomocniczy = wezel.nastepny
        while pomocniczy != self.ogon and self.porownaj(wezel, pomocniczy.nastepny) >= 0:
            pomocniczy = pomocniczy.nastepny

        if pomocniczy == self.ogon:
            wezel.nastepny = None
            wezel.poprzedni = self.ogon
            self.ogon.nastepny = wezel
            self.ogon = wezel
        else:
            wezel.poprzedni = pomocniczy
            wezel.nastepny = pomocniczy.nastepny
            pomocniczy.nastepny.poprzedni = wezel
            pomocniczy.nastepny = wezel

    def wypisz(self):
        pomocniczy = self.glowa
        while pomocniczy != None:
            print(pomocniczy.wyraz, "", end="")
            pomocniczy = pomocniczy.nastepny;
        print()


dane = ["dynamiczne", "Struktury", "danych", "Python"]

lista = Lista()
for wyraz in dane:
    lista.dodaj(wyraz)

lista.wypisz()
lista.sortuj()
lista.wypisz()

Przeczytaj

Sprawdź się