My OperaGiải bài toán qui hoạch động
Thursday, April 19, 2007 1:45:04 PM
Bài toán tính tổ hợp chập k của n phần tử
Input:
Hai số nguyên dương n, m.
Output:
Tổ hợp chập n của m phần tử.
Nhận xét:
-Ta dễ dàng có công thức tính tổ hợp
C[m,n]=C[m,m] nếu m<n
C[m,n]=C[m,n-1]+C[m-n,n] nếu m>=n
C[m,0]=0
C[0,n]=1
Với công thức trên ta cài đặt chương trình như sau:
long C(int m, int n){
if(n=0) return 0;
else if(m=0) return 1;
else if(n>m) return C(m,m);
else return C(m,n-1)+C(m-n,n);
}
Ta thử tính C(7,5) theo như chương trình trên:
C(7,5)=C(7,4)+C(2,4)
C(7,4)=C(7,3)+C(3,4)
C(7,3)=C(7,2)+C(4,3)
C(3,4)=C(3,3)
C(7,2)=C(7,1)+C(5,2)
C(4,3)=C(4,2)+C(1,3)
C(7,1)=C(7,0)+C(6,1)
C(5,2)=C(5,1)+C(2,2)
C(6,1)=C(6,0)+C(5,1)…
Ta nhận thấy có nhiều phép tính bị lặp lại làm tốn thời gian tính toán. Do đó ta loại bỏ các phép tính lặp bằng cách dùng mảng 2 chiều như sau:
- Gọi C[i,j] là tổ hợp chập j của i phần tử.
- Ta khởi tạo C[i,j]=0, i=0..m, j=0..n
- Gán C[0,j]=1, j=1..n
- Gán C[i,1]=1,i=1..m
- (i=2..m) (j=1..i) C[i,j]=C[i,j-1]+C[i-j,j]
(j=i+1..n) C[i,j]=C[i,i]
- Return C[m,n]
Nhận xét:
Nếu ta thực hiện điền vào bảng C[mxn] theo chiều tăng dần của i và j thì phần tử C[i,j] phụ thuộc vào các phần từ C[i,j-1] và C[i-j,j], tức là khi ta điền giá trị cho từng cột thì giá trị này sẽ phụ thuộc vào giá trị của cột kề trước nó. Như vậy ta có thể thay thế mảng 2 chiều này bằng một mảng 1 chiều được, và ta sẽ thực hiện như sau:
- Gọi A (i=0..m) giá trị đại diện cho một cột trong bảng.
- A=1 (i=0..m)
- (j=2..n) (i=j..m) A=A+A[i-j]
- Return A[m]
Input:
Hai số nguyên dương n, m.
Output:
Tổ hợp chập n của m phần tử.
Nhận xét:
-Ta dễ dàng có công thức tính tổ hợp
C[m,n]=C[m,m] nếu m<n
C[m,n]=C[m,n-1]+C[m-n,n] nếu m>=n
C[m,0]=0
C[0,n]=1
Với công thức trên ta cài đặt chương trình như sau:
long C(int m, int n){
if(n=0) return 0;
else if(m=0) return 1;
else if(n>m) return C(m,m);
else return C(m,n-1)+C(m-n,n);
}
Ta thử tính C(7,5) theo như chương trình trên:
C(7,5)=C(7,4)+C(2,4)
C(7,4)=C(7,3)+C(3,4)
C(7,3)=C(7,2)+C(4,3)
C(3,4)=C(3,3)
C(7,2)=C(7,1)+C(5,2)
C(4,3)=C(4,2)+C(1,3)
C(7,1)=C(7,0)+C(6,1)
C(5,2)=C(5,1)+C(2,2)
C(6,1)=C(6,0)+C(5,1)…
Ta nhận thấy có nhiều phép tính bị lặp lại làm tốn thời gian tính toán. Do đó ta loại bỏ các phép tính lặp bằng cách dùng mảng 2 chiều như sau:
- Gọi C[i,j] là tổ hợp chập j của i phần tử.
- Ta khởi tạo C[i,j]=0, i=0..m, j=0..n
- Gán C[0,j]=1, j=1..n
- Gán C[i,1]=1,i=1..m
- (i=2..m) (j=1..i) C[i,j]=C[i,j-1]+C[i-j,j]
(j=i+1..n) C[i,j]=C[i,i]
- Return C[m,n]
Nhận xét:
Nếu ta thực hiện điền vào bảng C[mxn] theo chiều tăng dần của i và j thì phần tử C[i,j] phụ thuộc vào các phần từ C[i,j-1] và C[i-j,j], tức là khi ta điền giá trị cho từng cột thì giá trị này sẽ phụ thuộc vào giá trị của cột kề trước nó. Như vậy ta có thể thay thế mảng 2 chiều này bằng một mảng 1 chiều được, và ta sẽ thực hiện như sau:
- Gọi A (i=0..m) giá trị đại diện cho một cột trong bảng.
- A=1 (i=0..m)
- (j=2..n) (i=j..m) A=A+A[i-j]
- Return A[m]
miencattrang102DVG45TH2 # Thursday, April 19, 2007 1:59:34 PM
Thuật toán này Pascal đã tìm ra cách đây cỡ 400 năm nhưng ý nghĩa của nó thì tồn tại vĩnh hằng.
Tổ chức lại bằng qui hoạch động sẽ giúp chúng ta giải quyết khá nhiều bài toán tốn kém bộ nhớ.
miencattrang102DVG45TH2 # Thursday, April 19, 2007 2:09:27 PM
Đơn giản chúng ta hãy tưởng tượng là trong phòng có n quả bóng (để lộn xộn) cần lấy ra k quả thì có bao nhiêu cách lấy? Đó chính là tổ hợp chập k của n. Cứ mỗi lần lấy k quả bóng ra ta phải đánh dấu nó rồi bỏ vào (được một cách), nếu lần sau mà lấy lại mà giống với một lần lấy trước nó thì ta không tính cách lấy này. Giả sử trong phòng có 5 quả bóng mà mỗi lần lấy 7 quả thì chắc chắn sẽ không có cách lấy nào.
Đó chính là câu trả lời>>>