Triunghiul lui Pascal

Calculul coeficienților binomiali C(n; k). Pentru rezolvarea problemei, amintim
formula de recurență:

Varianta de implementare a formulei folosind o funcție recursivă nu este recomandată, fiind una redundantă, aceeași valoare fiind calculată de mai multe ori (complexitate exponențială). Alegem să folosim metoda programării dinamice, valorile coeficienților binomiali calculându-se progresiv. Aceste valori vor fi salvate într-o matrice pătratică C de ordin n + 1. Doar partea inferioară a matricei împreună cu diagonala sa principală vor fi încărcate. Vom construi triunghiul lui Pascal până la o pereche dată (n; k). Complexitatea algoritmului este de ordinul O(nk). Dacă se cere să se calculeze doar valoarea C(n; k) se poate folosi ca spațiu de stocare un tablou unidimensional de dimensiune k.

Cod Sursa C++

// TriunghiulPascalCPP.cpp : Defines the entry point for the console application.
//
 
#include "stdafx.h"
#include <iostream>
 
using namespace std;
 
#define dim 100
 
int main()
{
	unsigned n, k;
	unsigned C[dim][dim];
	cout << "n : ";
	cin >> n;
	cout << "k , k <= n : ";
	cin >> k;
	while (k > n)
	{
		cout << "k, k <= n: ";
		cin >> k;
	}
	C[0][0] = 1;
	cout << C[0][0] << endl;
	for (unsigned i = 1; i <= n; i++)
	{
		for (unsigned j = 0; j <= i; j++)
		{
			if (j == 0 || j == i)
				C[i][j] = 1;
			else
				C[i][j] = C[i - 1][j - 1] + C[i - 1][j];
			cout << C[i][j] << " ";
		}
		cout << endl;
	}
	cout << endl << "Am generat triunghiul lui Pascal pana la " << " perechea data (" << n << " , " << k << ")" << endl;
	cout << "C(" << n << " , " << k << ") = " << C[n][k] << endl;
	system("pause");
}
 
 

Rezultat: