Paradygmaty programowania/Ćwiczenia 3: Typy, typy abstrakcyjne

Z Studia Informatyczne
< Paradygmaty programowania
Wersja z dnia 15:04, 22 wrz 2006 autorstwa Wkm (dyskusja | edycje) (→‎Zadanie 4)
(różn.) ← poprzednia wersja | przejdź do aktualnej wersji (różn.) | następna wersja → (różn.)
Przejdź do nawigacjiPrzejdź do wyszukiwania

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:

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:

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 , a indeks, dla którego liczymy adres, to

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:

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.