Najdlhšia postupnosť rôznych čísel – Pascal – Fórum – Programujte.com
 x   TIP: Přetáhni ikonu na hlavní panel pro připnutí webu

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

 

Toto vlákno bylo označeno za vyřešené — příspěvek s řešením.
Spuštěný nový filmový web Filmožrouti.cz — vše o Avengers, Pacific Rim, Thor, Star Wars…
Jozef010
Newbie
26. 10. 2016   #1
-
0
-

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

Nahlásit jako SPAM
IP: 212.26.187.–
peter
~ Anonymní uživatel
2921 příspěvků
27. 10. 2016   #2
-
0
-

- 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.

Nahlásit jako SPAM
IP: 2001:718:2601:26c:69f0:a9...–
Jozef010
Newbie
27. 10. 2016   #3
-
0
-

#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

Nahlásit jako SPAM
IP: 212.26.187.–
Ovrscout
~ Anonymní uživatel
89 příspěvků
27. 10. 2016   #4
-
0
-

#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.)
 

Nahlásit jako SPAM
IP: 178.255.168.–
Mircosoft+1
Věrný člen
31. 10. 2016   #5
-
0
-

...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ě.

Nahlásit jako SPAM
IP: 212.79.106.–
Chceš-li lepší odpověď, polož lepší otázku.
Moje stránka.
Jozef010
Newbie
2. 11. 2016   #6
-
0
-

#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;
Nahlásit jako SPAM
IP: 212.26.187.–
Jozef010
Newbie
9. 11. 2016   #7
-
0
-

Žiadny ďalší nápad?

Ďakujem

Nahlásit jako SPAM
IP: 212.26.187.–
Řešení
gna
~ Anonymní uživatel
412 příspěvků
10. 11. 2016   #8
-
+1
-
Zajímavé
Vyřešeno Nejlepší odpověď

Počítáš tu délku, když narazíš na prvek, kterým ta posloupnost začíná.

Počítej délku, dokud nenarazíš na prvek, který už v posloupnosti byl. A vyhoď to do funkce.

function DelkaPosloupnosti(pole: array of integer; pos: integer): integer;
var
  i, j, delka: integer;
  nalezeno: boolean;
begin
  delka := 1;
  nalezeno := false;
  
  { prochazet nasledujici prvky }
  for i := pos + 1 to high(pole) do
  begin
	{ dokud nenerazime na prvek, ktery uz v posloupnosti je }
	for j := pos to i - 1 do
	begin
	  if pole[j] = pole[i] then
	  begin
		nalezeno := true;
		break;
	  end;
	end;
	
	if nalezeno then break;
	
	inc(delka);
  end;

  DelkaPosloupnosti := delka;
end;
for i := 1 to n do
begin
  len := DelkaPosloupnosti(p, i - 1);
  if len > maxlen then
  begin
    maxpos := i;
    maxlen := len;
  end;
end;
Nahlásit jako SPAM
IP: 213.211.51.–
Jozef010
Newbie
10. 11. 2016   #9
-
0
-

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

Nahlásit jako SPAM
IP: 212.26.187.–
Zjistit počet nových příspěvků

Přidej příspěvek

Toto téma je starší jak čtvrt roku – přidej svůj příspěvek jen tehdy, máš-li k tématu opravdu co říct!

Ano, opravdu chci reagovat → zobrazí formulář pro přidání příspěvku

×Vložení zdrojáku

×Vložení obrázku

Vložit URL obrázku Vybrat obrázek na disku
Vlož URL adresu obrázku:
Klikni a vyber obrázek z počítače:

×Vložení videa

Aktuálně jsou podporována videa ze serverů YouTube, Vimeo a Dailymotion.
×
 
Podporujeme Gravatara.
Zadej URL adresu Avatara (40 x 40 px) nebo emailovou adresu pro použití Gravatara.
Email nikam neukládáme, po získání Gravatara je zahozen.
-
Pravidla pro psaní příspěvků, používej diakritiku. ENTER pro nový odstavec, SHIFT + ENTER pro nový řádek.
Sledovat nové příspěvky (pouze pro přihlášené)
Sleduj vlákno a v případě přidání nového příspěvku o tom budeš vědět mezi prvními.
Reaguješ na příspěvek:

Uživatelé prohlížející si toto vlákno

Uživatelé on-line: 0 registrovaných, 4 hosté

Moderátoři diskuze

 

Hostujeme u Českého hostingu       ISSN 1801-1586       ⇡ Nahoru Webtea.cz logo © 20032017 Programujte.com
Zasadilo a pěstuje Webtea.cz, šéfredaktor Lukáš Churý