Paradygmaty programowania/Ćwiczenia 3: Typy, typy abstrakcyjne

Zadanie 1

Zaimplementuj bibliotekę do obsługi liczb w reprezentacji stałopozycyjnej. Biblioteka powinna umożliwiać tworzenie liczb w reprezentacji stałopozycyjnej o różnych wielkościach (tzn. o danej liczbie cyfr przed i po przecinku) oraz prowadzenie typowych obliczeń — powiedzmy działań arytmetycznych, potęgowania i pierwiastkowania. Pamiętaj, że rzecz ma sens tylko wtedy, gdy będzie działała szybko.

Wskazówka:

Należy zadbać nie tylko o dobre struktury danych, ale i algorytmy. Dodawanie jest mało kontrowersyjne, ale już mnożenie można zrobić lepiej niż jako „mnożenie pisemne”... Tym bardziej potęgowanie — nie wolno stosować algorytmu naiwnego, mnożącego liczbę przez siebie odpowiednio wiele razy.

Zadanie 2

Napisz klasę w C++ lub Javie implementującą napisy w pełni dynamiczne. Oczywiście nie korzystaj z gotowych klas w rodzaju StringBuilder lub StringBuffer. Klasa powinna dawać przynajmniej takie metody: tworzenie napisu (pustego, ze stałej lub z innego napisu), sprawdzanie równości, porównywanie alfabetyczne, konkatenacja, długość, wycinanie fragmentu.

Wskazówka:

Pamiętaj o tym, by przy porównywaniu brać pod uwagę długość napisów. Rozważ różne sposoby alokowania pamięci, np. z naddatkiem w stosunku do tworzonego napisu, by mieć zapas „na później”.

Zadanie 3

Zapisz ogólną postać wzoru na adres elementu tablicy wielowymiarowej pamiętanej wierszami przy założeniu, że tablica ma k wymiarów, indeksujemy od zera, liczba elementów w poszczególnych wymiarach to $n_{1},n_{2},...,n_{k}$, a indeks, dla którego liczymy adres, to $i_{1},i_{2},...,i_{k}.$

Zadanie 4

Zaimplementuj tablice asocjacyjne w dowolnym języku (oczywiście nie korzystając z gotowego mechanizmu, jeśli on w języku już istnieje). Implementacja za pomocą funkcji haszujących pozwala uzyskać stały średni czas dostępu do tablicy, podczas gdy drzewo binarne daje średni czas rzędu log n, gdzie n jest liczbą elementów w tablicy. Czy w takim razie tablice haszujące są bezwzględnie lepsze od drzew w tej roli? W jakich sytuacjach drzewo mogłoby być lepsze?

Zadanie 5

Zaimplementuj sparametryzowaną klasę w C# lub Javie, obsługującą stos elementów dowolnego typu, z operacjami włożenia na stos, zdjęcia ze stosu i sprawdzenia, czy stos jest pusty. Jak zwykle, nie korzystaj z gotowych rozwiązań... Czy są sytuacje, gdzie lepiej zaimplementować kilka klas dla konkretnych typów zamiast jednej klasy sparametryzowanej?

Zadanie 6

Implementując klasy sparametryzowane, twórcy Javy zastosowali dość proste w istocie rozwiązanie. Kompilując kod sparametryzowany, kompilator usuwa z niego informacje o parametrach „typowych” i zastępuje je ogólnym typem Object, następnie generuje kod jak dla klas bez parametrów i w razie potrzeby dodaje konwersje typów. Jak sądzisz, dlaczego zdecydowano się na takie rozwiązanie?

Wskazówka:

Klasy sparametryzowane zostały dodane do Javy dopiero w wersji 5.0 (zwanej też 1.5). Dzięki takiej implementacji kod stworzony w nowszej wersji działa na starszych maszynach wirtualnych Javy. Wadą tego rozwiązania jest jednak nie najlepsza efektywność dla typów prostych (które muszą być „opakowywane”) oraz utrata dynamicznej informacji o typach.

Zadanie 7

Implementacja sparametryzowanych klas w C++, C# i Javie to trzy różne podejścia do sprawy. Jakie są wady i zalety tych rozwiązań? Ciekawe porównanie tych implementacji można znaleźć pod adresem http://www.artima.com/intv/generics.html.