3. cvičení - 16.10.2009

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.

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

function isPowerOfTwo(n:integer) : boolean;
begin
  isPowerOfTwo := (n AND (n - 1)) = 0
end;

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.

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;

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

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.

• 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 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 frekvenční analýza textu tak, aby analyzovala malá i velká písmena a také číslice.
• Zkuste rozšírit úlohu frekvenční analýza textu tak, aby analyzovala všechny tisknutelné znaky.
• Zkuste rozšírit úlohu 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 ASCII na Wikipedii) nevypisujte.

program helloworld;
begin
  writeln("Hello world!")
end.

• klávesové zkratky k FP/BP.
• Pár slov od dr. Holana, 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í debuggeru)
  • step over, trace into
  • watch, breakpoint, call stack
• nápověda - kontextová, index