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 30: Riadok 31:
 
* súbor [[Media:P34_graf.txt|graf.txt]] obsahuje popis grafu
 
* súbor [[Media:P34_graf.txt|graf.txt]] obsahuje popis grafu
 
** prečítať a vytvoriť graf (prvé meno v riadku má niektorých svojich kamarátov vymenovaných do konca riadka) = graf je neorientovaný
 
** prečítať a vytvoriť graf (prvé meno v riadku má niektorých svojich kamarátov vymenovaných do konca riadka) = graf je neorientovaný
** zistiť počet vrcholov, počet komponentov, vrchol s najmenším aj najväčším počtom susedov
+
:* spracovať do matice susedností (zdá sa, že vrcholov je menej ako 1000)
** zistiť, či je graf súvislý (algoritmus do hĺbky)
+
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 ===
 
=== Domáca úloha ===

Verzia zo dňa a času 09:34, 10. 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)


Cvičenie

práca s grafom a s textovým (binárnym) súborom

  • súbor graf.txt obsahuje popis grafu
    • prečítať a vytvoriť graf (prvé meno v riadku má niektorých svojich kamarátov 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

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