© 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
