[[programovani-i|Programování I - cvičení]]

====== 3. cvičení - 16.10.2009 ======

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

==== Ukázky různé složitosti algoritmů ====

=== Umocňování čísla na velký exponent ===

<code pascal>
program power;

{ Exponentiate a base to an exponent: base^exp }

{ Compute base^exp in O(n) time by simple multiplication. }
function power_linear_time(base, exp : integer) : integer;
var
	product : integer; {base i-times multiplied with itself = base^i}
        i : integer;
begin
	product := 1;
	for i := 0 to exp - 1 do
		product := product * base;
	power_linear_time := product
end;

{
Compute base^exp in O(log_2(n)) time.
The exponent is
Intermediate powers are utilized
}
function power_log_time(base, exp : integer) : integer;
var
	product : integer;
	tmp_power : integer; {intermediate power}
	i : integer;
begin
	tmp_power := base;
	product := 1;
	i := exp;
	while (i > 0) do
	begin
		if ((i mod 2) = 1) then
		begin
			product := product * tmp_power
		end;
		tmp_power := tmp_power * tmp_power;
		i := i div 2
	end;
	power_log_time := product
end;

var
   base, exp : integer;

begin
     readln(base, exp);
     writeln('exp O(n): ', base, '^', exp, ' = ', power_linear_time(base, exp));
     writeln('exp O(log(n)): ', base, '^', exp, ' = ', power_log_time(base, exp));
end.
</code>

=== Testování, jestli číslo je mocninou dvojky ===

Je-li číslo N mocninou dvojky, má v binárním zápisu jedničku a pak samé nuly. N-1 má binárním zápisu samé jedničky. Tedy bitový součin (N AND (N - 1)) je roven nule. To lze použít k efektivnímu testu v čase O(1).

Příklad:

  N = 32
  
      100000 = 32
  AND 011111 = 31
  ---------------
    = 000000 =  0
  
  N = 91
  
      1011010 = 90
  AND 1011001 = 89
  ----------------
    = 1011000 = 88 != 0
  
<code pascal>
function isPowerOfTwo(n:integer) : boolean;
begin
  isPowerOfTwo := (n AND (n - 1)) = 0
end;
</code>

Méně efektivním řešením by bylo například v cyklu dělit číslo dvojkou a koukat se, jestli někde nedostaneme jako zbytek jedničku. To nám ale zabere čas O(log(B)), kde B je počet bitů čísla.

<code pascal>
function isPowerOfTwo(n:integer) : boolean;
begin
  while (n > 0) do
  begin
    if ((n mod 2) = 1) then 
    begin
      isPowerOfTwo := false;
      exit
    end;
    n := n div 2
  end;
  isPowerOfTwo := true
end;
</code>

==== Práce s textovými řetězci a se znaky ====

=== Otočení textového řetězce (vypsání pozpátku) ===

Načteme textový řetězec a chceme ho vypsat v opačném pořadí znaků.

<code pascal>
program reverse_string;

var
   s : string;
   i, n : integer;

begin
     readln(s);
     n := length(s);
     for i:=1 to n do
     begin
          write(s[n-i+1]);
     end;
     writeln
end.
</code>

  * Zkuste si toto naimplementovat jako funkci ''function reverse(text : string) : string);''.
  * Zkuste si naimplementovat proceduru ''procedure reverse_array(var arr : array of integer));'', která otočí pole.

=== Zkuste si ===

Zkuste si naimplementovat pár jednoduchých funkcí pro práci se znaky a textem. Použijte funkce ''ord'' a ''chr'' (viz nápovědu v Borland Pascalu nebo Google). Využívejte už hotové věci pro tvorbu dalších věcí.

  * manipulace se znaky
    * napište funkci ''toLower(c : char) : char'', která velká písmena anglické abecedy převede na malá a ostatní znaky nechá být, jak jsou
    * napište funkci ''toUpper(c : char) : char'', která malá písmena anglické abecedy převede na velká a ostatní znaky nechá být, jak jsou
    * napište funkci ''toLowerStr(text : string) : string'', která převede v textu velká písmena anglické abecedy na malá a ostatní znaky nechá být, jak jsou
    * podobně napište symetrickou funkci ''toUpperStr(text : string) : string'', která převede v textu malá písmena anglické abecedy na velká a ostatní znaky nechá být, jak jsou
  * predikáty pro znaky
    * napište funkci ''isLower(c : char) : boolean'', která zjistí, zda-li znak je malé je písmeno anglické abecedy nebo není
    * podobně napište symetrickou ''isUpper(c : char) : boolean''
    * napište funkci ''isLetter(c : char) : boolean'', která zjistí, zda-li znak je písmeno anglické abecedy nebo není
    * napište funkci ''isDigit(c : char) : boolean'', která zjistí, zda-li znak je číslice nebo není
    * napište funkci ''isAlphaNum(c : char) : boolean'', která zjistí, zda-li znak je číslice nebo písmeno anglické abecedy, nebo není nic z toho
  * Zkuste rozšírit úlohu [[domaci-ulohy#frekvencni_analyza_textu|frekvenční analýza textu]] tak, aby analyzovala malá i velká písmena a také číslice.
  * Zkuste rozšírit úlohu [[domaci-ulohy#frekvencni_analyza_textu|frekvenční analýza textu]] tak, aby analyzovala všechny tisknutelné znaky.
  * Zkuste rozšírit úlohu [[domaci-ulohy#frekvencni_analyza_textu|frekvenční analýza textu]] tak, aby analyzovala všechny znaky znakové sady ASCII tak, že budete vypisovat i číslo znaku. Netisknutelné znaky (viz stránku o [[wp>ASCII]] na Wikipedii) nevypisujte.

==== Práce s IDE Borland Pascal ====

=== "Hello world!" ===

<code pascal>
program helloworld;
begin
  writeln("Hello world!")
end.
</code>

  * [[http://mff.lokiware.info/KlavesoveZkratky|klávesové zkratky]] k FP/BP.
  * Pár slov od dr. Holana, [[http://ksvi.mff.cuni.cz/~topfer/Texty/ide.pdf|jak se IDE Free Pascalu používá]] (je to velice podobné jako u BP).
  * IDE = Integrated Development Environment, tj. v rámci jednoho prostředí máte editor kódu, kompilátor, debugger, nápovědu a další funkce
  * spuštení, nastavení adresářů (hlavně pracovního)
  * práce se soubory - vytvoření, uložení, otevření
  * editace zdrojového kódu
  * práce s okny
  * kompilace, spuštení, pohled na výstup z programu
  * spuštění v režimu ladění (pomocí [[wp>Debugger|debuggeru]])
    * step over, trace into
    * watch, [[wp>Breakpoint|breakpoint]], [[wp>Call_stack|call stack]]
  * nápověda - kontextová, index