© 2013 dr inż. Jerzy R. Jaworowski, Instytut Teleinformatyki, Politechnika Krakowska im. Tadeusza Kościuszki

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 :

P

1

={1, 2, 3, 4} P

2

={1, 2, 4, 3} P

3

={1, 3, 2, 4} P

4

={1, 3, 4, 2} P

5

={1, 4, 2, 3} P

6

={1, 4, 3, 2} P

7

={2, 1, 3, 4 } ………. P

24

={4, 3, 2, 1}

Niech P

k

oznacza k-tą permutację w porządku leksykograficznym określonym jak wyżej (czyli 1 <= k <= n!).

W tekstowym pliku wejściowym <input_file> 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 P

k

należy znaleźć permutację ‘odwrotną’ P

o

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 <input_file>

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.