34.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
 
(3 intermediate revisions by the same user not shown)
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;
 
 
* konštruktor
 
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 opakovania
 
function opakujesa(S:String) : boolean;
 
var
 
  I: Integer;
 
begin
 
  Result := True;
 
  for I := 0 to High(Memo) do
 
    if Memo[I] = S then
 
      Exit;
 
  Result := False;
 
end;
 
* 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
 
:* funkciu '''opakujesa''' nam vlastne netreba
 
function index(S:String) : integer;
 
var
 
  I: Integer;
 
begin
 
  Result := -1;
 
  for I := 0 to High(Memo) do
 
    if Memo[I] = S then
 
      Result := I;
 
end;
 
* zostrojenie grafu
 
  SetLength(Pole, Length(Meno), Length(Meno));
 
  for I := 0 to High(Pole) do
 
    for J := 0 to High(Pole) do
 
      Pole[I, J] := False;
 
  //alebo
 
  //FillChar(Pole[0,0], ..., 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));
 
      Pole[I, J] := True;
 
      Pole[J, I] := True;
 
      Delete(S, 1, P);
 
    end;
 
  end;
 
* vrchol s najmenším a najväčším počtom susedov
 
function 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;
 
* zistiť, či je garf súvislý
 
procedure TGraf.DoHlbky(V:Integer);
 
begin
 
  Visited[V] := True;
 
  for I:= 0 to High(Pole) do
 
    if pole[I][v] and not Visited[I] then
 
      DoHlbky(I);
 
end;
 
 
function TGraf.JeSuvisly : Boolean;
 
begin
 
  SetLen)gth(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);   
 
  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)