Sáng kiến kinh nghiệm Cải tiến thuật Toán tìm kiếm nhị phân

Nội dung tài liệu: Sáng kiến kinh nghiệm Cải tiến thuật Toán tìm kiếm nhị phân

1. SÁNG KIẾN KINH NGHIỆM “CẢI TIẾN THUẬT TOÁN TÌM KIẾM NHỊ PHÂN” 1. Mô tả giải pháp trước khi tạo ra sáng kiến Tìm kiếm nhị phân là một trong những thuật toán phổ biến và được giới thiệu trong chương trình tin học lớp 11. Bài toán được mô tả như sau: 6 9 Cho dãy số nguyên A gồm n số nguyên a1 , a2 , ,an (1 ≤ n ≤ 10 , | ai | ≤ 10 ) đã sắp xếp theo thứ tự không giảm và cho số nguyên k (khóa tìm kiếm). Yêu cầu: Cho biết số nguyên k có xuất hiện trong dãy A hay không, nếu tìm thấy k cho biết vị trí số đó trong dãy? Thuật toán cho bài toán này: l=1; r=n; while (l<=r) { int m=(l+r)/2; if (a[m]==k) { cout<<k<<”xuat hien trong day o vi tri”<<m; break; } else if (a[m]>k) r=m-1; else l=m+1; } if (l>r) cout<<k<<”khong xuat hien trong day”; Thuật toán tìm kiếm nhị phân được mô tả khi các phần tử của mảng được sắp xếp, thuật toán luôn lấy phần tử ở giữa trong phạm vi tìm kiếm để so sánh với khóa tìm kiếm. Nếu phần tử ở giữa bằng với khóa tìm kiếm thì thuật toán sẽ dừng lại và trả về kết quả là tìm thấy. Nếu phần tử ở giữa lớn hơn khóa tìm kiếm thì quá trình tìm kiếm tiếp tục nửa đầu của phạm vi tìm kiếm. Nếu phần tử ở giữa nhỏ hơn khóa tìm kiếm thì quá trình tìm kiếm sẽ tiếp tục ở nửa sau của phạm vi tìm kiếm. Như vậy, mỗi lần lặp thuật toán có thể loại bỏ được một nửa số phần tử trong phạm vi tìm kiếm mà chắc chắn khóa tìm kiếm sẽ không xuất hiện. Đây là thuật toán tìm kiếm rất nhanh, hiệu quả và số lần lặp để trả lời khóa tìm kiếm có xuất hiện hay không rất nhỏ. Cụ thể, mỗi lần lặp nếu chưa tìm thấy khóa tìm kiếm, thuật toán loại đi được một nửa dãy (do so sánh khóa tìm kiếm với phần tử ở giữa dãy). Độ phức tạp của thuật toán là O(log n). Ví dụ, với kích thước cho trong bài toán trên thì trong trường hợp xấu nhất là không tìm thấy khóa chỉ cần tối đa khoảng 20 lần lặp. Thuật toán trên nếu trong dãy có nhiều số bằng k thì kết quả trả về là vị trí bất kì tìm được. Tuy nhiên, trong quá trình giảng dạy, tôi gặp rất nhiều bài tập khi sử dụng
2. thuật toán tìm kiếm nhị phân thì yêu cầu không đơn giản là cho biết vị trí khóa tìm kiếm nếu có xuất hiện trong dãy. Những bài tập thường yêu cầu cao hơn là nếu có tìm thấy khóa k thì cho biết vị trí đầu tiên hoặc vị trí cuối cùng mà khóa k xuất hiện. Khi tôi yêu cầu học sinh đưa ra giải pháp cải tiến thuật toán trên đáp ứng yêu cầu tìm vị trí xuất hiện đầu tiên khóa k trong dãy nếu tìm thấy. Giải pháp trong hầu hết ý kiến các em đưa ra dùng thuật toán tìm kiếm nhị phân để tìm ví trí khóa k xuất hiện bất kì, sau đó dùng tiếp lệnh lặp để tìm ví trí đầu tiên của khóa k từ vị trí bất kì tìm được đi lùi về đầu dãy tìm kiếm. Từ giải pháp của học sinh đưa ra, chúng ta nhận thấy ngay trong trường hợp xấu nhất (khi các phần tử trong dãy đều bằng khóa k) thì thuật toán cho bài toán này không khác gì thuật toán tìm kiếm tuần tự. Khi đó đòi hỏi chúng ta phải hiểu kĩ về thuật toán cũng như khéo léo trong cài đặt thì mới giải thích để học sinh hiểu và cách làm như vậy chưa đáp ứng được yêu cầu của bài toán. Đó là lí do tôi đưa ra giải pháp để giải quyết vấn đề này một cách triệt để, để có thể ứng dụng một cách hiệu quả thuật toán tìm kiếm nhị phân trong quá trình giảng dạy, bồi dưỡng học sinh giỏi môn tin học. 2. Mô tả giải pháp sau khi có sáng kiến Vấn đề trọng tâm trong sáng kiến của tôi là cải tiến thuật toán tìm kiếm nhị phân để khi tìm được khóa tìm kiếm k thì luôn trả về vị trí đầu tiên hoặc vị trí cuối cùng tìm được khóa ở trong dãy. a. Tìm kiếm trả về vị trí đầu tiên khi tìm thấy khóa 6 9 Bài toán: Cho dãy số nguyên gồm số nguyên a1, a2, ,an (1 ≤ n ≤ 10 , |ai| ≤ 10 ) đã sắp xếp theo thứ tự không giảm và cho số nguyên (khóa tìm kiếm). Yêu cầu: Cho biết số nguyên có xuất hiện trong dãy hay không, nếu tìm thấy cho biết vị trí đầu tiên tìm được? Từ thuật toán đưa ra ở mục 1, ta cải tiến như sau: l=1;r=n; while (l<r) { int m=(l+r)/2; if (a[m]==k) r=m; else if (a[m]>k) r=m-1; else l=m+1; } if (a[l]==k) cout<<k<<”xuat hien trong day o vi tri”<<l; else cout<<k<<”khong xuat hien trong day”;
3. - Cải tiến đầu tiên là ở câu lệnh lặp while, ta còn đi tìm khóa nếu phạm vi tìm kiếm nhiều hơn một phần tử (l<r). - Cải tiến thứ hai, khi a [m] ==k ta vẫn sẽ tiếp tục tìm kiếm bằng cách thu hẹp phạm vi tìm kiếm về phần đầu bằng cách gán r =m. Như vậy, phạm vi tìm kiếm mới vẫn đảm bảo chắc chắn khóa tồn tại trong kết quả tìm kiếm cuối cùng. Khi câu lệnh while kết thúc, tức là khi l =r . Phạm vi tìm kiếm chỉ còn một phần tử trong dãy, thì công việc còn lại rất đơn giản. Ta kiểm tra nếu a[l] == k thì chính là vị trí đầu tiên tìm được, ngược lại thì kết quả là không tìm thấy. Như vậy, ta đã cải tiến thuật toán tìm kiếm nhị phân ban đầu để đáp ứng yêu cầu trả về vị trí đầu tiên tìm thấy. Độ phức tạp của thuật toán sau khi cải tiến vẫn không bị thay đổi O(log n). Thuật toán tìm kiếm nhị phân vừa cải tiến còn có thể viết gọn hơn như sau: l=1;r=n; while (l<r) { int m=(l+r)/2; if (a[m]>=k) r=m; else l=m+1; } if (a[l]==k) cout<<k<<”xuat hien trong day o vi tri”<<l; else cout<<k<<”khong xuat hien trong day”; Trong cách viết gọn này, ta gộp hai điều kiện a[m] ==k và a[m] >k vào thành một điều kiện a[m] ≥ k và gộp hai lệnh r = m−1 và r=m thàng một lệnh r = m. Câu hỏi đặt ra là: tại sao ta lại có thể gộp được như vậy? Câu trả lời đơn giản như sau, trong câu lệnh: if (a[m]>k) r=m-1; Nếu chúng ta thay phạm vi r = m− 1 thành r = m thì phạm vi tìm kiếm của chúng ta chỉ thêm một phần tử. Điều này không ảnh hưởng đến kết quả bài toán, đó là cơ sở để có thể viết gọn lại cách cài đặt thuật toán. b. Tìm kiếm trả về vị trí cuối cùng khi tìm thấy khóa 6 9 Bài toán: Cho dãy số nguyên gồm số nguyên a1, a2, ,an ( 1 ≤ n ≤ 10 , |ai| ≤ 10 ) đã sắp xếp theo thứ tự không giảm và cho số nguyên (khóa tìm kiếm). Yêu cầu: Cho biết số nguyên có xuất hiện trong dãy hay không, nếu tìm thấy cho biết vị trí cuối cùng tìm được? Từ thuật toán ở mục 2.a, ta cải tiến như sau: l=1;r=n; while (l<r) { int m=(l+r+1)/2;
4. if (a[m]<=k) l=m; else r=m-1; } if (a[l]==k) cout<<k<<”xuat hien trong day o vi tri”<<l; else cout<<k<<”khong xuat hien trong day”; - Cải tiến dễ nhất và trực quan nhất đó là nếu a[m] ≤ k thì khóa k nằm ở nửa sau của dãy tìm kiếm, ta chỉ việc thu nhỏ phạm vi tìm kiếm bằng cách gán l=m. Ngược lại thì khóa nằm ở nửa đầu của dãy tìm kiếm nên ta gán r = m− 1. - Cải tiến thứ hai cũng là cải tiến quan trọng nhất đó là lệnh int m=(l+r+1)/2; Câu hỏi đặt ra đầu tiên khi thấy lệnh này đó là tại sao phải cộng 1 sau đó mới chia 2. Để hiểu rõ hơn về lệnh này chúng tôi đưa ra một ví dụ như sau: Cho dãy A gồm n= 2 phần tử a[1] = 2; a[2] = 5, khóa tìm kiếm k= 5. Nếu ta để lệnh: int m=(l+r)/2; Với l= 1, m= 2 thì m luôn có giá trị = 1 và điều kiện a[m] ≤ k luôn đúng. Như vậy giá trị l, r không đổi, dẫn đến lệnh lặp while không bao giờ kết thúc. Vấn đề này được giải thích như sau: câu lệnh int m=(l+r)/2; làm việc trên các biến số nguyên nên khi ta chia cho 2 kết quả luôn luôn làm tròn xuống. Trong khi phần này ta cần giải quyết vấn đề tìm vị trí cuối cùng mà khóa xuất hiện. Tức là, ta cần tiến về phía cuối dãy để tìm thỏa mãn. Vậy nên ta phải làm tròn lên khi chia cho 2, đó là lí do vì sao ta phải cộng thêm 1. Với cải tiến cho thuật toán tìm kiếm nhị phân áp dụng trong trường hợp này thì độ phức tạp không thay đổi: O(log n) Tiếp theo tôi sẽ giới thiệu một số bài toán để thấy rõ hơn ứng dụng của cải tiến này. c. Một số ví dụ áp dụng Ví dụ 1: TỔNG CẶP SỐ Xét dãy số nguyên dương khác nhau từng đôi một a1, a2, . . . an, trong đó 1 ≤ ai ≤ 109, 1 ≤ n ≤ 105). Yêu cầu: Với số nguyên x cho trước (1 ≤ x ≤ 109) hãy xác định số cặp (ai, aj) thỏa mãn các điều kiện: • ai + aj = x, • 1 ≤ i < j ≤ n. Dữ liệu: Vào từ file văn bản SUMX.INP: • Dòng đầu tiên chứa số nguyên n, • Dòng thứ 2 chứa n số nguyên a1, a2, . . . an, • Dòng thứ 3 xhứa số nguyên x. Kết quả: Đưa ra file văn bản SUMX.OUT một số nguyên – số cặp tìm được. Ví dụ:
5. SUMX.INP SUMX.OUT 9 3 5 12710912311 13 Hướng dẫn: - Sắp xếp dãy số theo thứ tự không giảm. - Duyệt lần lượt các số trong dãy, với mỗi số ở vị trí ta cần tìm số số trong dãy các số ai +1, , an có giá trị bằng x−xi . - Để tìm số số có giá trị bằng x −ai trong dãy a từ [ i+ 1,n] ta sử dụng thuật toán tìm kiếm nhị phân: o Tìm vị trí l bé nhất có a[ l ] = x – ai o Tìm vị trí r lớn nhất có a[ r ] = x – ai o Số cần tìm là l − r + 1 - Cộng tổng tất cả số số thỏa mãn ở từng vị trí i ta thu được kết quả đáp ứng yêu cầu của bài. Chương trình: #include using namespace std; int n, a[100005],x; long long res=0; int tim_vi_tri_nho_nhat(int i, int j,int key) { int l=i,r=j; while (l<r) { int m=(l+r)/2; if (a[m]>=key) r=m; else l=m+1; } if (a[l]==key) return l; return -1; } int tim_vi_tri_lon_nhat(int i, int j, int key) { int l=i,r=j; while (l<r) {
6. int m=(l+r+1)/2; if (a[m]<=key) l=m; else r=m-1; } if (a[l]==key) return l; return -1; } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); freopen("sumx.inp","r",stdin); freopen("sumx.out","w",stdout); cin>>n; for(int i=1;i >a[i]; cin>>x; sort(a+1,a+n+1); for(int i=1;i<n;i++) { int left=tim_vi_tri_nho_nhat(i+1,n,x-a[i]); if (left<0) continue; int right=tim_vi_tri_lon_nhat(i+1,n,x-a[i]); res+=right-left+1ll; } cout<<res; return 0; } Ví dụ 2:Trò chơi với dãy số (VOI2008) Hai bạn học sinh trong lúc nhàn rỗi nghĩ ra trò chơi sau đây. Mỗi bạn chọn trước một dãy số gồm n số nguyên. Giả sử dãy số mà bạn thứ nhất chọn là: a1, a2,..., an còn dãy số mà bạn thứ hai chọn là b1, b2,...,bn Mỗi lượt chơi mỗi bạn đưa ra một số hạng trong dãy số của mình. Nếu bạn thứ nhất đưa ra số hạng ai (1 ≤ i ≤ n), còn bạn thứ hai đưa ra số hạng bj (1 ≤ j ≤ n) thì giá của lượt chơi đó sẽ là |ai+bj|. Ví dụ: Giả sử dãy số bạn thứ nhất chọn là 1, -2; còn dãy số mà bạn thứ hai chọn là 2, 3. Khi đó các khả năng có thể của một lượt chơi là (1, 2), (1, 3), (-2, 2), (-2, 3). Như vậy, giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể là 0 tương ứng với giá của lượt chơi (-2, 2). Yêu cầu: Hãy xác định giá nhỏ nhất của một lượt chơi trong số các lượt chơi có thể. Dữ liệu: Cho trong tệp AGAME.INP • Dòng ầđ u tiên chứa số nguyên dương n (n ≤ 105) 9 • Dòng thứ hai chứa dãy số nguyên a1, a2, ..., an (|ai| ≤ 10 , i=1, 2, ..., n)
7. 9 • Dòng thứ hai chứa dãy số nguyên b1, b2, ..., bn (|bi| ≤ 10 , i=1, 2, ..., n) Hai số liên tiếp trên một dòng được ghi cách nhau bởi dấu cách. Kết quảđưa ra tệp AGAME.OUTmột số duy nhất là giá nhỏ nhất tìm được. Ví dụ: AGAME.INP AGAME.OUT 2 0 1 -2 2 3 Hướng dẫn: - Sắp xếp dãy theo thứ tự không giảm. - Duyệt lần lượt từng phần tử của dãy b, với mỗi phần tử bj o Tìm phần tử có chỉ số lớn nhất j trên dãy a sao cho aj + bi ≤ 0 (sử dụng thuật toán tìm kiếm nhị phân) o Kết quả tốt nhất khi chọn bi là min (| bi + aj |, | bi + aj +1|) - Kết quả bài toán là giá trị nhỏ nhất trong các lượt chọn bi Chương trình: #include using namespace std; const int N=1e5+5; int n, a[N],b[N],res; int tim_vi_tri_lon_nhat(int i, int j,int key) { int l=i,r=j; while (l<r) { int m=(l+r+1)/2; if (a[m]+key<=0) l=m; else r=m-1; } return l; } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); freopen("agame.inp","r",stdin); freopen("agame.out","w",stdout); cin>>n; for(int i=1;i >a[i]; for(int i=1;i >b[i]; sort(a+1,a+n+1); sort(b+1,b+n+1); res=2e9+5;
8. for(int i=1;i<=n;i++) { Int j = tim_vi_tri_lon_nhat(1,n,b[i]); res=min(res,abs(a[j]+b[i])); if (j<n) res=min(res,abs(a[j+1]+b[i])); } cout<<res; return 0; } Ví dụ 3.Trò chơi trên dãy số (DH2018) Hai bạn A và B chơi trò chơi trên hai dãy số như sau: A sẽ tạo ra hai dãy số nguyên x1, x2, ,xm và y1, y2, ,yn. Sau đó, B sẽ chọn một số nguyên s và yêu cầu A tìm một số thuộc dãy thứ nhất và một số thuộc dãy thứ hai sao cho tổng hai số được chọn chênh lệch với là s nhỏ nhất. Yêu cầu: Cho hai dãy số nguyên x1, x2, ,xm và y1, y2, ,yn mà A tạo ra, cho s1, s2, ,sk là k câu hỏi của B. Với câu hỏi si (i = 1,2, ,k) đưa ra giá trị chênh lệch nhỏ nhất của si với tổng hai số tìm được. Dữ liệu: Vào từ file văn bản SEQGAME.INP: - Dòng ầđ u chứa ba số nguyên dương m, n, k (m, n ≤ 105, k ≤ 10); 9 - Dòng thứ hai chứa m số nguyên x1, x2, ,xm (| xi | ≤ 10 ); 9 - Dòng thứ ba chứa n số nguyên y1, y2, ,yn (| yi | ≤ 10 ); 9 - Dòng thứ tư chứa k số nguyên s1, s2, ,sk (| si | ≤ 10 ). Kết quả: Ghi ra file văn bản SEQGAME.OUT gồm k dòng, dòng thứ i ghi giá trị chênh lệch nhỏ nhất của si với tổng hai số tìm được. Ví dụ: SEQGAME.OU SEQGAME.INP T 3 4 2 0 1 3 2 1 -1531 2 9 Hướng dẫn: - Đây là bài tổng quát hơn bài đã cho trong ví dụ 2, thay vì tìm tổng ai + bj chệch lệch với 0 nhỏ nhất thì bài này yêu cầu tìm tổng ai + bj chệch lệch với s (là số cho trước) nhỏ nhất. - Chúng ta sửa chương trình đã cho ở ví dụ 2 là đáp ứng yêu cầu bài toán. Chương trình: #include using namespace std; const int N=1e5+5; int n,m,k,s,a[N],b[N],res;
9. int tim_vi_tri_lon_nhat(int i, int j,int key) { int l=i,r=j; while (l<r) { int m=(l+r+1)/2; if (a[m]+key<=s) l=m; else r=m-1; } return l; } int main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); freopen("seqgame.inp","r",stdin); freopen("seqgame.out","w",stdout); cin>>m>>n>>k; for(int i=1;i >a[i]; for(int i=1;i >b[i]; sort(a+1,a+m+1); sort(b+1,b+n+1); while (k--) { cin>>s; res=2e9+5; for(int i=1;i<=n;i++) { int j=tim_vi_tri_lon_nhat(1,m,b[i]); res=min(res,abs(a[j]+b[i]-s)); if (j<m) res=min(res,abs(a[j+1]+b[i]-s)); } cout<<res<<'\n'; } return 0; }