Cvičenie č. 5 - Euklidov algoritmus, procedúry vs funkcie

Úlohy

Test na syntax Pascalu

Rozhodnite čo robia nasledujúce programy:

1.

program test1;

var a : integer;

begin
  a := 4;
  if (a > 2) then
    writeln('foo 1')
  else
    a := a + 1;
    writeln('foo 2');
end.

2.

program test2;

var x,i : integer;

begin
  x:=1;
  for i:=1 to 20 do;
    x:=x+1;
  writeln(x);
end.

3.

program test3;

var x,y : integer;

begin
  x:=1;
  y:=2;
  if (x > 0 and 0 < y) then
    write('foo 1')
  else
    write('foo 2');
end.

Priorita operátorov v Pascale

Od najvyšej priority po najnižšiu:

  1. @, not
  2. *, /, div, mod, and
  3. +, -, or, xor
  4. =, <>, <, >, <=, >=

Euklidov algoritmus

Určite najväčšieho spoločného deliteľa (NSD) dvoch zadaných prirodzených čísel a a b.

Poznámka: Použite jednoduchú verziu Euklidovho algoritmu:

Vstup: prirodzené čísla a, b
while a != b:
   if a < b:
	 swap(a, b) # prehoď hodnoty
   a = a - b
return a

Naviac:

  • Dokážte správnosť tohto algoritmu.
  • Aká je pamäťová a časová zložitosť tohto algoritmu?

Procedúry vs funkcie

  • procedúra predstavuje nejaký zoznam príkazov, ktoré sa majú vykonať
  • funkcia predstavuje výpočet nejakej hodnoty

Príklad:

program procedures_and_functions;

{Procedura nemá návratovú hodnotu}
procedure procedura(parameter: integer);
var  a : byte;
begin
  a:=10;
  writeln(a);
  writeln(parameter)
end;

{Funkcia musí vrátiť nejakú hodnotu}
function funkcia(parameter: integer): integer;
begin
  funkcia:=parameter * parameter;
end;

var tmp: integer;
begin
  writeln('Volame proceduru...');
  procedura(20);

  writeln('Volame funkciu...');
  tmp:=funkcia(9);
  writeln(tmp)
end.

Predávanie parametrov: hodnotou vs odkazom

  • parametre pred ktorými nie je kľúčové slovo var, sú predávané hodnotou
  • parametre pred ktorými je kľúčové slovo var, sú predávané odkazom

Príklad:

program predavanie_parametrov;

procedure parameter_hodnotou(parameter: integer);
begin
  parameter:=20;
end;

procedure parameter_odkazom(var parameter: integer);
begin
  parameter:=20;
end;


var v: integer;
begin
  v:=10;

  parameter_hodnotou(v);
  writeln(v);

  parameter_odkazom(v);
  writeln(v);
end.

Faktoriál

Napíšte funkciu faktorial, ktorá spočíta faktoriál čísla, ktoré dostane ako parameter.

Poznámka: Skúšajte to len na malých číslach.

Riešenie

{ Nerekurzivne riesenie }
function faktorial(n: integer): integer;
var i : integer;
begin
  faktorial := 1;
  for i:=1 to n do
    faktorial := faktorial * i;
end;

Fibonacci

Napíšte funkciu fibonacci, ktorá spočíta n-té Fibonacciho číslo (n je parameter funkcie).

Definícia Fibonacciho čísla:

Riešenie

{ Nerekurzivne riesenie }
function fibonacci(n: integer): integer;
var i, f0, f1, tmp: integer;
begin
  if n >= 1 then
  begin
    f0 := 0;
    f1 := 1;
    for i := 2 to n do
    begin
      tmp := f1;
      f1 := f0 + f1;
      f0 := tmp;
    end;
    fibonacci := f1;
  end
  else
    fibonacci := 0;
end;

NSD

Prepíšte svojú implementáciu Euklidovho algoritmu do funkcie nsd tak, že bude používať procedúru swap, ktorú si napíšete tiež. U procedúry swap použite predávanie odkazom.

Riešenie

procedure swap(var v1, v2: integer);
var tmp: integer;
begin
  tmp := v1;
  v1 := v2;
  v2 := tmp;
end;

function nsd(a, b: integer): integer;
begin
  while (a <> b) do
    begin
      if (a < b) then
        begin
          swap(a, b);
        end;
      a := a - b;
    end;
  nsd := a;
end;

2. najmenší prvok z N

Napíšte funkciu, ktorá vráti druhý najväčší prvok z pola, ktoré dostane na vstup (kľudne si predajte dĺžku poľa parametrom).

Riešenie

type
  tArray = array[1..1000] of integer;

{ Predpokladame, ze pole na vstupe bude dlzky aspon 2 }
function secondSmallest(arr: tArray; len: integer): integer;
var first, second, i: integer;
begin
  first := arr[1];
  second := arr[2];
  if (first > second) then
    swap(first, second);

  for i := 3 to len do begin
    if (arr[i] < first) then begin
      second := first;
      first := arr[i];
    end else begin
    if (arr[i] < second) then
      second := arr[i];
    end;
  end;
  second_smallest := second
end;

k-tý najmenší prvok z N

Zovšeobecnite vašu predchádzajúcu funkciu, tak aby vrátila k-tý najmenší prvok, k bude ďaľší parameter funkcie.

Riešenie

function min(v1, v2: integer): integer;
begin
  if v1 < v2 then
    min := v1
  else
    min := v2;
end;

function kthSmallest(arr: tArray; len, k: integer): integer;
var smallest: tArray;
    i, j: integer;
begin
  for i := 1 to len do begin
    j := min(i, k + 1) - 1;
    while (j > 0) and (smallest[j] > arr[i]) do begin
      smallest[j + 1] := smallest[j];
      dec(j);
    end;
    inc(j);
    if (j <= min(i, k)) then
      smallest[j] := arr[i];
  end;
  kth_smallest := smallest[k];
end;

Domáce úlohy

V CodEx-e nájdete svoje 2 povinné domáce úlohy: PPPPP 5.3 Setřídění posloupnosti a Řezání dřeva na zimu.

Termín odovzdania: 8. 11. 2016 (23:59)

Poznámka: Začnite premýšľať nad témou svojho zápočtového programu a svoje návrhy mi môžete pomaly začat posielať.