Cvičenie č. 7 - Úvod do rekurzie

Rekurzia

Základná myšlienka: súčasťou podprogramu (procedúry alebo funkcie) je volanie toho istého podprogramu. Takémuto volaniu sa hovorí rekurzia. Keďže nechceme rekurzívne volať podprogamy do nekonečna, potrebujeme aby každá vetva rekurzie bola ohraničená ukončujúcou podmienkou.

Príklad

program recursion_basic;

procedure stars(n: integer);
begin
  if n = 0 then begin
    ;  { ukoncovacia podmienka rekurzie }
  end else begin
    write('*');
    stars(n - 1);   { rekurzivne volanie}
  end;
end;

var num, i: integer;
begin
  readln(num);

  { vypisanie num hviezdiciek cyklom }
  for i := 1 to num do
    write('*');
  writeln;

  { vypisanie num hviezdiciek rekurziou}
  stars(num);
  writeln;
end.

Úlohy

Všetky riešenia v tejto časti musia používať rekurziu!

Faktoriál druhýkrát

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

Riešenie

function factorial(n: integer): integer;
begin
  if n = 0 then
    factorial := 1
  else
    factorial := n * factorial(n - 1);
end;

Fibonacci druhýkrát

Napíšte funkciu fibonacci, ktorá spočíta n-té fibonacciho čislo (n dostane ako parameter).

Riešenie

function fibonacci(n: integer): integer;
begin
  if n = 0 then
    fibonacci := 0
  else if n = 1 then
    fibonacci := 1
  else
    fibonacci := fibonacci(n - 1) + fibonacci(n - 2);
end;

Štvorce

Napíšte funkciu writeSquare, ktorá dostane ako jeden zo vstupov velkosť štvorca n a rekurzívne najprv vykreslí štvorec velkosti n, do jeho stredu vykreslí štvorec velkosti n-2, n-4, …, 0. Štvorce na jednotlivých úrovniach vykreslite rôznými znakmi, tak aby boli rozlíšitelné.

Príklad

n=1

+

n=2

++
++

n=3

+++
+o+
+++

n=5

+++++
+ooo+
+o+o+
+ooo+
+++++

n=10

++++++++++
+oooooooo+
+o++++++o+
+o+oooo+o+
+o+o++o+o+
+o+o++o+o+
+o+oooo+o+
+o++++++o+
+oooooooo+
++++++++++

Hint

Použite funkciu gotoXY:

program square_simple;

uses Crt; { naimportujeme modul obsahujuci funkciu gotoXY a clrScr}

var size, x, y: integer;
begin
  readln(size);
  clrScr; {vycistime konzolu }

  for x := 1 to size do
    for y :=1 to size do begin
      gotoXY(x, y); {pred vypisom sa posunieme na poziciu x,y}
      write('*');
    end;

  { presunieme kurzor na koniec,
   aby neprekazal na vyslednom obrazku}
  gotoXY(1, size + 1);
end.

Výstup pre size=5:

*****
*****
*****
*****
*****

Riešenie

program square;

uses Crt;

procedure writeSquare(x, y, size: integer; c: char);
var i, j: integer;
begin
  if size > 0 then begin
    for i := 0 to size - 1 do
      for j:= 0 to size - 1 do begin
        gotoXY(x + i, y + j);
        write(c);
      end;
    if c = '+' then
      c := 'o'
    else
      c := '+';
    writeSquare(x + 1, y + 1, size - 2, c);
  end;
end;

var size: integer;
begin
  readln(size);
  ClrScr;
  writeSquare(1, 1, size, '+');
  gotoXY(1,size + 1);
end.

Binárne vyhľadávanie druhýkrát

Napíšte rekurzívnu implementáciu binárneho vyhľadávania v zotriedenom poli.

Kostra algoritmu:

program binary_search;

{Definujeme si specialny typ, ktory budeme pouzivat
 pre vsetky polia }
type
    tArray = array[1..1000] of integer;

function binarySearch(arr: tArray;
                      element, left, right: integer): boolean;
begin
  { vasa implementacia }
end;

var testArray: tArray;
begin
 {...}
end.

Riešenie

program binary_search;

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

function binarySearch(arr: tArray;    { vstupne pole}
                      element,        { hladany prvok}
                      left,           { lava hranica intervalu }
                      right: integer  { prava hranica intervalu }
                      ): boolean;
var half: integer;
begin
  if right < left then
    binarySearch := false
  else begin
    half := (left + right) div 2;
    if arr[half] = element then
      binarySearch := true
    else if element < arr[half] then
      binarySearch := binarySearch(arr, element, left, half - 1)
    else
      binarySearch := binarySearch(arr, element, half + 1, right);
  end;
end;

var arr: tArray;

begin
  arr[1] := 1;
  arr[2] := 4;
  arr[3] := 6;
  arr[4] := 10;
  arr[5] := 12;
  writeln(binarySearch(arr, 1, 1, 5));
end.

Batoh

Na vstup dostanete pole s hodnotami mincí a cieľovú sumu. Vašou úlohou je vypísať všetky podmnožiny mincí z poľa, ktorých súčet sa rovná cieľovej sume. Predpokladajte, že každá minca je unikátna, ale aj napriek tomu môžu mať mince na vstupe rovnaké hodnoty. Na výstup vypíšte každú vhodnú pomnožinu ako zoznam indexov mincí zo vstupného poľa.

Príklad

Vstup::

mince = [1, 2, 2, 1, 2]
cielova_suma = 4

Výstup:

1 2 4
1 3 4
1 4 5
2 3
2 5
3 5

Riešenie

program knapsack;

Uses sysutils; { kvoli funkcii IntToStr() }

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

procedure findSolutions(coins: tArray;
                        numCoins, targetSum, idx, sum: integer;
                        solution: String);
begin
  if idx <= numCoins then begin
    { prvok na pozici idx pridam do riesenia }
    findSolutions(coins, numCoins, targetSum, idx + 1,
                  sum + coins[idx], solution + IntToStr(idx) + ' ');

    { prvok na pozici idx NEpridam do riesenia }
    findSolutions(coins, numCoins,
                  targetSum, idx + 1, sum, solution);
  end else begin
    if sum = targetSum then
      writeln(solution);
  end;
end;

var coins: tArray;
begin
  coins[1] := 1;
  coins[2] := 2;
  coins[3] := 2;
  coins[4] := 1;
  coins[5] := 2;
  findSolutions(coins, 5, 4, 1, 0, '');
end.

Domáce úlohy

V CodEx-e nájdete svoju domácu úlohu: Generování kombinací.

Termín odovzdania: 29. 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 začať posielať.