Nepokoje v nasich vazniciach narastaju do neusosnych medzi

Delphi & Pascal (česká wiki)
Přejít na: navigace, hledání
Category: KMP (Club of young programmers)

Author: Ján Mojžiš
Program: O_recidivistoch.pas
need: Recidivisti.dat
Example: O_recidivistoch.txt

Nepokoje v nasich vazniciach narastaju do neusosnych medzi. A to nielen preto, ze su preplnene, ale aj preto, ze recidivistom su vzdy pridelene nove cisla a nie tie ich, na kt. si uz zvykli. Vo vazniciach, kde sa vsetci oslovuju cislami, je tento fakt velmi nevytany.

Vsetko vyriesil novy projekt Alcatraz II. Ak pride do tejto vaznice dalsi vazen, dozorcovia zadaju do pocitaca jeho meno a priezvisko a program vypise NOVY, ak tu este predtym vazneny nebol, alebo RECIDIVISTA, ak neprisiel po prvy raz. Program tiez vypise cislo vazna. Novemu vaznovi moze program priradit lubovolne cislo, ktore avsak nema iny vazen, no recidivistovi musi priradit cislo z jeho predchadzajuceho pobytu. Mozno predpokladat ze cisla su priradovane iba uvedenym programom.
{  ==============                                                              }
{  KSP 15. rocnik    1511: O recidivistoch            Copyright (c) Jan Mojzis }
{  ==============                                                              }
{  Zadanie:                                                                    }
{  Nepokoje v nasich vazniciach narastaju do neusosnych medzi. A to nielen preto,}
{  ze su preplnene, ale aj preto, ze recidivistom su vzdy pridelene nove cisla a }
{  nie tie ich, na kt. si uz zvykli. Vo vazniciach, kde sa vsetci oslovuju     }
{  cislami, je tento fakt velmi nevytany.                                      }
{  Vsetko vyriesil novy projekt Alcatraz II. Ak pride do tejto vaznice dalsi   }
{  vazen, dozorcovia zadaju do pocitaca jeho meno a priezvisko a program vypise}
{  NOVY, ak tu este predtym vazneny nebol, alebo RECIDIVISTA, ak neprisiel po  }
{  prvy raz. Program tiez vypise cislo vazna. Novemu vaznovi moze program      }
{  priradit lubovolne cislo, ktore avsak nema iny vazen, no recidivistovi musi }
{  priradit cislo z jeho predchadzajuceho pobytu. Mozno predpokladat ze cisla su}
{  priradovane iba uvedenym programom.                                         }
{  ULOHA:                                                                      }
{      Vytvorte horeuvedeny program tak, aby fungoval co najrychlejsie a pre   }
{  co najvacsie mnozstva vaznov. Program bude uvedeny do prevadzky zaroven s   }
{  otvorenim vaznice, takze vaznica je na zaciatku prazdna. Kedze Alcatraz II  }
{  nikdy neprestane fungovat, mal by aj vas program fungovat v nekonecnej slucke.}
{  Mena vaznov su zlozene z velkych pismen abecedy a z medzier.                }
{      Priklad vstupu a vystupu:                                               }
{              ? LEX LUTHOR                                                    }
{                NOVY 3560                                                     }
{              ? JAMES BOND                                                    }
{              NOVY 007                                                        }
{              ? LEX LUTHOR                                                    }
{              RECIDIVISTA 3560                                                }
{              ? LOIS LANE                                                     }
{              NOVY 806070                                                     }
{              ? JAMES BOND                                                    }
{              RECIDIVISTA 007                                                 }
{                                                                              }
{                                                                              }
{      ----------------------------------------------------------------------  }
{    Lexikograficky strom pre rychle vyhladavanie.                             }
{    Ovladanie je ESC pre exit a ? klavesa pre vyhladavanie. Program si vie    }
{    aj zapamatat novopecenych recidivistov, ktorych si hned poznamena do      }
{    stromu, tabulky aj do suboru cez append.                                  }
{    Subor je obycajny textovy. Da sa premazat, ale nechal som dva prve riadky }
{    pre hlavicku Alcatraz II. Preto by mali byt vzdy 2 riadky zhora (program  }
{    automaticky preskakuje 2 riadky).                                         }
{    Program pouziva binarny strom, a sice dva. Jeden sluzi pre evidovanie     }
{    vaznov, ten je lexikograficky s vetvami nazvov 'a'..'z' a velke pismena sa}
{    osetruju hned na zaciatku ansilowercase-om. Druhy je strom cisielkovy, je }
{    naprosto rovnaky, len s mensim poctom vetiev. Podstatna je len platna cesta.}
{                                                                              }
{    STROM Vaznov (napriklad):                Strom Cisiel vaznov (napriklad): }
{    * * / *            * \ *  *                 * * /  *           * \*       }
{    *[a] = -1          *[c] = 7                 * [0] = nil?*      * [7]=nil?*}
{    (neexistuje)*        (1 index v tab)*          *  * *             * ***   }
{    Spolu 26 vetiev v kazdom uzle                   tu je vetiev 10           }
{                                                                              }
{    Tabulka cisiel vaznov:                                                    }
{    [0] 313                                                                   }
{    [7] 007                                                                   }
{    ...                                                                       }
{    Pri vkladani do cisloveho stromu sa len vytvaraju nove vetvy s nil podvetvami.}
{    Je to pre rychle vyhladavanie.                                            }
{    Pri vkladani do pismenkoveho stromu sa vytvaraju nove vetvy takisto, ale kazda }
{    novovytvorena vetva sa nastavi na -1 pre cislo indexu. Okrem poslednej vetvy,  }
{    kde uz sa vklada priamo cislo.                                            }
{                                                                              }
{    Toto cislo indexu je velmi dolezite, lebo "Karol Koubek" je recidivista.  }
{    Dozorca chce zistit, ci novoprijaty Karol Koube je uz v databaze. V beznom}
{    pripade ak by sme neskumali korektnost pomocou -1, by sme presli vetvami az po }
{    ..ek a zistime ze cesta je platna, vazen teda existuje. To je chyba.       }
{    Pre istotu som aj do cisloveho stromu dal -1 validator. Keby sa cesta skoncila }
{    predcasne a cislo by nemalo existovat. Napriklad pri generovani noveho cisla   }
{    pre noveho recidivistu, stary je zapisany ako 666, vytvori sa nahodou 666.     }
{    Toto sa uz nestane.                                                       }
{                                                                              }
{    Nesmu byt dvaja rovnaki recidivisti a dve rovnake cisla.                  }
{                                                                              }
{    Dolezite je este spomenut ze pre tabulku skutocnych cisiel vaznov, pouzivam}
{    hlavny index velkost_pola_recidivistov, ktory sluzi jednak ako posledna   }
{    aktualna velkost, a zaroven ako hodnota, ktora sa uklada do stromu vaznov.}
{                                                                              }
{    Pohyb v pismenkovom strome prebieha tak, ze sa retazec rozdeli na znaky, a}
{    zistuje sa len to, ci existuje vetva oznacena ako znak[z].                }
{    Pohyb v cisielkovom strome je rovnaky, pouziva vetvy oznacene ako 'a'..'z'.}
{    Mal som aj lepsie riesenie:                                               }
{    z ciselka berieme poslednu cifierku najpr, teda z 1567 si zoberieme       }
{    7 pomocou 1567 mod 10. Potom cisielko este zmensime div 10. Vysledok zapiseme }
{    a nastavime novu vetvu. Ale nesplnalo to kriteria pre 007.                }
{                                                                              }
{    Sofistikovane je prevedene zlucenie stromu cisielok a stromu vaznov. A to tak, }
{    ze vo vetve vaznov sa okrem mena eviduje cislo, ale nie konkretne instantne }
{    cislo, ale len poradove cislo indexu na lokalnej tabulke vaznov. Potom      }
{    konkretne cislo vazna dostaneme, ked pouzieme toto "cislo" v indexe tabulky,}
{    a tym ho spravne rozlustime. Pole je array of string, a je dynamicke, pre   }
{    rozny pocet vaznov a pre setrenie pamate. Jediny sposob ktory mi napadol pre}
{    okamzite zistenie ci novy vazen sa nekryje s inym vaznom (ciselne).         }
{                                                                                }
{    Z cisielkoveho stromu je jedno ci cislo berieme v strome od predu alebo od  }
{    zadu. Podstatne je len to, aby sme vzdy zvolili rovnaky postup.             }
{                                                                                }
{    V zadani som si vsimol aj cislo 007. Rozhodol som sa  teda, pre zjednodusenie }
{    vetvy urcit ako typ char.                                                   }
{                                                                                }
{    - Ostatne veci su uz prijemne, zlozitost programu je O^n, priamo umerna poctu }
{    pismeniek a cisielok.                                                       }
{                                                                                }
{    POZNAMKA:                                                                   }
{           CRT_EFD nie je sucastou tohto riesenia. Kniznicu CRT_EFD pre pracu s }
{           konzolovymi vypismi mozete stiahnut napriklad na:                    }
{           http://www.stano.wz.sk/index.php?id=8                                }
{                                                                                }
{                                                                              }
{  Author: (c) 2007 Jan Mojzis                                                 }
{  Date  : 06.07.2008                                     http://www.trsek.com }
 
program lexikograficky_strom;
 
{Program na simulovanie lexikografickeho stromu. Jeho vytvaranie a pouzitie.}
 
const subor = 'recidivisti.dat';
{------------ HLAVNY STROM VAZNOV --------------}
type m_basisti=^atom_b;
     atom_b=record
      cislo : integer; { recidivistovo cislo; }
      znak:array['a'..'z'] of m_basisti
     end;
{--------- HLAVNY STROM PRE CISLA --------------}
type c_basisti = ^atom_bc;
      atom_bc = record
      valid : integer;
       ch : array['0'..'9'] of c_basisti
      end;
 
var BASISTI:m_basisti;
    BAS_CISLA : c_basisti;
    j:integer;
    file_append : text;
    nove_cislo : integer = -1;
    recidivista:string  = '';
    cislo:integer = 0;
    cislarecidivistov : array of string;
    velkost_pola_recidivistov : integer = 0;
    volby : char = #0;
    prazdny : boolean = false;
 
procedure inicializuj(var s:m_basisti);
{Vytvorime si novy uzol a nastavime vsetky vetvy na prazdontu NIL}
var z:'a'..'z';
begin
 new(s);
 for z:='a' to 'z' do s^.znak[z]:=nil;
 s^.cislo:=-1;
end;
 
procedure inicializuj_strom_cisel(var rec_n:c_basisti);
{To iste pre cisielkovy strom}
var z:'0'..'9';
begin
 new(rec_n);
 for z:='0' to '9' do rec_n^.ch[z]:=nil;
 rec_n^.valid:=-1;
end;
 
procedure VlozBasistu(var s:m_basisti;slovo:string;cislo:integer);
{To ci vazen v databaze uz nahodou je, je nam nepotrebne, lebo to zistuje f. HladajBasistu}
var i:integer;
    z:'a'..'z';
    p:m_basisti;
begin
 slovo := AnsiLowerCase(slovo);
 p:=s;
 for i:=1 to length(slovo) do
 begin
  if(p^.znak[slovo[i]]=nil) then
  begin
   new(p^.znak[slovo[i]]);
   p:=p^.znak[slovo[i]];
   for z:='a' to 'z' do p^.znak[z]:=nil;
   p^.cislo:=-1;
  end
  else  p:=p^.znak[slovo[i]]
 end;
 p^.cislo:=cislo;
end;
procedure VlozCislo(var s:c_basisti;cislo:string);
var i:integer;
    z:'0'..'9';
    p:c_basisti;
    konci : boolean;
begin
 p:=s;
konci := false;
i:=0;
 for i:=1 to length(cislo) do
 begin
  if(p^.ch[cislo[i]]=nil) then
 begin
   new(p^.ch[cislo[i]]);
   p:=p^.ch[cislo[i]];
   for z:='0' to '9' do p^.ch[z]:=nil;
   p^.valid:=-1;
  end
  else  p:=p^.ch[cislo[i]];
 end;
p^.valid := 1;
end;
 
 
procedure HladajBasistu(var s:m_basisti;slovo:string; var cislo:integer);
var p:m_basisti;
    i:integer;
    stav:boolean;
begin
 stav:=true;
 p:=s;
 i:=1;
 slovo := AnsiLowerCase(slovo);
 if(slovo[1]=' ') then stav:=false
 else
  if(p=nil) then stav:=false
  else
   repeat
    if p^.znak[slovo[i]]<>nil then
    begin
     p:=p^.znak[slovo[i]];
     inc(i)
    end
    else  stav:=false;
   until (stav=false)or(i=length(slovo)+1);               { overenie identity }
  if (stav=false)and(p^.cislo=-1) then cislo:=-1
  else if (stav=true)and(p^.cislo<>-1) then cislo:=p^.cislo
   else cislo:=-1;
end;
function HladajCislo(var s:c_basisti; cislo:string) : integer;
var p:c_basisti;
    i:integer;
    stav:boolean;
    konci : boolean;
begin
 stav:=true;
 p:=s;
 i:=1;
 if(cislo[1]=' ') then stav:=false
 else
  if(p=nil) then stav:=false
  else
   repeat
    if p^.ch[cislo[i]]<>nil then
    begin
     p:=p^.ch[cislo[i]];
     inc(i)
    end
    else  stav:=false;
   until (stav=false)or(i=length(cislo)+1);                 { overovacie podmienky }
  if (stav=false)and(p^.valid=-1) then result:=-1           { antiduplicitne cisla }
  else if (stav=true)and(p^.valid<>-1) then result:=p^.valid
   else result:=-1;end;
 
 
procedure napln_mena(var s:m_basisti; slovnik:string);
var f:text;
    recidivista:string;
    i:byte;
    cislo : string;
    rez : integer;
begin
cislo:='';
rez:=-1;
 assign(f,subor);
 {I$-}
 reset(f);
 if ioresult<>0 then begin
                      writeln('Chyba subor obsahujuci slovnik!');
                      halt(1)
                     end;
 {I$+}
 velkost_pola_recidivistov:=0;
 readln(f);
 readln(f);
 if seekeof(f) then prazdny:=true
 else
 while not eof(f) do
 begin
 readln(f, cislo);
 rez:=AnsiPos(' ', cislo);
 inc(rez);
 recidivista:=Copy(cislo,rez,maxint);
 dec(rez);
 Delete(cislo,rez,maxint);
 
 setlength(cislarecidivistov,velkost_pola_recidivistov+1);
 cislarecidivistov[velkost_pola_recidivistov]:=cislo;
  VlozBasistu(s,recidivista, velkost_pola_recidivistov);
 inc(velkost_pola_recidivistov);
 end;
 close(f);
end;
 
procedure napln_cisla(var s:c_basisti; sub:string);
var f:text;
    i:byte;
    cislo : string;
    retazec : string;
    rez : integer;
begin
cislo:='';
 assign(f,sub);
 {I$-}
 reset(f);
 if ioresult<>0 then begin
                      writeln('Chyba subor obsahujuci slovnik!');
                      halt(1)
                     end;
 {I$+}
 readln(f);
 readln(f);
 while not eof(f) do
 begin
 readln(f, cislo);
 
 rez:=AnsiPos(' ', cislo);
 
 inc(rez);
 recidivista:=Copy(cislo,rez,maxint);
 dec(rez);
 Delete(cislo,rez,maxint);
 VlozCislo(s,cislo );
 end;
 close(f);
end;
 
procedure test(var s:m_basisti; slovnik:string);
var f:text;
    recidivista:string;
    i:byte;
    cislo : string;
    rez : integer;
    vratcislo: integer;
begin
vratcislo:=-1;
 assign(f,'recidivisti.dat');
 {I$-}
 reset(f);
 if ioresult<>0 then begin
                      writeln('Chyba subor obsahujuci slovnik!');
                      halt(1)
                     end;
 {I$+}
 velkost_pola_recidivistov:=0;
 readln(f);
 readln(f);
 while not eof(f) do
 begin
 readln(f, cislo);
 rez:=AnsiPos(' ', cislo);
 inc(rez);
 recidivista:=Copy(cislo,rez,maxint);
 dec(rez);
 Delete(cislo,rez,maxint);
 
 setlength(cislarecidivistov,velkost_pola_recidivistov+1);
 cislarecidivistov[velkost_pola_recidivistov]:=cislo;
 HladajBasistu(s,recidivista,vratcislo);
  inc(velkost_pola_recidivistov);
 end;
 close(f);
end;
 
procedure OdstranAtom(p:m_basisti);
var z:'a'..'z';
begin
 for z:='a' to 'z' do
  if (p^.znak[z]<>nil) then OdstranAtom(p^.znak[z]);
  if (p^.cislo<>-1)then begin
   write(p^.cislo);
   inc(j);
   write(' ',j);
   readln;
  end;
 dispose(p); p:=nil;
end;
 
procedure OdstranStrom(var s:m_basisti);
var p:m_basisti;
begin
 j:=0;
 p:=s;
 OdstranAtom(p);
 s:=nil;
end;
 
begin
 randomize;
 inicializuj(BASISTI);
 inicializuj_strom_cisel(BAS_CISLA);
 napln_mena(BASISTI, subor);
 if not prazdny then begin
 napln_cisla(BAS_CISLA, subor);
 test(BASISTI,subor);
  write('Zoznam recidivistov nacitany  ');
 end
 else write('Zoznam Alcatraz II je prazdny  ');
 writeln('volby [ESC] = koniec, [?] = hladat');
  repeat
          volby := ReadKey;
          if volby = '?' then begin
                write('? ');
                readln(recidivista);
                HladajBasistu(BASISTI,recidivista,cislo);
                if cislo <> -1 then
                  writeln(recidivista, ' - RECIDIVISTA c.', cislarecidivistov[cislo])
                else begin
                  write('NOVY ');
                     repeat
                      nove_cislo:=random(maxint);
{  test duplicity}       nove_cislo:=66;
                      j:=HladajCislo(BAS_CISLA, inttostr(nove_cislo));
                    until j <> 1;
                 writeln('c. ', nove_cislo);
                 VlozCislo(BAS_CISLA,inttostr(nove_cislo));
 
                 setlength(cislarecidivistov,velkost_pola_recidivistov+1);
                 cislarecidivistov[velkost_pola_recidivistov]:=inttostr(nove_cislo);
                 VlozBasistu(BASISTI,recidivista, velkost_pola_recidivistov);
                 inc(velkost_pola_recidivistov);
 
                 assignfile(file_append, 'recidivisti.dat');
                 append(file_append);
                 write(file_append,#13#10,nove_cislo, ' ', recidivista);
                 closefile(file_append);
 
                end;
          end;
  until volby = #27;
end.