Localize file www.TrSek.com/cover/mojzis/o_recidivistoch.pas{ ============== }
{ 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;
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);
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);
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));