Răspuns :
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:
[tex]\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.}[/tex]
Vă mulțumim că ați vizitat site-ul nostru dedicat Informatică. Sperăm că informațiile oferite v-au fost de ajutor. Dacă aveți întrebări sau nevoie de asistență suplimentară, nu ezitați să ne contactați. Ne vedem curând și nu uitați să ne adăugați la marcaje!