7.5.2002
|
Bodovanie
rozcvičky
|
0 - 40
|
prémia
|
0 - 5
|
projekt
|
0 - 10
|
test
|
0 - 15
|
pri počítači
|
0 - 30
|
súčet
|
0 - 100
|
Výsledná známka
známka A
|
90 - 100
|
známka B
|
84 - 89
|
známka C
|
78 - 83
|
známka D
|
72 - 77
|
známka E
|
66 - 71
|
známka Fx
|
0 - 65
|
Test ku skúške prebehne v stredu 15.5.
od 16:30 v posluchárňach A, B a F1
Termíny praktickej skúšky budú
v dňoch 20.5., 29.5.,
31.5. a 3.6.
vždy od 9:00 v halách H3 a H6
- na skúšku sa prihláste cez webovú
stránku Skúšky
- prihlasovať sa môžete do 19.5. - po tomto
dátume vám bude niektorý termín
pridelený ...
- na skúšku môžete prísť
už od 7:30 - vtedy máte 90 minút navyše
- môžete používať vlastný
ťahák formátu A4
- prvých 15 minút skúšky
môžete vzájomne spolupracovať - toto
sa týka len tých, ktorí na
skúšku prídu súčasne
Preriešte si úlohy z minuloročného
testu
(na začiatku každého
príkladu uvádzame počet bodov, ktoré
sa dali získať za príklad / priemerne
získaný počet bodov)
- (3 / 0.4) Neorientovaný ohodnotený graf
je zadaný tabuľkou susedností. Procedúra
back je nejaký algoritmus prehľadávania
s návratom na grafe.
var
g:array['a'..'d','a'..'d'] of byte =
((0,1,1,1),(1,0,1,1),(1,1,0,1),(1,1,1,0));
pocet:integer = 0;
procedure back(v:char);
var
i:char;
j:boolean;
begin
j:=true;
for i:='a' to 'd' do
if g[v,i]<>0 then begin
dec(g[v,i]); dec(g[i,v]); j:=false;
back(i);
inc(g[v,i]); inc(g[i,v]);
end;
if j then inc(pocet);
end;
|
Zistite, čo bude v premennej pocet po
zavolaní back('a').
- (3 / 1.1)
Procedúra kopiruj prekopíruje
obsah súboru s menom s1 do súboru
s menom s2. Pri kopírovaní použije
pomocnú pamäť - prístupnú
cez smerník buf veľkosti max.
procedure kopiruj(s1,s2:string; max:integer);
var
t1,t2:TStream;
buf:pointer;
begin
t1:=TFileStream.___________________;
try
t2:=TFileStream.___________________;
_________buf__________;
try
while t1.Position<t1.Size do
t2.Write(_________t1.Read__________);
finally
_________buf__________;
t2.___________________; // zatvoriť
end;
finally
t1.___________________; // zatvoriť
end;
end;
|
- (34/ 0.3)
Zistite, koľko existuje rôznych
aritmetických stromov, ktorých inorder
je
- (1 / 0.8)
Pre binárny strom nepoznáme
hodnoty vo vrcholoch ale vieme, že má tento
tvar:
a ak by sme vrcholy vypísali preorderom,
dostali by sme vzostupne usporiadanú postupnosť
rôznych čísel. Ďalej vieme, že všetky
vrcholy, ktoré sú rovnako vzdialené
od koreňa, majú svoju číselnú
hodnotu zloženú len z rovnakých cifier,
napr. samé 5, t.j. 5, 55, 555, 5555, ...
Očíslujte strom.
- (2.5 / 0.1)
Ideu lexikografického stromu
využijeme na zistenie frekvenčnej tabuľky z celých
čísel, pričom tieto čísla budeme "rozoberať"
po bitoch a z tohto sa budeme rozhodovať, kam pokračovať
v strome:
type
TLexStrom = class
pocet:integer;
p:array[0..1] of TLexStrom;
constructor Create;
procedure pridaj(i:integer);
function vypis(i,j:integer):string;
end;
constructor TLexStrom.Create;
begin
pocet:=0; p[0]:=nil; p[1]:=nil;
end;
procedure TLexStrom.pridaj(i:integer);
begin
if i=0 then inc(pocet)
else begin
if p[i mod 2]=nil then p[i mod 2]:=TLexStrom.Create;
p[i mod 2].pridaj(i div 2);
end;
end;
function TLexStrom.vypis(i,j:integer):string;
begin
if pocet>0 then Result:=IntToStr(i)+','
else Result:='';
if p[0]<>nil then Result:=Result+p[0].vypis(i+j,2*j);
if p[1]<>nil then Result:=Result+p[1].vypis(i,2*j);
end;
...
l:=TLexStrom.Create;
for i:=1 to 20 do l.pridaj(i);
Label1.Caption:=l.vypis(0,1);
|
- (2.3 / 1.1)
Pred vykonaním procedúry
VytvorHaldu vyzerá pole, z ktorého
chceme vytvoriť haldu, takto:
- (1.7 / 0.9)
Neorientovaný graf je reprezentovaný
poľom množín susedov:
type
TGraf = class
g:array of set of byte;
procedure pridajVrchol;
procedure pridajHranu(i,j:integer);
end;
procedure TGraf.pridajHranu(i,j:integer);
begin
if i<>j then begin
g[i]:=g[i]+[j]; g[j]:=g[j]+[i];
end;
end;
procedure TGraf.pridajVrchol;
var
i,j:integer;
begin
SetLength(g,Length(g)+1);
i:=high(g); g[i]:=[]; j:=i div 2;
while j>1 do begin
pridajHranu(i,j-2);
j:=j div 2;
end;
end;
|
g:=TGraf.Create;
for i:=1 to 10 do g.pridajVrchol;
|
- (2.7 / 1.1)
Pomocou triedenia zlučovaním
chceme utriediť 10-prvkové pole:
var
p:array[1..10] of integer;
pocet:integer = 0;
procedure mergeSort(z,k:integer);
var
s:integer;
begin
inc(pocet);
if z<k then begin
s:=(z+k) div 2;
mergeSort(z,s);
mergeSort(s+1,k);
zluc(z,s,k);
end;
end;
|
Pomocná procedúra zluc zlúči
utriedené časti. Zistite, koľkokrát
sa zavolá táto rekurzívna procedúra
mergeSort pre dané pole, ak je prvé
volanie mergeSort(1,10) - t.j. zaujíma
nás hodnota premennej pocet.
- (3 / 1.1)
Máme danú postupnosť
16 čísel, ktorú budeme postupne pridávať
do binárneho vyhľadávacieho stromu
pomocou nasledovného postupu:
var
p:array[0..15] of integer =
(17,50,27,77,100,93,73,64,273,237,151,173,13,37,91,71);
...
s:=TBVS.Create;
i:=0; j:=0;
while i<16 do begin
s.vloz(p[i]); s.vloz(p[i+1]); inc(i,2);
s.zrus(p[j]); inc(j);
end;
|
Nakreslite výsledný strom. Predpokladáme,
že metóda zrus, keď treba, zamieňa
vyhadzovaný vrchol s minimálnym vrcholom
z pravého podstromu.
- (2.7 / 1.1)
Pre jednosmerný spájaný
zoznam potrebujeme zadefinovať metódu vsetky,
ktorá bude postupne testovať rôzne
filtrovacie funkcie a ak je nejaká z nich
splnená, tak sa spustí príslušný
príkaz. Filter aj príkaz zadeklarujte
ako procedurálne typy s jedným parametrom
typu TVrchol:
type
prikaz = _________________________;
filter = _________________________;
fprikaz = record f:filter; pr:prikaz; end;
TZoznam = class
z,k:TVrchol;
procedure vsetky(fp:array of fprikaz);
end;
procedure TZoznam.vsetky(fp:array of fprikaz);
var
p:TVrchol;
i:integer;
begin
p:=z;
while p<>nil do begin
for i:=low(fp) to high(fp) do
if ______________________________________________ then
_________________________;
p:=p.next;
end;
end;
|
Ak v poli fp je namiesto filtra nil,
znamená to, že príslušný príkaz
sa má vykonať.
Riešenie príkladu praktickej skúšky
z minulého roku
Agent 007 James Bond dostal mapu nepriateľského
územia. Potrebuje sa dostať z východiskového
miesta (bod A) do cieľového miesta
(bod B), aby mohol splniť tajné poslanie
- odovzdať šifrovanú depešu agentke
008 Jane Bondovej. Analytické špionážne
stredisko zaznačilo Jamesovi do mapy na
všetky cesty bezpečnosť prechodu po tejto
ceste v % - 0% bezpečnosť označuje, že bude
na nej určite zneškodnený, 100% označuje
absolútnu bezpečnosť bez akéhokoľvek
nebezpečia.
Navrhnite Jamesovi čo najbezpečnejšiu
trasu a vypočítajte jej celkovú
bezpečnosť. (Uvedomte si, že ak je na trase
aspoň jeden úsek s 0% bezpečnosťou,
tak celá trasa má túto
0% bezpečnosť. Ale 100% úsek neznamená,
že celá trasa má 100%. Celková
bezpečnosť trasy je teda definovaná
ako súčin pravdepodobností
jednotlivých ciest na trase.)
Úlohu budete riešiť pomocou prehľadávania
s návratom (backtracking) - na grafe
budete hľadať najbezpečnejšiu trasu z A
do B. Zo zadania vyplýva, že graf
je neorientovaný ohodnotený
a budeme predpokladať, že vrcholov môže
byť až 1000. Na reprezentovanie grafu použite
nasledujúcu štruktúru:
- graf je jednorozmerné pole
vrcholov;
- pre každý vrchol si pamätá
svoje súradnice na obrazovke
a jednorozmerné bajtové
pole, v ktorom sú uchované
váhy, resp. informácia
o tom, že vrchol nemá spojenie
s iným vrcholom.
Je to vlastne zmodifikovaná tabuľka
susedností. To, že nejaké
dva vrcholy nie sú spojené
cestou, budete reprezentovať inou hodnotou
ako 0 (0 označuje absolútne nebezpečnú
cestu). Graf zadefinujte ako triedu TGraf
v samostatnom unite (napr. UnitGraf.pas),
pričom všetky stavové premenné
a väčšinu metód definujte ako
private (okrem konštruktora a metód,
ktoré odštartujú, resp. zastavia
backtracking). Tento unit sa môže
odvolávať (uses) len na štandardné
delphi-unity (nesmie sa v ňom použiť napr.
uses Unit1) a nesmú v ňom byť definované
žiadne globálne premenné.
Analytické stredisko informácie
o mape pripravilo do binárneho súboru
bond.dat, v ktorom je každá
veta premenlivej dĺžky a opisuje jeden vrchol
grafu. Každý vrchol má svoje
poradové číslo od 1 do 1000
(nie je to číslo vety v súbore),
pričom tieto poradové čísla
nemusia tvoriť súvislú postupnosť.
Tieto poradové čísla budú
indexmi vo vašej dátovej štruktúre
graf. Každá veta súboru obsahuje
tieto informácie:
- poradové číslo vrcholu
1..1000;
- súradnice v mape - dve celé
čísla x a y;
- postupnosť susediacich vrcholov
v tvare dvojice: poradové číslo
suseda (1..1000) a bezpečnosť cesty
(0..100);
- postupnosť je ukončená celým
číslom 0.
Všetky čísla v súbore okrem
hodnoty bezpečnosti cesty sú typu
integer (4-bajty), bezpečnosť je typu bajt.
So súborom pracujte pomocou triedy
TStream. Môžete predpokladať,
že súbor je korektný a všetky
hrany v grafe majú v oboch smeroch
rovnakú hodnotu nebezpečnosti. Východiskové
miesto pre agenta je vrchol v prvej vete
súboru, cieľové miesto je
vo vrchole v druhej vete súboru.
Program uloží tieto údaje
do štruktúry graf. Potom vykreslí
tento graf na obrazovku a na každú
hranu zapíše jej bezpečnosť. Východiskové
aj cieľové miesto v grafe nejako
vyznačte. Po stlačení tlačidla Štart
sa na ňom spustí algoritmus prehľadávania
s návratom (backtracking). Ten hľadá
najlepšiu cestu (počas backtrackingu sa
zafarbuje momentálna cesta), pričom
niekde na obrazovke sa vypisuje jej momentálna
bezpečnosť celej trasy. Ak sa počas backtrackingu
stlačí tlačidlo Stop, tak
algoritmus zastane a vykreslí doteraz
najlepšie riešenie. Ak neexistuje žiadna
trasa, alebo všetky trasy majú 0%
bezpečnosť, program o tom vypíše
správu.
Na testovanie programu môžete použiť
údajové súbory bond.zip.
|
unit UnitGraf;
interface
uses
Graphics;
const
max = 1000;
type
TVrchol = class
x,y:integer;
s:array [1..max] of integer;
visited:boolean;
constructor Create;
end;
TGraf = class
private
g:array [1..max] of TVrchol;
zac,kon:integer;
cesta,maxcesta:array of integer;
maxh:real;
stop:boolean;
c:TCanvas;
procedure kresli;
procedure backtracking(i:integer; h:real);
procedure ciara(i,j:integer; col:TColor);
public
constructor Create(meno:string; cc:TCanvas);
procedure start;
procedure zastav;
end;
implementation
uses
Classes, SysUtils, Forms;
const
nie=255;
constructor TVrchol.Create;
var
i:integer;
begin
for i:=1 to max do s[i]:=nie;
visited:=false;
end;
constructor TGraf.Create(meno:string; cc:TCanvas);
var
t:TStream;
i,j,k:integer;
begin
c:=cc;
t:=TFileStream.Create(meno,fmOpenRead);
k:=1;
while t.Position<t.Size do begin
t.Read(i,4);
g[i]:=TVrchol.Create;
if k=1 then zac:=i
else if k=2 then kon:=i;
inc(k);
with g[i] do begin
t.Read(x,4); t.Read(y,4);
repeat
t.Read(j,4); if j<>0 then t.Read(s[j],1);
until j=0;
end;
end;
t.Free;
kresli;
end;
procedure TGraf.kresli;
var
i,j:integer;
begin
c.Pen.Width:=3;
for i:=1 to max do
if g[i]<>nil then
with g[i] do begin
for j:=i+1 to max do
if s[j]<>nie then begin
ciara(i,j,clDkGray);
c.TextOut((x+g[j].x)div 2,(y+g[j].y)div 2,IntToStr(s[j])+'%');
end;
end;
c.Pen.Width:=1;
c.Brush.Color:=clBlue; with g[zac] do c.Ellipse(x-5,y-5,x+5,y+5);
c.Brush.Color:=clRed; with g[kon] do c.Ellipse(x-5,y-5,x+5,y+5);
end;
procedure TGraf.start;
var
i:integer;
begin
stop:=false; maxh:=0;
backtracking(zac,1);
c.Font.Height:=20; c.Brush.Style:=bsClear;
if maxh=0 then begin
c.TextOut(0,0,'Riešenie neexistuje')
end
else begin
c.TextOut(0,0,'Bezpečnosť cesty = '+FloatToStr(maxh*100)+'%');
for i:=0 to high(maxcesta)-1 do
ciara(maxcesta[i],maxcesta[i+1],clBlue);
end;
end;
procedure TGraf.ciara(i,j:integer; col:TColor);
begin
c.Pen.Color:=col;
with g[i] do c.MoveTo(x,y);
with g[j] do c.LineTo(x,y);
end;
procedure cakaj(ms:Longint);
var
potom:TDateTime;
begin
potom:=Now + EncodeTime(0,ms div 60000,(ms div 1000) mod 60,ms mod 1000);
while Now < potom do Application.ProcessMessages;
end;
procedure TGraf.backtracking(i:integer; h:real);
var
j:integer;
begin
if (h=0) or (h<maxh) then exit;
g[i].visited:=true; SetLength(cesta,Length(cesta)+1); cesta[high(cesta)]:=i;
if i=kon then begin
if h>maxh then begin
maxh:=h; maxcesta:=cesta;
end
end
else
for j:=1 to max do
if (g[j]<>nil) and not g[j].visited and (g[i].s[j]<>nie) then begin
ciara(i,j,clRed); cakaj(10);
backtracking(j,h*g[i].s[j]/100);
ciara(i,j,clDkGray);
if stop then exit;
end;
g[i].visited:=false; SetLength(cesta,Length(cesta)-1);
end;
procedure TGraf.zastav;
begin
stop:=true;
end;
end.
|
unit1 s formulárom:
|
unit Unit1;
interface
uses
Windows, Messages, SysUtils, Classes, Graphics, Controls, Forms, Dialogs,
StdCtrls, ExtCtrls;
type
TForm1 = class(TForm)
Image1: TImage;
Button1: TButton;
Button2: TButton;
procedure FormCreate(Sender: TObject);
procedure Button1Click(Sender: TObject);
procedure Button2Click(Sender: TObject);
end;
var
Form1: TForm1;
implementation
uses
UnitGraf;
{$R *.DFM}
var
g:TGraf;
procedure TForm1.FormCreate(Sender: TObject);
begin
DoubleBuffered:=true;
g:=TGraf.Create('bond1.dat',Image1.Canvas);
Button1.Enabled:=true;
Button2.Enabled:=false;
end;
procedure TForm1.Button1Click(Sender: TObject);
begin
Button1.Enabled:=false;
Button2.Enabled:=true;
g.start;
Button2.Enabled:=false;
end;
procedure TForm1.Button2Click(Sender: TObject);
begin
Button2.Enabled:=false;
g.zastav;
end;
end.
|
|
© 2002 AB, KVI blaho@fmph.uniba.sk
|