A. Considerații teoretice
Se spune despre un concept că este recursiv dacă el este definit prin el însuși. În acest fel pot fi definite numerele naturale, șiruri de numere sau unele functii:
tri1 = 1; trin = n + trin-1, pentru n > 1 |
ack(m,n) = ack(m-1, ack(m, n-1)); ack(0,n) = n+1; ack(m,0) = ack(m-1,1);
Cu ajutorul calculatorului, putem determina o submulțime finită a mulțimii acestor obiecte, transformând definițiile matematice recursive în algoritmi recursivi. Aceștia au particularitatea că, la un moment dat, se apelează pe ei înșiși. La modul general, algoritmul pentru calculul valorii unei funcții definite recursiv se poate exprima în felul urmator:
function f(x): <tip_functie>; begin if p(x) then f := h(x) else f := f(g(x)) {apelul recursiv} end;
Caracteristicile funcțiilor și procedurilor recursive:
B. Exemple
cmmdc(a, b) = cmmd(b, a mod b), daca b <> 0, cmmdc(a, 0) = a
Rezolvare:
program CelMaiMareDivizorComun; var x, y, c: integer; function cmmdc(a, b: integer): integer; begin writeln('Intrare in CMMDC, a = ', a:1, ' b = ', b:1); readln; if b <> 0 then cmmdc := cmmdc(b, a mod b) else cmmdc := a; writeln('Iesire din CMMDC, a = ', a:1, ' b = ', b:1); readln; end; begin write(' x= '); readln(x); write(' y= '); readln(y); c := cmmdc(x, y); writeln(' cmmdc( ', x:1, ' , ', y:1,' ) = ', c:1); end. |
Click aici pentru sursa completă (ex03_1.pas)
modulo(a, b) = modulo((a-b), b), daca a >= b, modulo(a, b) = a, daca a < b.
Rezolvare:
program FunctiaModulo; var x, y : integer; m: integer; function modulo (a, b : integer): integer; begin writeln(' Intrarea in MODULO, a = ', a:1, ' b = ', b:1); readln; if a >= b then modulo := modulo((a-b), b) else modulo := a; writeln(' Iesire din MODULO, a= ', a:1, ' b = ', b:1); readln end; begin write (' x= '); readln (x); write (' y= '); readln (y); m := modulo(x, y); writeln(' modulo(', x:1, ', ', y:1,' )= ', m:1 ) end.Click aici pentru sursa completă (ex03_2.pas)
1,1 1,2 1,3 1,4 2,1 2,2 2,3 2,4 3,1 3,2 3,3 3,4 4,1 4,2 4,3 4,4
program aranj_rep; const maxcar = 10; {numarul maxim de caractere acceptat} var litere: string[maxcar]; indici: array[1..maxcar] of integer; m, n: integer; procedure tipareste; var i: integer; begin for i := m downto 1 do write(litere[indici[i]]); writeln end; {tipareste} procedure aranj_r(k: integer); var j: integer; begin if k = 0 then tipareste else for j := 1 to n do begin indici[k] := j; aranj_r(k-1) end end; {aranj_r} begin {programul principal} write('Numarul de caractere: '); readln(n); write('luate cate: '); readln(m); if (n > maxcar) or (m > n) then write('*** Date eronate ***') else begin write('Textul: '); readln(litere); aranj_r(m) end; readln end.Click aici pentru sursa completă (ex03_3.pas)
Rezolvare:
În acest caz, la introducerea unei valori în tabloul indici, se verifică
dacă ea mai este cumva prezentă în tablou; dacă da, atunci valoarea ei va fi
înlocuită cu următoarea, înainte de a se încerca continuarea generări.
program aranjamente; ... procedure aranj(k: integer); var j, t: integer; begin if k = 0 then tipareste else for j := 1 to n do begin indici[k] := j; t := m; while indici[t] <> j do t := t - 1; if t = k then aranj_r(k-1) end end; {aranj} begin {programul principal} write('Numarul de caractere: '); readln(n); write('luate cate: '); readln(m); if (n > maxcar) or (m > n) then write('*** Date eronate ***') else begin write('Textul: '); readln(litere); aranj(m) end; readln end.Click aici pentru sursa completă (ex03_4.pas)
Rezolvare:
Caracterele se vor citi în tabloul litere. În tabloul indici
se va genera succesiunea de indici corespunzătoare combinărilor. Pentru
patru caractere, de exemplu, în cazul în care se cer combinări cu repetiție
luate câte două, se generează pe rând indicii:
1,1 1,2 1,3 1,4 2,2 2,3 2,4 3,3 3,4 4,4
program comb_rep; const maxcar = 10; {numarul maxim de caractere acceptat} var litere: string[maxcar]; indici: array[1..maxcar+1] of integer; m, n: integer; procedure tipareste; var i: integer; begin for i := m downto 1 do write(litere[indici[i]]); writeln end; {tipareste} procedure comb_r(k: integer); var j: integer; begin if k = 0 then tipareste else for j := indici[k+1] to n do begin indici[k] := j; comb_r(k-1) end end; {aranj_r} begin {programul principal} write('Numarul de caractere: '); readln(n); write('luate cate: '); readln(m); if (n > maxcar) or (m > n) then write('*** Date eronate ***') else begin write('Textul: '); readln(litere); indici[m+1] := 1; comb_r(m) end; readln end.Click aici pentru sursa completă (ex03_5.pas)
C. Teme