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
0
Znalazlem taka definicje:
Podciagiem ciagu (Xn) lub ciagiem wyrwanym z ciagu (Xn) nazywamy kazdy ciag otrzymany z ciagu (Xn) poprzez skreslenie pewniej liczby jego wyrazow.
Zatem Legolas ma racje. W podanym ciagu:
4, 8, 1, 6, 2, 10, 23, 4, 35
mamy podciagi rosnace:
4, 8, 10, 23, 35
4, 8
23, 35
ale podciagiem rosnacym jest rowniez
4, 6, 10, 23, 35
0
Kiedyś pisałem ten program na jakies zaliczenie. Stary kod, dzisiaj pewnie wygladalby inaczej. Moduł crt2 to modul crt z Pascala przeznaczony dla szybkich kompow.
program podciag_rosnacy;
uses crt2;
var a:string;
ciagl,tmp:array [1..30] of longint;
pdcgi:array [1..30] of longint;
ilpd,mxdlpd,dlpd,n,i,j,k:longint;
function pt2(a1:longint):longint;
begin
if a1=0 then pt2:=1 else pt2:=pt2(a1-1)*2;
end;
procedure ten2bin(a1,n1:longint;var aa:string);
var i1:longint;
bb:string;
begin
i1:=0;aa:='';
repeat
begin
i1:=i1+1;
str((a1 mod 2),bb);
insert(bb,aa,i1);
a1:=(a1 div 2);
end until (a1 = 0);
if i1 < n1 then
repeat
begin
insert('0',aa,i1+1);
i1:=i1+1;
end until i1 = n1;
end;
begin
clrscr;
writeln('Program szuka najdluzszego podciagu rosnacego z danego ciagu.');
write('Podaj ilosc elementow ciagu: ');read(n);
for i:=1 to n do
begin
write('a[',i,']=');
read(ciagl[i]);
end;
mxdlpd:=0;ilpd:=0;
for i:=1 to pt2(n)-1 do
begin
ten2bin(i,n,a);
dlpd:=0;
for k:=1 to n do tmp[k]:=0;
for j:=1 to n do
begin
if a[j] = '1' then
begin
dlpd:=dlpd+1;
tmp[dlpd]:=ciagl[j];
end;
end;
for k:=1 to (dlpd - 1) do
begin
if tmp[k] >= tmp[k+1] then break;
if (k = dlpd - 1) then
begin
if mxdlpd = dlpd then
begin
ilpd:=ilpd+1;
pdcgi[ilpd]:=i;
end;
if mxdlpd < dlpd then
begin
mxdlpd:=dlpd;
ilpd:=1;
pdcgi[ilpd]:=i;
end;
end;
end;
end;
if ilpd > 0 then
begin
writeln('Ilosc najdluzszych podciagow rosnacych wynosi: ',ilpd);
writeln('Oto one:');
for i:=1 to ilpd do
begin
ten2bin(pdcgi[i],n,a);
for j:=1 to n do if a[j] = '1' then write(ciagl[j],' ');
writeln;
end;
end else writeln('W podanym ciagu nie wystepuja podciagi rosnace.');
repeat until keypressed;
end.
0
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
Może zanim walniesz jakąś głupotę, to sprawdzisz? Tak się składa, że znam definicję podciągu i chrzanisz od rzeczy za przeproszeniem.
0
A ten kod towarzysza paralityka ma coś wspólnego z tym ciągle ciągłym ciągiem podciągów, czy raczej z tym nieciągłym?
Ma to złożoność chyba rzędu 10(2n!)... 8-O
0
Program pisalem dawno temu. Idea jest taka ze sprawwdza wszytkie mozliwosci. Tak jak na logice do sprawdzania tautologii (kto robil tabelki to wie o co mi chodzi). Np. mamy ciag:
1, 4, 5, 6, 20, 8
i teraz tak liczba 1 w systemie binarnym ma reprezentacje 000001, tu oznacza ze wyjsciowy podciag bedzie mial 1 element wybrany. Jest to ciag numer 1 o elemencie (1).
Dalej np. liczba 46 (101110) oznacza ze wybieramy ciag (1, 5, 6, 20). Zero w postaci binarnej danej liczby oznacza, ze dany element ciagu glownego wywalamy (wykreslamy). Potem prog sprawdza czy jest to podciag rosnacy.
Nie wiem czy jest to najlepszy sposob na rozwiazanie tego problemu. Wiem ze dziala prawidlowo i wypisuje podciagi ktorych tak zawziecie broni Legolas.
0
matematyk paralityk napisał(a)
Wiem ze dziala prawidlowo i wypisuje podciagi ktorych tak zawziecie broni Legolas.
Legolas! No tak! Nie poznałem, bo taki... chropowaty.
Metoda dość szalona.
To można przecież rozwalić zwykłą podwójną pętlą, a powiem ci skrycie że są i bardziejsze na to sposoby! [green]
A ten krasnal włochaty to jak się zwał? :)