SKKN Phương pháp chia để trị để giải quyết bài toán sắp xếp và tìm kiếm nâng cao trong quá trình bồi dưỡng học sinh giỏi môn lập trình Pascal bậc THCS

Trong cuộc sống và trong công việc hằng ngày, chúng ta đều gặp những vấn đề cần phải đưa ra hướng giải quyết. Ngay từ lúc còn ngồi trong ghế nhà trường ta đã được luyện tập giải quyết các vấn đề qua môn toán học thông qua tập hợp hữu hạn hay một dãy các quy tắc chặt chẽ của các chỉ thị, phương cách hay 1 trình tự các thao tác trên một đối tượng cụ thể được xác định và định nghĩa rõ ràng cho việc hoàn tất một số sự việc từ một trạng thái ban đầu cho trước; khi các chỉ thị này được áp dụng triệt để thì sẽ dẫn đến kết quả sau cùng như đã dự đoán trước. Như vậy một bài toán có thể dùng rất nhiều thuật toán để giải quyết, vấn đề là chọn thuật toán nào hay phương pháp nào phù hợp với từng kiểu bài để đạt hiệu quả cao nhất (Quá trình xác định dữ liệu Input sau khi thực hiện dãy các thao tác ta thu được kết quả Output cần tìm đó được gọi là Thuật toán).

Trong chương trình Tin học bậc THCS nói riêng và chương trình tin học chuyên sâu nói chung (bồi dưỡng học sinh giỏi) đã có một số thuật toán để giải một lớp bài toán nhất định như: các thuật toán Sắp xếp, tìm kiếm,...và một số phương pháp thiết kế thuật toán như: Chia để trị, tham lam, quy hoạch động, cao hơn là các phương pháp nhị phân, ...

Từ thực tế giảng dạy và tham gia tuyển chọn bồi dưỡng học sinh giỏi môn lập trình Pascal bậc THCS của bản thân tôi nhận thấy việc nắm vững các thuật toán và áp dụng nó một cách linh hoạt trong các bài tập nhất định là không đơn giản. Sắp xếp và tìm kiếm là hai bài toán rất quen thuộc, rất nhiều học sinh có thể cài đặt chương trình sắp xếp hay tìm kiếm một cách dễ dàng. Tuy nhiên để có thể nhận dạng một bài toán có thể thực hiện với các thuật toán này không phải dễ, ngoài ra để cài đặt được thuật toán hiệu quả nhất cũng đòi hỏi người lập trình nắm vững các phương pháp thiết kế thuật giải.

Trong thiết kế thuật giải thì Chia để trị (Divide and Conquer) là một phương pháp quen thuộc sử dụng để giải khá nhiều bài toán. Chúng ta có thể áp dụng phương pháp này trong các bài toán sắp xếp và tìm kiếm. Với tư tưởng chia để trị chúng ta có thể cải thiện đáng kể độ phức tạp của thuật toán trong các bài toán sắp xếp và tìm kiếm. Tư tưởng chia để trị trong sắp xếp và tìm kiếm đã được viết ở nhiều tài kiệu khác nhau, trong đề tài này tôi tập trung đưa ra một số dạng bài tập từ phổ biến từ cơ bản đến khó có thể áp dụng phương pháp này và phân tích tính hiệu quả của nó đối với từng bài toán.