Cơ bản về cấu trúc dữ liệu và giải thuật – Đệ quy (P2)

[trungndm]

Hôm nay, chúng ta sẽ tìm hiểu sâu hơn về 2 kỹ thuật đệ quy nâng cao hơn. Đó là Đệ quy có nhớ và Quay lui (Backtracking)

Đệ quy có nhớ:
Xét bài toán tính C(k,n) đã trình bày giải thuật ở phần trước

“Giải thuật:

int C(int k, int n){
if k==0 || k==n) :
return 1
return C(k-1,n-1) + C(k,n-1)

”

Ta có sơ đồ như sau với C(3,5)

Ở đây có thể thấy có 1 vài công thức bị lặp lại như C(2,3), C(1,2),…
Nếu dùng đệ quy để tính lại các công thức này sẽ mất rất nhiều thời gian
Để giảm bớt thời gian tính toán, ta có thể lưu lại các giá trị đã biết vào 1 mảng để sau này khi gặp lại chỉ việc lấy giá trị ra chứ không cần tính lại.
Như ví dụ trên có thể lưu vào 1 mảng 2 chiều n*n :

Giải thuật mới :

long D[100][100] ;
long C( int k , int n ) {
     if ( k == 0 | | k == n ) D[k][n] = 1 ;
else {
     if (D[k][n]