Sprawdź się

111

Pokaż ćwiczenia:

Ćwiczenie 1

W języku Python 3 dostępny jest standardowy moduł queue. Zapoznaj się z pokazanym kodem, a następnie wykonaj umieszczone pod nim polecenia.

Linia 1. import queue. Linia 3. class Wezel dwukropek. Linia 4. def podkreślnik podkreślnik init podkreślnik podkreślnik otwórz nawias okrągły self przecinek lewy znak równości None przecinek prawy znak równości None zamknij nawias okrągły dwukropek. Linia 5. self kropka lewy znak równości lewy. Linia 6. self kropka prawy znak równości prawy. Linia 8. def stworz otwórz nawias okrągły elementy zamknij nawias okrągły dwukropek. Linia 9. kolejka znak równości queue kropka Queue otwórz nawias okrągły zamknij nawias okrągły. Linia 10. for element in elementy dwukropek. Linia 11. wezel znak równości Wezel otwórz nawias okrągły element otwórz nawias kwadratowy 0 zamknij nawias kwadratowy przecinek element otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias okrągły. Linia 12. kolejka kropka put otwórz nawias okrągły wezel zamknij nawias okrągły. Linia 13. return kolejka. Linia 15. elementy znak równości otwórz nawias kwadratowy otwórz nawias okrągły 65 przecinek apostrof A apostrof zamknij nawias okrągły przecinek otwórz nawias okrągły 66 przecinek apostrof B apostrof zamknij nawias okrągły przecinek otwórz nawias okrągły 67 przecinek apostrof C apostrof zamknij nawias okrągły przecinek otwórz nawias okrągły 68 przecinek apostrof D apostrof zamknij nawias okrągły przecinek otwórz nawias okrągły 69 przecinek apostrof E apostrof zamknij nawias okrągły przecinek otwórz nawias okrągły 70 przecinek apostrof F apostrof zamknij nawias okrągły zamknij nawias kwadratowy. Linia 17. p znak równości stworz otwórz nawias okrągły elementy zamknij nawias okrągły. Linia 19. kratka wywołania wraz z oczekiwanymi wynikami. Linia 20. print otwórz nawias okrągły p kropka get otwórz nawias okrągły zamknij nawias okrągły kropka dzieci otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 21. kratka otwórz nawias okrągły 65 przecinek apostrof A apostrof zamknij nawias okrągły. Linia 22. print otwórz nawias okrągły p kropka get otwórz nawias okrągły zamknij nawias okrągły kropka dzieci otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 23. kratka otwórz nawias okrągły 66 przecinek apostrof B apostrof zamknij nawias okrągły. Linia 24. print otwórz nawias okrągły p kropka get otwórz nawias okrągły zamknij nawias okrągły kropka dzieci otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 25. kratka otwórz nawias okrągły 67 przecinek apostrof C apostrof zamknij nawias okrągły.

import queue

class Wezel:
	def __init__(self, lewy=None, prawy=None):
		self.lewy = lewy
		self.prawy = prawy

def stworz(elementy):
	kolejka = queue.Queue()
	for element in elementy:
		wezel = Wezel(element[0], element[1])
		kolejka.put(wezel)
	return kolejka

elementy = [(65, 'A'), (66, 'B'), (67, 'C'), (68, 'D'), (69, 'E'), (70, 'F')]

p = stworz(elementy)

#wywołania wraz z oczekiwanymi wynikami
print(p.get().dzieci())
# (65, 'A')
print(p.get().dzieci())
# (66, 'B')
print(p.get().dzieci())
# (67, 'C')

RYigv1hFDBjyj

RJsCpHINi0MEh

Zaznacz wszystkie prawidłowe odpowiedzi Możliwe odpowiedzi: 1. Klasa Queue ma zdefiniowane 3 kolejki : FIFO, LIFO, Priorytetowa, 2. Klasa Queue ma zdefiniowane 2 kolejki : FIFO, LIFO, 3. metoda get() zwraca element kolejki i nie usuwa go., 4. metoda get() zwraca element kolejki i usuwa go.

Ćwiczenie 2

Zdefiniuj klasę class Wezel o następujących polach i metodach:

Pola:

dane – o domyślnej wartości None
lewo – o domyślnej wartości None
prawo – o domyślnej wartości None

Metody:

konstruktor – przypisuje każdemu polu odpowiednie wartości
dunder __str__ – nadpisuje domyślną metodę odpowiedzialną za zwracanie łańcucha znaków odpowiadającego danemu obiektowi; deklarujemy ją w ten sposób: def __str__(self); zaimplementowana metoda powinna zwracać łańcuch znaków f"Wartość = {self.dane}"
dzieci – zwraca łańcuch znaków: f"Dzieci: L -> {self.lewo} P -> {self.prawo}"

Następnie dla każdej krotki zawartej w liście wezly stwórz obiekty klasy Wezel z zawartością pola dane zgodną z pierwszą wartością krotki. Wartościami pól lewo i prawo powinny być nowo utworzone obiekty, których indeks w tablicy wezly odpowiada kolejno drugiej i trzeciej wartości z krotki (None oznacza brak dziecka, a więc wartością pola lewo bądź prawo będzie None).

Przykład 1

Dla listy wezly = [("korzen", None, 1), ("prawo", None, None)] musimy utworzyć węzeł z polami dane o wartości "korzen", lewo zawierające wartość None i prawo zawierające obiekt klasy Wezel, którego dane to "prawo", lewo to None i prawo to None

Specyfikacja problemu:

Dane:

wezly – lista zawierająca krotki z wartościami pól instancji klasy

Wynik:

Na standardowym wyjściu program wypisuje dane dla zadanych węzłów, a następnie ich dzieci.

Swoje rozwiązanie przetestuj dla listy: wezly = [("korzen", 1, 2), ("lewo", None, None), ("prawo", None, None)].

RXWC4qQBwPddz

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 dane znak równości None przecinek lewo znak równości None przecinek prawo znak równości None zamknij nawias okrągły dwukropek. Linia 3. self kropka dane znak równości dane. Linia 4. self kropka lewo znak równości lewo. Linia 5. self kropka prawo znak równości prawo. Linia 7. def podkreślnik podkreślnik str podkreślnik podkreślnik otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 8. return f cudzysłów Wartość znak równości otwórz nawias klamrowy self kropka dane zamknij nawias klamrowy cudzysłów. Linia 10. def dzieci otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 11. return f cudzysłów Dzieci dwukropek L minus zamknij nawias ostrokątny otwórz nawias klamrowy self kropka lewo zamknij nawias klamrowy P minus zamknij nawias ostrokątny otwórz nawias klamrowy self kropka prawo zamknij nawias klamrowy cudzysłów. Linia 13. wezly znak równości otwórz nawias kwadratowy otwórz nawias okrągły cudzysłów korzen cudzysłów przecinek 1 przecinek 2 zamknij nawias okrągły przecinek otwórz nawias okrągły cudzysłów lewo cudzysłów przecinek None przecinek None zamknij nawias okrągły przecinek otwórz nawias okrągły cudzysłów prawo cudzysłów przecinek None przecinek None zamknij nawias okrągły zamknij nawias kwadratowy. Linia 15. utworzone podkreślnik wezly znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 17. kratka zapisywanie nowych węzłów w tablicy. Linia 18. for wezel in wezly dwukropek. Linia 19. utworzone podkreślnik wezly kropka append otwórz nawias okrągły Wezel otwórz nawias okrągły wezel otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły. Linia 21. kratka dopinanie dzieci do każdego węzła. Linia 22. for i in range otwórz nawias okrągły len otwórz nawias okrągły wezly zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 23. if wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 1 zamknij nawias kwadratowy is None dwukropek. Linia 24. utworzone podkreślnik wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka lewo znak równości None. Linia 25. else dwukropek. Linia 26. utworzone podkreślnik wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka lewo znak równości utworzone podkreślnik wezly otwórz nawias kwadratowy wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias kwadratowy. Linia 27. if wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 2 zamknij nawias kwadratowy is None dwukropek. Linia 28. utworzone podkreślnik wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka prawo znak równości None. Linia 29. else dwukropek. Linia 30. utworzone podkreślnik wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka prawo znak równości utworzone podkreślnik wezly otwórz nawias kwadratowy wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 2 zamknij nawias kwadratowy zamknij nawias kwadratowy. Linia 32. for wezel in utworzone podkreślnik wezly dwukropek. Linia 33. print otwórz nawias okrągły wezel zamknij nawias okrągły. Linia 35. kratka Wartość znak równości korzen. Linia 36. kratka Wartość znak równości lewo. Linia 37. kratka Wartość znak równości prawo. Linia 39. for wezel in utworzone podkreślnik wezly dwukropek. Linia 40. print otwórz nawias okrągły wezel kropka dzieci otwórz nawias okrągły zamknij nawias okrągły zamknij nawias okrągły. Linia 42. kratka Dzieci dwukropek L minus zamknij nawias ostrokątny Wartość znak równości lewo P minus zamknij nawias ostrokątny Wartość znak równości prawo. Linia 43. kratka Dzieci dwukropek L minus zamknij nawias ostrokątny None P minus zamknij nawias ostrokątny None. Linia 44. kratka Dzieci dwukropek L minus zamknij nawias ostrokątny None P minus zamknij nawias ostrokątny None.

class Wezel:
	def __init__(self, dane=None, lewo=None, prawo=None):
		self.dane = dane
		self.lewo = lewo
		self.prawo = prawo

	def __str__(self):
		return f"Wartość = {self.dane}"

	def dzieci(self):
		return f"Dzieci: L -> {self.lewo} P -> {self.prawo}"

wezly = [("korzen", 1, 2), ("lewo", None, None), ("prawo", None, None)]

utworzone_wezly = []

# zapisywanie nowych węzłów w tablicy
for wezel in wezly:
	utworzone_wezly.append(Wezel(wezel[0]))

# dopinanie dzieci do każdego węzła
for i in range(len(wezly)):
	if wezly[i][1] is None:
		utworzone_wezly[i].lewo = None
	else:
		utworzone_wezly[i].lewo = utworzone_wezly[wezly[i][1]]
	if wezly[i][2] is None:
		utworzone_wezly[i].prawo = None
	else:
		utworzone_wezly[i].prawo = utworzone_wezly[wezly[i][2]]

for wezel in utworzone_wezly:
	print(wezel)

# Wartość = korzen
# Wartość = lewo
# Wartość = prawo

for wezel in utworzone_wezly:
	print(wezel.dzieci())

# Dzieci: L -> Wartość = lewo P -> Wartość = prawo
# Dzieci: L -> None P -> None
# Dzieci: L -> None P -> None

Ćwiczenie 3

Korzystając z klasy zaimplementowanej w zadaniu 2, utwórz węzły w ten sam sposób, a następnie zapisz funkcję wedrownik(element) przechodzącą po drzewie binarnym. Powinna ona działać rekurencyjnie według następującego algorytmu:

jeśli wywoływany element jest wartością None, funkcja kończy działanie;
w pozostałych przypadkach funkcja wyświetla wartość zawartą w węźle, a następnie rekurencyjnie wywołuje się dla elementów najpierw lewego, a potem prawego.

Specyfikacja problemu:

Dane:

wezly – lista zawierająca krotki z wartościami pól instancji klasy

Wynik:

Na standardowym wyjściu program wypisuje dane wszystkich węzłów, po których przeszedł za pomocą funkcji wedrownik().

Swoje rozwiązanie przetestuj dla listy: wezly = [("Główny", 1, 2), ("Posredni", 3, None ), ("Prawy", None, None), ("Lewy", 4, None), ("Ostatni", None, None)].

Rrv5OQa8sSQq4

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 dane znak równości None przecinek lewo znak równości None przecinek prawo znak równości None zamknij nawias okrągły dwukropek. Linia 3. self kropka dane znak równości dane. Linia 4. self kropka lewo znak równości lewo. Linia 5. self kropka prawo znak równości prawo. Linia 7. def podkreślnik podkreślnik str podkreślnik podkreślnik otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 8. return cudzysłów Wartość znak równości cudzysłów plus self kropka dane. Linia 10. def dzieci otwórz nawias okrągły self zamknij nawias okrągły dwukropek. Linia 11. return cudzysłów Dzieci dwukropek L minus zamknij nawias ostrokątny cudzysłów plus str otwórz nawias okrągły self kropka lewo zamknij nawias okrągły plus cudzysłów P minus zamknij nawias ostrokątny cudzysłów plus str otwórz nawias okrągły self kropka prawo zamknij nawias okrągły. Linia 13. def wedrownik otwórz nawias okrągły wezel zamknij nawias okrągły dwukropek. Linia 14. if wezel is None dwukropek. Linia 15. return. Linia 16. print otwórz nawias okrągły wezel zamknij nawias okrągły. Linia 17. wedrownik otwórz nawias okrągły wezel kropka lewo zamknij nawias okrągły. Linia 18. wedrownik otwórz nawias okrągły wezel kropka prawo zamknij nawias okrągły. Linia 20. kratka definicja wezlow i sprawdzenie funkcji. Linia 21. wezly znak równości otwórz nawias kwadratowy otwórz nawias okrągły cudzysłów Główny cudzysłów przecinek 1 przecinek 2 zamknij nawias okrągły przecinek otwórz nawias okrągły cudzysłów Posredni cudzysłów przecinek 3 przecinek None zamknij nawias okrągły przecinek otwórz nawias okrągły cudzysłów Prawy cudzysłów przecinek None przecinek None zamknij nawias okrągły przecinek otwórz nawias okrągły cudzysłów Lewy cudzysłów przecinek 4 przecinek None zamknij nawias okrągły przecinek otwórz nawias okrągły cudzysłów Ostatni cudzysłów przecinek None przecinek None zamknij nawias okrągły zamknij nawias kwadratowy. Linia 23. utworzone podkreślnik wezly znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 25. kratka tworzenie węzłów. Linia 26. for wezel in wezly dwukropek. Linia 27. utworzone podkreślnik wezly kropka append otwórz nawias okrągły Wezel otwórz nawias okrągły wezel otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły zamknij nawias okrągły. Linia 29. for i in range otwórz nawias okrągły len otwórz nawias okrągły wezly zamknij nawias okrągły zamknij nawias okrągły dwukropek. Linia 30. if wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 1 zamknij nawias kwadratowy is None dwukropek. Linia 31. utworzone podkreślnik wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka lewo znak równości None. Linia 32. else dwukropek. Linia 33. utworzone podkreślnik wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka lewo znak równości utworzone podkreślnik wezly otwórz nawias kwadratowy wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias kwadratowy. Linia 34. if wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 2 zamknij nawias kwadratowy is None dwukropek. Linia 35. utworzone podkreślnik wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka prawo znak równości None. Linia 36. else dwukropek. Linia 37. utworzone podkreślnik wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy kropka prawo znak równości utworzone podkreślnik wezly otwórz nawias kwadratowy wezly otwórz nawias kwadratowy i zamknij nawias kwadratowy otwórz nawias kwadratowy 2 zamknij nawias kwadratowy zamknij nawias kwadratowy. Linia 39. wedrownik otwórz nawias okrągły utworzone podkreślnik wezly otwórz nawias kwadratowy 0 zamknij nawias kwadratowy zamknij nawias okrągły.

class Wezel:
	def __init__(self, dane=None, lewo=None, prawo=None):
		self.dane = dane
		self.lewo = lewo
		self.prawo = prawo

	def __str__(self):
		return "Wartość = "+ self.dane

	def dzieci(self):
		return "Dzieci: L -> "+str(self.lewo) + " P -> " + str(self.prawo)

def wedrownik(wezel):
	if wezel is None:
		return
	print(wezel)
	wedrownik(wezel.lewo)
	wedrownik(wezel.prawo)

# definicja wezlow i sprawdzenie funkcji
wezly = [("Główny", 1, 2), ("Posredni", 3, None ), ("Prawy", None, None), ("Lewy", 4, None), ("Ostatni", None, None)]

utworzone_wezly = []

# tworzenie węzłów
for wezel in wezly:
	utworzone_wezly.append(Wezel(wezel[0]))

for i in range(len(wezly)):
	if wezly[i][1] is None:
		utworzone_wezly[i].lewo = None
	else:
		utworzone_wezly[i].lewo = utworzone_wezly[wezly[i][1]]
	if wezly[i][2] is None:
		utworzone_wezly[i].prawo = None
	else:
		utworzone_wezly[i].prawo = utworzone_wezly[wezly[i][2]]

wedrownik(utworzone_wezly[0])

Film samouczek

Dla nauczyciela