Witam!
Bylbym wdzieczny za wskazowki odnosnie algorytmu lub podanie kodu zrodlowego w pascalu procedury wyszukujacej najdluzszy podciag rosnacy.
pozdrawiam
0
0
masz to w c++ chyba na pascala nie bedzie problemu przerobić co?
szuka naiwiekszego podciagu i wypisuje z ulu sie składa elementów;
ty chyba nie bedzie problemu aby go jesczez wyswietlić bo wystarczy dodać jedna zmiennę pamietająca początek tego podciagu i mając jego długość i początek mozna go wyswietlić. jesli sobie nie porardzisz z przerobieniem niech ktoś tu to zrobi [browar]
#include <iostream.h>
#include <string.h>
#include <stdlib.h>
main()
{
randomize();
float ciag[20];
int a;
int b,c,max;
for(a=0;a<=19;a++) ciag[a]=random(100);
cout<<"wylosowane liczby ciagu : "<<endl;
for(a=0;a<=19;a++) cout<<ciag[a]<<", ";
cout<<endl;
c=0;
max=0;
for(b=1;b<=19;b++)
{
if (ciag[b]>ciag[b-1]) c=c+1;
else c=0;
if (max<c) max=c;
}
cout<<"maxymalny podciag rosnacy ma = "<<max+1<<endl;
}
0
var t : array[1..N] of Integer; // lub string jeśli chodzi o znaki
ix := 1; // ix - pozycja najdłuższego
lmax := 1;
l := 1;
for i := 2 to N do
if t[i] > t[i-1] then inc(l)
else begin
if l > lmax then begin lmax := l; ix := i end;
l := 1;
end;
if l > lmax then begin lmax := l; ix := N+1-l end
else dec(ix, l);
0
Pozostaje jeszcze kwestia, czy autorowi chodzi o maksymalny SPÓJNY podciąg rosnący (wasze kody są rozwiązaniem tego problemu), czy o najdłuższy dowolny podciąg.
W tym drugim wypadku, jest to sztandarowy przykład zastosowania programowania dynamicznego. Jeśli zrozumiesz idee tej techniki, to bez problemu rozwiążesz ten problem. Google ci pomoże :P
0
Pawel200x.5 napisał(a)
Pozostaje jeszcze kwestia, czy autorowi chodzi o maksymalny SPÓJNY podciąg rosnący (wasze kody są rozwiązaniem tego problemu), czy o najdłuższy dowolny podciąg.
W tym drugim wypadku, jest to sztandarowy przykład zastosowania programowania dynamicznego. Jeśli zrozumiesz idee tej techniki, to bez problemu rozwiążesz ten problem. Google ci pomoże :P
wiadomo, że o to pierwsze chodzi bo to drugie to wtedy nie jest szukamiem podciągu tylko tworzeniem nowego ciągu
0
Autor pytania nie precyzuje, czy chodzi o spójny podciąg, więc w domyśle, chodzi o dowolny.
A rozwiązanie tego problemu (tak przy okazji): http://www.algorithmist.com/index.php/Longest_Increasing_Subsequence
0
mefistofesesafilus napisał(a)
wiadomo, że o to pierwsze chodzi bo to drugie to wtedy nie jest szukamiem podciągu tylko tworzeniem nowego ciągu
Nie żebym się czepiał, ale definicja podciągu wcale nie oznacza sekwencji elementów następujących w oryginalnym podciągu po sobie.
0
Adam.Pilorz napisał(a)
Nie żebym się czepiał, ale definicja podciągu wcale nie oznacza sekwencji elementów następujących w oryginalnym podciągu po sobie.
Nie żebym się czepiał, ale jakoś nie wyobrażam sobie dowolnego podciągu rosnącego w ciągu.
Co to właściwie miałoby być?
Suma tych 'ciągłych podciągów' rosnących, czy jak? [???]
0
Dowolne elementy, których indeksy i wartości są ustawione rosnąco. Przykładowo:
4, 8, 1, 6, 2, 10, 23, 4, 35
Podciągiem rosnącym w takim ciągu może być:
4, 6, 10, 23, 35.
Taka jest definicja podciągu.
0
Adam.Pilorz napisał(a)
Dowolne elementy, których indeksy i wartości są ustawione rosnąco. Przykładowo:
4, 8, 1, 6, 2, 10, 23, 4, 35
Podciągiem rosnącym w takim ciągu może być:
4, 6, 10, 23, 35.
Taka jest definicja podciągu.
hehe własnie utworzyłeś nowy ciag a nie znalazłeś podciag
podciag ciagu musi byś spójny bo by nie był podciagien
czyli
2,10,23 to max podciag rosnacy
a
4, 6, 10, 23, 35. to ciag rosnący utworzony (zgodnie z jakąś regółą ; czyli w tym przypadku wybranie elementów rosnących) z ciagu głównego i rownie dobrze mozna by było wszystko posortować i wypisać i też by to był ciag utworzony z innego ciagu.
podciagu nie można tworzyć - jesli się tworzy to nie można nazwać podciagiem