Riešte nasledujúce úlohy. Vo všetkých úlohách môžete do tried dodefinovať pomocné metódy (nie nové položky).

1. Naprogramujte metódy triedy TLexStrom, ktorá umožňuje evidovať slová zložené z písmen {a,b,c}. Ďalej skonštruujte taký strom, ktorý obsahuje všetky slová dĺžky 5 zložené len z týchto písmen, pričom slová obsahujú rovnaký počet písmen a aj b. Vypíšte počet slov v tomto strome, použite na to metódu zisti.

type
  TLexStrom = class
    pocet:integer;
    p:array['a'..'c'] of TLexStrom;
    constructor Create;
    procedure pridaj(s:string);
    function zisti:integer;     // zistí počet všetkých slov v strome
  end;

2. Zadefinujte aritmetický strom tak, aby sa vo vrcholoch, ktoré reprezentujú operácie, namiesto jej znaku (napr. '+' alebo '*') pamätala funkcia (procedurálny typ), ktorá túto operáciu počíta.

type
  TOperacia = ...  // procedurálny typ
  TAStrom = class
    function hodnota:real; virtual; abstract;
  end;
  TAOperacia = class(TAStrom)
    f:TOperacia;
    ...
    constructor Create(ff:TOperacia; ll,pp:TAStrom);
    function hodnota:real; ...
  end;
  TAOperand = class(TAStrom)
    hod:real;
    constructor Create(h:real);
    function hodnota:real; ...
  end;

Dopíšte deklarácie a zadefinujte všetky metódy a ukážkovo jednu operáciu plus – sčítanie dvoch reálnych čísel, ktorú by sme mohli použiť pri definovaní takéhoto stromu.

3. Vytvorte graf, ktorý je reprezentovaný pomocou "množiny susedov" a je uložený v dátovom prúde (stream) takto: každý vrchol je popísaný jedným blokom; blok začína menom vrcholu (jeden znak) a pokračuje postupnosťou znakov, ktoré sú menami susediacich vrcholov – táto postupnosť je ukončená nulovým znakom #0. Pole g musí obsahovať toľko prvkov, koľko je vrcholov v grafe.

type
  TVrchol = class
    s:set of byte;        // množina susedov = indexy do poľa g
    meno:char;
    constructor Create(mm:char);
  end;
  TGraf = class
    g:array of TVrchol
    constructor Create(subor:TStream);
    function index(c:char):byte;
  end;

4. Napíšte program, ktorý v dvojrozmernom celočíselnom poli P rozmerov NxN nahradí nulové hodnoty tak, aby vznikol magický štvorec - súčet prvkov v každom riadku aj v každom stĺpci je tá istá konštanta K. Nenulové čísla v tomto poli už meniť nesmiete.
   Pole môže obsahovať len čísla z intervalu 1..N (v riadku alebo v stĺpci sa číslo môže nachádzať aj viackrát). Úlohu riešte metódou prehľadávania s návratom (backtracking). Ak neexistuje žiadne riešenie, program vypíše správu. Stačí nájsť jediné riešenie.

// 1. príklad
constructor TLexStrom.Create;
begin
  pocet:=0; p['a']:=nil; p['b']:=nil; p['c']:=nil;
end;

procedure TLexStrom.pridaj(const s:string);
begin
  if s='' then inc(pocet)
  else if s[1] in ['a'..'c'] then begin
    if p[s[1]]=nil then p[s[1]]:=TLexStrom.Create;
    p[s[1]].pridaj(copy(s,2,maxint));
  end;
end;

function TLexStrom.zisti: integer;
var
  c:char;
begin
  Result:=pocet;
  for c:='a' to 'c' do
    if p[c]<>nil then inc(Result,p[c].zisti);
end;

//////////////////////

procedure TForm1.Button1Click(Sender: TObject);
var
  l:TLexStrom;
  z1,z2,z3,z4,z5:char;

  function pocet(z:char):integer;
  begin
    Result:=ord(z=z1)+ord(z=z2)+ord(z=z3)+ord(z=z4)+ord(z=z5);
  end;

begin
  l:=TLexStrom.Create;
  for z1:='a' to 'c' do
    for z2:='a' to 'c' do
      for z3:='a' to 'c' do
        for z4:='a' to 'c' do
          for z5:='a' to 'c' do
            if pocet('a')=pocet('b') then
              l.pridaj(z1+z2+z3+z4+z5);
  Memo1.Lines.Add(IntToStr(l.zisti));
  l.Free;
end;

// 2. príklad
type
  TOperacia = function(a,b:real):real;

  TAStrom = class
    function hodnota:real; virtual; abstract;
  end;

  TAOperacia = class(TAStrom)
    f:TOperacia;
    l,p:TAStrom;
    constructor Create(ff:TOperacia; ll,pp:TAStrom);
    function hodnota:real; override;
  end;

  TAOperand = class(TAStrom)
    hod:real;
    constructor Create(h:real);
    function hodnota:real; override;
  end;

constructor TAOperacia.Create(ff:TOperacia; ll,pp:TAStrom);
begin
  f:=ff; l:=ll; p:=pp;
end;

function TAOperacia.hodnota:real;
begin
  Result:=f(l.hodnota,p.hodnota);
end;

constructor TAOperand.Create(h:real);
begin
  hod:=h;
end;

function TAOperand.hodnota:real;
begin
  Result:=hod;
end;

//////////////////////

function plus(a,b:real):real;
begin
  Result:=a+b;
end;

// 3. príklad
constructor TGraf.Create(subor: TStream);
var
  c:char;
  i:integer;
begin
  subor.Position:=0;
  while subor.Position<subor.Size do begin
    subor.Read(c,1);
    SetLength(g,length(g)+1);
    g[high(g)]:=TVrchol.Create(c);
    repeat
      subor.Read(c,1);
    until c=#0;
  end;
  subor.Position:=0;
  while subor.Position<subor.Size do begin
    subor.Read(c,1); i:=index(c);
    subor.Read(c,1);
    while c<>#0 do begin
      g[i].s:=g[i].s+[index(c)];
      subor.Read(c,1);
    end;
  end;
end;

function TGraf.index(c: char): byte;
begin
  Result:=high(g);
  while (Result>0) and (c<>g[Result].meno) do dec(Result);
end;

// 4. príklad
var
  ok:boolean = false;

procedure backtracking;
var
  i,j,m,sum:integer;
  b:boolean;
begin
  if ok then exit;
  for i:=1 to N do begin     // zisti, či je to zatiaľ ok
    sum:=0; b:=true;
    for j:=1 to N do begin   // kontroluj po riadkoch
      inc(sum,p[i,j]); if p[i,j]=0 then b:=false;
    end;
    if b and (sum<>K) or not b and (sum>=K) then exit;
    sum:=0; b:=true;
    for j:=1 to N do begin   // kontroluj po stĺpcoch
      inc(sum,p[j,i]); if p[j,i]=0 then b:=false;
    end;
    if b and (sum<>K) or not b and (sum>=K) then exit;
  end;
  i:=1;
  while i<=N do begin        // nájdi prvé p[i,j]=0
    j:=1;
    while (j<=N) and (P[i,j]<>0) do inc(j);
    if j<=N then break else inc(i);
  end;
  if i>N then begin          // nenašiel  => mám riešenie
    ok:=true; exit;
  end;
  for m:=1 to N do begin
    p[i,j]:=m;
    backtracking; if ok then exit;
    p[i,j]:=0;
  end;
end;