Paradygmaty programowania/Ćwiczenia 3: Typy, typy abstrakcyjne: Różnice pomiędzy wersjami

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania
 
Linia 15: Linia 15:
  
 
===Zadanie 4===
 
===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?
+
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===
 
===Zadanie 5===

Aktualna wersja na dzień 15:04, 22 wrz 2006

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.