1
SỞ GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN
TRƯỜNG THPT THÁI HÒA
SÁNG KIẾN KINH NGHIỆM
SỬ DỤNG PHƯƠNG PHÁP CHIA ĐỂ TRỊ ĐỂ GIẢI
MỘT SỐ BÀI TOÁN
Lĩnh vực : Tin học
Tên tác giả : Châu Đức Vinh
Tổ : Toán Tin
Điện thoại : 0942 910 226
Năm học: 2020- 2021
2
A. PHẦN MỞ ĐẦU
I. Lí do chọn đề tài
Hiện nay tài liệu dạng chuyên đề nâng cao phục vụ cho việc bồi dưỡng học
sinh giỏi môn Tin học là chưa thật sự đầy đủ và tổng quát, đặc biệt là những
chuyên đề khá mới và rất khó, giờ đã được đưa vào các đề thi học sinh giỏi tỉnh
như: Chia để trị, Quy hoạch động, …
Từ thực tiễn giảng dạy tin tại trường THPT tôi thấy rằng để đạt hiệu quả cao
trong bồi dưỡng học sinh giỏi, cần có cách thiết kế bài giảng cho phù hợp với nội
dung kiến thức dựa trên tài liệu chuyên đề đầy đủ rõ ràng từ lý thuyết đến bài
tập và theo đúng xu thế chung của các kì thi học sinh giỏi các cấp hiện nay và
trong tương lai, để mang lại thành tích cao cho đội tuyển học sinh giỏi trong các kì
thi.
Xuất phát từ cơ sở trên, tôi đã 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 sẽ giúp học sinh của trường THPT Thái
Hòa vận dụng các kiến thức vào làm tốt các dạng đề thi học sinh giỏi tỉnh có liên
quan đến phương pháp chia để trị, phục vụ cho việc bồi dưỡng học sinh giỏi của
trường.
II. 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 ra nguồn tài liệu tham khảo về phương pháp cũng như thuật toán nhằm
hỗ trợ cho học sinh, giáo viên dạy bồi dưỡng học sinh giỏi tin học.
III. Đối tượng và phạm vi nghiên cứu
1. Đối tượng 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
2. Phạm vi nghiên cứu
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.
IV. 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ị.
3
- 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ả.
B. NỘI DUNG SÁNG KIẾN KINH NGHIỆM
I. Cơ sở lý luận:
- Cách tiếp cận về tri thức mới, hiện đại của học sinh trong trường THPT ở
một số trường thuộc trung du miền núi nói chung trong đó có THPT Thái Hòa nói
riêng là rất khó khăn vì: Thứ nhất là thiếu tài liệu chuyên sâu về bồi dưỡng học
sinh giỏi, thứ hai các em hầu như chưa quan tâm lắm đến lập trình bởi lẽ nó khó.
- Vì vậy tôi đã tham khảo tài liệu để viết đề tài về phương pháp chia để trị từ
lý thuyết đến thuật toán và có một số bài toán cho các em vận dụng để thực hành
trên máy tính. Từ đó các em làm tốt các đề bài có dạng tương tự trong các kì thi
chọn học sinh giỏi tin học.
II. Nội dung và giải pháp thực hiện
1. Khái niệm:
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. Sơ đồ chung:
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 bước này thì bài toán ban đầu sẽ được chia thành các bài toán con cho
đến khi không thể chia nhỏ được nữa. Các bài toán con sẽ trở thành 1 bước nhỏ
trong việc 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
4
Khi đã giải quyết xong cái bài toán nhỏ, lặp lại các bước giải quyết đó và kết
hợp lại những lời giải đó để suy ra kết quả cần tìm (có thể dạng đệ quy).
3. Thuật toán β:
Giả sử chúng ta có thuật toán α để giải bài toán kích thước dữ liệu vào n với
thời gian bị chặn bởi cn2 (c: hằng số). Xét thuật giải β để giải bài toán bằng cách:
- 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ô).
Gọi:
T α(n)= thời gian của thuật toán α.
T β(n)= thời gian của thuật toán β
Ta có:
T α(n)= cn2 (theo giả thuyết)
T β(n)= 3. T α(n/2) + dn = ¾.cn2 + dn.
Nếu:
dn < c.n2/4 hay n > 4.d/c thì thuật toán β nhanh hơn thuật toán α. Do 4.d/c là
hằng số nên với n đủ lớn ta luôn có n > 4.d/c.
Điều đó cho thấy việc sử dụng thuật toán β để giải bài toán đặt ra bằng cách
chia nó thành các bài toán con có kích thước càng ngày càng nhỏ đến khi thu được
bài toán con kích thước n0 < 4.d/c sẽ thu được hiệu quả cao.
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
Begin
If (A đủ nhỏ) then Solve(A)
Else
Begin
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;
5
1 2 3
End;
End;
Chúng ta sẽ nghiên cứu bài toán Tháp Hà nội, là một bài toán điển hình
được giải bằng phương pháp chia để trị để thấy được 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 có đường kính khác nhau được đặt chồng lên nhau theo thứ tự
giảm dần của đường kính tính từ dưới lên. Có ba vị trí có thể đặt các đĩa đánh số 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.
Tại một vị trí, đĩa nào mới chuyển đến sẽ phải đặt lên trên cùng. Đĩa
lớn hơn không bao giờ được phép đặt lên trên đĩa nhỏ hơn (hay nói cách khác:
một đĩa chỉ được đặt trên mặt đất hoặc đặt trên một đĩa lớn hơn)
Bài toán này có nguồn gốc là một truyền thuyết của Ấn độ rằng có một
nhóm cao tăng Ấn độ giáo được giao trọng trách chuyển dần 64 đĩa vàng giữa 3
cọc kim cương theo các điều kiện đã nói ở phần trên. Khi nào hoàn tất công việc,
tức là khi chuyển xong toàn bộ 64 đĩa từ vị trí ban đầu sang vị trí kết thúc thì cũng
là thời điểm 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.
Chú ý rằng bài toán 1 và 3 tương tự như bài toán ban đầu, chỉ khác là kích
thước nhỏ hơn. Chúng cũng sẽ được giải bằng phương pháp “chia để trị” giống