http://oi.edu.pl/html/zadania/oi16/prz.pdf
Nie mogę zrozumieć czemu prefiks jest taki a sufiks taki ....
Pomoże ktoś ?
0
0
Nie rozumiesz dlaczego dla ciągu x=(2,3,7,2,7,4,7,2,4) prefix p(x) = (2,3,7,2,7), a sufix s(x) = (7,2,7,4,7,2,4) ? To daj sobie spokój z programowaniem.
0
Praca musi być samodzielna!
Pamiętaj, że rozmiar pamięci dla tego zadania jest najmniejszy spośród wszystkich, więc optymalizuj rozmiar zmiennych oraz szybkość działania algorytmu bo o to chodzi w tym zadaniu! Powodzenia ;>
0
Wiem że praca musi być samodzielna, tylko tak jak Bogdans powiedział - nie rozumiem tego sufiksu i prefiksu z tego ciągu ...
0
bogdans napisał(a)
dla ciągu x=(2,3,7,2,7,4,7,2,4) prefix p(x) = (2,3,7,2,7), a sufix s(x) = (7,2,7,4,7,2,4) ? To daj sobie spokój z programowaniem.
Tak 'po ludzku' (?) definicje z pdfa można przetłumaczyć tak:
- z ciągu x usuń wszystkie powtarzające się liczby (zachowując kolejność reszty)
Po takiej operacji ciąg x = (2,3,7,4) - Znajdź index (czyli który z kolei jest) ostatniego elementu (czyli 4) w początkowym ciągu. Jest to 6 (licząc od 1).
- Prefix ciągu x składa się więc z jego 5 (index ostatniego - 1) początkowych elementów.
Analogicznie dla sufiksu, tylko tym razem usuwamy elementy idąc od końca - czyli po usunięciu powtarzających się, ciąg x będzie wygladał tak:
(3,7,2,4)
Znajdujesz indeks pierwszego elementu w ciągu początkowym (jest to 2).
Sufix ciągu x składa się więc z |x| - indeks elementów, a jego pierwszym elementem jest element o indeksie 3 (indeks pierwszego + 1) w ciągu początkowym.
@bogdans - fora są świetnym miejscem do leczenia kompleksów co?
@autree - w każdym zadaniu chodzi o szybkość działania algorytmu :D A limity są dla Javy, i tak na wyrost;w takim c++ w żadnym zadaniu nie trzeba więcej niż 16MB
0
@ogonek, uważasz, że osoba, która nie rozumie definicji z PDF-a powinna brać udział w OI ?
0
OK już oba załapałem. Dla testu jeżeli mamy ciąg ( ten sam ale bez 3 )
x=(2,7,2,7,4,7,2,4) to wyrazy nie powtarzające sie to {2,7,4}
prefiks(x)=(2,7,2,7)
sufiks(x)=(2,4)
dobrze zrobiłem?
@bogdans zadania i tak raczej nie wyśle na oi. Samo zrobienie ich to już dla mnie coś. Odpowiedzi szukałem na wiki ale nie zrozumiałem. W pdf-ie nie było nic napisane jak jest tam rozumiane sufiks i prefiks. Nauczyciela z infy pytałem ( po jakimś ekonomiku był) to też nie wiedział o co chodzi.
0
Po mojemu dobrze.
Jak nie było w PDF-ie, skoro było.
Chociaż po przyjrzeniu się czystej definicji (bez wyjaśniającego przykładu) dochodzę do wniosku, że definicja jest myląca, a nawet niepoprawna - słowo najdłuższy umieszczone jest w złym miejscu.
IMO definicja winna wyglądać tak:
prefiksem ciągu x nazywamy najdłuższy początkowy fragment p(x) tego ciągu, taki że W(x)<>W(p(x))