PHẦN MỞ ĐẦU
Lí do chọn đề tài
Hiện nay, tài liệu chuyên đề nâng cao phục vụ bồi dưỡng học sinh giỏi môn Tin học còn thiếu đầy đủ và tổng quát, đặc biệt là các chuyên đề mới và khó như Chia để trị và Quy hoạch động, đã được đưa vào các đề thi học sinh giỏi tỉnh.
Để nâng cao hiệu quả bồi dưỡng học sinh giỏi trong giảng dạy môn Tin tại trường THPT, cần thiết kế bài giảng phù hợp với nội dung kiến thức, dựa trên tài liệu chuyên đề đầy đủ và rõ ràng Việc này bao gồm cả lý thuyết và bài tập, đồng thời phải theo đúng xu thế các kỳ thi học sinh giỏi hiện nay và trong tương lai, nhằm đạt thành tích cao cho đội tuyển học sinh giỏi.
Dựa trên cơ sở nghiên cứu, tôi đã quyết định chọn đề tài “Sử dụng phương pháp chia để trị để giải một số bài toán” Sáng kiến này nhằm hỗ trợ học sinh trường THPT Thái trong việc nâng cao khả năng giải quyết vấn đề toán học một cách hiệu quả.
Hòa áp dụng kiến thức để giải quyết hiệu quả các dạng đề thi học sinh giỏi tỉnh liên quan đến phương pháp chia để trị, nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi tại trường.
Mục đích của đề tài
- Mục tiêu chính của đề tài là nghiên cứu về phương pháp “Chia để trị” để giải một số bài toán
- Giúp cho việc ôn thi học sinh giỏi đạt kết quả cao
Tạo nguồn tài liệu tham khảo phong phú về các phương pháp và thuật toán sẽ hỗ trợ hiệu quả cho học sinh và giáo viên trong việc bồi dưỡng học sinh giỏi môn tin học.
Đối tượng và phạm vi nghiên cứu
- Sử dụng phương pháp chia để trị và một số bài toán
- Học sinh giỏi tin khối 11, giáo viên giảng dạy học sinh giỏi tin 11
Sử dụng phương pháp chia để trị để giải một số bài toán bồi dưỡng học sinh giỏi tin học 11.
Phương pháp nghiên cứu
- Thu thập, phân tích các tài liệu và thông tin liên quan đến phương pháp chia để trị
- Lựa chọn một số bài toán để sử dụng phương pháp chia để trị
- Thiết kế các bài toán đã được lựa chọn trong chương trình tin học 11 để bồi dưỡng học sinh giỏi
- Dùng ngôn ngữ lập trình Free Pascal để cài đặt bài toán và chạy thử nghiệm trên một số bộ test để đánh giá kết quả.
NỘI DUNG SÁNG KIẾN KINH NGHIỆM
Cơ sở lý luận
Học sinh THPT ở các trường trung du miền núi, đặc biệt là THPT Thái Hòa, đang gặp nhiều khó khăn trong việc tiếp cận tri thức mới và hiện đại Một trong những nguyên nhân chính là sự thiếu hụt tài liệu chuyên sâu phục vụ cho việc bồi dưỡng học sinh giỏi Thêm vào đó, các em chưa thực sự quan tâm đến lập trình do cảm thấy môn học này khó khăn.
Tôi đã nghiên cứu tài liệu để xây dựng đề tài về phương pháp chia để trị, bao gồm lý thuyết, thuật toán và các bài toán thực hành trên máy tính Qua đó, học sinh có thể áp dụng kiến thức để giải quyết các đề bài tương tự trong các kỳ thi chọn học sinh giỏi môn tin học.
Nội dung và giải pháp thực hiện
Chia để trị là một phương pháp phổ biến trong Tin học, giúp giải quyết các bài toán phức tạp bằng cách phân chia chúng thành các bài toán con Các bài toán con này tiếp tục được chia nhỏ cho đến khi đạt được những bài toán đơn giản hơn, có thể dễ dàng giải quyết Sau khi tìm ra nghiệm cho các bài toán con, ta kết hợp chúng lại để tìm ra nghiệm cho bài toán lớn hơn, cuối cùng dẫn đến nghiệm của bài toán gốc Thông thường, các bài toán con có cùng dạng với bài toán ban đầu nhưng kích thước nhỏ hơn.
Các bài toán có thể giải quyết bằng phương pháp chia để trị thông qua 3 bước:
Bước 1: Chia: Chia bài toán cần giải thành một loạt các bài toán con độc lập
Tại giai đoạn này, bài toán ban đầu được phân chia thành các bài toán con cho đến khi không thể chia nhỏ hơn nữa Những bài toán con này sẽ trở thành những bước nhỏ trong quá trình giải quyết bài toán lớn.
Bước 2 Trị: Giải quyết bài toán con một cách đệ quy
Tại bước này ta sẽ phải tìm phương án để giải quyết cho bài toán con một cách cụ thể
Bước 3 Kết hợp lời giải lại để suy ra lời giải
Sau khi hoàn thành bài toán nhỏ, hãy lặp lại các bước giải quyết và kết hợp các lời giải để suy ra kết quả mong muốn, có thể áp dụng theo dạng đệ quy.
Giả sử chúng ta có thuật toán α để giải bài toán với kích thước dữ liệu n và thời gian bị giới hạn bởi cn² (c: hằng số) Xét thuật toán β, được sử dụng để giải bài toán này.
- Bước 1: Chia bài toán cần giải thành 3 bài toán con với kích thước n/2
- Bước 2: Giải 3 bài toán bằng thuật toán α
- Bước 3: Tổng hợp lời giải của 3 bài toán con để thu được lời giải của bài toán
Tính đúng đắn của thuật toán:
Giả sử bước 3 đòi hỏi thời gian dn (d: hằng sô)
T α(n)= thời gian của thuật toán α
T β(n)= thời gian của thuật toán β
Nếu dn < c.n2/4 hoặc n > 4.d/c, thuật toán β sẽ nhanh hơn thuật toán α Vì 4.d/c là hằng số, với n đủ lớn, ta luôn có n > 4.d/c Điều này chứng tỏ rằng việc áp dụng thuật toán β để giải bài toán bằng cách chia nó thành các bài toán con có kích thước ngày càng nhỏ sẽ mang lại hiệu quả cao khi đạt được kích thước n0 < 4.d/c.
4 Thuật toán chia để trị có thể biểu diễn bằng mô hình đệ quy như sau: Procedure DivideConquer(A,x); //Tìm nghiệm x của bài toán A
If (A đủ nhỏ) then Solve(A)
Phân A thành các bài toán con A1, , Am;
For i:=1 to m do DivideConquer(Ai,xi);
Kết hợp nghiệm xi của bài toán con Ai để được nghiệm của bài toán A;
Chúng ta sẽ khám phá bài toán Tháp Hà Nội, một ví dụ tiêu biểu được giải quyết bằng phương pháp chia để trị, nhằm làm rõ hơn tư tưởng của phương pháp này.
Ví dụ Bài toán Tháp Hà Nội
Có N đĩa với các đường kính khác nhau được xếp chồng lên nhau theo thứ tự giảm dần từ dưới lên Có ba vị trí để đặt các đĩa được đánh số từ 1.
2, 3 Chồng đĩa ban đầu được đặt ở vị trí 1:
Cần chuyển cả chồng đĩa từ vị trí 1 sang vị trí 2, theo những quy tắc sau:
Khi di chuyển một đĩa, phải đặt nó vào một trong ba vị trí đã cho
Mỗi lần chỉ có thể chuyển một đĩa và phải là đĩa ở trên cùng
Khi một đĩa mới được chuyển đến một vị trí, nó phải được đặt lên trên cùng Điều quan trọng là đĩa lớn hơn không được phép đặt lên đĩa nhỏ hơn; tức là, một đĩa chỉ có thể đặt trên mặt đất hoặc trên một đĩa lớn hơn.
Bài toán này xuất phát từ một truyền thuyết Ấn Độ, trong đó một nhóm cao tăng Ấn Độ giáo được giao nhiệm vụ chuyển 64 đĩa vàng giữa ba cọc kim cương Công việc này phải tuân theo các quy tắc cụ thể đã được đề cập Khi tất cả 64 đĩa được chuyển từ vị trí ban đầu sang vị trí kết thúc, đó cũng là thời điểm báo hiệu tận thế.
Chúng ta giải bài toán bằng cách chia bài toán chuyển N đĩa, từ vị trí 1 sang vị trí 2 thành ba bài toán đơn giản hơn như sau:
1 Chuyển N-1 đĩa trên cùng từ vị trí 1 sang vị trí 3, dùng vị trí 2 làm trung gian
2 Chuyển đĩa thứ N từ vị trí 1 sang vị trí 2
3 Chuyển N-1 đĩa từ vị trí 3 sang vị trí 2, dùng vị trí 1 làm trung gian
Bài toán 1 và 3 có cấu trúc tương tự như bài toán gốc, chỉ khác ở kích thước nhỏ hơn Cả hai bài toán này sẽ được giải quyết bằng phương pháp "chia để trị".
6 như bài toán ban đầu Dễ dàng kiểm tra là khi giải như vậy chúng vẫn thoả mãn các điều kiện Bài toán 2 thì được giải rất đơn giản
Thuật toán được viết dưới dạng giả mã như sau:
Procedure Hanoi; begin Move(n,1,2,3); end;
{chuyển n đĩa, từ vị trí a sang vị trí b, dùng vị trí c làm trung gian } begin if n=0 then exit;
Move(n-1,a,c,b); writeln('Chuyển đĩa ',n, ' từ vị trí ',a, 'sang vi tri ',b);
The ThapHN program implements the Tower of Hanoi algorithm using a recursive procedure to move disks between three positions It prompts the user to input the number of disks (N) and then calls the 'move' procedure to transfer the disks from position 1 to position 2, utilizing position 3 as an auxiliary The process involves recursively moving the disks, displaying each move with a message indicating the disk number and its source and destination positions This program effectively demonstrates the principles of recursion and problem-solving in programming.
Để phân tích độ phức tạp tính toán, ta định nghĩa T(n) là số thao tác chuyển đĩa cần thiết để hoàn thành việc chuyển n đĩa Theo thuật toán đã nêu, ta có thể xác định được giá trị của T(n).
Bằng cách sử dụng công thức truy hồi, ta tính được T(n) = 2^n - 1 Nếu mỗi cao tăng cần 1 giây để chuyển một đĩa từ cọc này sang cọc kia, thời gian để chuyển toàn bộ 64 đĩa vàng sẽ là T(64) = 2^64 - 1 giây, tương đương với 18.446.744.073.709.551.615 giây Theo đó, theo truyền thuyết, ngày tận thế sẽ phải đến sau 600 tỷ năm Phương pháp chia để trị cũng có thể được áp dụng cho bài toán tìm kiếm.
Thuật toán tìm kiếm nhị phân
Bài toán yêu cầu xác định xem trong dãy A gồm N số nguyên được sắp xếp không giảm có tồn tại phần tử nào có giá trị bằng K hay không Để giải quyết vấn đề này, ta có thể áp dụng phương pháp tìm kiếm nhị phân để kiểm tra sự hiện diện của K trong dãy.
Bằng cách áp dụng tính chất của dãy số tăng, chúng ta có thể thu hẹp phạm vi tìm kiếm sau mỗi lần so sánh khóa K với các số hạng trong dãy Để thực hiện điều này, ta chọn số hạng ở vị trí giữa của dãy để so sánh với K, trong đó vị trí giữa được tính bằng công thức Giữa = [(n+1)/2].
Khi đó xẩy ra một trong 3 trường hợp sau:
- Nếu AGiữa = K thì Giữa là chỉ số cần tìm Việc tìm kiếm kết thúc
Hiệu quả của sáng kiến
Sau khi áp dụng sáng kiến kinh nghiệm này cho đội tuyển HSG tại trường THPT Thái Hòa từ năm học 2015 đến nay đạt được kết quả như sau:
Tất cả học sinh trong đội tuyển đều nhận thức được thực trạng không thể giải quyết các bài test lớn của chương trình khi gặp các bài toán cùng dạng Đồng thời, các em đã biết vận dụng thuật toán chia để trị nhằm giải quyết bài toán hiệu quả.