32.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
(Vytvorená stránka „{{Nadpis| 32. Cvičenie}} < 32.Prednáška | riešené úlohy <!-- --> === Rozcvička === 1. napíšte podprogram, ktorý pr...“)
 
Riadok 8: Riadok 8:
  
  
1. napíšte podprogram, ktorý pre '''neorientovaný''' graf:
+
1. napíšte funkciu, ktorá pre '''neorientovaný''' graf:
 
{{Prog}}
 
{{Prog}}
 
  type
 
  type
Riadok 17: Riadok 17:
 
  function TGraf.PocetIzolovanych: Integer;
 
  function TGraf.PocetIzolovanych: Integer;
 
|}
 
|}
* funkcia zistí počet izolovaných vrcholov
+
* zistí počet izolovaných vrcholov
  
2. napíšte funkciu
+
2. napíšte funkciu, ktorá pre graf:
 
{{Prog}}
 
{{Prog}}
  ...
+
  type
 +
  TGraf = class
 +
    G: array [1..N,1..N] of Boolean;  // alebo G: array of set of Byte;
 +
  end;
 +
&nbsp;
 +
function TGraf.JeOrientovany: Boolean;
 
|}
 
|}
* vráti
+
* zistí, či je graf orientovaný
  
  
Riadok 31: Riadok 36:
  
  
*  
+
pre rôzne grafy (okolo 12 vrcholov, alebo labyrint v štvorcovej sieti)
 +
* najprv ručne: do hĺbky, do šírky, vzdialenosť/cestu medzi dvoma vrcholmi
 +
* potom zapisovať algoritmy pre:
 +
** veľkosť komponentu, ktorý obsahuje vrchol V
 +
** počet komponentov
 +
** najväčší komponent
 +
** do šírky bez Queue ale pomocou pomocného dynamického poľa
 +
 
 +
 
 
<!-- -->
 
<!-- -->
  
 
=== Domáca úloha ===
 
=== Domáca úloha ===
  
1. naprogramovať
+
1. naprogramovať podprogram, ktorý do grafu pridá pridá novú hranu tak, že sa vďaka tomu zníži počet komponentov:
 +
function TGraf.PridajHranu: Boolean;
 +
* vráti False, ak sa už hrana pridať nedala (graf bol už súvislý)

Verzia zo dňa a času 05:43, 12. apríl 2013

32. Cvičenie


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


Rozcvička

1. napíšte funkciu, ktorá pre neorientovaný graf:

type
  TGraf = class
    G: array [1..N,1..N] of Boolean;
  end;
 
function TGraf.PocetIzolovanych: Integer;
  • zistí počet izolovaných vrcholov

2. napíšte funkciu, ktorá pre graf:

type
  TGraf = class
    G: array [1..N,1..N] of Boolean;   // alebo G: array of set of Byte;
  end;
 
function TGraf.JeOrientovany: Boolean;
  • zistí, či je graf orientovaný


Cvičenie

pre rôzne grafy (okolo 12 vrcholov, alebo labyrint v štvorcovej sieti)

  • najprv ručne: do hĺbky, do šírky, vzdialenosť/cestu medzi dvoma vrcholmi
  • potom zapisovať algoritmy pre:
    • veľkosť komponentu, ktorý obsahuje vrchol V
    • počet komponentov
    • najväčší komponent
    • do šírky bez Queue ale pomocou pomocného dynamického poľa


Domáca úloha

1. naprogramovať podprogram, ktorý do grafu pridá pridá novú hranu tak, že sa vďaka tomu zníži počet komponentov:

function TGraf.PridajHranu: Boolean;
  • vráti False, ak sa už hrana pridať nedala (graf bol už súvislý)