program SilnicniSit;
{Reseni ulohy o silnicni siti}
{Pro jednoduchost je silnicni sit zadana primo v konstantach
programu - upravte si sami na vstup z klavesnice}
{Pet variant reseni - pet procedur Cesty}

const N = 10;                        {pocet mest}
      X: array[1..N] of integer
        = (2,3,4,5,6,8,8,9,10,0);    {ulozeni silnicni site}
      Y: array[1..N] of integer
        = (3,5,5,0,7,9,9,10,0,0);    {ulozeni silnicni site}

var C: array[1..N] of integer;   {pocet cest vedoucich do N}
    I: integer;

function Cesty1(K: integer): integer;
  {pocet ruznych cest z mesta 1 do mesta K - prosta rekurze}
  var Pocet, I: integer;
  begin
  if K = 1 then
    Cesty1 := 1
  else
    begin
    Pocet := 0;
    for I:=1 to K-1 do
      if (X[I]=K) or (Y[I]=K) then
        Pocet := Pocet + Cesty1(I);
    Cesty1 := Pocet
    end
  end;  {function Cesty1}

function Cesty2(K: integer): integer;
  {pocet ruznych cest z mesta K do mesta N - prosta rekurze}
  var Pocet: integer;
  begin
  if K = N then
    Cesty2 := 1
  else
    begin
    Pocet := 0;
    if X[K] > 0 then Pocet := Pocet + Cesty2(X[K]);
    if Y[K] > 0 then Pocet := Pocet + Cesty2(Y[K]);
    Cesty2 := Pocet
    end
  end;  {function Cesty2}

function Cesty3(K: integer): integer;
  {pocet ruznych cest z mesta K do mesta N - rekurze
   s pouzitim globalniho pomocneho pole C pro ulozeni
   jiz znamych hodnot}
  begin
  if C[K] >= 0 then       {hodnota je jiz znama z drivejska}
    Cesty3 := C[K]
  else
    begin
    C[K] := 0;
    if X[K] > 0 then C[K] := C[K] + Cesty3(X[K]);
    if Y[K] > 0 then C[K] := C[K] + Cesty3(Y[K]);
    Cesty3 := C[K]
    end
  end;  {function Cesty3}

function Cesty4: integer;
  {pocet ruznych cest z mesta 1 do mesta N - cyklem
   s pouzitim globalniho pomocneho pole C pro ulozeni
   jiz znamych hodnot}
  var C: array[1..N] of integer; {pocet cest vedoucich do N}
      K: integer;
  begin
  C[N] := 1;
  for K:=N-1 downto 1 do
    begin
    C[K] := 0;
    if X[K] > 0 then C[K] := C[K] + C[X[K]];
    if Y[K] > 0 then C[K] := C[K] + C[Y[K]]
    end;
  Cesty4 := C[1]
  end;  {function Cesty4}

function Cesty5: integer;
  {pocet ruznych cest z mesta 1 do mesta N - cyklem
   s pouzitim globalniho pomocneho pole C pro ulozeni
   jiz znamych hodnot}
  var C: array[0..N] of integer; {pocet cest vedoucich do N}
      K: integer;
  begin
  C[0] := 0;            {umela hodnota z technickych duvodu}
  C[N] := 1;
  for K:=N-1 downto 1 do
    C[K] := C[X[K]] + C[Y[K]];
  Cesty5 := C[1]
  end;  {function Cesty5}

begin
{inicializace pole C:}
for I:= 1 to N-1 do C[I] := -1;      {hodnota dosud neznama}
C[N] := 1;

{SILNICNI SIT JE ULOZENA V KONSTANTACH X, Y !}

{vlastni vypocet:}
writeln('Pocet cest zjisteny jednotlivymi metodami:');
write('1.metoda: ');
writeln(Cesty1(N));
write('2.metoda: ');
writeln(Cesty2(1));
write('3.metoda: ');
writeln(Cesty3(1));
write('4.metoda: ');
writeln(Cesty4);
write('5.metoda: ');
writeln(Cesty5);
end.