Schemat interaktywny

Polecenie 1

Skonstruuj algorytm realizujący tworzenie drzewa binarnego (kopca) dla zbioru składającego się z n liczb naturalnych, zakładając wariant, że wartość w węźle nadrzędnym nie powinna być mniejsza niż w węzłach podrzędnych. Postaraj się dokładnie odwzorować porównywanie ze sobą kolejnych węzłów według opisanych w e‑materiale zasad. Algorytm skonstruuj, używając schematu interaktywnego lub wybranego języka programowania.

Przetestuj działanie algorytmu dla czteroelementowego zbioru {3, 1, 5, 7}.

Opracuj program w języku Python realizujący tworzenie drzewa binarnego (kopca) dla zbioru {3, 1, 5, 7}, zakładając wariant, że wartość w węźle nadrzędnym nie powinna być mniejsza niż w węzłach podrzędnych. Postaraj się dokładnie odwzorować porównywanie ze sobą kolejnych węzłów według opisanych w e‑materiale zasad.

Stwórz dwie listy: pierwsza przechowuje ciąg wejściowy; druga, pomocnicza, posłuży do budowania drzewa. Po uruchomieniu programu wypisywany będzie ciąg liczb uporządkowany nierosnąco.

Specyfikacja:

Dane:

n – liczba naturalna
tablica – lista liczb naturalnych, lista liczb wejściowych
drzewo – lista liczb naturalnych, lista pomocnicza służąca do budowania drzewa

Wynik:

drzewo – lista liczb naturalnych, która przechowuje w kolejności nierosnącej liczby z listy tablica

RuKOE0gOxLnpu

R1G16AVwyHyAs1

Rhk7hbCoCtY8k

Przykładowe rozwiązanie zadania:

R13kfKIsFbbDl1

Linia 1. tablica znak równości None. Linia 2. drzewo znak równości None. Linia 3. i znak równości None. Linia 4. pami podkreślnik C4 podkreślnik 99 podkreślnik C4 podkreślnik 87 znak równości None. Linia 7. tablica znak równości otwórz nawias kwadratowy 3 przecinek 1 przecinek 5 przecinek 7 zamknij nawias kwadratowy. Linia 8. drzewo znak równości otwórz nawias kwadratowy zamknij nawias kwadratowy. Linia 9. for i in range otwórz nawias okrągły 1 przecinek 5 zamknij nawias okrągły dwukropek. Linia 10. drzewo otwórz nawias kwadratowy int otwórz nawias okrągły i minus 1 zamknij nawias okrągły zamknij nawias kwadratowy znak równości tablica otwórz nawias kwadratowy int otwórz nawias okrągły i minus 1 zamknij nawias okrągły zamknij nawias kwadratowy. Linia 11. if drzewo otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości drzewo otwórz nawias kwadratowy 0 zamknij nawias kwadratowy dwukropek. Linia 12. pami podkreślnik C4 podkreślnik 99 podkreślnik C4 podkreślnik 87 znak równości drzewo otwórz nawias kwadratowy 1 zamknij nawias kwadratowy. Linia 13. drzewo otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości drzewo otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 14. drzewo otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości pami podkreślnik C4 podkreślnik 99 podkreślnik C4 podkreślnik 87. Linia 15. if drzewo otwórz nawias kwadratowy 2 zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości drzewo otwórz nawias kwadratowy 0 zamknij nawias kwadratowy dwukropek. Linia 16. pami podkreślnik C4 podkreślnik 99 podkreślnik C4 podkreślnik 87 znak równości drzewo otwórz nawias kwadratowy 2 zamknij nawias kwadratowy. Linia 17. drzewo otwórz nawias kwadratowy 2 zamknij nawias kwadratowy znak równości drzewo otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 18. drzewo otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości pami podkreślnik C4 podkreślnik 99 podkreślnik C4 podkreślnik 87. Linia 19. if drzewo otwórz nawias kwadratowy 3 zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości drzewo otwórz nawias kwadratowy 1 zamknij nawias kwadratowy dwukropek. Linia 20. pami podkreślnik C4 podkreślnik 99 podkreślnik C4 podkreślnik 87 znak równości drzewo otwórz nawias kwadratowy 3 zamknij nawias kwadratowy. Linia 21. drzewo otwórz nawias kwadratowy 3 zamknij nawias kwadratowy znak równości drzewo otwórz nawias kwadratowy 1 zamknij nawias kwadratowy. Linia 22. drzewo otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości pami podkreślnik C4 podkreślnik 99 podkreślnik C4 podkreślnik 87. Linia 23. if drzewo otwórz nawias kwadratowy 1 zamknij nawias kwadratowy zamknij nawias ostrokątny znak równości drzewo otwórz nawias kwadratowy 0 zamknij nawias kwadratowy dwukropek. Linia 24. pami podkreślnik C4 podkreślnik 99 podkreślnik C4 podkreślnik 87 znak równości drzewo otwórz nawias kwadratowy 1 zamknij nawias kwadratowy. Linia 25. drzewo otwórz nawias kwadratowy 1 zamknij nawias kwadratowy znak równości drzewo otwórz nawias kwadratowy 0 zamknij nawias kwadratowy. Linia 26. drzewo otwórz nawias kwadratowy 0 zamknij nawias kwadratowy znak równości pami podkreślnik C4 podkreślnik 99 podkreślnik C4 podkreślnik 87. Linia 27. print otwórz nawias okrągły drzewo zamknij nawias okrągły.

tablica = None
drzewo = None
i = None
pami_C4_99_C4_87 = None


tablica = [3, 1, 5, 7]
drzewo = []
for i in range(1, 5):
  drzewo[int(i - 1)] = tablica[int(i - 1)]
if drzewo[1] >= drzewo[0]:
  pami_C4_99_C4_87 = drzewo[1]
  drzewo[1] = drzewo[0]
  drzewo[0] = pami_C4_99_C4_87
if drzewo[2] >= drzewo[0]:
  pami_C4_99_C4_87 = drzewo[2]
  drzewo[2] = drzewo[0]
  drzewo[0] = pami_C4_99_C4_87
if drzewo[3] >= drzewo[1]:
  pami_C4_99_C4_87 = drzewo[3]
  drzewo[3] = drzewo[1]
  drzewo[1] = pami_C4_99_C4_87
if drzewo[1] >= drzewo[0]:
  pami_C4_99_C4_87 = drzewo[1]
  drzewo[1] = drzewo[0]
  drzewo[0] = pami_C4_99_C4_87
print(drzewo)

Polecenie 2

Dodaj do swojego programu komentarze tak, żeby był zrozumiały dla osoby, która nie potrafi programować.

Przeczytaj

Sprawdź się