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

I. PHẦN MỞ ĐẦU

1. Lý do chọn đề tài

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.

Vì thế tôi chọn đề tài: “ 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”

2. Mục tiêu nhiệm vụ của đề tài

Trong phạm vi đề tài của mình tôi muốn nghiên cứu một số phương pháp tuy không phải mới nhưng là các phương pháp khá hiệu quả trong việc giải các bài toán tin học nhằm giúp học sinh hình thành kỹ năng giải bài toán tin học và rèn luyện tư duy thuật toán từ đó rèn luyện tư duy lập trình. Cũng qua đề tài, tôi muốn cùng đồng nghiệp trao đổi, trau dồi chuyên môn nhằm góp phần nâng cao trình độ chuyên môn nghiệp vụ và khả năng mở rộng kiến thức. Với bản thân nghiên cứu đề tài sáng kiến kinh nghiệm là cơ hội tốt để nghiên cứu khoa học làm quen với phương pháp làm khoa học tuy chỉ trong phạm vi hẹp nhưng tôi hy vọng cùng với nổ lực của bản thân và sự giúp đỡ của đồng nghiệp sẽ có những đề tài khoa học tốt, lý thú và hiệu quả.

Giáo viên hoàn thành nội dung đề tài và định hướng cho học sinh thực hiện đề tài trong quá trình ôn tập và luyện thi học sinh giỏi.

Báo cáo thành chuyên đề trong các lần họp tổ, cụm chuyên môn để cùng đồng nghiệp bổ sung những thiếu sót của đề tài.

Học sinh dưới sự hướng dẫn của giáo viên nghiêm túc nghiên cứu đề tài và có định hướng phát triển khả năng lập trình của bản thân, đồng thời áp dụng lồng ghép với  nguyên lý 5R để giải quyết quyết triệt để các yêu cầu sau:

3. Đối tượng nghiên cứu: Đề tài này được áp dụng đối với học sinh khá và giỏi với nhiệm vụ chủ yếu là ôn thi học sinh giỏi và bồi dưỡng kiến thức cho học sinh yêu thích môn tin
4. Giới hạn phạm vi nghiên cứu: Phạm vi nghiên cứu được thực hiện đối với học sinh lớp 8, 9 tham gia bồi dưỡng học sinh giỏi

1. Phương pháp nghiên cứu

Để hoàn thành đề tài này, tôi đã tiến hành áp dụng một số phương pháp nghiên cứu sau:

– Phương pháp đặt vấn đề – giải quyết vấn đề

– Phương pháp phân tích tổng hợp.

– Phương pháp so sánh đối chiếu.

– Phương pháp thực nghiệm

– Phương pháp 5R

1. PHẦN NỘI DUNG

1. Cơ sở lý luận của phương pháp Chia để trị (Divide and Conquer):

Chia để trị là một tư tưởng rất phổ biến trong cuộc sống và được áp dụng rất hiệu quả trong Tin học. Tư tưởng cơ bản của phương pháp chia để trị là: Người ta phân bài toán thành các bài toán con, các bài toán con lại tiếp tục được phân thành các bài toán con nhỏ hơn, cứ tiếp tục như thế cho đến khi ta nhận được bài toán con đã có thuật giải hoặc có thể dễ dàng đưa ra thuật giải. Sau đó kết hợp nghiệm của các bài toán con để nhận được nghiệm của bài toán con lớn hơn để cuối cùng nhận được nghiệm của bài toán cần giải. Thông thường các bài toán con được phân chia là cùng dạng với bài toán ban đầu chỉ có cỡ của chúng là nhỏ hơn.

2. Thực trạng của vấn đề 

           Thực tế qua nhiều năm trực tiếp giảng dạy bộ môn Tin học, tham gia bồi dưỡng đội tuyển học sinh giỏi thị xã cũng như trao đổi với đồng nghiệp tôi nhận thấy: Hầu như học sinh đều rất yêu thích và hứng thú với môn Tin học. Tuy nhiên, chất lượng giảng dạy của bộ môn qua các năm học chưa cao, đặc biệt là kĩ năng lập trình trên máy của học sinh còn yếu, thậm chí một số học sinh còn rất ngại học lập trình Pascal và việc sử dụng máy tính để rèn luyện và trau đôi kĩ năng cho mình.

3. Nội dung, biện pháp giải quyết vấn đề đối với bài toán tìm kiếm và sắp xếp trong môn ngôn ngữ lập trình Pascal
4. a) Mục tiêu của việc Chia đề trị (Divide and Conquer)

Phương pháp Chia để trị là 1 phương pháp áp dụng cho các bài toán có thể giải quyết bằng cách chia nhỏ ra thành các bài toán con từ việc giải quyết các bài toán con này. Sau đó lời giải của các bài toán nhỏ được tổng hợp lại thành lời giải cho bài toán ban đầu

Mô hình Phương pháp chia để trị đượ