5. cvičení - 30.10.2009

Cvičili jsme ještě kus rekurze a složitosti, ale už jsme nakousli i zásobník.

Zadání:

Máme na vstupu posloupnost čísel typu integer. Víme, že obsahuje čísla z nějaké množiny (kterou předem neznáme) a že jedno číslo se tam vyskytuje samotné, ostatní právě ve dvojici. Čísla ale mohou být libovolně rozházena. Cílem je určit, které číslo je to, co se vyskytuje jednou.

Možné efektivní řešení:

Využijeme předpokladu, že se jedná o posloupnost integerů, a pak vlastností bitové operace XOR (viz úlohu o hradle XOR). Použijeme jednu pomocnou proměnnou, např. T, se kterou v jediném průchodu budeme XORovat prvky posloupnosti. T bude inicializována na 0. Dvojice stejných čísel se vyruší XORem na nulu a zbyde pouze onen samotný prvek.

Využíváme toho, že platí:

A xor A = 0
A xor B = B xor A  (komutativita)
(A xor B) xor C = A xor (B xor C)  (asociativita)

Složitost: časová O(n), paměťová O(1)

function samotny_prvek(pole : array of integer) : integer;
var
  s : integer;
begin
  s := 0;
  for i := 0 to length(pole) do
  begin
    s := s xor pole[i]
  end;
  single := s
end;

Kolik nul obsahuje v desítkovém zápisu n! pro dané n? Přitom nechceme vyhodnocovat samotnou hodnotu faktoriálu.

Uvědomíme se, že nuly jsou za desítky, kterých je stejně jako pětek, tj. stačí spočítat počet pětek mezi členy faktoriálu. Pětky se počítají jednou za násobky 5, podruhé za násobky 25, potřetí za násobky 125, …

sum_{k=1}^{floor(ln_5(n))} floor(n/5^k)

Logaritmus o libovolném základu lze počítat pomocí přirozeného logaritmu:

ln_5(n) = ln(n) / ln(5).

Lze jednoduše spočítat ve for cyklu.

Pozn.: dolní celá část (běžně označovaná jako floor) v Borland Pascalu tak úplně není přítomna. Jelikož víme, že členy faktoriálového součinu jsou kladná čísla, použijeme funcki trunc, která ořízne desetinná čísla, tj. kladná čísla zaokrouhlí dolů.

Mocniny 5^k nemusíme pokaždé vyhodnocovat zvlášť, stačí postupně násobit pětkou a pamatovat si mezivýsledek.

{ Kolika nulami konci n! }
function nulyVeFaktorialu(n : integer) : integer;
var
   nuly, i, max, mocnina5 : integer;
begin
     nuly := 0;
     mocnina5 := 1;
     max := trunc(ln(n) / ln(5));
     for i := 1 to max do
     begin
          mocnina5 := mocnina5 * 5; {iterativni pocitani mocniny 5^i}
          nuly := nuly + trunc(n / mocnina5)
     end;
     nulyVeFaktorialu := nuly;
end;

Poznámka na okraj: obecná mocnina a^b v Pascalu není, ale je možno použít toto:

exp(a * ln(b))

Zadání:

F(0) = 0, F(1) = 1, F(n) = F(n-1) + F(n-2)

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

Máme spočítat hodnotu n-tého Fibonacciho čísla F(n).

Jakými způsoby to lze řešit?

• rekurzivně, odshora, přímo podle vzorce - čas O(2^n)

function fib(n:longint) : longint;
begin
     { write('*'); }
     if (n <= 1) then
         fib := n
     else
         fib := fib(n - 1) + fib(n - 2)
end;

• rekurzivně, odshora, přídavná paměť pro už spočítaná čísla - čas O(n), paměť O(n)
• rekurzivně, odshora, mezivýpočty v parametrech pomocné funkce - čas O(n)
  • zdroj, přepsáno z C do Pascalu

function fib2(n,p0,p1:longint) : longint;
begin
     { write('.'); }
     if (n = 1) then
         fib2 := p1
     else
         fib2 := fib2(n - 1, p1, p0 + p1)
end;
 
function fib(n:longint) : longint;
begin
     { write('*'); }
     if (n = 0) then
         fib := 0
     else
         fib := fib2(n, 0, 1)
end;

• iterativně (v cyklu), pomocná paměť na předchozí výpočty - čas O(n), paměť O(n)
• iterativně (v cyklu), konstatní pomocná paměť (3 proměnné) - čas O(n), paměť O(1)

Pozn.: zkuste si tyhle kousky kódu pustit pomocí takovéhoto cyklu:

var
   i : integer;
begin
     for i := 0 to 10 do
          writeln('fib(', i, ') = ', fib(i));
end.

Když odkomentujete výpis hvězdiček a teček, jasně uvitíte rozdál, kolikrát se která funkce volá. Také si to můžete zkusit odtrasovat přes příkaz Borland Pascalu STEP INTO (F7).

Btw: Fibonacciho čísla se hustě vyskytují v nejrůznějších oblastech, nejen matematiky, informatiky, ale i například biologie či umění a v mnoha dalších oborech.

Další ukázkový zdroják - doc. Pavel Töpfer

Zadání:

Máme na vstupu řetězec složený právě ze závorek, tj. symbolů ( a ). Cílem je zjistit, jestli je korektně uzávorkovaný.

Korektní uzávorkování je dáno následujícími pravidly (gramatikou), která můžeme opakovat konečně-krát (0- až n-krát):

• prázdný řetězec je OK
• () je OK
• máme-li uzávorkování A, pak A(), ()A i (A) je OK

Příklad:

Korektní:
  ()
  (()((()())()))()()
Nekorektní:
  (
  )(
  ((()(

Možné řešení:

Budeme procházet vstupní posloupnost závorek. V číselné proměnné A si budeme pamatovat, kolik jsme závorek otevřeli. Narazíme-li na otvírací závorku, A zvětšíme o 1, narazíme-li na zavírací závorku, A zmenšíme o 1. Pokud se někdy dostaneme s A pod 0, končíme, protože je tu navíc zavírací závorka, která nemá co zavírat. Je-li A na konci nulové, výraz je korektní. Je-li větší než nula, nějaká otvírací závorka nebyla nikde uzavřena a výraz korektní není.

Složitost: časová O(n), paměťová O(1).

Pokud bychom dokázali rychle zjistit velikost vstupní posloupnosti, můžeme se popsaným testem ještě podívat, zda-li je posloupnost sudé délky. Pokud ne, výraz nemůže být korektně uzávorkovaný.

Zadání:

V posloupnosti na vstupu může být navíc oproti předchozímu zadání použito více typů závorek, např. (), {}, [], <>. Kromě posloupnosti je vstupem i výčet různých dvojic závorek.

Možné řešení:

Místo jedné proměnné použijeme zásobník na symboly závorka (reprezentované např. pomocí typu charu). Budeme postupně procházet testovanou vstupní posloupnost. Narazíme-li na otevírací závorku, vložíme na vrchol zásobníku odpovídající uzavírací závorku. Narazíme-li na zavírací závorku, porovnáme je se symbolem na vrcholu zásobníku. Shodují-li se, odstraníme ji z vrcholu zásobníku a pokračujeme, jinak končíme s tím, že je výraz nekorektní. Pokud bychom během výpočtu četli z prázdného zásobíku nebo na zásobníku na konci výpočtu něco zůstane, výraz korektní není, jinak je.

Info:

• domácí úkol Kontrola uzávorkování
• Zásobník (datová struktura) - česká Wikipedia

Úloha na kombinační logické obvody. Máme implementovat hradlo XOR¹⁾ se dvěma vstupy a jedním výstupem, které dělá to, co bitová funkce XOR. Přitom můžeme použít právě čtyři hradla NAND²⁾, tj. znegované AND, která mají také dva vstupy a jeden výstup. Úkolem je najít správné propojení těchto hradel.

Co je to logické hradlo? Je to něco jako krabička, která má několik vstupních šlahounů a několik výstupních. Na nich je nějaké napětí, typicky ve dvou úrovních, a to značí, bitovou hodnotu - 0 nebo 1. Podle kombinace nul a jedniček na vstupech hradlo hodí nějaké nuly nebo jedničky na výstupy. Jaké hodnoty to budou, má hradlo zadrátováno uvnitř.

Hradla je možno propojovat mezi sebou, a to tak, že na vstup nějakého hradla se připojí výstup hradla jiného. Na takové spojení je pak možné nahlížet zase jako na jednu větší černou krabičku - hradlo, které má své vstupy a výstupy.

Kombinační obvody je tomu říká proto, že hodnoty výstupů jsou vždy přesně určeny hodnotami vstupů. Tj. hradlo reaguje na stejné vstupy vždycky stejně. Narozdíl od sekvenčních obvodů si takový kombinatorický obvod nic nepamatuje, natožpak aby výstupní hodnoty určovat třeba náhodně.

Motivace: Funkce XOR se v integrovaných obvodech občas použije. Je možné ji naimplementovat přímo nebo pomocí propojení jednoduchého propojení tří různých hradel. To je ale z hlediska výroby nevýhodné. Proto je lepší použít sice čtyři, ale zato stejná hradla, a to právě NAND, jejichž výroba je zvládnutá dost dobře a používá se jich v integrovaných obvodech mraky.

Bonus: Dokážete XOR implementovat pomocí pěti hradel NOR, tj. Not OR?

Jako klíč máme jeden byte. Tímto klíčem z XORujeme celý string znak po znaku. Jakmile na zašifrovaný text aplikujeme tuto operaci znovu, dostaneme původní text, neboť (klíč XOR klíč) = 0 a zůstane původní hodnota znaku. Využíváme stejných vlastností XORu jako v první úloze.

function xorsifra(s:string;klic:char):string;
var
   kod:string;
   i:integer;
begin
     kod := s;
     for i := 1 to length(s) do
     begin
          kod[i] := chr(ord(s[i]) xor ord(klic));
     end;
     xorsifra := kod;
end;