Najdlhšia postupnosť rôznych čísel – Pascal – Fórum – Programujte.com

Zdravím, v Pascale potrebujem nájsť najdlhšiu postupnosť rôznych prvkov poľa. Stačí mi zistiť dĺžku a začiatok.

Počet prvkov je známy.

Napríklad z pola: 1 2 1 2 3 4 5 5 6  - dĺžka 5, začiatok 3.

Skúšal som rôzne cykly, ale neviem ako zisťovať, či je postupnosť najdlhšia možná.

Ako by to bolo vhodné urobiť tak, aby bola nájdená vhodná postupnosť?

Ďakujem za odpovede

- podminka b - a == 1
- pokud neni splnena, je konec posloupnosti
- pokud je splnena, je to zacatek nebo uz probihajici posloupnost
- odectes konec - zacatek a mas delku
- pokud je delka vetsi nez max, tak ulozis zacatek, konec a max delku

v js by se to napsalo jako 

function check(a,b)
  {
  return b - a == 1;
  }

arr = [1, 2, 1, 2, 3, 4, 5, 5, 6];
out = {start:0, end:0, max:0};
tmp = {start:0, end:0, max:0};
li = arr.length - 1;
for (i=0; i<li; i++)
  {
  if (check(arr[i], arr[i+1]))
    {
    if (tmp.start == 0)
      {
      tmp.start = i;
      }
    }
  else 
    {
    tmp.start = 0; 
    tmp.end = i;
    if (tmp.max < tmp.end - tmp.start)
      {
      out.start = tmp.start;
      out.end = tmp.end;
      out.max = tmp.max;
      }
    }
  }
alert(out.toSource())

Melo by to resit i pripad, kdy je v poli jen 1 prvek. Ale kdyz je pole prazdne, tak to da chybne vsechny nulove v out. Ale urcite by to slo napsat jednoduseji.

#2 peter
Ďakujem, ale asi to môj problém nerieši.

Postupnosť nemusí byť rastúca, len sa v nej nesmú opakovať prvky.

Napr. 1 50 1 4 7 7 9 50 47 9

Počet 4, začiatok 2 alebo 6

#3 Jozef01

Rozdel si to na dve casti:

Udělej funkci DelkaPosloupnosti() která ti spočítá délku posloupnosti od zadaného indexu do konce pole.
(pro tvuj priklad a projiti pole od prvni polozky by mnela vratit hodnotu 2.
 po projiti od druhe polozky do konce pole by mnela vratit hodnotu take 2, pak 5,..)

Potom tu DelkaPosloupnosti zavolas ve for-u tak abys zjistil delku posloupnosti od prvni pozice v poli, od druhé, ... až do konce pole. V kazdem kroku porovnas vracenou delku a pokud je delsi nez budes mit zapamatovano, tak si ji zapamatuj spolu s aktualni pozici v poli pro kterou byla spocitana.

Zamnerne jsem to nenapsal jako navod, aby ses o to mohl pokusit sam.
Take to neni zrovna ten nejefektivnejsi algoritmus jak to udelat, spis naopak - je to reseni hrubou silou.
Je ale mozne to reseni rozvinout a optimalizovat.
(napr ukoncit pocitani pokud je zbyvajici delka kratsi nez nejdelsi nalezena posloupnost. Nebo třeba ve vnějším cyklu neprocházet pole striktne po 1, ale vyuzit toho ze vnitrni funkce najde index (ten prvni, ne nakonci) hodnoty ktera se opakuje.)
 

...a ta funkce DelkaPosloupnosti by mohla pracovat buď přes množinu (set of ...), do které by si zpracovaná čísla ukládala, nebo zpětným procházením od aktuálního prvku k počátečnímu. První způsob je podstatně efektivnější, ale v některých překladačích je omezený na osmibitová celá čísla.

#1 Jozef01, hoď sem svůj kód, ať můžeme radit aspoň trochu cíleně.

#5 Mircosoft
Tak toto je môj pokus, ale niečo tam je ešte zle.

for i:=1 to n do begin
  for j:=i+1 to n do if p[j]=p[i] then begin
    aktualnadlzka:=j-i-1;
    break;
    end;
  if aktualnadlzka>dlz then begin
    dlz:=aktualnadlzka;
    poz:=i;
    end;
  end;

Žiadny ďalší nápad?

Ďakujem

#8 gna
Ďakujem všetkým, problém vyriešený.