Wczytujesz liczby z jednego zestawu do tablicy . Tworzysz procedure która jako parametry bedzie miała indeks od którego zaczynasz szukać . W tej procedurze - - Bierzesz pierwsza liczbe ( pod tym indeksem ) i drugą ( index + 1 ) - wyznaczasz rożnice miedzy nimi = nazwijmy tą liczbe R . Teraz sprawdzasz czy różnica miedzy kolejnymi liczbami jest równa R . Jeżeli tak to sprawdzasz kolejną parę , aż do końca tablicy . Czyli różnice miedzy (Index+3) i ( Index+4 ), ........ Jak różnica nie jest równa R to wychodzisz z pętli i zwracasz jaka najdalej doszedł algorytm .
Tylko ty podałeś rozwiązanie na największy spójny podciąg. Tez na początku tak myślałem.Tylko w tym rzecz trzeba znaleźć największy podciąg i niemam pomysłu kompletnie jak to rozwiązać w dobrym czasie narazie mam tylko O(n*n*t) i z programowaniem dynamicznym nie ma nic wspólnego.
No to pozostaje zastosować taki myk - tworzysz tablice n*2001 ( - 1000..1000 ). W tablicy zaznaczasz różnice między bierzącym elementem danych wejściowych a wszystkimi kolejnymi do końca .
9 1 0 7 9 12 13 14 15 19
Analizę danych zaczynasz od ostatniego elementu danych wejściowych __| 0 1 2 3 4 5 6 7 8 ( index ) 19| 0 0 0 0 0 0 0 0 0 ...
Będzie ona wypełniona samymi zerami . Dla przed ostatniego elementu __| 0 1 2 3 4 5 6 7 8 ( index ) Iteracja 1 15| 0 0 0 0 1 0 0 0... 19| 0 0 0 0 0 0 0 0...
Jak nietrudno zauważyć - wszystkie dane w bieżącym wierszu w stosunku do wiersza poniżej , są przesunięte o różnice między wartościami kolejnych danych wejściowych ( wystarczy przekopiować odpowiednio przesuwając ) .
Złożoność dla brute force -- pewnie gdzieś w okolicy n*n/2*sqrt(n*2) . Załóżmy że pierwsza liczba to 100 a druga to 600 to kolejny element takiego ciągu już wychodzi po za zakres 1000 i podciąg dla różnicy 500 będzie miał co najwyżej 2 elementy . Jeżeli znalazłeś już podciąg o długości 50 elementów to w dalszych poszukiwaniach nie ma sensu rozpatrywać większej różnicy miedzy elementami niż 20 .
Moim zdaniem trochę złe podejśćie, nawet a może przede wszystkim w procesie uczenia się programowania i algorytmiki. Masz do rozwiązania zadanie-problem i to Ty decydujesz jaką metodą starasz się je rozwiążać/ywać. Potem to może faktycznie, kierownik powie, że masz to zrobić w taki i taki sposób, taką lub inną metodą i już. Teraz masz jeszcze wolność i swobodę wyboru. Więc jeżeli tak bardzo chcesz tu masz zadania otagowane programowanie dynamiczne: http://www.spoj.com/problems/tag/dynamic-programming7 ale czy są fajne, nie mam ani bladego ani zielonego pojęcia.
To nie znaczy, że musisz je tak rozwiązywać - ja zrobiłem zwykłym brutem z małą optymalizacją - ale trudno to nazwać, że zrobiłem w PD.
Tam raczej nie ma wszystkiego, więc może najlepiej zapytać prowadzącego?
PS
Dzień bez wtopy to dzień zmarnowany Nie rozumiem twojej metody - rozwiązałeś w taki sposób to zadanie?
Dla dwu elementowego ciągu [np 0, 1000 lub 1000, 0] tak - ale czy dla dwóch warto sprawdzać? Dla trzech elementów max diff [[0,500,1000] == 500 lub -500, ale może też to szybko sprawdzić, a tablicę zacząć budować dopiero dla ciągów większych niż ..... i wtedy też mniejsza tablica lub tablica dynamiczna - mapa itd. Nie widzę, jak twoja tablica zadziała dla ciągu np 1 1 1 1 1 2 3 .... lub 3 3 3 3 1 1 1 1 1 itd Także, gdy jednakowe różnice "zazębią" się: np (0 4 6 10 ...) 6 - 0 = 6 i 10 - 4 = 6 ?
No tak, ale jeżeli wybrane jest zadanie już z konkretnego działu to domyślnie pomysł na zadanie i jego rozwiazanie powinno być z tego wypadku PD. Każde zadanie powinno dać się też w inny sposób. W tym zadaniu trudno znaleźć pomysł na PD. Oczywiście te zadanie nie należy do łatwych, ale chciałbym je zrobić na PD.
Dla takich danych algorytm zawiedzie -- trzeba go udoskonalić . W tablicy zamiast trzymać informacje że dana różnica wystąpiła trzeba przechowywać informacje o najdłuższe ścieżce podciągu ( dla danej różnicy ) jaka dotychczas wystąpiła .
For L1=N-1 downto 1 do Begin
For L2=L1+1 to N do Begin
Rest := Input[ oL1 ] - Input[ oL2 ];
If Dat[ L1 ][ Rest ] <= Dat[ L2 ][ oRest ] Then Dat[ L1 ][ Rest ] = Dat[ L2 ][ Rest ] +1;
End;
End;
Nie rozwiązywałem tego zadania ale ciąg stały to też jest ciąg arytmetyczny z różnicą równą zero.Tak jest w tablicach matematycznych do szkół średnich.
W poradniku matematyczny dotyczącym już bardziej zaawansowanej matematyki (red. Dziubiński i Świątkowski) nie znalazłem wprost odniesienia do ciągu stałego, ale ciąg stały spełnia założenia definicji.
W podręcznikach zaawansowanej matematyki (przynajmniej w tych do których zaglądałem) nie znalazłem w ogóle odwołań do ciągu arytmetycznego. Jest dość zrozumiałe gdyż na studiach ciągiem arytmetycznym nikt się zajmuje.
A jak jest tutaj?
Może Autor wyłączył ciąg stały jako trywialny?
Moim zdaniem nie byłoby to dobre rozwiązanie, ale też nie robiłbym z tego tragedii.
W każdym razie to Autor ma władzę
Napisałem, że nie zrobiłem tego zadania i faktycznie, na podstronie WSDOCPP, nie zrobiłem. Ale to zadanie jest też na stronie pl.spoj i tam mam je zrobione.
Co do twojego rozwiązania. Dla ciągu dłuższego niż dwuelementowy, minimalna długoć to 2.
Masz w swoim teście wstawioną złą wartość t i może coś jeszcze? W jednym teście masz wynik 0 - a i w ostatnim - jaki dodałem też jest żle: https://ideone.com/8QqZMB3
Faktycznie, był jezcze jeden błąd w teście, poprawiłem i teraz jest ok.
Tzn, troche lepiej.
Wydaje mi się, że Twoj kod ma problem z powtarzającymi się liczbami. No i gdy juz jakas mamy długość, to nie szukamy do n-1, tylko raczej n-dl, czy może n-dl-1?
for(int j=i+1;j<n;j++) // szukamy ciągu arytmetycznego kończącego się na j i zaczynającego się na i
///a w środku tej pętli zmieniasz sobie j, więc Sama rozumiesz co się dzieje? :
j = ..... mp[next][k]; // uaktualniamy j na indeks kolejnego elementu ciągu
No i za wolno, dużo za woooooooolno. Pomyśl:
Taki ciąg:
1000
4 4 4 4 4 … 4 4 4 4 4 4 4 4 4
Mimo, że już po pierwszej iteracji program znajdzie najdłuższy ciąg = 1000, to i tak, będzie dalej szukał coraz to krótszych ciągów.
Podobnie dla takiego ciągu:
1000
1 2 … 999 1000
I dla podobnych do powyższych, lekko “zanieczyzczonych” wtrąconymi, dowolnymi liczbami.
Wspominałem o tym 3 posty wyżej.