33.Prednaska/Cvicenie0: Rozdiel medzi revíziami

Z Pascal
Prejsť na: navigácia, hľadanie
 
Riadok 27: Riadok 27:
  
 
<!-- -->
 
<!-- -->
 
=== 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;
 
&nbsp;
 
begin
 
  Generuj({{''}}, 'abc');
 
  ReadLn;
 
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
 
 
 
<!-- -->
 
 
=== Domáca úloha ===
 
 
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 12:00, 15. 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);