Metody Programowania - Lista 7

Zadanie 1

Przerobić procedury wstawiania i usuwania z drzew AVL, tak by zamiast rekursji używać iteracji i stosu (tzn. użyć stos Poplogu).

Zadanie 2

Podlistą listy L nazywamy listę otrzymaną z L przez usunięcie niektórych elementów (być może wszystkich). Napisać procedurę która wygeneruje wszystkie podlisty danej listy (w dowolnej kolejności, ale bez powtórzeń). Podobnie, procedurę która wygeneruje podlisty ustalonej długości. Następnie, wzorując się na programie genperm2.p przerobić je na generatory.

Zadanie 3

Zakładamy że wyrażenia logiczne są reprezentowane tak jak w zadaniu 3 z Listy 6. Napisać procedurę która mając dane wyrażenie, wartość logiczną (true lub false) i zmienną wyprodukuje nowe wyrażenie w którym ta zmienna jest zastąpiona przez podaną wartość.

Zadanie 4

Zakładamy że wyrażenie "algebraiczne" jest reprezentowane przez drzewo gdzie każdy węzeł jest stałą, zmienną lub zawiera operator i argumenty (jeden lub dwa). Np.

[+ x [* 2 [* y [exp x]]]]

Dostępne operatory to +, -, *, / (dzielenie), exp i log (funkcja wykładnicza i logarytm). Zmienne są reprezentowane przez słowa Poplogu. Napisać procedurę która mając dane drzewo reprezentujące wyrażenie i zmienną obliczy wyrażenie reprezentujące pochodną.

Zadanie 5

Kolejka priorytetowa różni się tym od zwykłej kolejki że dane wstawia się w dowolnej kolejności zaś pobierana jest zawsze największa wartość (z pomiędzy dostępnych). Napisać dwie realizacje kolejki priorytetowej, jedną bazującą na drzewach, drugą będącą modyfikacją programu heapsort.p . Chodzi przy tym o to by wstawianie elementu do kolejki priorytetowej i pobieranie elementu wymagało przeciętnie liczby operacji proporcjonalnej do logarytmu rozmiaru kolejki. Wskazówka: program heapsort.p w zasadzie już zawiera potrzebne operacje wstawiania i pobierania, trzeba je tylko oddzielić od reszty i dodać powiększanie tablicy (tzn. przydzielanie większej i kopiowanie z miniejszej do większej).