chip hôi
30-06-2009, 17:01
Bài toán 1: Dãy con có tổng bằng S:
Cho dãy a1,a2,..an. Tìm một dãy con của dãy đó có tổng bằng S.
Lời giải:
Đặt L[i,t)=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các phần tử a1,a2,..ai. Ngược lại thì L[i,t)=0. Nếu L[n,S)=1 thì đáp án của bài toán trên là “có”.
Ta có thể tính L[i,t] theo công thức: L[i,t]=1 nếu L[i–1,t]=1 hoặc L[i–1,t–a[i]]=1.
Cài đặt
Nếu áp dụng luôn công thức trên thì ta cần dùng bảng phương án hai chiều. Ta có thể nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i–1. Bảng phương án khi đó chỉ cần 1 mảng 1 chiều L[0..S] và được tính như sau:
L[t]:=0; L[0]:=1;
for i := 1 to n do
for t := S downto a[i] do
if (L[t]=0) and (L[t–a[i]]=1) then L[t]:=1;
Dễ thấy chi phí không gian của cách cài đặt trên là O(m), chi phí thời gian là O(nm), với m là tổng của n số. Hãy tự kiểm tra xem tại sao vòng for thứ 2 lại là for downto chứ không phải là for to.
=====> Câu hỏi của mình là: tại sao là for downto chứ không phải là for to. Nếu là for to thì chương trình vẫn hoạt động được bình thường mà. Vì để tính dòng i thì chỉ cần thông qua dòng i – 1 thôi.
Bài toán 2: Palindrom (IOI 2000)
Một xâu gọi là xâu đối xứng (palindrom) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng.
Lời giải: Bài toán này có một công thức QHĐ như sau:
Gọi L(i,j) là số kí tự ít nhất cần thêm vào xâu con S[i..j] của S để xâu đó trở thành đối xứng.
Đáp số của bài toán sẽ là L(1,n) với n là số kí tự của S. Ta có công thức sau để tính L(i,j):
• L(i,i)=0.
• L(i,j)=L(i+1,j–1) nếu S[i]=S[j]
• L(i,j)=max(L(i+1,j), L(i,j–1)) nếu S[i]S[j]
=====> Theo mình trong trường hợp S[i]S[j] thì L(i, j) phải tính là: L(i, j) = L(i,j)=min(L(i+1,j), L(i,j–1)) + 1 chứ không phải là max như công thức trên đúng không nhỉ. Bởi ở đây ta đang đi tìm min cơ mà.
Thuật toán Floyd
Tư tưởng của thuật toán là: Đường đi ngắn nhất từ i tới j đi qua k thì: Từ i tới k và từ k tới j đều là hai đường đi ngắn nhất. Khi thực hiện qui hoạch động để tính L[i, j] thì cần phải biết trước L[i, k] và L[k, j]. Tuy nhiên, ở đây vai trò của i, j, k là bình đẳng. Vậy tổ chức thuật toán như thế nào để có thể giải quyết được triệt để vấn đề trên.
Mình đang học về Qui hoạch động. Khá thú vị, mình đã đọc các bài toán cơ bản về nó nhưng không hiểu khi tiếp cận bài toán mới thì khá khó. Mong các bạn chỉ giáo.
Cho dãy a1,a2,..an. Tìm một dãy con của dãy đó có tổng bằng S.
Lời giải:
Đặt L[i,t)=1 nếu có thể tạo ra tổng t từ một dãy con của dãy gồm các phần tử a1,a2,..ai. Ngược lại thì L[i,t)=0. Nếu L[n,S)=1 thì đáp án của bài toán trên là “có”.
Ta có thể tính L[i,t] theo công thức: L[i,t]=1 nếu L[i–1,t]=1 hoặc L[i–1,t–a[i]]=1.
Cài đặt
Nếu áp dụng luôn công thức trên thì ta cần dùng bảng phương án hai chiều. Ta có thể nhận xét rằng để tính dòng thứ i, ta chỉ cần dòng i–1. Bảng phương án khi đó chỉ cần 1 mảng 1 chiều L[0..S] và được tính như sau:
L[t]:=0; L[0]:=1;
for i := 1 to n do
for t := S downto a[i] do
if (L[t]=0) and (L[t–a[i]]=1) then L[t]:=1;
Dễ thấy chi phí không gian của cách cài đặt trên là O(m), chi phí thời gian là O(nm), với m là tổng của n số. Hãy tự kiểm tra xem tại sao vòng for thứ 2 lại là for downto chứ không phải là for to.
=====> Câu hỏi của mình là: tại sao là for downto chứ không phải là for to. Nếu là for to thì chương trình vẫn hoạt động được bình thường mà. Vì để tính dòng i thì chỉ cần thông qua dòng i – 1 thôi.
Bài toán 2: Palindrom (IOI 2000)
Một xâu gọi là xâu đối xứng (palindrom) nếu xâu đó đọc từ trái sang phải hay từ phải sang trái đều như nhau. Cho một xâu S, hãy tìm số kí tự ít nhất cần thêm vào S để S trở thành xâu đối xứng.
Lời giải: Bài toán này có một công thức QHĐ như sau:
Gọi L(i,j) là số kí tự ít nhất cần thêm vào xâu con S[i..j] của S để xâu đó trở thành đối xứng.
Đáp số của bài toán sẽ là L(1,n) với n là số kí tự của S. Ta có công thức sau để tính L(i,j):
• L(i,i)=0.
• L(i,j)=L(i+1,j–1) nếu S[i]=S[j]
• L(i,j)=max(L(i+1,j), L(i,j–1)) nếu S[i]S[j]
=====> Theo mình trong trường hợp S[i]S[j] thì L(i, j) phải tính là: L(i, j) = L(i,j)=min(L(i+1,j), L(i,j–1)) + 1 chứ không phải là max như công thức trên đúng không nhỉ. Bởi ở đây ta đang đi tìm min cơ mà.
Thuật toán Floyd
Tư tưởng của thuật toán là: Đường đi ngắn nhất từ i tới j đi qua k thì: Từ i tới k và từ k tới j đều là hai đường đi ngắn nhất. Khi thực hiện qui hoạch động để tính L[i, j] thì cần phải biết trước L[i, k] và L[k, j]. Tuy nhiên, ở đây vai trò của i, j, k là bình đẳng. Vậy tổ chức thuật toán như thế nào để có thể giải quyết được triệt để vấn đề trên.
Mình đang học về Qui hoạch động. Khá thú vị, mình đã đọc các bài toán cơ bản về nó nhưng không hiểu khi tiếp cận bài toán mới thì khá khó. Mong các bạn chỉ giáo.