34.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
 
Riadok 1: Riadok 1:
 
{{Nadpis| 34. Cvičenie}}
 
{{Nadpis| 34. Cvičenie}}
 
[[34.Prednaska|< 34.Prednáška]] | [[34.Prednaska/Ulohy|riešené úlohy]]
 
[[34.Prednaska|< 34.Prednáška]] | [[34.Prednaska/Ulohy|riešené úlohy]]
 
 
  
 
<!-- -->
 
<!-- -->
Riadok 22: Riadok 20:
 
|}
 
|}
 
* pre daný graf metóda '''Dosirky''' spustí algoritmus do šírky a očísluje všetky vrcholy (do premennej '''Meno''') tak, že štartový vrchol '''V''' má '''Meno''' = 0, jeho bezprostrední susedia majú postupne hodnoty od 1 vyššie, všetci ich ďalší susedia majú vyššie a vyššie očíslovanie; zrejme sú vrcholy očíslované rôznymi hodnotami 0 až '''N'''-1 (nemáme k dispozícii štruktúru '''Queue''')
 
* pre daný graf metóda '''Dosirky''' spustí algoritmus do šírky a očísluje všetky vrcholy (do premennej '''Meno''') tak, že štartový vrchol '''V''' má '''Meno''' = 0, jeho bezprostrední susedia majú postupne hodnoty od 1 vyššie, všetci ich ďalší susedia majú vyššie a vyššie očíslovanie; zrejme sú vrcholy očíslované rôznymi hodnotami 0 až '''N'''-1 (nemáme k dispozícii štruktúru '''Queue''')
 
<!-- -->
 
 
=== Cvičenie ===
 
 
 
práca s grafom a s textovým (binárnym) súborom
 
* súbor [[Media:P34_graf.txt|graf.txt]] obsahuje popis grafu
 
** prečítať a vytvoriť graf (prvé meno v každom riadku má uvedených niektorých svojich kamarátov postupne vymenovaných do konca riadka) = graf je neorientovaný
 
** spracovať do matice susedností (zdá sa, že vrcholov je menej ako 1000)
 
type TGraf = class
 
  Pole: array of array of Boolean;
 
  Meno: array of string;
 
  constructor Create;
 
  function OpakujeSa(S: string): Boolean;
 
end;
 
 
* najprv v konštruktore prečítame všetky mená a zaradíme ich do poľa '''Mena''' - každé meno práve raz:
 
constructor TGraf.Create;
 
var
 
  F: TextFile;
 
  S, T: string;
 
  I, J: Integer;
 
begin
 
  AssignFile(F, 'graf.txt');
 
  Reset(F);
 
  while not EOF(F) do
 
  begin
 
    ReadLn(F, S);
 
    while S <> {{''}} do begin
 
      P := Pos(' ', S + ' ');
 
      T := Copy(S, 1, P - 1);
 
      if not OpakujeSa(T) do
 
      begin
 
        SetLength(Meno, Length(Meno) + 1);
 
        Meno[High(Meno)] := T;
 
      end;
 
      Delete(S, 1, P);
 
    end;
 
  end;
 
  // Tu bude kod na zostrojenie grafu
 
end;
 
* test, aby sa slová v poli '''Mena''' neopakovali
 
function TGraf.OpakujeSa(S: string): Boolean;
 
var
 
  I: Integer;
 
begin
 
  Result := True;
 
  for I := 0 to High(Meno) do
 
    if Meno[I] = S then
 
      Exit;
 
  Result := False;
 
end;
 
* v hlavnom programe môžeme otestovať a odladiť
 
...
 
Graf := TGraf.Create;
 
for I := 0 to High(Graf.Meno) do
 
  Write(Graf.Meno[I], ' ');
 
Writeln(Length(Graf.Meno));
 
...
 
* funkcia, ktorá zistí index mena v poli '''Mena'''
 
:* funkciu '''OpakujeSa''' teraz už nebudeme potrebovať
 
function Index(S: string): Integer;
 
var
 
  I: Integer;
 
begin
 
  for I := 0 to High(Memo) do
 
    if Memo[I] = S then
 
    begin
 
      Result := I;
 
      Exit;
 
    end;
 
  Result := -1;
 
end;
 
* dopíšeme zostrojenie grafu v konštruktore '''TGraf''':
 
  SetLength(Pole, Length(Meno), Length(Meno));          ''// najprv inicializujeme dvojrozmerné pole''
 
  for I := 0 to High(Pole) do
 
    for J := 0 to High(Pole) do
 
      Pole[I, J] := False;
 
  Reset(F);
 
  while not EOF(F) do
 
  begin
 
    ReadLn(F, S);
 
    P:=Pos(' ', S + ' ');
 
    I := Index(Copy(S, 1, P - 1));
 
    Delete(S, 1, P);
 
    while S <> {{''}} do
 
    begin
 
      P:=Pos(' ', S + ' ');
 
      J := Index(Copy(S, 1, P - 1));  ''// index ďalšieho mena v riadku''
 
      Pole[I, J] := True;
 
      Pole[J, I] := True;
 
      Delete(S, 1, P);
 
    end;
 
  end;
 
* aby sme mohli vypísať vrchol s najmenším a tiež najväčším počtom susedov
 
function TGraf.PocetSusedov(K: Integer): Integer;
 
var
 
  I:Integer;
 
begin
 
  Result := 0;
 
  for I := 0 to High(Pole) do
 
    if Pole[K, I] then begin
 
      Inc(Result);
 
end;
 
* aby sme mohli zistiť, či je graf súvislý
 
procedure TGraf.DoHlbky(V: Integer);
 
var
 
  I: Integer;
 
begin
 
  Visited[V] := True;
 
  for I:= 0 to High(Pole) do
 
    if Pole[I][V] and not Visited[I] then
 
      DoHlbky(I);
 
end;
 
&nbsp;
 
function TGraf.JeSuvisly : Boolean;
 
var
 
  I: Integer;
 
begin
 
  SetLength(Visited, Length(Pole));
 
  for I := 0 to High(Pole) do
 
    Visited[I] := False;
 
  DoHlbky(0);
 
  for I := 0 to High(Pole) do
 
    if Visited[I] = False then
 
      Exit(False);        ''// takto Exit ešte nastaví aj Result''
 
  Result := True;
 
end;
 
 
 
<!-- -->
 
 
=== Domáca úloha ===
 
 
1. do reprezentácie grafu doplnte pole a metódu
 
{{Prog}}
 
type
 
  TGraf = class
 
    ...
 
    Komponent: array of Integer;
 
    procedure UrobKomponenty;
 
  end;
 
|}
 
* metóda do poľa '''Komponent''' pre každý vrchol grafu zapíše číslo komponentu, v ktorom sa tento vrchol nachádza; ak sú dva vrcholy v tom istom komponente, majú v tomto poli rovnaké číslo; ak je graf súvislý, všetky vrcholy majú hodnotu 1
 

Aktuálna revízia z 10:09, 15. máj 2013

34. Cvičenie


< 34.Prednáška | riešené úlohy


Rozcvička

1. graf je zadeklarovaný:

type
  TVrchol = class
    Meno: Integer;
    Sus: set of 1..N;
  end;
  TGraf = class
    G: array [1..N] of TVrchol;
    procedure Dosirky(V: Integer);
  end;
  • pre daný graf metóda Dosirky spustí algoritmus do šírky a očísluje všetky vrcholy (do premennej Meno) tak, že štartový vrchol VMeno = 0, jeho bezprostrední susedia majú postupne hodnoty od 1 vyššie, všetci ich ďalší susedia majú vyššie a vyššie očíslovanie; zrejme sú vrcholy očíslované rôznymi hodnotami 0 až N-1 (nemáme k dispozícii štruktúru Queue)