Đơn công nhận sáng kiến Vận dụng thuật toán tìm kiếm nhị phân để giải các bài toán trong tin học

Nội dung text: Đơn công nhận sáng kiến Vận dụng thuật toán tìm kiếm nhị phân để giải các bài toán trong tin học

1. Mẫu M-02 CỘNG HOÀ XÃ HỘI CHỦ NGHĨA VIỆT NAM Độc lập - Tự do - Hạnh phúc ĐƠN YÊU CẦU CÔNG NHẬN SÁNG KIẾN Kính gửi: - Hội đồng TVNV Khoa học & Công nghệ thành phố Tam Điệp; - Hội đồng Sáng kiến Sở GD&ĐT Ninh Bình Tôi là tác giả đề nghị xét công nhận sáng kiến: “Vận dụng thuật toán tìm kiếm nhị phân để giải các bài toán trong tin học” - Lĩnh vực áp dụng sáng kiến: Giáo dục - Ngày sáng kiến được áp dụng lần đầu: Từ năm học 2020 - 2021 I. Mô tả bản chất của sáng kiến + Bài toán tìm kiếm trong cuộc sống: Cần tìm cục tẩy trong hộp bút. + Bài toán tìm kiếm trong tin học: Tìm số 13 ở vị trí nào trong một dãy số cho trước. Mục tiêu tìm kiếm trong cả hai bài toán đều đã được xác định rõ ràng, đó là "cục tẩy" và "số 13" (cần tìm thấy số 13 xong mới có được vị trí). Và tập "dữ liệu" của chúng ta có (hay phạm vi tìm kiếm) chính là "những đồ vật trong hộp bút" hoặc "các số trong dãy số đã cho trước". Như vậy có thể hiểu, tìm kiếm là quá trình tìm một phần tử nằm trong một tập hợp rất nhiều phần tử dựa vào một yêu cầu nào đó. Bài toán tìm kiếm trong Tin học có thể phát biểu như sau: "Cho một dãy gồm n đối tượng a1,a2,...,an. Mỗi đối tượng ai có một khóa key (1≤i≤n) gọi là khóa tìm kiếm. Cần tìm kiếm đối tượng có khóa bằng k cho trước, tức là ai.key=k. Quá trình tìm kiếm sẽ hoàn thành nếu như có một trong hai trường hợp sau đây xảy ra: + Tìm được đối tượng có khóa tương ứng bằng k, khi đó phép tìm kiếm thành công. + Không tìm được đối tượng nào có khóa tương ứng bằng k, khi đó phép tìm kiếm thất bại. 1. Giải pháp cũ thường làm Mô tả bản chất của giải pháp cũ thường làm (đã có): Thông thường khi gặp một bài toán tìm kiếm, cách đơn giản nhất mà học sinh hay làm là các em thực hiện tìm kiếm tuần tự từ đầu đến khi tìm thấy giá trị cần tìm, hoặc đến cuối mà không tìm
2. thấy thì sẽ kết luận giá trị đó không tồn tại. Cách làm này được gọi là tìm kiếm tuần tự. Giải thuật tìm kiếm tuần tự (Sequential Search) Ý tưởng Tìm kiếm tuần tự (Sequential Search hay Linear Search) là một giải thuật đơn giản, rất dễ cài đặt. Bắt đầu từ đối tượng a1, duyệt qua tất cả các đối tượng, cho tới khi tìm thấy đối tượng có khóa mong muốn, hoặc duyệt hết toàn bộ dãy mà không tìm thấy khóa đó. Mặc dù giải thuật Tìm kiếm tuần tự rất đơn giản và dễ cài đặt, tuy nhiên nhược điểm của nó nằm ở độ phức tạp. Trong trường hợp tốt nhất, với dãy số có n số thì giải thuật có độ phức tạp là O(1), nhưng trong trường hợp xấu nhất lên tới O(n). Vì vậy độ phức tạp tổng quát của giải thuật là O(n), chỉ phù hợp với những bài toán có kích thước không gian tìm kiếm nhỏ. * Ưu điểm: - Đơn giản, dễ cài đặt. - Phù hợp với bài toán có không gian tìm kiếm nhỏ. * Nhược điểm: - Độ phức tạp lớn, không giải quyết được các bài toán có không gian tìm kiếm lớn. 2. Giải pháp mới 2.1. Sử dụng phương pháp tìm kiếm nhị phân Ý tưởng Trước tiên, không gian tìm kiếm cần được sắp xếp lại theo chiều tăng dần hoặc giảm dần của khóa tìm kiếm (mục tiêu là để tạo ra dãy có tính thứ tự). Giả sử dãy đã được sắp xếp tăng dần theo khóa, giải thuật tìm kiếm nhị phân được thực hiện như sau: - Giả sử cần tìm kiếm trong đoạn a[l...r] với khóa tìm kiếm là k, trước hết ta xét phần tử nằm ở giữa dãy là amid với mid=⌊2l+r⌋. - Nếu amid.key<k thì nghĩa là đoạn từ al tới amid chỉ chứa toàn các đối tượng có khóa nhỏ hơn k, nên ta tiếp tục quá trình tìm kiếm trên đoạn từ amid+1 tới ar. - Nếu amid.key>k thì nghĩa là đoạn từ amid tới ar chỉ chứa toàn các đối tượng có khóa lớn hơn k, nên ta tiếp tục quá trình tìm kiếm trên đoạn từ al tới amid−1. - Nếu amid.key=k thì quá trình tìm kiếm thành công. Quá trình tìm kiếm sẽ thất bại nếu như đến một bước nào đó, tập tìm kiếm bị rỗng (l>r).
3. Cài đặt giải thuật bằng ngôn ngữ lập trình C++: Tim_kiem_nhi_phan(k) { // Sắp xếp lại tập tìm kiếm theo thứ tự tăng dần của khóa tìm kiếm. sort(a); l = 1, r = n; // Trong khi tập tìm kiếm chưa rỗng while (l <= r) { mid = (l + r) / 2; // Tìm thấy đối tượng có khóa bằng k, trả về vị trí. if (a[mid].key == k) return mid; /// Điều chỉnh khoảng tìm kiếm cho phù hợp. if (a[mid].key < k) l = mid + 1; else r = mid - 1; } // Không tìm thấy khóa, trả về -1. return -1; } * Ưu điểm: - Thuật toán tìm kiếm nhị phân thu hẹp được phạm vi tìm kiếm chỉ còn tối đa là một nửa sau mỗi lần lặp. - Thuật toán chia bài toán thành những bài toán nhỏ hơn giúp tăng hiệu quả tìm kiếm. - Thuật toán hoạt động rất nhanh và hiệu quả với danh sách đã được sắp xếp, với độ phức tạp thời gian là O(log n), trong đó “n” là số phần tử trong danh sách. - Thuật toán có thể dùng để giải quyết nhiều loại vấn đề hơn, như tìm phần tử nhỏ nhất hoặc lớn nhất tiếp theo trong mảng so với giá trị cho trước, kể cả khi nó không có trong mảng. * Nhược điểm - Chỉ áp dụng cho danh sách đã được sắp xếp.
4. 2.2. Một số bài toán tìm kiếm sử dụng phương pháp tìm kiếm nhị phân 2.2.1. Bài toán tìm kiếm trên mảng a Bài toán: Cho mảng a có n phần tử đã được sắp xếp không giảm (với mọi i sao cho 1, i n aii a 1 và q truy vấn, mỗi truy vấn là một số x ( 6 5 9 9 2 n 10 , q 10 ,| ai | 10 ,| x | 10 ), với mỗi truy vấn, xác định xem có phần tử ai=x trong mảng a hay không, nếu tìm thấy thì in ra “YES”, không tìm thấy thì in ra “NO”. * Phân tích bài toán: Dựa vào đề bài, ta thiết lập được một thuật toán thu hẹp phạm vi tìm kiếm dựa trên giá trị của phần tử. Để hiểu hơn về cách giải thuật này hoạt động, ta xét ví dụ sau với n=9, a={3,5,8,13,18,19,21,27,32}, q=1 và phần tử cần tìm trong truy vấn có giá trị x=13. Đặt l là vị trí đầu tiên bên trái, r là vị trí cuối cùng bên phải của vùng cần xét. Ban đầu l=1, r=9 a={3,5,8,13,18,19,21,27,32} Xét vị trí chính giữa của a bằng công thức: mid=(l+r)/2=5, lúc này ta được giá trị của phần tử chính giữa a[mid]=18 Vì a[mid]>x (18>13) nên ta sẽ đi xét đoạn [l mid-1] (chính là đoạn [1,4]) a={3,5,8,13, } Khi đó, ta có mid=(l+r)/2=(1+4)/2=2. Xét a[2]=5 Vì a[mid]<x (5<12) nên ta tiếp tục xét đoạn [3,4] a={..,8,13, } Lúc này mid=(3+4)/2=3. Xét a[3]=8<13, Ta tiếp tục xét đoạn [4,4] Khi đó mid=(4+4)/2=4. Xét a[4]=13. Ta thấy a[4]=x. Như vậy có tồn tại phần tử x tại vị trí i=4 trong mảng a * Cài đặt thuật toán bằng ngôn ngữ lập trình C++: void TKNP(long long x) { int left = 1, right = n; while (left <= right) { int mid = (left + right) / 2; if (a[mid] == x) { cout << "YES"<<endl; return; }
5. else if(a[mid] > x) right = mid - 1; else left = mid + 1; } cout << "NO"<<endl; return; } 2.2.2. Bài toán tìm vị trí đầu tiên của phần tử X trong mảng đã sắp tăng dần * Phân tích bài toán: Tương tự như thuật toán tìm kiếm nhị phân nhưng khi tìm thấy phần tử X trong mảng thì ta chỉ lưu lại kết quả và cố gắng tìm kiếm thêm ở nửa bên trái. * Cài đặt thuật toán bằng ngôn ngữ lập trình C++: #include int firstPos(int a[], int n, int x){ int l = 0, r = n - 1; int pos = -1; // cập nhật kết quả while(l <= r){ //Tính chỉ số của phần tử ở giữa int m = (l + r) / 2; if(a[m] == x){ pos = m; // lưu lại //Tìm thêm bên trái r = m - 1; } else if(a[m] < x){ //tìm kiếm ở bên phải l = m + 1; } else{ //tìm kiếm ở bên trái r = m - 1; } } return pos; } int main(){ int n = 10, x = 3; int a[10] = {1, 1, 2, 2, 3, 3, 3, 5, 7, 9}; int res = firstPos(a, n, x); if(res == -1){
6. cout<<"Khong xuat hien trong mang."<<endl; } else{ cout<<"Vi tri dau tien cua" <x<<" trong mang: "<<res<<endl; } return 0; } Output : Vi tri dau tien cua 3 trong mang : 4 2.3.3. Bài toán tìm vị trí cuối cùng của phần tử X trong mảng đã sắp tăng dần * Phân tích bài toán: Tương tự như thuật toán tìm kiếm nhị phân nhưng khi tìm thấy phần tử X trong mảng thì ta chỉ lưu lại kết quả và cố gắng tìm kiếm thêm ở nửa bên phải. * Cài đặt thuật toán bằng ngôn ngữ lập trình C++: #include int lastPos(int a[], int n, int x){ int l = 0, r = n - 1; int pos = -1; // cập nhật kết quả while(l <= r){ //Tính chỉ số của phần tử ở giữa int m = (l + r) / 2; if(a[m] == x){ pos = m; // lưu lại //Tìm thêm bên phải l = m + 1; } else if(a[m] < x){ //tìm kiếm ở bên phải l = m + 1; } else{ //tìm kiếm ở bên trái r = m - 1; } } return pos; } int main(){ int n = 10, x = 3;
7. int a[10] = {1, 1, 2, 2, 3, 3, 3, 5, 7, 9}; int res = lastPos(a, n, x); if(res == -1){ cout<<"Khong xuat hien trong mang"<<endl; } else{ cout<<"Vi tri cuoi cung cua"<<x<<" trong mang "<< res<<endl; } return 0; } Output : Vi tri cuoi cung cua 3 trong mang : 6 2.2.4. Bài toán tìm vị trí đầu tiên của phần tử lớn hơn hoặc bằng X trong mảng đã sắp tăng dần * Phân tích bài toán: Tương tự như thuật toán tìm kiếm nhị phân nhưng khi tìm thấy phần tử ở giữa lớn hơn hoặc bằng phần tử X thì ta chỉ lưu lại kết quả và cố gắng tìm kiếm thêm ở nửa bên trái. * Cài đặt thuật toán bằng ngôn ngữ lập trình C++: #include int firstPos(int a[], int n, int x){ int l = 0, r = n - 1; int pos = -1; // cập nhật kết quả while(l <= r){ //Tính chỉ số của phần tử ở giữa int m = (l + r) / 2; if(a[m] >= x){ pos = m; // lưu lại //Tìm thêm bên trái r = m - 1; } else{ //tìm kiếm ở bên phải l = m + 1; } } return pos; } int main(){ int n = 10, x = 4; int a[10] = {1, 1, 2, 2, 3, 3, 3, 5, 7, 9};
8. int res = firstPos(a, n, x); if(res == -1){ cout<<"Khong xuat hien trong mang"<<endl; } else{ cout = "<<x<<" trong mang :"<< res<<endl; } return 0; } Output : Vi tri dau tien cua phan tu >= 4 trong mang : 7 2.2.5. Bài toán “Dãy con” Bài toán: Cho một dãy số nguyên dương a1, a2, ..., aN (10 < N < 105), ai ≤109 với mọi i=1..N và một số nguyên dương S (S < 1015). Yêu cầu: Tìm độ dài nhỏ nhất của dãy con chứa các phần tử liên tiếp của dãy mà có tổng các phần tử lớn hơn hoặc bằng S. Dữ liệu vào: Dòng 1 chứa N và S ở dòng đầu. Dòng 2 chứa các phần tử của dãy. Kết quả: Độ dài của dãy con tìm được. Ví dụ input 10 15 5 1 3 5 10 7 4 9 2 8 Output 2 * Cài đặt bài toán bằng ngôn ngữ lập trình C++ #include using namespace std; long long n,s,a[1000006],t[1000006]; long long dodai=1e6,d,c; int main() { cin>>n>>s; for (int i=1;i >a[i]; t[0]=0; for (int i=1;i<=n;i++) t[i]=t[i-1]+a[i];
9. for (int i=1;i<=n;i++) { long long x=t[i]-s; int j =upper_bound(t,t+i,x) - t; if(j==0 || j>i) continue; j=j-1; if (j>=0 && dodai>i-j) dodai=i-j; } cout<<dodai; return 0; } 2.2.6. Bài toán “Băng chuyền” Bài toán: Một băng chuyền có các gói hàng được vận chuyển từ cảng này sang cảng khác trong vòng t ngày. Gói hàng thứ i trên tải băng chuyền có khối lượng w[i]. Mỗi ngày chúng tôi chất hàng lên tàu bằng các băng chuyền (theo thứ tự trọng lượng). Tải trọng mỗi ngày của băng chuyền không được phép lớn hơn trọng lượng tối đa của tàu. Hãy in ra trọng lượng nhỏ nhất của tàu để tất cả các gói hàng trên băng chuyền được chuyển đi trong t ngày. (1<=days<=w.lenghts<=5.109) Input Output 1,2,3,4,5,6,7,8,9,10 15 5 3,2,2,4,1,4 6 3 1,2,3,1,1 3 4 * Phân tích bài toán: Trong bài này, một băng chuyền phải vận chuyển các gói hàng theo thứ tự cho trước trong t ngày. Gói hàng thứ i có trọng lượng w[i]. Biết mỗi ngày tổng khối lượng tối đa băng chuyền có thể vận chuyển là MAX (trọng lượng tối đa của tàu). Đề bài yêu cầu tìm MAX nhỏ nhất để băng chuyền có thể hoàn thành nhiệm vụ được giao. Để ý thấy rằng, với một số MAX, ta có thể tính toán được số ngày để chuyển hết các gói hàng sao cho mỗi ngày tổng khối lượng vận chuyển không quá MAX. Ban đầu, giao gói hàng 1 để ngày n1 chuyển. Nếu vận chuyển gói hàng 2 trong ngày n1 không làm tổng khối lượng trong ngày vượt MAX, thì ta sẽ chuyển
10. luôn gói đó trong ngày n1. Nếu không, ta sẽ chuyển gói đó trong ngày 2. Làm lần lượt như thế tới khi mọi gói hàng đều được chuyển, ta sẽ có được số ngày tối thiểu cần để chuyển hết gói hàng với tổng khối lượng mỗi ngày không quá MAX. Quay lại đề bài, ta thấy rằng thực ra vấn đề của bài toán là tìm số MAX nhỏ nhất sao cho số ngày tối thiểu để chuyển hết gói hàng không quá t ngày. Như vậy, ta có thể dùng tìm kiếm nhị phân với hàm kiểm tra P được xây dựng bằng thuật toán tham lam được trình bày ở trên để kiểm tra các giá trị MAX. Để ý tính chất đơn điệu ở đây thể hiện ở chỗ nếu MAX tăng lên thì số lượng ngày cần dùng chỉ có thể giữ nguyên hoặc giảm đi nên hàm P thỏa định lý chính và có thể áp dụng tìm kiếm nhị phân. Sau đây là đoạn code mẫu bằng C++: // hàm kiểm tra P bool check(int capacity, const vector & weights, int days) { int current_weight = 0; --days; for(int i = 0; i < weights.size(); ++i) { if (current_weight + weights[i] <= capacity) current_weight += weights[i]; else { --days; current_weight = weights[i]; } } return days >= 0; } // hàm tìm kiếm nhị phân int shipWithinDays(const vector & weights, int days) { int lo = 0, hi = 0; for (int i = 0; i < weights.size(); ++i) { lo = max(lo, weights[i]); hi += weights[i]; } while (lo < hi) { int mid = lo + (hi - lo)/2; if (check(mid, weights, days)) hi = mid; else lo = mid + 1; } return lo; }