Witam, chciałbym się zwrócić do was z prośbą o pomoc w rozwiązaniu pewnego na pierwszy rzut oka dość prostego problemu :).
Moim zadaniem jest napisanie dwóch algorytmów, które wykonywały by sortowanie w takim zadaniu:
Dane jest n beczek, znajdujących się na równi pochyłej. Beczki są w jednym z trzech kolorów - czerwone, niebieskie lub zielone. Do przenoszenie beczek z dowolnego miejsca równi pochyłej służy dźwig który może przenosić nie mniej i nie więcej niż 3 beczki jednocześnie. Beczki mogą być przenoszone tylko na górę równi pochyłej - nad pozostałe beczki. Przy założeniu, że n >= 3 i ilość zielonych >= 3, należy posortować je korzystając z dźwigu tak, żeby na dole równi były same czerwone, po środku równi same niebieskie, a na górze równi zielone.
Znana jest ilość beczek poszczególnych kolorów.
Jeden z tych algorytmów napisałem i o ile się nie mylę jest dobry:
- Wyszukuje pierwsze miejsce od doły, na którym jest beczka, której nie powinno tam być - jeżeli nie ma takiej pozycji (beczki są w dobrej kolejności) to koniec.
- Wyszukuje beczkę odpowiedniego koloru, która jest w odległości%3 = 0 od tej pozycji - jeżeli nie ma takiej beczki wyszukuję inną beczkę tego koloru i przenoszę ją w taki sposób* na górę, żeby odległość od zadanej pozycji była bez reszty podzielna przez 3.
- Wykonuje odpowiednią ilość przeniesień beczek znajdujących się między zadaną beczką, a beczką docelową.
- Wracam do 1.
*sposób ten zależy od odległości beczki do zadanej pozycji i odległości do szczytu równi (a raczej reszty z dzielenia przez 3 tych odległości) - został przeze mnie dopracowany i jest dobry, więc nieistotny :P
Natomiast na drugi algorytm nie mam pomysłu ... myślałem że można po prostu na chama przenosić beczki trójkami poczynając od pierwszej niepasującej beczki, ale taki naiwny algorytm zapętla się dla cyklicznych ciągów beczek.
Czy ktoś ma jakąś podpowiedź? :)
Z góry dziękuję :)