Matematické Fórum

↑ Týnuuus:
Ahoj,
není to nic složitého, jen se toho nesmíš bát;-)

ad 1: První nápad by asi byl čísla třídit do dvou polí, ale to je zbytečné plýtvání pamětí, zejm. pokud máš omezen jen počet lichých čísel. Lepší je ze vstupu číst číslo po čísle a testovat je na sudost/lichost (zbytek po celočíselném dělení dvojkou). Sudá zrovna vypíšeš, lichá si uložíš do pole licha:Array[1..1000] of integer. Až bude na vstupu -1, načítání končí a druhým cyklem vypíšeš obsah pole licha.

ad 2: Tohle už je zajímavější, protože jde vymyslet několik postupů:
Přímočaré řešení: Při prvním průchodu najdi maximum vč. jeho indexu, po průchodu celým polem maximum vyřaď přepsáním hodnoty na -1. Pokud jsou ještě v poli nezáporné prvky pokračuj hledáním nového maxima. Pokud je totožné s maximem z předchozího kroku, má nalezen výsledek, jinak opakuj.

Jiné přímočaré řešení: Modifikuj Bubble Sort tak, aby při vložení nového prvku "nahoru" kontroloval, jestli nad ním není stejně velký prvek.

Lepší řešení: Posloupnost si načti do pole, pole si celé uspořádej a pak ho procházej od největšího prvku, zda v něm nejsou za sebou dva stejné prvky. První taková nalezená dvojice splňuje zadání. Pokud na to takhle po ránu koukám dobře, má toto řešení lepší asymptotickou složitost než přímočaré postupy.

No, já si myslím že najít největší duplicitní číslo se dá na jeden jediný průchod.
Ale možná se mýlím.
Princip:
procházím pole, a nalezené prvky si ukládám do zásobníku. Při každém novém prvku se dotážu, zda zásobník ten nový prvek obsahuje. Když ano, a bude větší jak dosavadní největší duplicita, zapamatuji si jí, jinak procházím dál.
Jo, ten program je jen kostra, a obsahuje určitou malou chybu ;-) ale ta se dá snadno napravit, aby čísla v zásobníku byla nezaměnitelná.

Program Duplicita;

var a:ansistring;
    b:string;
    i,j,maxdubl:integer;

    vstup:array[1..7] of integer;

begin
  {toto je jen ilustracni testovaci vstup}
  vstup[1]:=1;
  vstup[2]:=8;
  vstup[3]:=2;
  vstup[4]:=3;
  vstup[5]:=18;
  vstup[6]:=8;
  vstup[7]:=1;
  a:='*';
  maxdubl:=-9999;

  for i:=1 to 7 do
  begin
    str(vstup[i],b);
    if pos(b,a)>0 then {proste se zeptam zda uz je neco takoveho v zasobniku}
      begin {ano, je}
      if vstup[i]>maxdubl then {a je to vetsi jak dosavadni dubl?}
        begin
        maxdubl:=vstup[i]; {ano, hura, mame dalsi nejvyssi dubl}
        writeln(a,'->',maxdubl)
        end
      end
    else
      a:=Concat(a,b,'*'); {vrazime do zasobniku; hvezdicky oddeluji cisla!}
      writeln(a);
  end;
  writeln(a);
  writeln(maxdubl); {a to je nejvetsi z vicekrat uvedenych cisel}
end.