====== 6. cvičení - 6.11.2009 ======

===== Co jsme dělali? =====

==== Fronta, zásobník a jejich aplikace ====

  * sémantika, úvod do implementace
  * [[wp>Queue_(data_structure)|fronta]]
    * [[#ukazka_fronty|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í [[#skakani_po_sachovnici|nejkratší cesty figurky po šachovnici]]
  * [[wp>Stack_(data_structure)|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

=== Skákání po šachovnici ===

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
        * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/KUN_VLN1.PAS|řízené přímo políčky]]
        * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/KUN_VLN2.PAS|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
     * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/KUN_BACK.PAS|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ě, ...

==== Dlouhá čísla ====

  * [[wp>Arbitrary_precision_arithmetic|čísla s libovolnou přesností]], zamaskované polynomy
  * reprezentace celých čísel i [[wp>Fixed_point_arithmetic|čí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í [[wp>Taylor_polynoial|Taylorova polynomu]]
    * Machinova formule [[http://www.cs.ualberta.ca/~smillie/PiNotes/PiNotes.html#Sect05|1]], [[http://en.literateprograms.org/Pi_with_Machin%27s_formula_%28Python%29|2]]
  * {{:vyuka:2009-10:dlouha-cisla-holan.pdf|Dlouhá čísla}} (autor: [[http://ksvi.mff.cuni.cz/~holan/|RNDr. Tomáš Holan]])

===== Příklady zdrojáků =====

  * další zdrojáky
    * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/ZASOB1.PAS|zásobník]] v poli
    * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/ZASOB2.PAS|zásobník]] pomocí lineárního spojového seznamu
    * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/FRONTA1.PAS|fronta]] v poli
    * [[http://mff.zamecnik.org/NPRG044-programovani-I/topfer/FRONTA2.PAS|fronta]] pomocí lineárního spojového seznamu

==== Ukázka fronty ====


<code pascal>
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.
</code>