Tmp

Zadania implementacje
2008/2009 Grzegorz Wierzowiecki
(Dokument jest w kodowaniu utf-8, a ew. "obrazki" stworzone przy stałej szerokości czcionki).

Wybierz zadanie, które chciałabyś/chciałbyś zaimplementować. Prześlij prośbę o rezerwację z dodatkowymi propozycjami innych. W odpowiedzi dostaniesz potwierdzenie rezerwacji pierwszego z listy wolnego zadania lub informację o dostępności zadań.
Punkty zdobyte za zadanie nie przepadają i dane "+0,5" czy "+1" do oceny z kolokwium, pozostaje również w przypadku poprawy. Więc osoby mające "2" jak najbardziej mogą "na zapas" zacząć pracować nad zadaniem. W przypadku poprawienia kolokwium z kategorii "3" na "4" może dane zadanie być mniej punktowane (o tym w "Typy zadań").

Każde z zadań trzeba:

  • samodzielnie zaimplementować,
  • rozumieć dlaczego działa tak, a nie inaczej.

To będzie potrzebne do obrony zadania.

Typy zadań

Poniższe zadania są podzielone na kategorie: "3; +0,5", "3; +1", "4; +0,5", "4; +1".
Zadania z kategorii "3; +0,5", "3; +1" mogą robić osoby o ocenach <2;4), na dodatkowe "+0,5" lub "+1" oceny do kolokwium.
Zadania z kategorii "4; +0,5", "4; +1" mogą robić osoby o ocenach <4;5>, na dodatkowe "+0,5" lub "+1" oceny do kolokwium.
Jeżeli ktoś chciałby zrobić zadanie z kategorii wyżej lub niżej, proszę bardzo, tylko trzeba skonsultować.
Można konsultować zadania, proponować własne. Można np. ustalić wykonanie części zadania na "+1" by było ocenione na "+0,5". Można zadanie na "+0,5" rozbudować do "+1", albo analogicznie z "3" rozbudować by było do kategorii "4", Tudzież np. zrobić zadanie z "3;+1" jako "4+;0,5".
Informacje o kategoriach w liście zadań.

Język programowania

Dozwolona jest znaczna większość języków imperatywnych, np. C/C++, Java. Może być też wiele innych, ale tylko przy niektórych - jak np. Lua, Python, JavaScript - można liczyć na moją pomoc, więc proszę śmiało pytać. W przypadku niektórych zadań, jeżeli będzie to miało sens mogę dopuścić języki z innych rodzin, np. funkcyjne czy deklaratywne.

Terminy

Trzeba przesłać implementację do końca zajęć 6stego stycznia 2009. (Najlepiej wysłać wcześniej, a potem można przesłać wersję poprawioną). Jeżeli, ktoś tego dnia będzie posiadał implementację z błędami (niekompletną, czasami niestabilną etc.), zwykle będzie możliwe dosłanie kolejnej poprawionej wersji w ciągu tygodnia oraz obrona. Można konsultować się w sprawie rozwiązań, czy też przyjść z problemami na konsultacje.

Nazewnictwo plików

Nadsyłane pliki muszą być postaci:
YYYY-MM-DD_sZZZZ_verV_imie_nazwisko_opis.rozszerzenie
Gdzie
YYYY - czterocyfrowy rok
MM - dwucyfrowy numer miesiąca
DD - dwucyfrowy numer dnia
ZZZZ - numer studentki/ta
V - numer wersji
imie_nazwisko_opis.rozszerzenie - tu chyba wiadomo co można umieścić.
Przykład poprawnie nazwanych plików:
2008-12-21_s1234_ver0.1_John_Doe_choinka.cpp
2009-01-03_s4321_ver1.9_Adam_Kowalski_implementacja_w_On.zip
etc.

Lista zadań

3 +0,5 Zadanie - ilość różnych liczb w posortowanych ciągach
3 +0,5 Zadanie - maksymalny podciąg
3 +0,5 Zadanie - wysokość drzewa BST
3 +0,5 Zadanie - droga w labiryncie
3 +1 Zadanie - Porównanie algorytmów sortujących: Bubble, Insertion, Selection
3 +1 Zadanie - Porównanie algorytmów sortujących: QuickSort, ShellSort, ShakerSort
4 +0,5 Zadanie - liczby zmiennoprzecinkowe
4 +1 Zadanie - ile liczb w przedziale (BST)
4 +1 Zadanie - wysokość drzewa AVL i ilość operacji rotacji
4 +1 Zadanie - 2-3drzewo

Zadanie - liczby zmiennoprzecinkowe

Jasio ma do dodania dużo liczb zmiennoprzecinkowych. Wie, że można zrobić to lepiej lub gorzej. Poproszono go, by pokazał jaka może być różnica pomiędzy wynikiem lepszego i gorszego dodawania danych liczb.

Wejście:

W pierwszej linii standardowego wejścia znajdzie się liczba "n", gdzie 1<=n<=10^7.
W każdej z kolejnych "n" linii znajduje się liczba zmiennoprzecinkowa.

Wyjście:

wyjściem programu jest jedna linia z trzema liczbami.
Pierwsza to suma liczb zmiennoprzecinkowych - podanych na wejściu - obliczona optymalnym algorytmem.
Druga to suma liczb zmiennoprzecinkowych, obliczona "gorszym" algorytmem.
Trzecia to różnica między pierwszym, a drugim wynikiem.

Zadanie:

Zaimplementuj program który wczyta wejście, obliczy sumy - optymalnym i gorszym algorytmem - i zaprezentuje wyniki oraz ich różnicę.
Dodatkowo stwórz co najmniej jeden przykładowy zestaw danych, dla którego ta różnica jest różna od zera. (Im mniejszy zestaw danych, a większa różnica tym lepiej ;) ).

Zadanie - wysokość drzewa BST

Stwórz implementacje drzewa BST.
Wstawiaj do niego kolejne liczby i sprawdzaj za każdym razem jak się zmienia wysokość.
Sprawdzanie wysokości ma być sprytne, to znaczy mieć złożoność nie gorszą od operacji wstawiania.
(Tak, więc zamiast obchodzić całe drzewo za każdym razem, prędzej wzbogacić strukturę o dodatkowe rzeczy…).

Wejście:

W pierwszej linii standardowego wejścia znajdzie się liczba "n", gdzie 1<=n<=10^6.
W drugiej linii znajduje się "n" liczb całkowitych <0,1'000'000>.

Wyjście:

Program ma wypisać n liczb. "i"-ta liczba oznacza wysokość drzewa po wstawieniu "i"-tej liczby z wejścia.

Zadanie - wysokość drzewa AVL i ilość operacji rotacji

Stwórz implementacje drzewa AVL.
Wstawiaj do niego kolejne liczby z pierwszego ciągu i sprawdzaj za każdym razem jak się zmienia wysokość oraz ile operacji wymagało wstawienie.
Potem usuwaj z niego kolejne liczby podane w drugim ciągu (UWAGA:mogą nie zawierać się w drzewie) i sprawdzaj za każdym razem jak zmienia się wysokość drzewa oraz ile rotacji trzeba było wykonać.

Wejście:

W pierwszej linii standardowego wejścia znajdą się liczby "n","m", gdzie 1<=n,m<=10^6.
W drugiej linii znajduje się "n" liczb całkowitych <0,1'000'000> do wstawiania kolejno.
W trzeciej linii znajduje się "m" liczb całkowitych <0,1'000'000> do usuwania kolejno.

Wyjście:

Program ma wypisać wpierw n zestawów liczb (w n liniach).
W i-tej linii (1<=i<=n) kolejno:
* wysokość drzewa po wstawieniu "i"-tej liczby z drugiej linii wejścia
* ilość operacji rotacji która została przy tym wykonana
Potem ma wypisać kolejne m zestawów liczb (w m liniach).
W i+j-tej linii (1<=j<=m) kolejno:
* wysokość drzewa po usunięciu "j"-tej liczby z trzeciej linii wejścia.
* ilość operacji rotacji która została przy tym wykonana
W przypadku żądania usuwania liczby której nie ma w drzewie, należy wypisać wysokość drzewa i "0" rotacji.

Zadanie - 2-3drzewo

Stwórz implementacje 2-3 drzewa. (Np. według: Algorytmy i Struktury danych - Alfred V.Aho, John E.Hopcroft, Jefferey D.Ullman).
Wstawiaj do niego kolejne liczby z pierwszego ciągu i sprawdzaj za każdym razem jak się zmienia wysokość drzewa oraz ile operacji "rozszczepienia węzła" (node split), to ta która następuje kiedy węzeł jest już przepełniony.
Potem usuwaj z niego kolejne liczby podane w drugim ciągu (UWAGA:mogą nie zawierać się w drzewie) i sprawdzaj za każdym razem, jak zmienia się wysokość drzewa oraz ile było wymaganych operacji równoważeń i komasacji węzłów.
Sprawdzanie wysokości ma być sprytne, to znaczy mieć złożoność nie gorszą od operacji wstawiania.
(Tak, więc zamiast obchodzić całe drzewo za każdym razem, prędzej wzbogacić strukturę o dodatkowe rzeczy…).

Wejście:

W pierwszej linii standardowego wejścia znajdą się liczby "n","m", gdzie 1<=n,m<=10^6.
W drugiej linii znajduje się "n" liczb całkowitych <0,1'000'000> do wstawiania kolejno.
W trzeciej linii znajduje się "m" liczb całkowitych <0,1'000'000> do usuwania kolejno.

Wyjście:

Program ma wypisać wpierw n zestawów liczb (w n liniach).
W i-tej linii (1<=i<=n) kolejno:
* wysokość drzewa po wstawieniu "i"-tej liczby z drugiej linii wejścia
* ilość operacji rozszczepienia węzła (node split).
Potem ma wypisać kolejne m zestawów liczb (w m liniach).
W i+j-tej linii (1<=j<=m) kolejno:
* wysokość drzewa po usunięciu "j"-tej liczby z trzeciej linii wejścia.
* ilość operacji równoważenia i komasacji (sumarycznie, lub dwie oddzielnie) które były przy tym wykonane.
W przypadku żądania usuwania liczby której nie ma w drzewie, należy wypisać wysokość drzewa i "0".

Zadanie - ile liczb w przedziale (BST)

Stwórz wzbogaconą implementację drzewa (BST), która będzie posiadała operację CountBetween, która będzie dla podanego przedziału (dwóch liczb) podawać ile się zawiera w drzewie liczb (łącznie z powtórkami) w danym przedziale włącznie.
Złożoność operacji CountBetween musi być taka sama jak dwa wyszukiwania: liczby z lewej strony przedziału i z prawej.
Zadanie polega na wczytaniu pierwszego zestawu liczb i utworzeniu drzewa zrównoważonego (w tym celu nie trzeba dokonywać rotacji, a można skorzystać z metody przesortowania wczytanych liczb jakąś funkcją biblioteczną (nie trzeba implementować sortowania), a potem wstawiania w odpowiednim porządku - jeśli jesteś zainteresowana/y możesz zapytać o więcej szczegółów dotyczących tej części).
Po zbudowaniu drzewa, należy podawać wynik CountBetween dla kolejnych par liczb.

Wejście:

W pierwszej linii standardowego wejścia znajduje się "n", gdzie 1<=n<=10^6.
W drugiej linii znajduje się "n" liczb całkowitych <0,1'000'000> z których ma zostać zbudowane drzewo.
W trzeciej linii znajduje się "m", gdzie 1<=m<=10^6.
W kolejnych m liniach znajdują się pary liczb z przedziału <0,1'000'000>.

Wyjście:

Program ma wypisać m liczb (w jednej lub oddzielnych liniach), gdzie j-ta liczba odpowiada wynikowi CountBetween dla j-tej pary liczb z wejścia.

Zadanie - maksymalny podciąg

Dla danego ciągu liczb znajdź maksymalny podciąg, czyli podciąg o maksymalnej sumie.
W trakcie działania algorytmu po każdej iteracji wyświetl tablicę liczb i oznacz za pomocą "i" "j" aktualnie rozpatrywany przedział, za pomocą gwiazdek "*" maksymalny aktualnie znaleziony. Wizualizacje aktualizuj po każdej zmianie, któregoś z iteratorów (oraz ew. po zakończeniu algorytmu).

Zadanie - droga w labiryncie

Jasio szuka drogi do skarbu w ogromnym labiryncie - pomóż mu ją odnaleźć. Najkrótszą !
(Do tego zastosuj przeszukiwanie BFS, przy użyciu własnej implementacji kolejki FIFO).

Wejście:

W pierwszej lini liczby x,y,n,m. "x,y" oznacza miejsce startowe wędrówki w labiryncie, gdzie (0,0) to lewy górny róg. "n,m" oznaczają wymiary labiryntu (1<=n*m<=10^6).
W kolejnych m liniach znajdują się wiersze, a w każdym po n znaków: '.', '#', '*'. Oznaczające kolejno: '.' drogę po której można iść. '#' ścianę przez którą nie można przejść, '*' skarb.

Wyjście:

Ten sam rysunek co na wejściu, tylko z zaznaczoną drogą. Drogę można zaznaczyć na dowolny sposób.

Przykład:

We:

0 0 
....##
###...
...##.
....#.
*.#...

Wy:
@@@@##
###@@@
...##@
.@@@#@
@@#@@@

Wejście:

W pierwszej linii wejścia znajduje się liczba "n" ; 1<=n,m<=1'000.
W drugiej linii znajduje się n liczb całkowitych dodatnich <0;1'000'000> (zwykłe inty).

Zadanie - ilość różnych liczb w posortowanych ciągach

Dane są dwie posortowane rosnąco tablice liczb.
Zaimplementuj funkcje:

  • ilosc_roznych_w_tablicy, która będzie przyjmować jako parametr tablicę (wskaźnik/referencję) oraz jej rozmiar, a zwracać ilość róznych elementów (np. dla "3 3 4 4 5 5" -> 3)
  • ilosc_roznych_w_tablicach, która będzie przyjmować jako argument dwie tablice z rozmiarami i zwracać ilość różnych w nich elementów (np. dla "3 4 4 4 5" oraz "3 3 5 7" -> 4, bo to {3,4,5,7} )

Algorytm ma wczytać dwa zestawy liczb do dwóch tablic, użyć pierwszej funkcji na każdej z tablic, a potem drugiej na nich.

Wejście:

W pierwszej linii wejścia znajdują się liczby "n", "m" ; 1<=n,m<=1'000'000.
W drugiej linii znajduje się n liczb całkowitych dodatnich <0;1'000'000> (zwykłe inty).
W trzeciej linii znajduje się m liczb całkowitych dodatnich <0;1'000'000> (zwykłe inty).

Wyjście:
Mniej więcej takie:
"
ilosc_roznych_w_tablicy A: 3
ilosc_roznych_w_tablicy B: 4
ilosc_roznych_w_tablicach A i B: 6
"
W poprzedzających liniach, mogą i będą mile widziane wizualizacje procesu działania algorytmu.

Zadanie - Porównanie algorytmów sortujących: Bubble, Insertion, Selection

Zaimplementuj algorytmy : BubbleSort, InsertionSort, SelectionSort.
Niech prezentują kolejne stany tablicy, jak to sortowanie przebiega, i zliczają ilość wykonanych operacji SWAP.

Wejście:

W pierwszej linii wejścia znajduje się jedna z liter : "B", "I", "S" (duże).
W drugiej linii wejścia liczba "n" ; 1<=n<=1'000 oznaczająca ilość liczb to posortowania.
W trzeciej linii znajduje się n liczb całkowitych dodatnich <0;1'000'000> (zwykłe inty).

Wyjście:

Pierwsze litera oznacza algorytm sortowania : B - Bubble, I - Insertion, S - Selection.
Dla wybranego algorytmu sortowania pokaż stan tablicy wejściowej, a potem, po każdej operacji swap oraz zmianie któregoś z iteratorów.
W ostatniej linii napis "operacji swap:" oraz ilość operacji swap.
Mile widziane oznaczanie wyświetlonych liczb. Dla przykładu: jeżeli w algorytmach używamy w zewnętrznej w pętli iteratora "i", w wewnętrznej "j", to możemy po każdej liczbie napisać :
"i " - kiedy jest wskazywana przez i
"j " - kiedy jest wskazywana przez j
". " - kiedy jest jedna z dwóch które podległy właśnie zamianie w wyniku działania "SWAP
" " - dwie spacje w innym wypadku
To jest tylko propozycja, pokazująca o co mi chodzi… oto jak mogłoby wyglądać przykładowe wyjście dla :
I
3
3 2 1
Przykładowe wyjście:
4j 3i 2 1
3. 4. 2 1
3 4j 2i 1
3 2. 4. 1
3j 2 4i 1
2. 3. 4i 1
2 3 4j 1i
2 3j 1. 4.
2 1. 3. 4i
2j 1 3 4i
1. 2. 3 4i
operacji swap: 6

Zadanie - Porównanie algorytmów sortujących: QuickSort, ShellSort, ShakerSort.

jak w zadaniu "Porównanie algorytmów sortujących: Bubble, Insertion, Selection", tylko odpowiednio:
Q - QuickSort
S - ShellSort
K - ShakerSort
Opis algorytmu ShakerSort można znaleźć w publikacji Wróblewskiego, mogę przesłać opis w przypadku trudności w znalezieniu.

Zadanie - Wizualizacja kopca

Zaimplementuj kopiec maksymalny na tablicy i jego wizualizację, wyświetlającą kopiec w postaci tekstowej (ew. graficznej), ot np. tak:

.      ___ 3___
      /        \
   _ 6_       _ 8_
  /    \     /    \
 2      3   4      7

Program ma wczytać pierwszy zestaw liczb do tablicy i wykonać build-heap.
Po zbudowaniu kopca, ma do niego dodawać kolejno liczby z drugiego zestawu.

Przy przetwarzaniu kopca, należy odświeżać wizualizację po każdej operacji swap. Mile widziane oznaczanie w jakiś sposób węzłów które uległy zamianie.

Wejście:
W pierwszej linii wejścia liczby "n","m" ; 1<=n,m<=128.
W drugiej linii znajduje się pierwszy zestaw: n liczb całkowitych dodatnich <0;99> (dwucyfrowe).
W trzeciej linii znajduje się drugi zestaw: m liczb całkowitych dodatnich <0;99> (dwucyfrowe).

O ile nie zaznaczono inaczej, treść tej strony objęta jest licencją Creative Commons Attribution-ShareAlike 3.0 License