Praca domowa 08  calc
Termin zwrotu : 04 czerwca godz. 23.00
Zadanie uznaje siÄ™ za zaliczone, gdy praca oceniona zostanie na co najmniej 6 pkt.
Dany jest zbiór liczb naturalnych P = {1, 2, 3., & ., n-1, n}. Rozważmy wszystkie n-elementowe permutacje utworzone z elementów
zbioru P. Wszystkich możliwych permutacji jest n!
Załóżmy, że permutacje zbioru P zachowują porządek leksykograficzny, tj. kolejne permutacje tworzone są wg zasady, iż w pierwszej
kolejności dokonujemy wymiany elementów na prawym końcu ciągu, posuwając się w miarę tworzenia kolejnych od prawej do lewej, czyli
przykładowo dla n = 4 uporządkowany leksykograficznie ciąg permutacji wyglądać będzie następująco :
P1={1, 2, 3, 4} P2={1, 2, 4, 3} P3={1, 3, 2, 4} P4={1, 3, 4, 2} P5={1, 4, 2, 3} P6={1, 4, 3, 2} P7={2, 1, 3, 4 } & & & . P24={4, 3, 2, 1}
Niech Pk oznacza k-tą permutację w porządku leksykograficznym określonym jak wyżej (czyli 1 <= k <= n!).
W tekstowym pliku wejściowym zapisany jest w formacie swobodnym ciąg kolejnych liczb całkowitych
stanowiących pewną permutację, a więc przykładowo:
7 4 2 5 1 6 3
Dla podanej permutacji Pk należy znalez
ć permutację  odwrotną Po a następnie wyznaczyć (obliczyć) różnicę indeksów k-o, gdzie k oraz
o określają ich położenie w porządku leksykograficznym. Algorytm rozwiązania NIE MOŻE korzystać z mechanizmu opartego na obliczaniu
kolejnych permutacji w porzÄ…dku leksykograficznym w celu znalezienia indeksu k.
Przykładowo dla n = 4 niech badaną permutacją będzie {1,4,3,2}. Wtedy k = 6. Permutacja  odwrotna ma postać {2,3,4,1}, czyli o = 10.
Wynikiem działania programu jest zatem wartość -4.
Program ma być zapisany wyłącznie w dwóch plikach : Calc.java zawierającym implementację mechanizmu wyznaczania indeksu k,
oraz Main.java  zawierającym programem główny. Program nie może korzystać z jakichkolwiek bibliotek zewnętrznych..
Proces kompilacji musi być możliwy z użyciem komendy
javac  Xlint Calc.java Main.java
Uruchomienie programu winno być możliwe z użyciem komendy
© 2013 dr inż. Jerzy R. Jaworowski, Instytut Teleinformatyki, Politechnika Krakowska im. Tadeusza KoÅ›ciuszki
java Main
Wynik końcowy (w strumieniu wyjściowym nie powinny pojawiać się jakiekolwiek inne elementy  np. wydruki kontrolne) działania
programu musi zawierać pojedynczą liczbę określającą wartość poszukiwanego indeksu, a więc np.
Indeks : 31
Wymagania :
" Klasa implementująca problem winna zostać zdefiniowana w pliku Calc.java
" Klasa implementująca mechanizm program główny (metoda main) winny być zdefiniowane w pliku Main.java
" W pliku README.pdf winien być zawarty szczegółowy opis organizacji struktur danych oraz szczegółowy opis zastosowanego
algorytmu.
" Proces obliczenia rozwiązania winien się kończyć w czasie nie przekraczającym 2 min (orientacyjnie dla typowego notebooka). Po
przekroczeniu limitu czasu zadanie będzie przerywane, i traktowane podobnie jak w sytuacji błędów wykonania (czyli nie podlega
dalszej ocenie).
Sposób oceny :
" 1 pkt  Kompilacja : każdy z plików winien być kompilowany bez jakichkolwiek błędów lub ostrzeżeń (w sposób omówiony wyżej)
" 1 pkt  Wykonanie : program powinien wykonywać się bez jakichkolwiek błędów i ostrzeżeń (dla pliku danych wejściowych zgodnych
z wyżej zamieszczoną specyfikacją) z wykorzystaniem omówionych wyżej parametrów linii komend
" 2 pkt  README : plik README.pdf dokumentuje w sposób kompletny i właściwy struktury danych, oraz opis przyjętej koncepcji
algorytmu całkowania z wykorzystaniem techniki Monte Carlo
" 1 pkt  Komentarze wewnętrzne : czy program jest skomentowany w sposób zapewniający zrozumienie jego działania, oraz
wyjaśniający warunki, które muszą zachodzić przed i po wykonaniu każdej z funkcji.
" 1 pkt  Styl kodowania : czy funkcji i zmienne posiadają samo-wyjaśniające nazwy ? Czy podział na funkcje ułatwia czytelność i
zrozumiałość kodu ? Czy funkcje eliminują (redukują) powtarzające się bloki kodu ? Czy wcięcia, odstępy, wykorzystanie nawiasów itp.
(formatowanie kodu) są spójne i sensowne ?
" 4 pkt  Poprawność algorytmu : czy algorytm został zaimplementowany poprawnie a wynik odpowiada prawidłowej (określonej
zbiorem danych testowej) wartości.
© 2013 dr inż. Jerzy R. Jaworowski, Instytut Teleinformatyki, Politechnika Krakowska im. Tadeusza KoÅ›ciuszki