[Pascal] program liczący długość najdłuższego podciągu

[ct985]

Jak napisać program który dla danej tablicy uporzadkowanej n liczb całkowitych zwraca długosc
najdłuzszego podciagu arytmetycznego tego ciagu o róznicy 5? Nie mam pojęcia jak zliczyć dlugość kilku ciągów w tablicy żeby porownać ich dlugość?

Kod: Zaznacz cały

program dlugosc_najdl_podciagu;
uses crt;

var     tablica:array[1..6] of integer;
        i:integer;

function dlugosc(A:array of integer):integer;
var     l,i:integer;
begin
        l:=1;
        for i:=1 to 5 do
        begin
                if ((A[i+1] - A[i])=5) then l:=l+1;
        end;
        dlugosc:=l;
end;

begin
        writeln('Podaj 6 liczb');
        for i:=1 to 6 do
        readln(tablica[i]);
        writeln('Dlugosc= ', dlugosc(tablica));
        readln
end.

[adambak]

drobne modyfikacje w treści mogą bardzo wpłynąć na złożoność i trudność rozwiązania..
czy dobrze rozumiem, że fragment

tablicy uporzadkowanej n liczb całkowitych

zapewnia, że tablica będzie posortowana rosnąco? czy taka jest specyfikacja tego zadania? widzę, że dane są wprowadzane przez użytkownika, ale nie widzę nakazu wprowadzania liczb rosnąco, stąd moja niepewność..

-- 19 lut 2012, o 18:41 --

w sumie to jednak nie wiem po co mi był ten warunek na posortowaną tablicę..

rozwiązanie:

Kod: Zaznacz cały

program dlugosc_najdl_podciagu;

const N=6;
      R=5;

var  tablica:array[1..N] of integer;
     i:integer;

function dlugosc(A:array of integer):integer;
var dl,akt,j,najdluzszy:integer;
begin
  najdluzszy:=0;

  for i:=1 to N do begin
    dl:=1; akt:=A[i];
    for j:=i+1 to N do 
      if A[j]-akt=R then begin
        akt:=A[j];
        dl:=dl+1;
      end;
    
    if dl>najdluzszy then najdluzszy:=dl; 
  end;

  dlugosc:=najdluzszy;
end;

begin
  writeln('Podaj ',N,' liczb:');
  for i:=1 to N do
    readln(tablica[i]);

  writeln('Dlugosc= ', dlugosc(tablica));
end.

metoda nie jest wyrafinowana, ale rozumiem, że lepszej chyba nie trzeba.. podciąg jest niekoniecznie spójnym fragmentem ciągu stąd potrzebne są aż dwie pętle.. przeglądamy każdy możliwy podciąg o danej własności (od tego jest pętla for - sprawdzamy każdy możliwy początkowy wyraz ciągu).. dalej w pętli while już prosty warunek czy aktualnie sprawdzana wartość nadaje się do tego ciągu.. jeśli tak to uaktualniamy ostatni wyraz ciągu (zmienna akt, potrzebne do sprawdzania reszty liczb) i jego długość.. na koniec wybieramy i zwracamy najdłuższy z tych podciągów.. koniec