Question

Ce calculeaza urmatorul algoritm?


int alg(int m, int n)

{

if (m==0){

return 1;

}

else if (n ==0)

return 1;

else

return alg(m-1, n) + alg(m, n-1);

}.

Answer 1

Răspuns:

Algoritmul calculeaza combinari de m+n luate cate n, folosind formula de recurenta a combinarilor.

Explicație:

Putem sa ne gandim la alg(m ,n) ca la o functie matematica si sa analizam mai indeaproape relatia de recurenta. Astfel, alg(m, n) poate fi definit astfel:

alg(0, n) = 1;

alg(m, 0) = 1;

alg(m, n) = alg(m - 1, n) + alg(m, n - 1), daca m si n sunt mai mari decat 0.

De exemplu:

alg(2, 2) = alg(1, 2) + alg(2, 1) = (alg(0, 2) + alg(1, 1)) + (alg(1, 1) + alg(2, 0)) =

= (1 + (alg(1, 0) + alg(0, 1))) + ((alg(0, 1) + alg(1, 0)) + 1) = (1 + 2) + (2 + 1) = 6

Se poate observa ca anumite valori sunt recalculate. Pentru ca avem doar 2 variabile, putem analiza valorile functiei uitandu-ne la matricea cu n linii si m coloane. Astfel, pozitia (i, j) din matrice va avea valoarea alg(i, j).

Din primele doua relatii ale lui alg, stim ca marginea din stanga si marginea de sus a matricei au valoarea 1. Restul valorilor pot fi calculate din relatia de recurenta. Mai exact, casuta (i, j) este suma dintre casuta de sus si casuta din stanga.

1 1 1 1 1 1 1

1 2 3 4 5 6

1 3 6 10 15 21

1 4 10 20 35 56

Asa ar arata valorile matricei pentru n = 3 si m = 5 (numerotarea se face de la 0). Astfel, alg(3, 5) = 56.

Am facut matricea asta pentru a pune in evidenta modul in care se calculeaza valorile lui alg. Surpriza este ca matricea asta este triunghiul lui Pascal. Daca o intorci la 45 de grade in sensul acelor de ceasornic, vei observa asta. Ei bine, triunghiul lui Pascal este folosit pentru a calcula combinarile. Intors, ar arata astfel:

                1

              1   1

            1   2   1

          1   3  3   1

       ......................

Notam cu C(a, b), combinarile de a luate cate b. Valoarea a este data de linia triunghiului, iar valoarea b este data de al catalea element pe linie este.

Reintorcandu-ne la matricea noastra, pentru linia i si coloana j, celula respectiva va contine C(i + j, i). Nu pun demonstratia aici, deoarece e mai usor sa verifici prin cateva exemple.

De ex. alg(3, 5) = C(8, 3) = 56, ceea ce e adevarat.

Faptul ca matricea are in ea triunghiul lui Pascal, reiese din relatia de recurenta:

$\text{alg}(m,n)=\text{alg}(m-1,n)+\text{alg}(m,n-1)\\\\\text{Daca }\text{alg}(m,n)=C_{m+n}^n\\\\\text{Atunci }C_{m+n}^n = C_{m+n-1}^n + C_{m+n-1}^{n-1}\text{ , ceea ce este adevarat.}$