Table of Contents

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

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.

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

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;

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ů. 

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

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í.

Práce s IDE Borland Pascal

"Hello world!"

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