36. Informácie ku skúške


posledná zmena: 9.5.2002

Banner Text 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)

  1. (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').

  1. (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;

    Doplňte chýbajúce časti programu.

  1. (34/ 0.3)  Zistite, koľko existuje rôznych aritmetických stromov, ktorých inorder je
    1+2+3+4+5+6+7+8
  1. (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.

  1. (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);

    V programe je chyba a preto nám výpis nedá správne výsledky.

      1. Zistite, čo sa presne vypíše.
      2. Opravte chybu.
      3. Zistite, čo sa vypíše po oprave chyby.
  1. (2.3 / 1.1)  Pred vykonaním procedúry VytvorHaldu vyzerá pole, z ktorého chceme vytvoriť haldu, takto:
1
9
7
8
5
6
3
2
4

    Vypíšte obsah poľa po skončení procedúry.

  1. (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;

    Po zavolaní

  g:=TGraf.Create;
  for i:=1 to 10 do g.pridajVrchol;

    sa vytvorí graf s 10 vrcholmi.

      1. Nakreslite tento graf.
      2. Navrhnite do grafu minimálny počet nových hrán tak, aby sa tento graf stal súvislý.
  1. (2.7 / 1.1)  Pomocou triedenia zlučovaním chceme utriediť 10-prvkové pole:
5
15
3
8
1
23
7
3
17
27

    Časť algoritmu vyzerá takto:

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.

  1. (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.

  1. (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ži­te 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