6. cvičení - 6.11.2009

• sémantika, úvod do implementace
• fronta
  • ukázka implementace
  • operace
    • insert - přidání prvku na konec fronty, není-li plná
    • pop - odebrání prvku ze začátku fronty, není-li prázdná
  • aplikace: prohledávání do šířky
    • např. pro hledání nejkratší cesty figurky po šachovnici
• zásobník
  • operace
    • push - přidání prvku na vrchol zásobníku, není-li zásobník plný
    • pop - odebrání prvku z vrcholu zásobníku, není-li zásobník prázdný
  • závorky
  • rozpoznávání jazyků
    • A^nB^n, n >= 1

Zadání lze nakombinovat z následujících podmínek:

• cíl programu:
  • najít délku nejkratší cesty ze zdrojového políčka na cílové políčko
    • → prohledávání do šířky
      • řízené přímo políčky
      • frontou dalších políček
  • najít nejkratší cestu ze zdrojového políčka na cílové políčko
    • → prohledávání do šířky
    • navíc si pamatujeme odkud jsme se dostali na každé políčko
  • najít všechna políčka, kam se lze dostat ze zdrojového políčka
    • → backtracking, tj. prohledávání do hloubky - pomocí rekurze nebo vlastního zásobníku
• navštívit všechna dostupná políčka právě jednou
  • backtracking
• podmínky
  • šachovnice - rozměry NxN, MxN, wrapovací
  • použita zakázaná políčka (tj. miny nebo políčka obsazená jinými figurkami) - ano/ne
  • figurka:
    • chodí na relativně zadaná sousední políčka - př.: kůň, král, …
    • chodí podle jednoho pravidla - př.: věž, střelec, …
    • při chůzi si může vybrat z více možných pravidel pohybu, např.:
      • dáma - kombinace věže a střelce
      • různé „power“ figurky - kombinace dámy a koně, věže a koně, střelce a koně, …

• čísla s libovolnou přesností, zamaskované polynomy
• reprezentace celých čísel i čísel s pevnou řádovou čárkou
• operace s nimi - sčítání, [násobení, opačné číslo]
• výpočet hodnot některých iracionálních čísel na hodně míst - e, pí, [sqrt(2), …]
• výpočet hodnot dlouhých čísel - faktoriál, kombinační čísla, …
  • aproximace pomocí Taylorova polynomu
  • Machinova formule 1, 2
• Dlouhá čísla (autor: RNDr. Tomáš Holan)

• další zdrojáky
  • zásobník v poli
  • zásobník pomocí lineárního spojového seznamu
  • fronta v poli
  • fronta pomocí lineárního spojového seznamu

program circularQueue;
{ A circular queue implemented in an array. }
 
{ Author: Bohumir Zamecnik. Date: 2009/11/11 }
 
const
    maxQueueSize = 10;
type
    tQueue = array [0..maxQueueSize-1] of integer;
var
    queue : tQueue;
    qFront : integer;
    qBack : integer;
    nItems : integer;
 
procedure init;
begin
     qFront := 0; {pointer to the first item}
     qBack := maxQueueSize - 1; {pointer to the last item}
end;
 
function getUsedCapacity : integer;
begin
     getUsedCapacity := nItems
end;
 
function getFreeCapacity : integer;
begin
     getFreeCapacity := maxQueueSize - getUsedCapacity
end;
 
{insert an item to the back of the queue}
procedure insert(item:integer);
begin
     writeln('insert(', item, ')');
     if (getFreeCapacity > 0) then
     begin
          qBack := (qBack + 1) mod maxQueueSize;
          queue[qBack] := item;
          nItems := nItems + 1
     end
     else
     begin
          writeln('insert(): error - inserting into a full queue.');
     end
end;
 
{get an item from the front of the queue and remove it from there}
function pop : integer;
begin
     if (getUsedCapacity > 0) then
     begin
          pop := queue[qFront];
          writeln('pop(): ', queue[qFront]);
          qFront := (qFront + 1) mod maxQueueSize;
          nItems := nItems - 1;
     end
     else
     begin
          writeln('pop(): error - popping from an empty queue.');
          pop := -1
     end
end;
 
procedure printQueue;
var
   i : integer;
   first, last, tmp : integer;
begin
     for i := 0 to maxQueueSize - 1 do
     begin
          write(queue[i], ', ');
     end;
     writeln
end;
 
var
   i : integer;
begin
     init;
     { a queue test }
     printQueue;
     for i := 0 to maxQueueSize - 1 do
     begin
          insert(i*2);
          insert(i*2+1);
          pop;
          printQueue;
     end;
 
     for i := 0 to maxQueueSize - 1 do
     begin
          pop;
          printQueue;
     end;
end.