Sáng kiến kinh nghiệm Một số giải pháp sử dụng thuật toán duyệt cho một số bài toán cơ bản

 MỘT SỐ GIẢI PHÁP SỬ DỤNG THUẬT TOÁN DUYỆT 
 CHO MỘT SỐ BÀI TOÁN CƠ BẢN
1. Bài toán XÂU TIỀN TỐ DÀI NHẤT 
 1.1. Đề bài
 Xâu A được gọi là tiền tố của xâu B nếu length(A) length(B) và sau khi 
ta xóa đi một số kí tự cuối cùng của B thì thu được xâu A. 
 Yêu cầu: Cho N xâu, bạn hãy tìm một xâu dài nhất sao cho nó là tiền tố của 
ít nhất 2 trong số N xâu đã cho. Nếu có nhiều xâu thỏa mãn có cùng độ dài, hãy 
đưa ra đáp án xuất hiện đầu tiên theo thứ tự từ điển.
 Dữ liệu: Vào từ file văn bản LPREFIX.INP:
 • Dòng thứ nhất ghi số nguyên dương N (2 ≤ N ≤ 5000).
 • Dòng thứ i trong N dòng tiếp theo ghi xâu Wi (2 ≤ length(Wi) ≤ 100).
 Kết quả: Ghi ra file văn bản LPREFIX.OUT một dòng duy nhất ghi xâu tiền 
tố dài nhất thỏa mãn yêu cầu đề bài.
 Ví dụ:
 LPREFIX.INP LPREFIX.OUT
 7 CHA
 CHEDDAR
 CHESSO
 CHAOURCE
 PARMESAN
 CHAUMES
 ROQUEFORT
 POSSIA
 Giải thích: Các xâu là tiền tố của ít nhất 2 xâu là C, CH, CHA, CHE, P. Xâu 
dài nhất là xâu CHA và CHE nhưng xâu CHA xuất hiện trước CHE trong thứ tự 
từ điển.
 1.2. Hướng dẫn Procedure Bai1_p2;
 Begin
 Smax:=’’;
 For i:=1 To N-1 Do
 Begin
 temp:=tiento(S[i],S[i+1]);
 If (Length(temp)>Length(Smax)) Or 
 ((Length(temp)>Length(Smax) And (temp<Smax)) 
 Then Smax:=temp;
 End;
 End;
 Trong đó hàm tiento(S[i],S[j]) nhận hai tham số đầu vào là hai xâu (xâu 
thứ i và xâu thứ j) và trả về xâu tiền tố dài nhất của hai xâu đó.
 Độ phức tạp của thuật toán: 
 - Sắp xếp các xâu theo thứ tự tăng dần: O(n.Logn)
 - Số trường hợp thử O(n) nhân với chi phí kiểm tra O(w), do đó độ phức 
tạp của thuật toán trên là O(n*w).
 Vậy độ phức tạp là Max(O(n.Logn), O(n*w)) = O(n.Logn).
2. Bài toán BỘ TAM HỢP 
 2.1. Đề bài
 Cho dãy số nguyên a 1, a2, ..., an, các số khác nhau từng đôi một (3 n 
 6
5000; với mọi i ta có |ai| 10 ). Bộ ba số ai, aj, ak (i j k) được gọi là Bộ tam 
hợp nếu có một số bất kỳ trong ba số đó bằng trung bình cộng của hai số còn lại.
 Yêu cầu: Hãy đếm số lượng bộ tam hợp và tìm bộ tam hợp có tổng giá trị 
của ba số là lớn nhất.
 Dữ liệu vào: Đọc từ file văn bản có tên TAMHOP.INP có cấu trúc như sau:
 - Dòng 1 chứa số n;
 - Dòng 2 chứa n số a1, a2, ..., an cách nhau ít nhất một dấu cách - Sắp xếp dãy số theo thứ tự tăng dần (dùng Quick Sort có độ phức tạp 
O(n.Logn))
 - Dùng hai vòng để liệt kê các trường hợp thử cho x1 và x2, khi biết phần 
tử A[x1], A[x2] thì sẽ biết được phần tử A[x3].
 - Dùng tìm kiếm nhị phân để xem A[x3] có trong dãy đã sắp xếp trước đó 
chưa.
 Procedure bai2_p2;
 Begin
 Quicksort; {Sắp xếp dãy số}
 count:=0;
 For x1:=1 To N-2 Do
 For x2:=x1+1 To N-1 Do
 Begin
 x:=A[x2]*2-A[x1];
 If Binary(x) Then Inc(Count);
 end;
 End;
 Như vậy, độ phức tạp thuật toán là O(n.Logn + n 2.Logn), rút gọp lại ta có 
độ phức tạp thuật toán chỉ còn O(n2.Logn).
 c. Lời giải O(n2)
 Để giảm độ phức tạp thuật toán ta giữ nguyên số trường hợp thử O(n 2) và 
giảm chi phí kiểm tra lên xuống O(1) như sau:
 - Dùng mảng KT[A[i]] =1 để đánh dấu số A[i] có xuất hiện trong dãy số.
 - Dùng hai vòng để liệt kê các trường hợp thử cho x1 và x2, khi biết phần 
tử A[x1], A[x2] thì sẽ biết được phần tử A[x3].
 - Kiểm tra xem A[x3] có tồn tại trong mảng KT hay không bằng cách: 
Nếu KT[A[x3]] =1 thì tồn tại số A[x3].
 Procedure Bai2_p3;
 Begin
 For i:=1 To N Do Inc(KT(A[i]); 
 count:=0;