Najdluzszy podciag rosnacy

0

Witam!

Bylbym wdzieczny za wskazowki odnosnie algorytmu lub podanie kodu zrodlowego w pascalu procedury wyszukujacej najdluzszy podciag rosnacy.

pozdrawiam

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

1 użytkowników online, w tym zalogowanych: 0, gości: 1