33.Prednaska/Cvicenie: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
(Vytvorená stránka „{{Nadpis| 33. Cvičenie}} < 33.Prednáška | riešené úlohy pracujeme s triedami: TVrchol = class Sus: set of byte; end;...“)
 
 
Riadok 3: Riadok 3:
  
  
pracujeme s triedami:
+
<!-- -->
  TVrchol = class
+
 
   Sus: set of byte;
+
=== Cvičenie ===
 +
 
 +
 
 +
generovanie všetkých možností a backtracking - zatiaľ bez grafov
 +
* z daného slova vyrobiť všetky permutácie písmen (písmená v slove sú rôzne)
 +
{{Prog}}
 +
procedure Generuj(Vysledok, Vstup: string);
 +
  var
 +
  I: Integer;
 +
begin
 +
  if Vstup = {{''}} then
 +
    WriteLn(Vysledok)
 +
   else
 +
    for I := 1 to Length(Vstup) do
 +
      Generuj(Vysledok + Vstup[I], Copy(Vstup, 1, I - 1) + Copy(Vstup, I + 1, MaxInt));
 
  end;
 
  end;
   
+
  &nbsp;
  TGraf = class
+
  begin
   Visited: set of byte;
+
  Generuj({{''}}, 'abc');
   G: array of TVrchol;
+
  ReadLn;
  end;       
+
end.
 +
|}
 +
* to isté, ale schémou backtracking: globálna premenná '''Vysledok''', do ktorej sa skladá výsledok:
 +
{{Prog}}
 +
var
 +
  Vysledok: string = {{''}};
 +
   Vstup: string = 'ako';
 +
  Pocet: Integer;
 +
&nbsp;
 +
procedure Generuj;
 +
var
 +
  Z: Char;
 +
begin
 +
  if Length(Vysledok) = Length(Vstup) then
 +
  begin
 +
    WriteLn(Vysledok);
 +
    Inc(Pocet);
 +
  end
 +
  else
 +
    for Z in Vstup do
 +
      if Pos(Z, Vysledok) = 0 then    ''// if Moze then''
 +
      begin
 +
        Vysledok := Vysledok + Z;      ''// zaznač ťah''
 +
        Generuj;
 +
        SetLength(Vysledok, Length(Vysledok) - 1);      ''// odznač ťah''
 +
      end;
 +
end;
 +
&nbsp;
 +
begin
 +
  Generuj;
 +
  Writeln('pocet = ', Pocet);
 +
  ReadLn;
 +
end.
 +
|}
 +
* zamyslite sa nad tým, ako by mohla vyzerať funkcia, ktorá by vrátila dynamické pole všetkých takto vygenerovaných slov
 +
{{Prog}}
 +
type
 +
  TPole: array of string;
 +
function Permutacie(Slovo: string): TPole;
 +
|}
 +
* generovanie postupnosti číslic - všetky N-ciferné čísla, ktoré sú zložené len z číslic {2,3,5}
 +
{{Prog}}
 +
const
 +
   Mn = [2, 3, 5];
 +
  N = 6;
 +
var
 +
  Pole: array[1..N] of 0..9;
 +
&nbsp;
 +
procedure VypisPole;
 +
var
 +
  I: Integer;
 +
begin
 +
  for I := 1 to N do
 +
    Write(Pole[I]);
 +
  WriteLn;
 +
  end;
 +
&nbsp;
 +
procedure Generuj(Index: Integer);
 +
var
 +
  I: Integer;
 +
begin
 +
    for I in Mn do
 +
    begin
 +
      Pole[Index] := I;        ''// zaznač ťah''
 +
      if Index = N then
 +
        VypisPole
 +
      else
 +
        Generuj(Index + 1);
 +
      ''// odznač ťah - netreba''
 +
    end;
 +
end;
 +
|}
 +
* generovanie 3-písmenových slov (napr. z možiny {a, b, ..., z})
 +
* generovanie slov dĺžky 5: spoluhláska + samohláska + spoluhláska + samohláska + spoluhláska
 +
:* spoluhláska z množiny {k, m, p}
 +
:* samohláska  z množiny {a, e, o}
 +
:* vypísať všetky dĺžky 5 alebo aj kratšie
 +
* generovať všetky magické štvorce NxN políčok
 +
:* v každom riadku a stĺpci písmeno {'A', 'B, 'C', ...}
 +
:* na začiatku sa inicializuje prvý riadok a prvý stĺpec postupne hodnotami 'A', 'B, 'C', ...
 +
{{Prog}}
 +
const
 +
  N = 4;
 +
var
 +
  Pole: array[1..N, 1..N] of Char;
 +
&nbsp;
 +
procedure VypisPole;
 +
var
 +
  I: Integer;
 +
begin
 +
  for I := 1 to N do
 +
     Write(Pole[I]);
 +
  WriteLn('=============');
 +
end;
 +
&nbsp;
 +
procedure Stvorec(I, J: Integer);
 +
var
 +
  Znak: Char;
 +
begin
 +
    for Znak := 'A' to Char(64 + N) do
 +
    begin
 +
      Pole[I, J] := Znak;        ''// zaznač ťah''
 +
      if J < N then
 +
        Stvorec(I, J + 1)
 +
      else if I < N then
 +
        Stvorec(I + 1, 2)
 +
      else
 +
        VypisPole
 +
      ''// odznač ťah - netreba''
 +
    end;
 +
end;
 +
&nbsp;
 +
var
 +
  I: Integer;
 +
begin
 +
  for I := 1 to N do
 +
  begin
 +
    Pole[1, I] := Char(64 + I);
 +
    Pole[I, 1] := Char(64 + I);
 +
  end;
 +
  Stvorec(2, 2);
 +
|}
 +
* zamyslite sa nad tým, ako urobiť, aby program vypísal len 1. riešenie a korektne skončil (nie Halt)
 +
 
 +
* magické súčtové štvorce NxN s číslami 1..N*N
 +
:* každé číslo len raz, v každom riadku a stĺpci rovnaký súčet
 +
 
 +
* koľkými spôsobmi sa dá prejsť v sieti MxN z ľavého horného do pravého dolného rohu (niektoré políčka môžu byť obsadené)
 +
:* riešenia vypisovať tak, že v každom políčku je poradové číslo v ceste, nenavštívené budú 0
 +
{{Prog}}
 +
const
 +
  M = 3;
 +
  N = 4;
 +
var
 +
  Pole: array[1..M, 1..N] of Integer;
 +
  Pocet: Integer;
 +
&nbsp;
 +
procedure VypisPole;
 +
var
 +
  I, J: Integer;
 +
begin
 +
  for I := 1 to M do
 +
  begin
 +
    for J := 1 to N do
 +
      Write(Pole[I, J]:3);
 +
    WriteLn;
 +
  end;
 +
  WriteLn('=============');
 +
  Inc(Pocet);
 +
end;
 +
&nbsp;
 +
procedure HladajCestu(I, J, Cislo: Integer);
 +
begin
 +
  if (I in [1..M]) and (J in [1..N]) and (Pole[I, J] = 0) then
 +
  begin
 +
    Pole[I, J] := Cislo;        ''// zaznač ťah''
 +
    if (I = M) and (J = N) then
 +
      VypisPole
 +
    else
 +
    begin
 +
      HladajCestu(I -1 , J, Cislo + 1);
 +
      HladajCestu(I, J - 1, Cislo + 1);
 +
      HladajCestu(I + 1, J, Cislo + 1);
 +
      HladajCestu(I, J + 1, Cislo + 1);
 +
    end;
 +
    Pole[I, J] := 0;            ''// odznač ťah''
 +
  end;
 +
end;
 +
&nbsp;
 +
begin
 +
  ''// inicializuj Pole, napr. prečítaj zo súboru
 +
  HladajCestu(1, 1, 1);
 +
  WriteLn('pocet rieseni = ', Pocet);
 +
|}
 +
* zamyslite sa nad tým, ako urobiť, aby program vypísal len 1. riešenie a korektne skončil (nie Halt)
 +
* do políčok môžeme namiesto čísel dávať znaky '>', '^', '<', 'v', podľa toho ktorým smerom sa treba pohnúť na nasledovné políčko
 +
 
  
 
<!-- -->
 
<!-- -->
Riadok 17: Riadok 207:
 
=== Domáca úloha ===
 
=== Domáca úloha ===
  
1. naprogramovať podprogram, ktorý v neorientovanom grafe nájde pre zadaný vrchol '''V''' počet vrcholov v komponente v ktorom sa nachádza:
+
0. naprogramovať podprogram, ktorý v neorientovanom grafe nájde pre zadaný vrchol '''V''' počet vrcholov v komponente v ktorom sa nachádza:
 
  function TGraf.PocetVrcholovKomponentu(V:Integer): Integer;
 
  function TGraf.PocetVrcholovKomponentu(V:Integer): Integer;
 
* graf samozrejme nemusí byť súvislý
 
* graf samozrejme nemusí byť súvislý
 +
 +
1. (aspoň za 2 body) štvorcová plocha má MxN políčok, niektoré z nich sú už obsadené (prečítať z textového súboru)
 +
* hľadáme ľubovoľné pokrytie tejto plochy triominami
 +
:* triomina sú zložené z troch štvorčekov - navzájom sa dotýkajú stranami - neležia v jednom rade
 +
* počet voľných políčok v ploche je násobok 3
 +
* napr. pre zadanie (x sú obsadené) je takéto pokrytie triminami (a..e)
 +
{{Prog}}
 +
..x...    aaxcee
 +
......    abccde
 +
..x..x    bbxddx
 +
|}
 +
 +
2. (aspoň za 2 body) na šachovnici MxN (niektoré políčka môžu byť už obsadené) treba obísť všetky políčka (každé len raz) šachovou figúrkou koňa
 +
 +
<!-- -->

Aktuálna revízia z 11:59, 15. máj 2013

33. Cvičenie


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


Cvičenie

generovanie všetkých možností a backtracking - zatiaľ bez grafov

  • z daného slova vyrobiť všetky permutácie písmen (písmená v slove sú rôzne)
procedure Generuj(Vysledok, Vstup: string);
var
  I: Integer;
begin
  if Vstup = '' then
    WriteLn(Vysledok)
  else
    for I := 1 to Length(Vstup) do
      Generuj(Vysledok + Vstup[I], Copy(Vstup, 1, I - 1) + Copy(Vstup, I + 1, MaxInt));
end;
 
begin
  Generuj('', 'abc');
  ReadLn;
end.
  • to isté, ale schémou backtracking: globálna premenná Vysledok, do ktorej sa skladá výsledok:
var
  Vysledok: string = '';
  Vstup: string = 'ako';
  Pocet: Integer;
 
procedure Generuj;
var
  Z: Char;
begin
  if Length(Vysledok) = Length(Vstup) then
  begin
    WriteLn(Vysledok);
    Inc(Pocet);
  end
  else
    for Z in Vstup do
      if Pos(Z, Vysledok) = 0 then    // if Moze then
      begin
        Vysledok := Vysledok + Z;      // zaznač ťah
        Generuj;
        SetLength(Vysledok, Length(Vysledok) - 1);      // odznač ťah
      end;
end;
 
begin
  Generuj;
  Writeln('pocet = ', Pocet);
  ReadLn;
end.
  • zamyslite sa nad tým, ako by mohla vyzerať funkcia, ktorá by vrátila dynamické pole všetkých takto vygenerovaných slov
type
  TPole: array of string;
function Permutacie(Slovo: string): TPole;
  • generovanie postupnosti číslic - všetky N-ciferné čísla, ktoré sú zložené len z číslic {2,3,5}
const
  Mn = [2, 3, 5];
  N = 6;
var
  Pole: array[1..N] of 0..9;
 
procedure VypisPole;
var
  I: Integer;
begin
  for I := 1 to N do
    Write(Pole[I]);
  WriteLn;
end;
 
procedure Generuj(Index: Integer);
var
  I: Integer;
begin
   for I in Mn do
   begin
     Pole[Index] := I;        // zaznač ťah
     if Index = N then
       VypisPole
     else
       Generuj(Index + 1);
     // odznač ťah - netreba
   end;
end;
  • generovanie 3-písmenových slov (napr. z možiny {a, b, ..., z})
  • generovanie slov dĺžky 5: spoluhláska + samohláska + spoluhláska + samohláska + spoluhláska
  • spoluhláska z množiny {k, m, p}
  • samohláska z množiny {a, e, o}
  • vypísať všetky dĺžky 5 alebo aj kratšie
  • generovať všetky magické štvorce NxN políčok
  • v každom riadku a stĺpci písmeno {'A', 'B, 'C', ...}
  • na začiatku sa inicializuje prvý riadok a prvý stĺpec postupne hodnotami 'A', 'B, 'C', ...
const
  N = 4;
var
  Pole: array[1..N, 1..N] of Char;
 
procedure VypisPole;
var
  I: Integer;
begin
  for I := 1 to N do
    Write(Pole[I]);
  WriteLn('=============');
end;
 
procedure Stvorec(I, J: Integer);
var
  Znak: Char;
begin
   for Znak := 'A' to Char(64 + N) do
   begin
     Pole[I, J] := Znak;        // zaznač ťah
     if J < N then
       Stvorec(I, J + 1)
     else if I < N then
       Stvorec(I + 1, 2)
     else
       VypisPole
     // odznač ťah - netreba
   end;
end;
 
var
  I: Integer;
begin
  for I := 1 to N do
  begin
    Pole[1, I] := Char(64 + I);
    Pole[I, 1] := Char(64 + I);
  end;
  Stvorec(2, 2);
  • zamyslite sa nad tým, ako urobiť, aby program vypísal len 1. riešenie a korektne skončil (nie Halt)
  • magické súčtové štvorce NxN s číslami 1..N*N
  • každé číslo len raz, v každom riadku a stĺpci rovnaký súčet
  • koľkými spôsobmi sa dá prejsť v sieti MxN z ľavého horného do pravého dolného rohu (niektoré políčka môžu byť obsadené)
  • riešenia vypisovať tak, že v každom políčku je poradové číslo v ceste, nenavštívené budú 0
const
  M = 3;
  N = 4;
var
  Pole: array[1..M, 1..N] of Integer;
  Pocet: Integer;
 
procedure VypisPole;
var
  I, J: Integer;
begin
  for I := 1 to M do
  begin
    for J := 1 to N do
      Write(Pole[I, J]:3);
    WriteLn;
  end;
  WriteLn('=============');
  Inc(Pocet);
end;
 
procedure HladajCestu(I, J, Cislo: Integer);
begin
  if (I in [1..M]) and (J in [1..N]) and (Pole[I, J] = 0) then
  begin
    Pole[I, J] := Cislo;        // zaznač ťah
    if (I = M) and (J = N) then
      VypisPole
    else
    begin
      HladajCestu(I -1 , J, Cislo + 1);
      HladajCestu(I, J - 1, Cislo + 1);
      HladajCestu(I + 1, J, Cislo + 1);
      HladajCestu(I, J + 1, Cislo + 1);
    end;
    Pole[I, J] := 0;            // odznač ťah
  end;
end;
 
begin
  // inicializuj Pole, napr. prečítaj zo súboru
  HladajCestu(1, 1, 1);
  WriteLn('pocet rieseni = ', Pocet);
  • zamyslite sa nad tým, ako urobiť, aby program vypísal len 1. riešenie a korektne skončil (nie Halt)
  • do políčok môžeme namiesto čísel dávať znaky '>', '^', '<', 'v', podľa toho ktorým smerom sa treba pohnúť na nasledovné políčko


Domáca úloha

0. naprogramovať podprogram, ktorý v neorientovanom grafe nájde pre zadaný vrchol V počet vrcholov v komponente v ktorom sa nachádza:

function TGraf.PocetVrcholovKomponentu(V:Integer): Integer;
  • graf samozrejme nemusí byť súvislý

1. (aspoň za 2 body) štvorcová plocha má MxN políčok, niektoré z nich sú už obsadené (prečítať z textového súboru)

  • hľadáme ľubovoľné pokrytie tejto plochy triominami
  • triomina sú zložené z troch štvorčekov - navzájom sa dotýkajú stranami - neležia v jednom rade
  • počet voľných políčok v ploche je násobok 3
  • napr. pre zadanie (x sú obsadené) je takéto pokrytie triminami (a..e)
..x...    aaxcee
......    abccde
..x..x    bbxddx

2. (aspoň za 2 body) na šachovnici MxN (niektoré políčka môžu byť už obsadené) treba obísť všetky políčka (každé len raz) šachovou figúrkou koňa