Witam. Mam za zadanie wymyślić algorytm który ciąg z literami P,I,E,S uporządkuje w ten sposób aby utworzyć wyrazy PIES. Np mam PPIIEESS i musimy ułożyć PIESPIES. Do dyspozycji mam tylko jeden typ przełożenia - czwórka(dokładnie i tylko czwórka) znaków obok siebie na koniec ciągu (wiadomo nie wszystkie układy będzie można w ten sposób ułożyć - te pozostawiamy bez zmian). Jedyne co przychodzi mi na razie do głowy to brute force czyli sprawdzenie liter - jesli jest coś nie tak to przekładamy na koniec, ale tutaj wydajność leży i kwiczy. Jakby był ktoś tak miły i nakierował mnie na jakieś inne,lepsze rozwiązanie to byłbym bardzo wdzięczny. Proszę o pomoc. Pozdrawiam.
0
0
Odświeżam.
0
Nie do konca rozumiem to twoje przełożenie. To znaczy ze mając ciąg YXXXXY mogę wykonać przełożenie YYXXXX? A jakie jest kryterium? Mamy znaleźć jak najwięcej psów? Mamy mieć na koniec spójny podciag psów?
0
Tak, dokładnie tak ma to wyglądać. Z dowolnego miejsca moge przełożyć naraz tylko ( i dokładnie ) 4 litery na prawy koniec całego ciągu. Algortym ma poukładać tak litery aby powstał "ciąg psów" : PIESPIESPIESPIES. końcówka ( gdy np mam 6 liter - 2 dodatkowe ) nie musi być sortowana. Niby tylko jeden ruch do dyspozycji a cięzko cos wymylic : (
0
Wygląda to trochę jak układanie kostki rubika. Popatrzyłbym na algorytmy do jej rozwiązywania i spróbował znaleźć analogię.
0
A mógłbyś to jakoś porównać , wskazać podobieństwa ? Bo ja jakoś nie zabardzo widzę tą analogie :P
0
W kostce rubika też mozesz przesuwać pola tylko całym blokiem po N elementów. Analogicznie tak jak i tutaj możesz dokonać przesunięcia wybranego elementu z takiego bloku, ale przesuwając jednocześnie sąsiadujące z nim elementy. Nie ma tu jakiejś bardzo wyraźnej analogii, ale problemy z którymi trzeba się borykać w obu algorytmach wydają się dośc podobne i warto zerknąć jak zostały rozwiązane z kostce rubika.
0
Ok dzięki będę próbował cos poczytać. Jakby ktoś miał jakiś inny pomysł to pomoc zawsze mile widziana : ).
0
Czy zadanie polega na ułożeniu czy na odpowiedzi czy się da?
0
Na ułożeniu tak wielu wyrazów PIES obok siebie ilu się da przy użyciu tego jednego ruchu.
1
@Artur12 nie rozumiesz pytania. Co ma byc wynikiem algorytmu? Ciąg ulożonych wyrazów? Lista kroków w jaki sposób należy układać? Informacja ile psów można uzyskać? Informacja czy da się ułożyć cały ciąg czy nie (z dokładnością do końcówki)? I co jest kryterium poprawności? Czy rozwiązanie:
PPIES
jest poprawne? Czy psy muszą iśc od lewego końca? A rozwiązanie
PPIESP
? Czy jednak muszą mieć jakikolwiek "koniec"? A rozwiązanie
PIESPPIES
? Czy psy muszą tworzyć spójny podciąg?
0
Wynikiem algorytmu ma być ułożony ciąg wyrazów PIES jeden po drugim, bez przerw ,od lewej do prawej(o ile to w ogóle możliwe bo np jeśli mamy taki ciąg wejściowy PEIS to już z nim nic nie zrobimy). Ewentualne nadmiarowe litery mają być na końcu ciągu z prawej ( ich kolejność może być dowolna) więc ciągi wynikowe takie jak : PPIES czy PIESPIPIES nie są poprawne. Poprawne natomiast są : PIESP , PIESPIESIP (PIESPIESPI). Więc mamy najpierw wszystkie możliwe wyrazy PIES a dopiero potem "śmieci".
0
Jest taka gra http://pl.wikipedia.org/wiki/Pi%C4%99tnastka_%28uk%C5%82adanka%29
Da się ją złożyć o permutacja jest parzysta: http://www.matematyka.pl/262940.htm
Tu będzie to samo.
Czyli wypisujesz tyle razy ile trzeba PIES, natomiast pozostałe przemieszczasz tak aby zrównoważyć tą parzystość.
Oczywiście trzeba nieco to przemyśleć, wszak przesuwamy po 4-ry.
0
Posiedziałem troche ale jakoś nie mogę przełożyć tej gry na swój problem. Po 1 to tam można przekładać od 3 do 1 elementu ( u mnie równo 4 ) i to nie z kazdego miejsca ( u mnie mozna przelozenie zrobic z kazdego na koniec ). Po 2 tam mam ułożenie 2d, u siebie mam jeden wymiar. Więc jakoś tego nie widzę :( Mógłby ktoś mi to łopatologicznie wyjaśnić lub podać jakiś inny możliwy sposób takiego rozwiązania ?
0
Odswiezam. Dodam tylko, że algorytm nie musi być jakiś efektywny ale musi to być coś lepszego od zwykłego brute forca. Aktualnie nie wiem nawet jaki mógłby być warunek końca dla takiego algorytmu, tzn skad mam wiedzieć że ułożyłem już maksymalną liczbę słów z podanych liter :(
0
Jako że dalej borykam się z tym problemem to mam takie pytanie bardziej ogólne. Ile jest wszystkich możliwych ciągów ( niekoniecznie różnych - tzn ten sam ciąg otrzymany w inny sposób jest rozróżnialny ) jakie możemy otrzymać przy pomocy tej operacji dla ciągu rozmiaru n ?
dla n = 4 mamy 1
dla n = 5 mamy 5 ( wiadomo ze dla PPPPP bedzie tez 1 ale w ogólności 5 )
dla n = 6 ... ?