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

 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”
 1 - 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
 II. 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
 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ị được minh họa như sau:
 3 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;
 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:
 1 2 3
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:
 5 move(n-1,a,c,b);
 writeln('Chuyen dia ',n,' tu vi tri ',a,' sang vi tri ',b);
 move(n-1,c,b,a);
 end;
 begin
 write('Nhap N = ');readln(n);
 move(n,1,2,3);
 readln
 end.
 Chúng ta hãy dừng lại một chút để phân tích độ phức tạp tính toán. Gọi 
T(n) là số thao tác chuyển đĩa cần thiết để chuyển xong n đĩa. Theo thuật toán 
trên ta có:
 T(n) = T(n-1) + 1 + T(n-1).
 Bằng các phương pháp giải công thức truy hồi ta có được T(n) = 2 n-1. Áp 
dụng kết quả này với giả thiết rằng mỗi cao tăng phải mất 1 giây để chuyển xong 
một đĩa từ cọc này sang cọc kia, ta thấy thời gian để chuyển toàn bộ 64 đĩa vàng 
là T(64)=216-1=18446744073709551615 giây. Như vậy ngày tận thế (nếu có) 
theo truyền thuyết phải 600 tỉ năm nữa mới đến.
 b) Cách thức thực hiện phương pháp Chia để trị trong bài toán sắp 
xếp và tìm kiếm 
 - Bài toán sắp xếp
 Bài toán: Cho dãy A gồm N số nguyên. Sắp xếp dãy A thành dãy không 
giảm.
 Bài toán sắp xếp là bài toán quen thuộc và có nhiều thuật toán để giải bài 
toán này. Các thuật toán Sắp xếp nổi bọt (Bubble Sort) hay chèn trực tiếp 
(Insertion Sort) đều có độ phức tạp cỡ O(n 2). Thuật toán sắp xếp nhanh (Quick 
Sort) hay sắp xếp trộn (Merge Sort) là hai thuật toán sắp xếp theo tư tưởng chia 
để trị. 0Với tư tưởng chia để trị, Quick Sort và Merge Sort cho ta độ phức tạp 
nhỏ hơn thường là O(nlogn). Trong đề tài này tôi chỉ tập trung nghiên cứu thuật 
toán QuickSort
 Chúng ta xét thuật toán sắp xếp nhanh (Quick Sort) 
 7 Đánh giá độ phức tạp
 Việc chọn chốt để phân đoạn quyết định hiệu quả của thuật toán, nếu chọn 
chốt không tốt rất có thể việc phân đoạn bị suy biến thành trường hợp xấu khiến 
QuickSort hoạt động chậm.
 ❖ Trường hợp tốt nhất: mỗi lần phân hoạch ta đều chọn được phần tử 
median (phần tử lớn hơn hay bằng nửa số phần tử và nhỏ hơn hay bằng nửa số 
phần tử còn lại) làm chốt. Khi đó dãy được phân đoạn thành hai phần bằng nhau, 
và ta cần log 2(n) lần phân đoạn thì sắp xếp xong. Ta cũng dễ nhận thấy trong 
mỗi lần phân đoạn ta cần duyệt qua n phần tử. Vậy độ phức tạp trong trường 
hợp tốt nhất cỡ O(nlogn).
 ❖ Trường hợp xấu nhất: mỗi lần phần đoạn ta chọn phải phần tử có giá trị 
cực đại hoặc cực tiểu làm mốc. Khi đó dãy bị phân đoạn thành hai phần không 
đều: một phần chỉ có một phần tử, phần còn lại có n-1 phần tử. Do đó, ta cần tới 
n lần phân đoạn mới sắp xếp xong. Vậy độ phức tạp trong trường hợp xấu nhất 
thuộc O(n2). Trường hợp này ít khi xẩy ra nếu việc chọn chốt là ngẫu nhiên.
Bài toán áp dụng:
 Bài 1 : Đề thi chọn đội dự tuyển học sinh giỏi quốc gia năm học 2017– 
2018 Hà Tĩnh (Bài 1- vòng 2)
 Các bến xe Buýt
 Khắc Hiếu vừa đậu đại học, cậu ra Hà Nội và gặp anh Khánh Hòa – một 
thành viên cũ của đội tuyển quốc gia môn Tin học. Hiếu muốn tìm hiểu về các 
bến xe Buýt ở Hà Nội còn Hòa thì biết rất rõ về các bến xe và số lượng xe của 
các bến xe. Hà Nội có N bến xe Buýt được đánh số từ 1 đến N, Hòa đố Hiếu: 
Hãy chọn trong N bến xe Buýt một số xe sao cho tổng số xe của 3 bến bất kỳ 
được chọn không lớn hơn tổng số xe của các bến còn lại và số lượng bến xe 
được chọn là nhiều nhất. Phần thưởng là một chuyyến dạo chơi bằng xe Buýt để 
ngắm thành phố Hà Nội. Bạn hãy giúp Hiếu.
 Dữ liệu vào: từ file văn bản BUYT.INP
 - Dòng đầu tiên ghi số N cho biết số bến xe Buýt (4≤ N≤104)
 - Dòng tiếp theo ghi N số nguyên dương A1 ... AN (Ai là số lượng xe của 
 2
 bến xe thứ i, Ai ≤ 10 ).
 Dữ liệu ra: Ghi vào file văn bản BUYT.OUT
 - Dòng duy nhất ghi số lượng bến xe được chọn.
 Các số trên một dòng ghi cách nhau bởi một dấu cách.
 Ý tưởng:
 9 if i<=j then
 begin
 tg:=a[i];
 a[i]:=a[j];
 a[j]:=tg;
 inc(i); dec(j);
 end;
 until i>j;
 if j>l then quicksort(l,j);
 if i<h then quicksort(i,h);
 end;
 procedure main;
 var i:longint;
 sum:int64;
 f:text;
 begin
 assign(f,’BUYT.out’);rewrite(f);
 sum:=0;
 for i:=1 to n do
 sum:=sum+a[i];
 i:=n;
 while i>3 do
 if (a[i]+a[i-1]+a[i-2])<=(sum shr 1) then break
 else dec(i);
 write(f,'so xe chon duoc nhieu nhat la: ',i);
 Close(f);
 end;
 BEGIN
 enter;
 quicksort(1,n);
 main;
 readln
 END.
 Bài 2. Đua ngựa
 Ở thời Xuân Thu, vua Tề và Điền Kỵ thường hay tổ chức đua ngựa từng 
cặp với nhau. Mỗi một con ngựa có một hệ số khác nhau. Trong cuộc đua, con 
ngựa nào có hệ số cao hơn thì sẽ thắng, nếu có hệ số ngang nhau thì sẽ về đích 
cùng một lúc mỗi một con ngựa chỉ được thi đấu một lượt. Ai có tổng số trận 
thắng nhiều hơn thì sẽ thắng chung cuộc. Số trận <= 1000 trận. Bạn hãy giúp 
Điền Kỵ sắp xếp các lượt đấu để đạt số trận thắng cao nhất có thể.
 Dữ liệu vào từ file DUANGUA.INP bao gồm:
 - Dòng đầu là số lượng ngựa: n 
 11