Treść zadnia może być aktualizowana na edu (w szczególności sekcja z przykładami), przed wysłaniem rozwiązania proszę sprawdzić, czy nie pojawiła się nowa wersja - są numerowane.
W zadaniu ma być użyty algorytm sortowania QuickSortSplit w wersji przedstawionej w pseudokodzie na edu.
Problem
Dostaliśmy plik z pomiarami z czujnika, który na bieżąco liczy sumę pomiarów korzystając z liczb zmiennoprzecinkowych pojedynczej precyzji. Chcemy obliczyć sumę pomiarów. Jako, iż czujnik mierzy wartości rzeczywistych parametrów, jego dynamika jest bardzo duża. Dlatego wartości przechowujemy w liczbach zmiennoprzecinkowych, typu "float" (pojedynczej precyzji "Single precision", 32bitowe) opisanych w standardzie IEEE.
Jak wiemy, ze względów technicznych trzeba najpierw posortować takie liczby, zanim się je doda by nie tracić na dokładności sumowań. Stąd sumaryczną wartość pokazywaną przez czujnik na wyświetlaczu traktujemy jako "podgląd", "oszacowanie" prawdziwej sumy.
Jesteśmy ciekawi różnicy między prawidłowo dodanymi pomiarami, oraz chcemy mieć podgląd na proces sortowania liczb, by mieć pewność że zostaną dobrze dodane.
Specyfikacja wejścia
W pierwszej linii wejścia znajdują się : liczba całkowita oraz litera, niech to będą n i u. Litera u może być równa "g" kiedy użytkownik chce podgląd graficzny, "n" kiedy numeryczny. Natomiast n oznacza liczbę pomiarów do zsumowania.
W kolejnych n liniach znajdują się kolejne liczby do zsumowania. Są to liczby zmiennoprzecinkowe i mogą być zarówno w notacji tradycyjnej, jak i naukowej. Liczby i ich suma, mieszczą się w zakresie liczb zmiennoprzecinkowych :"Single precision" opisanych w standardzie IEEE_754.
1 =< n =< 1000
Specyfikacja problemu
Wczytać liczby. Posortować wczytane liczby algorytmem QuickSortSplit, pokazując w kolejnych liniach kolejne etapy sortowania po operacji Split w zdefiniowanym przez użytkownika formacie. Na końcu bezwzględna różnica sum uzyskanych poprzez sumowanie elementów w kolejności wczytywania oraz po posortowaniu.
Wczytane liczby z pomiarów przechowujemy w liczbach pojedynczej precyzji, tak by odwzorować zachowanie czujnika. Dodawanie i przechowywanie sumy też realizujemy w liczbie zmiennoprzecinkowej pojedynczej precyzji.
Specyfikacja wyjścia
W kolejnych liniach pokazujemy kolejne etapy sortowania QuickSortSplit w zalezności od u :
-
u = "n" - "numbers mode" - wypisujemy trzy liczby oddzielone tabulatorami:
-
indeks (tablica indeksowana od 0ra) początku zakresu na którym był wykonywany algorytm Split
-
indeks elementu dzielącego po wykonaniu operacji Split
-
indeks ostatniego elementu zakresu na którym był wykonywany algorytm Split
-
-
u = "g" - "graphics mode" - wypisujemy n+2 znaki ascii zakończone enterem, następująco
-
zaczynamy "|"
-
każdy kolejny znak odpowiada kolejnemu elementowi w tablicy
-
elementy, które nie brały udziału w split : "-"
-
element dzielący ZAWSZE jako "#" (nawet jeżeli to początek lub koniec zakresu)
-
początek i koniec zakresu odpowiednio : "[" , "]" (o ile nie są elementem dzielącym)
-
reszta elementów biorących udział w Split-cie, jako "*"
-
kończymy "|"
-
Na końcu bezwzględna wartość różnicy między : * sumą float-ów sumowaną w liczbie float w kolejności wczytywania danych * sumą float-ów sumowaną w liczbie float w kolejności po posortowaniu danych
Różnica może być zarówno w notacji tradycyjnej jak i naukowej. (Wyniki będą wczytywane za pomocą "cin" z C++ , który powinien wczytać każdą z postaci)
element dzielący - ten którego indeks zwraca split, względem którego elementy są rozdzielone.
Limity
Pamięciowe: zmienne + rekurencja w QuickSortSplit + jedna tablica z floatami. (W rekurencji nie przekazujemy kopii tablicy !)
(Może też być jeszcze około n znakowa tablica).
Przykłady
test_g_n8err
Wejście
8 g 170141183460469231731687303715884105728 10141204801825835211973625643008 5070602400912917605986812821504 2535301200456458802993406410752 1267650600228229401496703205376 633825300114114700748351602688 316912650057057350374175801344 158456325028528675187087900672
Wyjście
|[******#| |#*****]-| |-[****#-| |-#***]--| |--[**#--| |--#*]---| |---[#---| 2.02824e+31
test_n_n15b3p50
Wejście
15 n 717897991954453806186496.000000 5287294009344.000000 38.940739 18435653959627151769600.000000 3486784512.000000 2299411.750000 135777959936.000000 312209419083448320.000000 1516.381104 12157665106179653632.000000 473428455559603945472.000000 89540784.000000 59049.000000 8017552890396672.000000 205891135602688.000000
Wyjście
0 14 14 0 8 13 0 1 7 2 7 7 2 4 6 2 3 3 5 5 6 9 11 13 9 10 10 12 13 13 0
test_g_n14sorted
Wejście
14 g 1 2 2.5 3 4 5 6 6.6 7 8 9 10 11 12
Wyjście
|#************]| |-#***********]| |--#**********]| |---#*********]| |----#********]| |-----#*******]| |------#******]| |-------#*****]| |--------#****]| |---------#***]| |----------#**]| |-----------#*]| |------------#]| 0
test_g_n20b4p8
Wejście
20 g 1.920093 2.519842 16.000000 2.094588 2.346921 1.792664 40.317474 1.741101 4.000000 3.428976 3.031433 6.349604 1.851749 9.189587 2.740702 2.208179 4.876055 65536.000000 256.000000 2.000000
Wyjście
|[**#***************]| |[#]-----------------| |----[**#***********]| |----[*#-------------| |----#]--------------| |--------[***#******]| |--------#**]--------| |---------[*#--------| |---------#]---------| |-------------[*#***]| |-------------#]-----| |----------------#**]| |-----------------[*#| |-----------------#]-| 0
test_g_n7err
Wejście
7 g 4194304 0.25 0.125 0.0625 0.03125 0.015625 0.0078125
Wyjście
|[*****#| |#****]-| |-[***#-| |-#**]--| |--[*#--| |--#]---| 0.5
test_n_n6err
Wejście
6 n 73786976294838206464 4398046511104 2199023255552 1099511627776 549755813888 274877906944
Wyjście
0 5 5 0 0 4 1 4 4 1 1 3 2 3 3 8.79609e+12
Uwagi odnośnie implementacji
Pamiętajcie testując przed wysłaniem rozwiązanie na ideone.com, aby zaznaczać opcję "private", co uchroni wasze rozwiązanie przed kradzieżą.
Nadanie odpowiedniego rozszerzenia pozwoli uniknąć złej detekcji języka.
W java, niezależnie jak nazywacie plik, klasa ma być Main, bo przed kompilacją źródła są kopiowane do pliku "Main.java". Usunięcie linii "package" pozwoli uniknąć dodatkowych problemów kompilacji.
Ten sam program może dawać różne wyniki na różnych maszynach, wynika to z architektury jednostek obliczeń zmiennoprzecinkowych. Część procesorów z serii celeron i niektórych innych tańszych ma np. większy błąd obliczeń. Proszę, więc się nie martwić jeżeli otrzymują państwo różne wyniki na różnych maszynach tym samym programem. Również użycie innej wersji kompilatora może wpłynąć na wyniki, gdyż optymalizacje kodu maszynowego mogą zmieniać kolejność operacji arytmetycznych, celem np. zwiększenia efektywności dostępu do pamięci, ale może skutkować innymi typami zaokrągleń przy operacjach zmiennoprzecinkowych. Więc, jeżeli program po aktualizacji kompilatora, zaczyna dawać inne wyniki, nie musi to być wcale zły objaw. Dla zainteresowanych, więcej informacji w linkach i literaturze.
Informacje
Liczby "Single precision", w C/C++ są to liczby typu float. (W wielu innych językach również pod tą samą nazwą - sprawdź w dokumentacji języka. Jeżeli twój język jak np. python implementuje typy zmiennoprzecinkowe przy użyciu liczb podwójnej precyzji, są dwa rozwiązania: emulować błędy jakie by wystąpiły w operacjach na liczba pojedynczej precyzji, albo zaimplementować własne dodawanie takich liczb (literatura: Hacker’s Delight) ).
Notacja naukowa to przy użyciu e. Jest w przykładach i typowa, większość parserów liczb zmiennoprzecinkowych w standardowych bibliotekach powinna je bezproblemowo wczytywać, tzn. funkcje wyczytujące liczby (np. "cin" w C++ , czy "scanf").
Ciekawa Literatura
Pomocna przy implementacji algorytmów i struktur danych:
-
"Algorytmika praktyczna - Nie tylko dla mistrzów", Piotr Stańczyk, wyd. Pwn;
A teraz literatura ciekawa, ponad program, dla entuzjastów:
"Praktyczne rozwiązania dla zaawansowanych programistów":
(budowa liczb zmiennoprzecinkowych, "ręczna" implementacja operacji na takich liczbach, i inne ciekawe wprawki implementacje, ciekawostki, sztuczki na poziomie operacji bitowych, walka o cykle procesora lub bajty pamięci i inne hackerskie zabawy):
-
"Uczta Programistów", Henry S. Warren, Jr. , wyd. Helion
-
(tytuł oryginału "Hacker’s Delight" wyd. published as Addison Wesley Professional, published by Pearson Education Inc.)
Natomiast do C++ :
-
"Exceptional C++ " oraz …
-
"More Exceptional C++ " by Herb Sutter, published as Addison Wesley Professional, published by Pearson Education Inc.