33.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
Riadok 31: Riadok 31:
  
  
backtracking - zatiaľ bez grafov
+
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)
 
* z daného slova vyrobiť všetky permutácie písmen (písmená v slove sú rôzne)
  procedure Generuj(const S, Z: string);
+
{{Prog}}
 +
  procedure Generuj(Vysledok, Vstup: string);
 
  var
 
  var
 
   I: Integer;
 
   I: Integer;
 
  begin
 
  begin
   if Z = {{''}} then
+
   if Vstup = {{''}} then
     WriteLn(S)
+
     WriteLn(Vysledok)
 
   else
 
   else
     for I := 1 to Length(Z) do
+
     for I := 1 to Length(Vstup) do
       Generuj(S + Z[I], Copy(Z, 1, I - 1) + Copy(Z, I + 1, MaxInt));
+
       Generuj(Vysledok + Vstup[I], Copy(Vstup, 1, I - 1) + Copy(Vstup, I + 1, MaxInt));
 
  end;
 
  end;
   
+
   
 
  begin
 
  begin
 
   Generuj({{''}}, 'abc');
 
   Generuj({{''}}, 'abc');
 
   ReadLn;
 
   ReadLn;
 
  end.
 
  end.
 
+
|}
* generovanie postupnosti číslic - všetky 6-ciferné len z číslic {2,3,5}
+
* 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;
 +
 
 +
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.
 +
|}
 +
* generovanie postupnosti číslic - všetky N-ciferné čísla, ktoré sú zložené len z číslic {2,3,5}
 +
{{Prog}}
 +
const
 +
  Mn = [2, 3, 5];
 +
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 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
 
* generovanie slov dĺžky 5: spoluhláska + samohláska + spoluhláska + samohláska + spoluhláska

Verzia zo dňa a času 09:23, 3. máj 2013

33. Cvičenie


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


Rozcvička

1. napíšte konštruktor TGraf2.Create(...):

type
  TGraf1 = class
    G: array [1..N,1..N] of Boolean;
  end;
 
type
  TGraf2 = class
    G: array [1..N] of set of 1..N;
    constructor Create(Graf1: TGraf1);
  end;
  • druhý graf s reprezentáciou pole množín bude kópiou grafu s reprezentáciou maticou susedností

2. skoro to isté, ale opačne: constructor TGraf1.Create(Graf2: TGraf2);


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.
  • generovanie postupnosti číslic - všetky N-ciferné čísla, ktoré sú zložené len z číslic {2,3,5}
const
  Mn = [2, 3, 5];
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
  • magické štvorce (všetky riešenia, alebo stačí len 1; v niektorých políčkach už môžu byť zadané hodnoty):
  • v každom riadku a stĺpci práve raz 1..N
  • 1..N*N: 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
  • riešenia vypisovať tak, že v každom políčku je poradové číslo v ceste, nenavštívené budú 0


Domáca úloha

1. š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