SKKN 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

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 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.  

• Mục đích nghiên cứu 

1. 1. • 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 

• Đối tượng và phạm vi nghiên cứu    – Thuật toán tìm kiếm nhị phân. 

1. 1. • 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. 

• 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. 

• Tính mới và đóng góp của đề tài 

1. • 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. 

PHẦN II: NỘI DUNG 

1. Cơ sở lý luận và thực tiễn 

• 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. 

• 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ử. 

• 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);