Sáng kiến kinh nghiệm THPT: Vận dụng thuật toán tìm kiếm nhị phân vào giải một số bài toán bằng ngôn ngữ lập trình C++ và python

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:51

Thêm vào BST

Báo xấu

74
lượt xem 27
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu sáng kiến nhằm nhìn nhận, giải quyết một số bài toán bằng phương pháp tìm kiếm nhị phân; Giúp các em tiếp cận một số hàm có sẵn thư viện C++, Python; Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT hoặc thi vào các trường chuyên

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Vận dụng thuật toán tìm kiếm nhị phân vào giải một số bài toán bằng ngôn ngữ lập trình C++ và python

SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT TƯƠNG DƯƠNG 2 SÁNG KIẾN KINH NGHIỆM VẬN DỤNG THUẬT TOÁN TÌM KIẾM NHỊ PHÂN VÀO GIẢI MỘT SỐ BÀI TOÁN BẰNG NGÔN NGỮ LẬP TRÌNH C++ VÀ PYTHON Môn: Tin học Giáo viên: Đinh Viết Mạnh Tổ: Toán-Lí-Tin-CN Số điện thoại: 0949239048 Năm học: 2022-2023 0
PHẦN I. ĐẶT VẤN ĐỀ 1. Lý do chọn đề tài Môn Tin học giữ vai trò chủ đạo trong việc chuẩn bị cho học sinh khả năng tìm kiếm, tiếp nhận và mở rộng tri thức cũng như sáng tạo trong thời đại thông tin, hỗ trợ đắc lực trong quá trình học tập và tự học của học sinh. Điều đó khẳng định vai trò và vị trí quan trọng của Tin học đối với toàn xã hội. Do đó mỗi người, mỗi học sinh cần hiểu và trang bị kiến thức cơ bản về Tin học để có thể theo kịp với thời đại, với sự phát triển của xã hội. Vì vậy khi học tin thì cần trang bị kiến thức, kỹ năng lập trình để giải quyết bài toán dễ dàng hơn. Trong chương trình giáo dục phổ thông 2018 thì ngôn ngữ lập trình Python đã đưa vào dạy học từ lớp 10 năm học 2022-2023, Ngoài ngôn ngữ lập trình Python thì C++ là ngôn ngữ lập trình hiện nay rất phổ biến trong chương trình dạy học cũng như tính ứng dụng ngôn ngữ này rất nhiều, nhất là trong các kỳ thi tin học trẻ, thi vào chuyên tin, học sinh giỏi tỉnh… Khi giải các bài toán Tin học người lập trình luôn mong muốn viết chương trình với thuật toán tối ưu, thời gian thực hiện nhanh, bộ nhớ hạn chế…Tuy nhiên, bài toán Tin học thường đa dạng, phong phú nên để có thể tìm được thuật toán tối ưu phù hợp dữ liệu bài toán là việc không hề dễ dàng. Trong lập trình tin học đã có rất nhiều phương pháp giải các bài toán nhưng để đảm bảo thời gian, không gian là không dễ. Vì vậy lựa chọn thuật toán để tối ưu là rất quan trọng. Qua quá trình giảng dạy, học tập, tìm tòi và đặc biệt là tham gia bồi dưỡng học sinh giỏi nhiều năm qua, trong đề thi có những bài toán kích thước lớn, nếu giải bằng cách thông thường thì sẽ không tối ưu về mặt thời gian, hoặc có thể không vét hết các trường hợp xảy ra của bài toán. Tuy nhiên, nếu áp dụng phương pháp tìm kiếm nhị phân (thường gọi là chặt nhị phân) thì sẽ giải quyết tốt được tất cả các trường hợp trên. Quá trình dạy tại các lớp mũi nhọn và ôn thi HSG cấp Tỉnh, tôi đã vận dụng phương pháp tìm kiếm nhị phân để giúp các em nhìn nhận một bài toán từ nhiều góc độ khác nhau. Qua đó có thể dễ dàng nhận ra việc áp dụng phương pháp này để giải bài toán nào đó. Vì vậy, tôi đã chọn đề tài “Vận dụng thuật toán tìm kiếm nhị phân vào giải một số bài toán bằng ngôn ngữ lập trình C++ và Python ". Đề tài ngoài tập trung nghiên cứu về thuật toán tìm kiếm nhị phân, đưa ra những ứng dụng của thuật toán khi giải các bài toán trên máy tính. Nhằm giúp học sinh vận dụng thuật toán này linh hoạt, giúp cải tiến về thời gian và không gian khi gặp các dạng bài toán này, cũng như các em hiểu kỹ hơn khi học chuyên đề tin 11 (Khoa học máy tính) trong năm học tới. Ngoài ra tôi cung cấp bộ test cho các bài tập giúp học sinh tự luyện code một cách hiệu quả nhất. Để cải thiện thời gian thuật toán thì cần kết hợp thuật toán tìm kiếm nhị phân với một số phương pháp 1
khác như quy hoạch động, tham lam…, cấu trúc dữ liệu set, map, hash…., để giải bài toán hiệu quả hơn. Để hoàn thành nhiệm vụ của đề tài, tôi đã nghiên cứu rất nhiều sách và các chuyên đề Tin học dành cho học sinh giỏi, các tài liệu trên các trang web. 2. Mục đích nghiên cứu - Với lý do chọn đề tài đã trình bày ở trên, tôi mong muốn đề tài của mình sẽ giúp đỡ phần nào các khó khăn khi nhận dạng bài toán tìm kiếm nhị phân trong quá trình ôn luyện học sinh giỏi. - Nhìn nhận, giải quyết một số bài toán bằng phương pháp tìm kiếm nhị phân. - Giúp các em tiếp cận một số hàm có sẵn thư viện C++, Python - Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT hoặc thi vào các trường chuyên 3. Đối tượng và phạm vi nghiên cứu - Thuật toán tìm kiếm nhị phân. - Một số bài tập thi HSG các cấp. - Sự tư duy, ý thức học tập của học sinh ôn thi học sinh giỏi. - Chương trình Tin học THCS, THPT để bồi dưỡng học sinh giỏi Tin học và thi vào trường chuyên THPT. 4. Phương pháp nghiên cứu Để thực hiện đề tài này, tôi đã sử dụng các phương pháp: - Phương pháp nghiên cứu xây dựng cơ sở lí thuyết: Cơ sở lý thuyết là phương pháp tìm kiếm nhị phân, một số bài toán trong các đề thi các cấp; Sự hứng thú trong giờ học môn Tin học và ý thức tự học của học sinh đối với môn học. - Phương pháp bồi dưỡng năng lực tự học, tư duy, giải quyết vấn đề cho học sinh - Phương pháp điều tra khảo sát, thống kê, để so sánh giữa nhóm thực nghiệm và đối chứng. 5. Tính mới và đóng góp của đề tài - Giúp cải thiện được thuật toán tối ưu hơn, đáp ứng thời gian theo yêu cầu của đề. - Giúp học sinh tiếp cận hàm bisect_left, bisect_right trong Python để giải bài tập - Là tài liệu cho học sinh giỏi cấp trường và cấp tỉnh tham khảo. Đồng thời tài liệu cho giáo viên dạy đội tuyển bậc THCS và THPT môn tin học. 2
PHẦN II: NỘI DUNG I. Cơ sở lý luận và thực tiễn 1. Cơ sở lý luận Giới thiệu thuật toán tìm kiếm nhị phân, các hàm tìm kiếm nhị phân có sẵn trong C++, Python cũng như nhìn nhận đánh giá được độ phức tạp thuật toán. 1.1. Thuật toán tìm kiếm nhị phân là gì? Thuật toán tìm kiếm nhị phân (Binary Search) là một thuật toán tìm kiếm trong một danh sách đã được sắp xếp theo thứ tự tăng dần hoặc giảm dần. Thuật toán này hoạt động bằng cách so sánh giá trị tại vị trí giữa danh sách với giá trị cần tìm kiếm. Nếu giá trị tại vị trí giữa bằng giá trị cần tìm kiếm, thuật toán sẽ trả về vị trí đó. Nếu giá trị tại vị trí giữa lớn hơn giá trị cần tìm kiếm, thuật toán sẽ tiếp tục tìm kiếm trong nửa đầu tiên của danh sách. Nếu giá trị tại vị trí giữa nhỏ hơn giá trị cần tìm kiếm, thuật toán sẽ tìm kiếm trong nửa sau của danh sách. Quá trình này được lặp lại cho đến khi tìm thấy giá trị cần tìm kiếm hoặc danh sách chỉ còn một phần tử. 1.2. Khái niệm hàm lower_bound, upper_bound, bisect_left, bisect_right có sẵn trong C++ và Python. 1.2.1. Giới thiệu về hàm lower_bound, bisect_left trong C++ và Python - Hàm lower_bound(a+1, a+n+1,x) -a với a[0]=-∞; a[n+1]=+∞: Đưa ra vị trí đầu tiên trong mảng a có giá trị >= x (từ vị trí 1 đến n), nếu không có x trong mảng a thì nó sẽ đưa kết quả là (n+1). - Hàm bisect_left(a, x): Cho ra vị trí đầu tiên trong mảng a có giá trị >= x; nếu không có x trong mảng a thì đưa ra kết quả là (n). Tương tự ta có thể đưa ra vị trí đầu tiên với giá trị a[k] >=x từ đoạn i đến j dùng hàn bisect_left(a, x,lo=i,hi=j); nếu không tìm thấy trả về vị trí hi. Áp dụng: Cho dãy số nguyên a1, a2, a3,..., an đã được sắp xếp không giảm và một số nguyên x. Tìm vị trí k nhỏ nhất sao cho a[k] >= x. Trong C++: kq = lower_bound(a+1, a+n+1, x) - a. Trong Python: kq= bisect.bisect_left(a,x); 1.2.2. Giới thiệu về hàm upper_bound, bisect_right trong C++ và Python - Hàm upper_bound(a+1,a+n+1,x)- a với a[0]=-∞; a[n+1]=+∞: Đưa ra vị trí đầu tiên trong mảng a có giá trị > x (từ vị trí l đến n), nếu không có x trong mảng a thì nó sẽ đưa kết quả là (n+1). - Hàm bisect_right(a, x): Cho ra vị trí đầu tiên trong mảng a có giá trị >x; nếu không có x trong mảng a thì đưa ra kết quả là (n). Tương tự ta có thể đưa ra vị trí đầu tiên với giá trị a[k] >x từ đoạn i đến j dùng hàm bisect_right(a,x,lo=i,hi=j); nếu không tìm thấy trả về vị trí hi. 3
Áp dụng: Cho dãy số nguyên a1, a2, a3,...,an đã được sắp xếp không giảm và một số nguyên x. Tìm vị trí k nhỏ nhất sao cho a[k] > x. Trong C++: kq = upper_bound(a+1, a+n+1, x) - a. Trong Python: kq= bisect_right(a,x). 1.2.3. Hệ quả 1: Đếm số lượng các phần tử trong dãy a 1, a2, a3,...,an có giá trị bằng x. Dãy đã được sắp xếp không giảm. Trong C++ ta có T = upper_bound(a+1, a+n+1, x) - lower_bound(a+1,a+n+1,x) Trong Python ta có: T = bisect_right(a,x)-bisect_left(a,x) 1.2.4. Hệ quả 2: Đếm số lượng các phần tử trong dãy a1, a2, ..., an có giá trị thỏa mãn x < ai < y (x, y là hai giá trị cho trước). Xem như dãy đã được sắp xếp theo thứ tự tăng dần. Trong C++ ta có T = lower_bound(a+1, a+n+1, y) - upper_bound(a+1, a+n+1, x) Trong Python ta có T= bisect_left(a, y)-bisect_right(a,x) 1.2.5. Hệ quả 3: Đếm số lượng các phần tử trong dãy a1, a2, ..., an đã được sắp xếp không giảm và một số nguyên x. Đếm xem có bao nhiêu phần tử có giá trị > x. Trong C++ ta có T = n+1 - (upper_bound(a+1, a+n+1, x) - a) Trong Python ta có T = n - (bisect_right(a, x)) 1.3. Độ phức tạp thuật toán Thuật toán tìm kiếm nhị phân (Binary Search) độ phức tạp tính toán của thuật toán tìm kiếm nhị phân trong trường hợp tốt nhất là O(1), trong trường hợp xấu nhất là O(logN). Thuật toán tìm kiếm nhị phân chỉ thực hiện được với dãy đã được sắp xếp, nên nếu dãy chưa sắp xếp thì cần phải tính đến thời gian cho việc sắp xếp lại dãy trước khi áp dụng tìm kiếm nhị phân. 2. Cơ sở thực tiễn Nêu ra thực trạng vấn đề, những thuận lợi, khó khăn của học sinh trong việc giải quyết các bài toán lớn, các bài toán ôn thi học sinh giỏi hiện nay. Qua đó giải quyết vấn đề và đưa ra các bài toán điển hình để so sánh sử dụng thuật toán tìm kiếm nhị phân với một số phương pháp khác, sử dụng thuật toán tìm kiếm nhị phân có thể vận dụng giải các bài toán trong các đề thi cũng như khi ôn luyện. Trang bị kiến thức cho học sinh và giáo viên để giải quyết tốt khi gặp các bài toán có liên quan đến sử dụng thuật toán tìm kiếm nhị phân, sử dụng thuật toán tìm kiếm nhị phân một cách hiệu quả nhất. 2.1 Đặc điểm tình hình 2.1.1 Thuận lợi - Với sự bùng nổ của ngành công nghệ thông tin cũng như chương trình giáo dục phổ thông 2018 các em học sinh đã học lập trình scratch từ tiểu học đến THCS, ở 4
THPT học Python giúp các em say mê, hứng thú, yêu thích đối với ngôn ngữ lập trình ngày càng nhiều hơn. - Ngày nay máy tính ngày càng có tốc độ xử lý cao đáp ứng được yêu cầu xử lý các bài toán có dữ liệu lớn trong thời gian thực hiện ngắn. - Các cuộc thi lập trình này ngày càng tổ chức nhiều hơn, việc học, xem tài lệu, luyện làm code cũng dễ dàng hơn, có thể xem các tài liệu trên web cũng như các kênh như youtube…. 2.1.2 Khó khăn - Ngôn ngữ lập trình Python còn khá mới mẽ, những kiến thức trong chương trình Tin học phổ thông còn hạn chế, hoặc chưa đủ đáp ứng cho việc giải một số bài toán trong các kỳ thi học sinh giỏi Tỉnh khi có yêu cầu dữ liệu lớn cùng thời gian thực hiện ngắn. - Thuật toán tìm kiếm nhị phân thường được dạy ngay sau giai đoạn học sinh học xong phần kĩ thuật lập trình cơ bản. Thời điểm này, học sinh đã có thể sử dụng ngôn ngữ lập trình cùng với các công cụ có sẵn trong thư viện để thể hiện thuật toán. Tuy nhiên, khả năng tự mình nhìn nhận, đánh giá và thiết kế được một thuật toán cho bài toán mới còn hạn chế. - Khi gặp các bài toán phải sử dụng kiểu dữ liệu lớn nhiều em lúng lúng. Việc giải các bài toán với kiểu dữ liệu lớn thực sự cần thiết cho các em khi làm các bài toán lập trình trong chương trình Tin học phổ thông nói riêng và việc giải quyết các bài toán thực tế nói chung. - Thực tế cho thấy, các đề thi HSG của tỉnh và các tỉnh đều có các bài tập tìm kiếm với số lớn. Nếu học sinh không hiểu rõ và nhận biết tốt thì thường khi giải các bài tập này hay gặp nhiều sai sót hoặc không xử lý hết test theo yêu cầu. 2.2. Thực trạng trước khi áp dụng đề tài - Nhiều học sinh có thể hiểu thuật toán tìm kiếm nhị phân nhưng việc vận dụng để giải một bài toán bằng phương pháp này thì thực sự chưa hiệu quả, chưa nhìn nhận được cách giải bài toán bằng phương pháp tìm kiếm nhị phân, nhất là các bài toán dạng tìm kiếm nhị phân theo kết quả. - Trong nội dung thi học sinh giỏi Tin học các cấp, có nhiều bài thường có thể giải với nhiều cách khác nhau, trong các cách đó thì không phải cách nào cũng có thể giải quyết hết các bộ dữ liệu giới hạn của bài toán, việc hướng đến giải quyết hết các test từ bé đến lớn với thời gian đảm bảo yêu cầu (thường là 1s) là vấn đề không phải học sinh nào cũng có thể làm được. Một trong những phương pháp giúp học sinh giải được khá nhiều bài ở mức độ vừa và khó là tìm kiếm nhị phân. 5
II. Các giải pháp giải quyết vấn đề của đề tài 1. Giới thiệu ví dụ minh họa thuật toán tìm kiếm nhị phân và mô phỏng thuật toán Thuật toán tìm kiếm nhị phân là một thuật toán cơ bản trong lĩnh vực khoa học máy tính, được sử dụng để tìm kiếm một giá trị cụ thể trong một mảng đã sắp xếp. Thuật toán này hoạt động bằng cách lặp đi lặp lại việc chia đôi mảng con trong quá trình tìm kiếm, đến khi tìm thấy giá trị cần tìm hoặc mảng đã bị chia nhỏ đến mức chỉ còn một phần tử. 1.1 Xét ví dụ sau: Cho dãy số gồm N phần tử đã được sắp xếp theo thứ tự không giảm. Tìm xem trong dãy có giá trị nào bằng X hay không? Ý tưởng: + Đầu tiên, mảng cần được sắp xếp theo thứ tự tăng dần hoặc giảm dần. + Lấy phần tử ở vị trí của phần nguyên phép của chia (left+right) cho 2 và so sánh với giá trị cần tìm. Nếu giá trị của vị trí phần nguyên phép của chia (left+right) cho 2 bằng giá trị cần tìm, thuật toán trả về vị trí của giá trị này trong mảng. + Nếu giá trị của vị trí phần nguyên của phép chia (left+right) cho 2 lớn hơn giá trị cần tìm, thuật toán sẽ tiếp tục tìm kiếm trong mảng con bên trái của phần nguyên phép chia (left+right) cho 2 + Nếu giá trị của vị trí phần nguyên phép chia (left+right) cho 2 nhỏ hơn giá trị cần tìm, thuật toán sẽ tiếp tục tìm kiếm trong mảng con bên phải của phần nguyên phép chia đó. + Thuật toán sẽ lặp lại quá trình này cho đến khi tìm thấy giá trị cần tìm hoặc mảng đã bị chia nhỏ đến mức chỉ còn một phần tử. Các bước để sử dụng thuật toán tìm kiếm nhị phân trong bài toán này như sau: - Khởi tạo giá trị left và right lần lượt là 0 và N - 1, trong đó N là số phần tử trong dãy. - So sánh X với phần tử giữa dãy a[mid], với mid là phần nguyên của phép chia (left+right) cho 2, có ba trường hợp xẩy ra: ● Nếu X=a[mid] thì trả về chỉ số mid và kết thúc chương trình. ● Nếu Xa[mid] thì phần tử cần tìm sẽ nằm dãy con bên phải của phần tử a[mid], cập nhật giá trị left=mid+1, giữ nguyên giá trị right. Lặp lại các bước trên cho đến khi tìm thấy phần tử bằng X hoặc phạm vi tìm kiếm bằng rỗng(right
1.2 . Nội dung chương trình bằng C++ và Python Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python Với đầu vào là một mảng đã sắp xếp arr và giá trị cần tìm x, hàm binary_search() sẽ trả về chỉ số đầu tiên của x trong arr nếu x có tồn tại trong mảng và -1 nếu không. Độ phức tạp thuật toán: O(logn) 2. Phân loại thuật toán tìm kiếm nhị phân 2.1. Giải bài toán bằng tìm kiếm nhị phân Ví dụ 1: Đoạn con ngắn nhất (Đề thi thử cụm Nam Đàn 2022) Cho một dãy số nguyên dương a1, a2, ..., aN (10
Hướng giải quyết 1: Sử dụng tìm kiếm nhị phân trên dãy số Ý tưởng thuật toán: Gọi T[i] là tổng của các số từ A[1] đến A[i] vì A[i] các số dương nên dãy T là dãy tăng dần, khi đó ta sẽ tiến hành tìm kiếm nhị phân trên dãy T như sau: Xét T[i] mổi vị trí i ta gán d=1; c=i-1; g=(d+c)/2 - Nếu T[i]-T[g]>=S thì kq=min(kq, i-g) và tìm kq tiếp tục ở đoạn bên phải T[g] - Nếu T[i]-T[g]
Hướng giải quyết 2: Sử dụng tìm kiếm nhị phân theo kết quả Ý tưởng thuật toán: - Gọi g là đoạn ngắn nhất cần tìm đoạn [1, n]. Nếu kiểm tra g thỏa mãn thì cập nhật và đi tìm g nhỏ hơn thỏa mãn tức là tìm g bên trái trên đoạn [d, g-1] ngược lại tìm g trên đoạn [g+1, c]. - Hàm check nhiệm vụ kiểm tra đoạn độ dài g trượt trên mảng s sao cho s[i]- s[i-g] >= x hay không. Nếu lớn hơn trả về true ngược lại trả về false Độ phức tạp thuật toán: O(nlogn) Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python Hướng giải quyết 3: Sử dụng hàm lower_bound, upper_bound, bisect_left, bisect_right Ý tưởng thuật toán: Ta sử dụng mảng s để lưu trữ tổng từ phần tử đầu tiên đến phần tử thứ i của mảng a. Sau đó, duyệt từng phần tử i của mảng a, tính tổng k = x + s[i], sử dụng hàm lower_bound, bisect_left để tìm vị trí đầu tiên trong mảng s mà có giá trị lớn hơn hoặc bằng k. 9
Nếu vị trí đó không vượt quá giới hạn n, ta cập nhật res bằng giá trị pos - i và tìm giá trị nhỏ nhất của res. Cuối cùng, in ra giá trị res đó. Độ phức tạp thuật toán: O(nlogn) Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python Nhận xét: Qua bài toán trên ta có thể giải quyết bài toán bằng 3 cách đều tìm kiếm nhị phân, do mảng f đã sắp xếp tăng dần nên ta mới áp dụng thuật toán này nếu áp dụng hàm lower_bound, upper_bound, bisect_left, bisect_right có sẵn trong thư viện thì chương trình ngắn ngọn hơn, còn tìm kiếm nhị phân theo kết quả cần định kết quả cần tìm trên đoạn nào thông thường bài toán tìm min hoặc max. Link test tải về https://drive.google.com/drive/u/0/folders/1ZzzgRMoZYDbhtpcU- fSMoYfYg7o_6sTm Bài 2. Cặp số hoàn hảo Hai số nguyên được gọi là một “Cặp số hoàn hảo” nếu như tổng của chúng bằng giá trị S cho trước. Hãy đếm xem trong dãy số nguyên a 1, a2, …, an có bao nhiêu cặp số hoàn hảo. • Input: capso.inp gồm có: - Dòng thứ nhất ghi số nguyên dương n(n≤105) và số nguyên S (│S│≤109). - Các dòng tiếp theo lần lượt ghi các số a1, a2, ..,an (│ai│≤109). • Output: capso.out một số nguyên duy nhất là số lượng cặp hoàn hảo. 10
capso.inp capso.out 10 7 7 5253431640 Hướng giải quyết 1: Sử dụng tìm kiếm nhị phân trên dãy số Ý tưởng thuật toán: Sắp xếp dãy tăng dần, sử dụng tìm kiếm nhị phân như sau. - Để giải quyết bài toán này, ta sắp xếp tăng dần mảng. Với mỗi phần tử S[i] trong mảng, ta sẽ tìm kiếm phần tử S[j] thỏa mãn S[i] + S[j] = B. Sử dụng thuật toán tìm kiếm nhị phân, ta có thể tìm kiếm S[j] trên đoạn từ 1 đến i. Tuy nhiên, khi tìm kiếm phần tử S[j] để tạo thành cặp với S[i], ta cần đảm bảo rằng j < i để tránh đếm một cặp phần tử trùng lặp. - Sau khi đã tìm được tất cả các cặp phần tử trong mảng, ta cần đếm số cặp có tổng bằng x và xuất kết quả. Nếu có k phần tử trong mảng có giá trị bằng x/2, ta sẽ đếm số cặp (k*(k-1))/2 để tránh đếm một cặp trùng lặp. Độ phức tạp thuật toán: O(nlogn) Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python 11
Hướng giải quyết 2: Sử dụng hàm lower_bound, upper_bound, bisect_left, bisect_right. Ý tưởng thuật toán: Ta sắp xếp dãy số a[1], a[2], ..., a[n] theo thứ tự tăng dần và duyệt từng phần tử a[i] trong dãy, với mỗi phần tử a[i] ta tìm phần tử a[j] sao cho a[i] + a[j] = s (tương đương với tìm phần tử có giá trị k = s - a[i]), sử dụng hai hàm upper_bound và lower_bound của STL trong C++, hàm bisect_left, bisect_right trong Python. Sau đó, ta kiểm tra xem giá trị k tìm được có trong đoạn [a[u], a[v]], trong đó u và v là chỉ số của phần tử nhỏ nhất và lớn nhất trong dãy thỏa mãn điều kiện a[u]
vì sẽ quá thời gian qui định (1s). Khi đó, có thể nghĩ đến sắp xếp và tìm kiếm nhị phân. Bài 1: Chia kẹo1 (Đề HSG lớp 9 Bảng B Nghệ An 2021) Có 𝑁 gói kẹo được đánh số hiệu từ 1 đến 𝑁. Gói kẹo thứ 𝑖 (𝑖 = 1, 2, 3, …, 𝑁) có 𝐴 𝑖 chiếc kẹo. Cần phân chia 𝑁 gói kẹo thành 2 phần: Phần 1 gồm các gói kẹo 1, 2, …, 𝑖. Tổng số chiếc kẹo của phần 1 là 𝑥 = 𝐴1 + 𝐴2 + ⋯ + 𝐴 𝑖. Phần 2 gồm các gói kẹo 𝑖 + 1, 𝑖 + 2, …, 𝑁. Tổng số chiếc kẹo của phần 2 là 𝑦 = 𝐴 𝑖+1 + 𝐴 𝑖+2 +⋯ + 𝐴 𝑁; Với 1 ≤ 𝑖
Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python Bài 2: Cho 1 dãy số gồm N số nguyên. Hãy tìm xem có bao nhiêu cặp số có chênh lệch bằng k đơn vị. Dữ liệu vào: Tệp ‘khieuvu.inp’: - Dòng đầu tiên là N - số lượng dãy số và số nguyên K (N≤105, 0
Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python 15
Link test tham khảo: https://drive.google.com/drive/u/0/folders/1NkgfHPWkbYDxUk49nxVfIBhT-lkR- DDW Bài 3: Chia kẹo 2 (Đề HSG 9 bảng A Nghệ An năm 2020-2021) Có 𝑁 gói kẹo được đánh số hiệu từ 1 đến 𝑁. Gói kẹo thứ 𝑖 (𝑖 = 1, 2, 3, …, 𝑁) có 𝐴𝑖 chiếc kẹo. Cần phân chia 𝑁 gói kẹo thành 3 phần: • Phần 1 gồm các gói kẹo 1, 2, …, 𝑖. Tổng số chiếc kẹo của phần 1 là 𝑥 = 𝐴1 + 𝐴2 + ⋯ + 𝐴i; • Phần 2 gồm các gói kẹo 𝑖 + 1, 𝑖 + 2, …, 𝑗. Tổng số chiếc kẹo của phần 2 là 𝑦 = 𝐴i+1 + 𝐴i+2 +⋯ + 𝐴j; • Phần 3 gồm các gói kẹo 𝑗 + 1, 𝑗 + 2, …, 𝑁. Tổng số chiếc kẹo của phần 3 là 𝑧 = 𝐴j+1 + 𝐴j+2 +… + 𝐴N. Với 1 ≤ 𝑖
Độ phức tạp thuật toán: O(nlogn) Ngôn ngữ lập trình C++ Ngôn ngữ lập trình Python Link test tham khảo: https://drive.google.com/drive/u/0/folders/10yxrCYNVDqPSaqZANzhato- mMMMjFD9p 2.3. DẠNG 2. Tìm kiếm nhị phân theo kết quả Dạng tìm một phần tử trên dãy được sắp xếp là dạng cơ bản quen thuộc. Ta có thể mở rộng việc tìm kiếm nhị phân trên miền kết quả. Bắt đầu bằng miền tìm kiếm là miền giá trị mà chắc chắn kết quả cần tìm sẽ thuộc vào đó. Với mỗi lần tìm kiếm, chia đôi miền đó. Gọi x là giá trị trên miền đó mà cần kiểm tra. Xây dựng hàm check(x) trả về true nếu kết quả của x là có thể, ngược lại trả về false. Dạng bài toán này, thường tìm giá trị lớn nhất, nhỏ nhất. 17
Bài 1: ƯỚC SỐ NHỎ NHẤT Cho dãy số nguyên gồm N phần tử từ a1,a2,…,aN và số nguyên k.(1
Link test tham khảo: https://drive.google.com/drive/u/0/folders/19L410YFXopgV8qgyGt5X0AVsz5o0 By9M Câu 2: Xâu con phân biệt (Nguồn Đề hsg 12 vĩnh phúc 2021) Một lần Mr. Bean được bạn gái gửi cho một dãy ký tự độ dài chỉ gồm các chữ cái in hoa (‘A’...’Z’). Bạn gái nhờ Mr. Bean xác định "Độ phân biệt" của dãy ký tự trên. Trong đó Độ phân biệt của dãy ký tự là số nguyên dương l nhỏ nhất sao cho tất cả các xâu con của S độ dài l là đôi một phân biệt. Chẳng hạn với = 7; = 'ABCDABC' thì l = 4 do tất cả các xâu con độ dài 4 đều phân biệt. Bạn hãy giúp Mr. Bean việc đó. Dữ liệu: ● Dòng 1: số nguyên dương ( ≤ 100). ● Dòng 2: chứa xâu ký tự Kết quả: ● Gồm một dòng duy nhất ghi một số nguyên duy nhất là "Độ phân biệt" của dãy ký tự . Ví dụ: DIFFSSTR.INP DIFFSSTR.OUT 7 4 ABCDABC Bài toán này có thể sử dụng 2 vòng lặp for kết hợp cấu trúc dữ liệu set, map để xác định các đoạn con phân biệt, ngoài ra sử dụng thuật toán đếm phân phối nữa. Dưới đây tôi đưa ra giải pháp bằng tìm kiếm nhị phân. Ý tưởng thuật toán: Sử dụng chặt nhị phân tìm kết quả - Kết quả bài toán thuộc đoạn [1, n] 19