Witam
Piszę swój projekt dotyczący palindromów, i napotkała mnie pewna trudność. Otóż po drodze potrzebuje wymyślić algorytm, który dla palindromu który jest wielokrotnością innego palindromu, zwróci ten palindrom składowy, np dla 121121121 zwróci 121, dla 1111 zwróci 1, a dla kajak zwróci kajak, bo ten nie składa się z innych palindromów. Mam nadzieję, że napisałem to w miarę czytelnie. Problem wydawać się może dość nietypowy, zwłaszcza, ciężko znaleźć dla takiego tworu złożoność obliczeniową, która w miarodajny sposób określałaby realną prędkość działania.
PZDR
0
0
Jaki warunek ma decydować, że dla ciągu 1111 należy zwrócić 1, a nie 11? Ma być zwracany najkrótszy palindrom składowy?
0
Myślę, że sprawa jest prosta. Jak się mylę, to mnie poprawcie.
Liczysz długość całego wyrazu do sprawdzenia, powiedzmy 121121121 - długość = 9. I teraz sprawdzasz czy ta długość jest podzielna przez jakąś liczbę bez reszty. Liczba ta, nazwijmy ją k, oczywiście zawiera się w przedziale [2, długość]. W momencie gdy długość % k == 0, dzielisz wyraz na k równych części. I rekurencyjne sprawdzasz każdą z tych części. W twoim przypadku k == 3, zatem masz 121 121 121.
Dalej sprawdzasz wyraz 121, tutaj k == 3 == długość, więc jedziesz z typowym algorytmem do sprawdzania palindromów. 121 jest palindromem, więc otrzymujesz to co chcesz :)
Jeśli chodzi o przypadek typu 1111, to takim palindromem składowym może być i 11, i 1. Pytanie tylko, czy można uznać jednoznakowy wyraz za palindrom? Niby można, ale co to za palindrom :P
0
Miałem prawie taki sam pomysł i dlatego zadałem pytanie wyjaśniające. Czy rozpocząć sprawdzanie od najmniejszego dzielnika czy od największego? Ja bym rozpoczął od sprawdzenia czy cały ciąg jest palindromem, jeśli nie jest to dalsze sprawdzanie można opuścić.
Jeżeli uważasz, że 1 to trochę niepełnosprawny palindrom, to rozważ ciąg 111111. Palindrom składowy, to 1, 11 czy 111?
0
Dzięki wszystkim za dotychczasowe pomysły.
Po pierwsze chodzi o najmniejszy taki palindrom, a więc dla 1111 zwrócić powinno 1
Po drugie nie trzeba sprawdzać, czy cały, ten długi, wyraz jest palindromem, bo to jest powiedziane już w zadaniu, przydałoby się tylko tą wiedzę jakoś sprytnie wykorzystać
Jeśli chodzi o podane rozwiązanie,to też myślałem w tym kierunku, tylko wydaje mi się, że można by wymyślić coś, co rozwiąże problem szybciej, aczkolwiek pewności nie mam. Druga sprawa to w jaki sposób oszacować czas działania dla tego algorytmu.
Można przyjąć doświadczalnie, że liczba liczb podzielnych przez n wynosi średnio ok 0,12n (np dla 20 mamy 2,4,5,10, czyli 4/20n=1/5n, ale dla 21 mamy tylko 3 i 7, więc 2/21n). Dalej pomnożyć tą liczbę przez liczbę sprawdzeń czy słowo jest palindromem, czyli n/2, ale tutaj powstaje problem, polegający na tym, że sprawdzenie każde ze sprawdzanych słów ma inną długość. Dlatego nie bardzo wiem jak można by jednoznacznie oszacować tą złożoność. Jeszcze raz dzięki.
PZDR