Định Hướng Giảng Dạy Thuật Toán Sắp Xếp Và Tìm Kiếm Trong Trường ...

Tải bản đầy đủ (.doc) (74 trang)

1. Trang chủ
>>
2. Giáo án - Bài giảng
>>
3. Ngữ văn

Định hướng giảng dạy thuật toán sắp xếp và tìm kiếm trong trường THPT

Bạn đang xem bản rút gọn của tài liệu. Xem và tải ngay bản đầy đủ của tài liệu tại đây (285.56 KB, 74 trang )

CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAMĐộc lập – Tự do – Hạnh phúcI. Tên sáng kiến, lĩnh vực áp dụng:- Tên sáng kiến: “Định hướng giảng dạy thuật toán sắp xếp và tìm kiếmtrong trường THPT”- Lĩnh vực áp dụng: Giảng dạy bộ môn tin học THPT, ôn luyện đội tuyển họcsinh giỏi.II. Nội dung sáng kiến:1. Giải pháp cũ thường làm:Việc tìm kiếm và sắp xếp thường là một vấn đề khó, trừu tượng đối vớimỗi học sinh khi mới bắt đầu tiếp cận tin học và lập trình. Trước đây giáo viênmỗi khi dạy đến phần tìm kiếm và sắp xếp theo cấu trúc thường cũng không hiểusâu vấn đề, dạy không rõ ràng, chiếu lệ, ví dụ áp dụng nghèo nàn không phongphú. Chủ yếu đưa ra ý tưởng ở dạng tổng quát để học sinh biết được tìm kiếm,sắp xếp là như thế nào. Dẫn đến học sinh mơ hồ, khó hiểu đối với nội dung phầnđang học, nội dung môn học. Mặt khác học sinh không chủ động tìm hiểu nộidung theo yêu cầu của giáo viên, nên hoàn toàn bị động đối với môn học.Bằng thực nghiệm với nhiều năm giảng dạy trên lớp và ôn thi học sinhgiỏi chúng tôi nhận thấy khi giảng dạy phần sắp xếp và tìm kiếm thường gặpcác vấn đề như:Thứ nhất, việc đưa thuật tìm kiếm và sắp xếp chưa phù hợp. Khi học thuậttoán là vào học kỳ I lớp 10 (Bài 4. Bài toán và thuật toán) thì đến HKII lớp 11(bài 11. Kiểu mảng) học sinh mới có bài tập để vận dụng, để tiếp cận thì họcsinh lại phải lật lại kiến thức về thuật toán đã học lớp 10 - những kiến thức họcsinh đã học khá lâu mà không phải học sinh nào cũng nhớ được, chính việc nàylàm vấn đề có thể phức tạp lên và học sinh sẽ trở nên thụ động tiếp thu thôngqua những gì giáo viên truyền đạt, không phát huy được tính chủ động, tích cựccủa mình. Trong các đợt ôn thi cho đội tuyển học sinh giỏi thì gần như giáo viênphải truyền đạt lại từ đầu, dẫn đến mất thời gian và hiệu quả đạt được thì khôngcao.Thứ hai, chưa xây dựng cụ thể hệ thống các ví dụ minh họa vận dụng vàbài tập phù hợp với tiến trình phát triển tư duy cho học sinh để học sinh có thểhiểu rõ về tìm kiếm và sắp xếp. Ngoài ví dụ mẫu trong sách giáo khoa ra thìkhông có thêm các ví dụ áp dụng cụ thể và nếu có thì học sinh cũng rất khó thựchiện và ghi nhớ vì chỉ dừng lại ở các bài toán biểu diễn dưới dạng liệt kê hoặc sơđồ khối chứ chưa thực hiện việc viết chương trình. Điều này dẫn đến học sinhhọc thụ động, không hiểu sâu kiến thức, kém linh hoạt khi vận dụng và bài tậpcụ thể. Tiến trình lên lớp cũ khi dạy về thuật toán:- Học sinh xác định bài toán- Giáo viên nêu ý tưởng- Giáo viên đưa ra thuật toán bằng liệt kê hoặc sơ đồi khối- Giáo viên mô phỏng ví dụ1Thứ ba, phần mô phỏng thuật toán để học sinh tiếp cận thuật toán mộtcách nhanh nhất thường ít được quan tâm và sử dụng. Trong tin học lớp 10 cóđưa ra việc mô phòng, tuy nhiên phần diễn đạt chưa sâu và đơn giản dẫn đến họcsinh khó thể hiểu hết được quá trình thực hiện thuật toán. Việc đi sâu vào biểudiễn thuật toán bằng sơ đồ khối hoặc liệt kê làm học sinh khó hiểu và nhàmchán.Thứ tư, không có nội dung để học sinh tham gia trong quá trình tìm hiểuthuật toán, làm mất đi tính chủ động của học sinh khi học thuật toán. Thường thìgiáo viên trình bày thuyết trình học sinh nghe giảng tiếp thu.2. Giải pháp mới cải tiến:Hiểu rõ các tồn tại của cách thức giảng dạy nói trên, nhóm chúng tôi đưara việc xây dựng tài liệu tìm hiểu về sắp xếp và tìm kiếm với cách thức tiếp cậnhoàn toàn mới nhằm khắc phục những tồn tại này, đó là:- Xây dựng kế hoạch dạy học nhà trường cho phù hợp với nội dung giảngdạy. Đưa nội dung của các thuật toán trong đó có thuật toán sắp xếp, tìm kiếmtrong bài 4 tin học 10 vào nội dung giảng dạy trong tin học 11.- Đưa ra nhiều thuật toán sắp xếp, tìm kiếm khác nhau khi ôn học sinhgiỏi. Mục đích ngoài để giải quyết các bài toán thì học sinh cũng được rèn luyệncách thức xử lý các công việc không khác nhau ngoài sắp xếp, rèn luyện được tưduy thuật toán tốt hơn.- Cung cấp cho học sinh đầy đủ kiến thức về các thuật toán tìm kiếm, sắpxếp và bổ sung một số kiến thức nâng cao. Sau mỗi thuật toán có đưa ra đánhgiá nhận xét đầy đủ để học sinh có cách nhìn tổng quan về thuật toán đang sửdụng.- Các ví dụ minh họa và bài tập được trình bày chi tiết, được sắp xếp mộtcách hợp lý, từ dễ đến khó, bài toán sau có liên hệ với bài toán trước. Đặc biệtđưa các dạng câu hỏi trắc nghiệm vào giảng dạy để luyện tập cũng như nâng caokhả năng tư duy nhanh khi tiếp cận thuật toán.- Sử dụng những kiến thức cũ để tiếp cận kiến thức mới thông qua hệthống các bài tập, có thể sử dụng kết quả của bài toán này cho bài toán kia.- Tài liệu đề cập đến nhiều dạng kiến thức khác nhau đặc biệt là các bàitoán thực tiễn. Việc làm này một mặt củng cố kiến thức cho học sinh. Mặt khácgiúp học sinh có cái nhìn chung nhất, thấy được mối liên hệ giữa tin học và thựctiễn cuộc sống.- Tài liệu cung cấp hệ thống bài tập phong phú. Điều này giúp cho họcsinh đứng trước mỗi bài toán phải biết phân tích, đánh giá, so sánh và nhận dạngđể lựa chọn phương pháp giải phù hợp nhất cho bài toán đó. Rèn luyện cho họcsinh tính chủ động, tích cực và kỹ năng vận dụng linh hoạt, sáng tạo kiến thứcđã học.Với những cải tiến trên và các kỹ thuật dạy học mới ngày nay thì việc họcsinh nghiên cứu tiếp nhận kiến thức thông qua các hệ thống câu hỏi trắc nghiệmhoặc các biểu diễn môn phỏng sẽ trở nên dễ dàng hơn rất nhiều.III. Hiệu quả kinh tế và xã hội1. Hiệu quả kinh tế2Thứ nhất, xét về mặt thời gian. Để biên soạn một chủ đề hoặc một chuyênđề dạy học thì giáo viên sẽ phải mất rất nhiều thời gian tìm kiếm, biên tập lại từcác tài liệu trên internet và các sách tham khảo. Học sinh có nhu cầu tìm kiếmbài tập để luyện thì cũng phải tìm kiếm trong nhiều tài liệu rồi hệ thống lại. Điềunày cũng sẽ mất rất nhiều thời gian. Trong khi đó, giáo viên và học sinh có thểsử dụng ngay tài liệu này để học cũng như sử dụng trong việc ôn thi học sinhgiỏi. Nếu cần thì giáo viên chỉ cần bổ sung hàng năm để có được tài liệu phongphú về bài tập cho riêng mình.Thứ hai, xét về tài chính. Để viết nên tài liệu này, không kể tài liệu sáchgiáo khoa (học sinh và giáo viên nào cũng có), giáo viên sẽ mất rất nhiều giờtruy cập internet, và nhiều giờ để nghĩ ra các bài toán. Trong khi với tài liệu này,giáo viên chỉ cần phô tô hoặc in tài liệu này với giá rẻ. Nếu tính về hiệu quả kinhtế sẽ tiết kiệm rất nhiều, vì với tài liệu này ta sẽ còn duy trì trong nhiều năm tiếptheo nữa.2. Hiệu quả xã hội:Sáng kiến là tài liệu dùng trong việc giảng dạy theo chương trình chuẩnTHPT và là tài liệu tham khảo tốt cho học sinh yêu thích với môn học lập trình,sử dụng cho quá trình ôn thi học sinh giỏi.Sáng kiến không chỉ giúp giải quyết cho vấn đề đổi mới phương pháp dạyhọc theo hướng tích cực chủ động khi giảng dạy cho học sinh về tìm kiếm vàsắp xếp nói riêng mà nó còn mở ra hướng đổi mới cho việc nghiên cứu cácchuyên đề khác để xử lý các nội dung khó của tin học 11.IV. Điều kiện và khả năng áp dụngĐể áp dụng được sáng kiến này thì mỗi nhà trường cần xây dựng một kếhoạch dạy học hợp lý, phù hợp với đối tượng học sinh mà mình giảng dạy.Qua thực nghiệm và tiến hành áp dụng trong các năm học đã qua, tài liệurất hữu ích trong công tác giảng dạy của giáo viên, đặc biệt là việc ôn luyện thihọc sinh giỏi. Đồng thời, nâng cao chất lượng giảng dạy và học tập bộ môn tinhọc 11, tạo được hứng thú học tập và góp phần bồi dưỡng năng lực tự học chohọc sinh. Vì vậy, sáng kiến có thể áp dụng rộng rãi trong nhà trường nói riêng vàtoàn tỉnh nói chung.Tài liệu này được các đồng nghiệp trong nhà trường đánh giá cao về chấtlượng nội dung và phương pháp dạy học.Chúng tôi xin cam đoan mọi thông tin nêu trong đơn là trung thực, đúngsự thật và hoàn toàn chịu trách nhiệm trước pháp luật.Gia Viễn, ngày 19 tháng 05 năm 2019Người nộp đơnXÁC NHẬN CỦA LÃNH ĐẠO(Ký và ghi rõ họ tên)ĐƠN VỊ CƠ SỞ3PHỤ LỤCPHẦN I – ĐẶT VẤN ĐỀ1. Lí do chọn sáng kiếnTrong những năm gần đây vấn đề đổi mới căn bản và toàn diện nền giáodục đã trở thành một vấn đề không chỉ riêng ngành giáo dục mà toàn xã hộiquan tâm, đổi mới để đáp ứng với nhu cầu thực tiễn xã hội ngày nay. Một trongnhững sự thay đổi đó là thay đổi phương pháp dạy học từ phương pháp dạy họctruyền thống sang phương pháp dạy học tích cực, từ người giáo viên là trungtâm của mọi hoạt động thì giờ đây với phương pháp dạy học tích cực học sinhtrở thành trung tâm của các hoạt động, từ tiếp thu thụ động sang chủ động, tưduy, sáng tạo; giáo viên chỉ là người định hướng và hỗ trợ. Đây là một phươngpháp đã được áp dụng rất thành công ở rất nhiều nước tiên tiến trên thế giới. Đểlàm được điều này người thầy cần phải thiết kế những bài giảng, những chuyênđề cho phù hợp với nội dung kiến thức; phương pháp, phương tiện dạy học phùhợp với từng đối tượng học sinh là một điều hết sức cấp thiết. Để qua mỗi phầnhọc, tiết học học sinh thích thú với kiến thức mới, qua đó hiểu được kiến thức đãhọc trên lớp, đồng thời học sinh thấy được tầm quan trọng của vấn đề và việcứng dụng của kiến thức trước hết để đáp ứng những yêu cầu của môn học, sauđó là việc ứng dụng của nó vào các công việc thực tiễn trong đời sống xã hội.Môn Tin học là một môn học mới mẻ của học sinh THPT, đặc biệt với nộidung tin học 11, với nhiều kiến thức trừu tượng chưa sát thực tế mà đối với họcsinh mới được tiếp xúc với môn lập trình sẽ cảm thấy khó tiếp thu, khó hiểu vàkhông làm được các bài tập áp dụng dẫn đến sự chán nản khi học bộ môn.Xuất phát từ thực tiễn giảng dạy tôi thấy rằng, để thay đổi điều này thì cầnphải xây dựng lại một số nội dung khó của tin học 11 sao cho phù hợp với đốitượng học sinh và tìm lại sự hứng thú với môn học cho các em học sinh. Xuấtphát từ cơ sở trên, tôi đã chọn đề tài “Định hướng giảng dạy thuật toán sắpxếp và tìm kiếm trong trường THPT”, nhằm giúp các em dễ tiếp cận các thuậttoán tìm kiếm và sắp xếp hơn, từ đó hiểu rõ được ngữ nghĩa cũng như cách sửdụng các thuật toán này phù hợp với nhiều bài toán khác nhau từ đó tiếp thu tốtnội dung bài học và làm tốt các bài tập áp dụng, cảm thấy yêu thích hơn môn tinhọc nói chung và nội dung về ngôn ngữ lập trình nói riêng.2. Mục đích của sáng kiếnNgoài việc giúp cho học sinh tiếp cận dễ dàng với các thuật toán sắp xếpvà tìm kiếm thì sáng kiến còn xây dựng hệ thống các dạng bài tập thường gặp đểôn luyện cho học sinh dự thi các kỳ thi học sinh giỏi môn tin học.3. Phạm vi nghiên cứuSáng kiến tập trung việc đổi mới trong xây dựng kế hoạch giáo dục phùhợp cũng như nghiên cứu nội dung các thuật toán tìm kiếm và sắp xếp theo4chương trình Chuẩn ở trường THPT. Bên cạnh đó cũng đề cập đến một số phầnmở rộng cũng như nâng cao của các thuật toán tìm kiếm và sắp xếp dùng trongôn thi học sinh giỏi. Cùng với đó là hệ thống ví dụ minh họa cũng như bài tập ápdụng với từng thuật toán cụ thể.4. Phương pháp nghiên cứua) Nghiên cứu lý luận: Tìm hiểu về các tài liệu đề cập đến các thuật toán tìmkiếm và sắp xếp,b) Nghiên cứu thực tiễn: Tìm hiểu về cách giảng dạy tìm kiếm và sắp xếp màgiáo viên thường làm. Phân tích và làm rõ ưu điểm, nhược điểm của từng cáchdạy để từ đó xây dựng nội dung một cách hợp lý nhằm bồi dưỡng năng lực tựhọc cho học sinh.c) Thực nghiệm sư phạm: Tiến hành thực nghiệm nhằm đánh giá tính khả thi, tínhhiệu quả và tính phổ dụng của sáng kiến. Đồng thời, cũng nhằm hoàn thiện vềmặt nội dung và lý luận trong sáng kiến.5PHẦN II - GIẢI QUYẾT VẤN ĐỀI. Cơ sở lý luận:Thuật toán sắp xếp và tìm kiếm là hai khái niệm căn bản trong bộ môn tinhọc nói chung và trong chuyên ngành lập trình nói riêng. Ngay cả trong cuộcsống hàng ngày ta vẫn thường gặp những công việc liên quan đến sắp xếp, tìmkiếm như xếp hàng tập trung cho học sinh theo thứ tự từ thấp đến cao, xếp điểmtrung bình các môn học cuối năm của một lớp theo thứ tự từ cao đến thấp; tìmnhững học sinh có học lực loại yếu, những học sinh phải thi lại… Nói một cáchtổng quát, cho một dãy đối tượng, cần sắp xếp lại vị trí các đối tượng hoặc tìmkiếm các đối tượng theo một tiêu chí nào đó.Dưới đây ta xét bài toán sắp xếp, tìm kiếm dạng đơn giản và hướng giảiquyết thông thường như sau:Bài toán 1: Cho dãy A gồm N số nguyên a1, a2,… aN. Sắp xếp các số hạng đểdãy A trở thành dãy không giảm (tức là số hạng trước không lớn hơn số hạngsau).- Xác định bài toán+ Input: Dãy A gồm N số nguyên a1, a2,… aN.+ Output: Dãy A được sắp xếp lại thành dãy không giảm.- Ý tưởng: Với mỗi cặp số hạng liền kề trong dãy, nếu số trước lớn hơn số sau tađổi vị trí của chúng cho nhau. Việc này được lặp lại cho đến khi không còn sựđổi chỗ nào xảy ra nữa.Bài toán 2: Cho dãy A gồm N số nguyên khác nhau: a 1, a2,…, aN và một sốnguyên K. Tìm xem có hay không chỉ số i (1 ≤ i ≤ N ) mà ai = K. Nếu có hãycho biết chỉ số só đó.- Xác định bài toán:+ Input: Dãy A gồm N số nguyên a1, a2,…, aN và số nguyên K.+ Output: Đưa ra chỉ số i sao cho ai=K (nếu có).- Ý tưởng: Lần lượt từ số hạng thứ nhất so sánh giá trị số hạng với K cho đếnkhi tìm được hoặc tìm hết mà không tìm được số hạng nào có giá trị bằng K.Đây là hai bài toán cơ bản mà học sinh có thể sử dụng những kiến thứcđã học trong sách giáo khoa để thực hiện.II. Cơ sở thực tiễnƯu điểm của việc sử dụng các thuật toán trong sách giáo khoa đó là dễnhớ, dễ sử dụng. Tuy nhiên nhược điểm của các thuật toán này là không áp dụngcho nhiều bài toán khác nhau, thời gian thực hiện không tối ưu với các loại dữliệu lớn, bên cạnh đó thì không kích thích được tư duy học sinh, dễ làm học sinhtiếp thu một các thụ động, gây ra sự nhàm chán khi học, khó phát triển tư duythuật toán của học sinh mà đây là một trong nội dung hết sức quan trọng vớiviệc học lập trình. Bên cạnh đó thì có quá ít bài tập về sắp xếp, tìm kiếm để học6sinh vận dụng dẫn đến học sinh hiểu về toán tìm kiếm và sắp xếp một cách rấtmơ hồ, không biết sử dụng một cách linh hoạt cho các bài toán khác nhau. Mặtkhác tôi nhận thấy giữa thuật toán được học ở lớp 10 và ngôn ngữ lập trình lớp11 chưa có sự gắn kết chặt chẽ. Các em được học về thuật toán nhưng sau gầnmột năm các em mới có thể vận dụng thuật toán đó sang một ngôn ngữ lập trìnhcụ thể. Điều đó dẫn tới việc các em quên, không nắm chắc được thuật toán, làmcho thuật toán vốn dĩ đã khó càng trở nên khó hơn nữa. Hậu quả là việc học môntin ở trường THPT đối với các em là đối phó không mang lại sự hấp dẫn mới mẻđối với một môn học mà nó là nền tảng của các công việc ngày nay.III. Các biện pháp để giải quyết vấn đề1. Xây dựng kế hoạch giảng dạy:Để học sinh có thể vận dụng các thuật toán trực tiếp vào thực tiễn thì mỗinhà trường cần thay đổi nội dung chương trình phù hợp quá trình học tập củahọc sinh. Cụ thể với bộ môn tin học của trường THPT Gia Viễn B chúng tôi đãthống nhất xây dựng nội dung chương trình tin học đó là đưa nội dung của phầnthuật toán, trong đó có thuật toán sắp xếp và tìm kiếm vào nội dung của chươngtrình tin học lớp 11 như sau:Tuầ TiếtnChương I.12345Nội dungMột số khái niệm lập trình và ngônngữ lập trình§1 Khái niệm lập trình và ngôn ngữ lập1trình§2 Các thành phần của ngôn ngữ lập2trình3§4 Bài toán và thuật toán (tiết 1)4§4 Bài toán và thuật toán (tiết 2)5§4 Bài toán và thuật toán (tiết 3)6§4 Bài toán và thuật toán (tiết 4)Chương II. Chương trình đơn giản§3 Cấu trúc chương trình§4 Một số kiểu dữ liệu chuẩn7§5 Khai báo biến§6 Phép toán, biểu thức, câu lệnh gán8(mục 1, 2, 3)§6 Phép toán, biểu thức, câu lệnh gán9( mục 4, 5, 6)§7 Các thủ tục chuẩn vào/ra đơn giản10 §8 Soạn thảo, dịch, thực hiện và hiệuchỉnh chương trình.11Bài tập và thực hành 1 ( mục a, b, c)12Bài tập và thực hành 1 ( mục d, e, f, g, h,i)67Ghi chúSách GK10PhòngmáyPhòngmáy789101112121314Chương III. Cấu trúc rẽ nhánh và lặp13 §9 Cấu trúc rẽ nhánh (mục 1, 2, 3)14 §9 Cấu trúc rẽ nhánh (mục 4)15 Bài tập16 §10 Cấu trúc lặp (mục 1)17 §10 Cấu trúc lặp (mục 2)18 §10 Cấu trúc lặp (mục 3)19 Bài tập20Bài tập và thực hành 2 ( mục a, b, c, d)21Bài tập và thực hành 2 ( mục e, f, g, h)222324252627Ôn tậpKiểm tra 1 tiếtChương IV. Kiểu dữ liệu có cấu trúc§11 Kiểu mảng (mục 1: a)§11 Kiểu mảng (mục 1: b ví dụ 1)§11 Kiểu mảng (mục 1: b ví dụ 2)Bài tập28Bài tập và thực hành 3 ( bài 1)29Bài tập và thực hành 3 ( bài 2)30Bài tập và thực hành 4 ( bài 1)31Bài tập và thực hành 4 ( bài 2)3233343536Ôn tậpÔn tậpKiểm tra học kỳ I§12 Kiểu xâu (mục 1, 2)§12 Kiểu xâu (mục 3)15161718PhòngmáyPhòngmáyPhòngmáyPhòngmáyPhòngmáyPhòngmáyNội dung phần thuật toán không dạy của tin học lớp 10 chuyển sangchuyên đề tháo lắp máy tính.2. Xây dựng nội dung giảng dạy các thuật toán:Bên cạnh việc thay đổi cấu trúc chương trình thì việc thay đổi nội dung,phương pháp giảng dạy cho phù hợp thực tiễn là một điều hết sức quan trọng.Dưới đây là nội dung mà chúng tôi thực hiện giảng dạy trong chuyên đề thuậttoán sắp xếp và tìm kiếm. Bên cạnh những thực toán trong sách giáo khoa chođối tượng học sinh lớp cơ bản là những thuật toán nâng cao để ôn luyện cho họcsinh giỏi.2.1. Bài toán đặt vấn đềTheo phương pháp dạy học tích cực để tiếp cận khái niệm sắp xếp và một8số thuật toán sắp xếp thì nên đưa ví dụ mang tính thực tiễn hoặc đơn giản đểphát huy khả năng của hiện có của học sinh.Ví dụ như ta có thể đưa ra bài toán sau cho học sinh thảo luận và đưa raphương án giải quyết:Bài toán 1: Cho dãy số A gồm 5 số: 5 3 1 2 4.Với những kiến thức đã được học, chắc chắn học sinh sẽ có đưa ra cáchthức như: So sánh lần lượt các số sau đó tìm số nhỏ nhất đặt ở đầu, sau đó vớicách làm tương tự tìm số nhỏ thứ 2,... Rồi cuối cùng là tìm được cả 5 vị trí.Sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán sắp xếp đượcbiểu diễn như sau:Lượt duyệt 1: So sánh các giá trị liền kề để đưa giá trị 1 về phía đầu dãy 5 3 1 245312453124531245132415324Lượt duyệt 2: Tiếp tục đưa giá trị 2 về phía đầu dãy 5 3 2 415324153241523412534Lượt duyệt 3: Đưa giá trị 3 về phía đầu dãy: 5 3 4125341253412354Lần duyệt 4: Đưa giá trị 4 về phía đầu dãy: 5 41235412345Sau đó giáo viên có thể đưa ra vấn đề mở rộng hơn:Bài toán 2: Cho dãy số A gồm 5000 số: a1, a2,...,a5000.Như vậy đến đây học sinh sẽ xuất hiện mâu thuẫn khó giải quyết nếu dữliệu nhỏ thì việc sắp xếp sẽ thực hiện rất đơn giản nhưng nếu dữ liệu lớn hơn thìthời gian để thực hiện sẽ rất khó kể cả sử dụng máy tính máy tính đi chăng nữa.Đến đây ta có thể đưa ra phương hướng giải quyết mâu thuẫn, đó là: lựa chọnvà sử dụng một thuật toán phù hợp để giải quyết một bài toán nào đó. Từ đó họcsinh cũng sẽ hiểu được kết luận: “Một bài toán thì có nhiều thuật toán để giải”.Dẫn dắt đến những thuật toán mới với những cách xử lý mới.2.2. Một số thuật toán sắp xếp cơ bản:Là hệ thống các dạng bài toán được trình bày theo mức độ phát triển tư9duy của học sinh. Trong mỗi thuật toán thì đều có mô phỏng ví dụ và đưa rađánh giá nhận xết cho từng thuật toán.2.2.1 Thuật toán sắp xếp nổi bọt (Bubble Sort)- Ý tưởng của thuật toán: Với mỗi cặp số hạng đứng liền kề trong dãy, nếu sốtrước lớn hơn số sau ta đổi chỗ chúng cho nhau. Việc đó được lặp đi lặp lại, chođến khi không có sự đổi chỗ nào xảy ra nữa.- Ý tưởng được mô tả cụ thể như sau:+ Lượt 1: Ta xét từ cuối dãy, nếu gặp hai phần tử kề nhau mà số đứng trước lớnhơn số đứng sau thì ta đổi chỗ chúng cho nhau. Sau lượt 1, phần tử nhỏ nhấtđược đưa về vị trí 1.+ Lượt 2: Ta xét từ cuối dãy (chỉ đến phần tử thứ 2), nếu gặp hai phần tử kề nhaumà số đứng trước lớn hơn số đứng sau thì ta đổi chỗ chúng cho nhau. Sau lượt 2,phần tử nhỏ thứ hai được đưa về vị trí 2.+ Lượt i: Ta xét từ cuối dãy (chỉ đến phần tử thứ i), nếu gặp hai phần tử kề nhaumà số đứng trước lớn hơn số đứng sau thì ta đổi chỗ chúng cho nhau. Sau lượt i,phần tử nhỏ thứ i được đưa về vị trí i.+ Xong lượt thứ n-1 thì dãy được sắp xếp xong.- Ví dụ: Cho dãy số A gồm 5 số: 5 3 1 2 4.Sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán sắp xếp nổi bọt đượcbiểu diễn như sau:Lượt duyệt 1: So sánh các giá trị liền kề để đưa giá trị 1 về phía đầu dãy 5 3 1 245312453124531245132415324Lượt duyệt 2: Tiếp tục đưa giá trị 2 về phía đầu dãy 5 3 2 415324153241523412534Lượt duyệt 3: Đưa giá trị 3 về phía đầu dãy: 5 3 4125341253412354Lần duyệt 4: Đưa giá trị 4 về phía đầu dãy: 5 41235412345- Chương trình cài đặt10Procedure BubbleSort;Var i, j: integer;tg: integer;BeginFor i:= 1 to n – 1 doFor j:= n downto i+1 doIf a[j – 1] > a[j] thenBeginTg:= a[j];a[j]:= a[j-1];a[j-1]:= tg;End;End;* Ngoài ra, còn cách cài đặt khác của thuật toán trên đó là xét từ đầu dãy vềcuối dãy hay đưa các giá trị lớn nhất về phía cuối dãy, chương trình cài đặtnhư sau:Procedure Bubble Sort;Var i, j: integer;tg: integer;BeginFor i:= 1 to n – 1 doFor j:= i+1 to n doIf a[j – 1] > a[j] thenBeginTg:= a[j];a[j]:= a[j-1];a[j-1]:= tg;End;End;Nhận xét: Tại lượt thứ i có n – i phép so sánh. Vậy số phép so sánh là:(n-1) + (n-2) + …+ 1 =n(n − 1).2Độ phức tạp của thuật toán là O(n2)2.2.2. Thuật toán sắp xếp kiểu chọn (Selection Sort)- Ý tưởng thuật toán:+ Ở lượt thứ nhất, chọn trong dãy khóa a 1, a2,…, aN ra khóa nhỏ nhất (khóa ≤mọi khóa khác) và đổi giá trị của nó với a1, khi đó giá trị khóa a1 trở thành giá trịkhóa nhỏ nhất.+ Ở lượt thứ hai, chọn trong dãy khóa a 2,…, aN ra khóa nhỏ nhất và đổi giá trịcủa nó với a2.11…+ Ở lượt thứ i, chọn trong dãy khóa a i, ai+1,…, aN ra khóa nhỏ nhất và đổi giá trịcủa nó với ai.…+ Ở lượt thứ n-1, chọn trong 2 khóa a n-1, aN ra khóa nhỏ nhất và đổi giá trị củanó với aN-1.- Ví dụ: Cho dãy số A gồm 5 số: 5 3 1 2 4.Sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán sắp xếp kiểu chọn nhưsau:Lần duyệt 1: Đổi khóa 1 cho 55312413524Lần duyệt 2: Đổi khóa 2 cho 31352412534Lần duyệt 3: Đổi khóa 3 cho 51253412354Lần duyệt 4: Đổi khóa 4 cho 51235412345- Chương trình cài đặt:Procedure SelectionSort;Var i, j, jmin, tg: integer;BeginFor i:= 1 to n-1 doBeginjmin := i;For j := i + 1 to nIf a[j] < a[jmin] then jmin:= j;If jmin i thenBegintg := a[j];a[j]:= a[jmin];a[jmin] := tg;end;end;End;Nhận xét: Tại lượt thứ i có n – i phép so sánh để tìm ra phần tử nhỏ nhất hiệnhành. Vậy số phép so sánh vẫn là:12(n-1) + (n-2) + …+ 1 =n(n − 1).2Độ phức tạp của thuật toán là O(N 2 )2.2.3. Thuật toán sắp xếp kiểu chèn (Insertion Sort)- Ý tưởng thuật toán:Xét dãy khóa a1, a2,…, aN.Ta thấy dãy con chỉ gồm mỗi một khóa a1 có thể coi là đã sắp xếp rồi.Xét thêm a2, so sánh a2 với a1, nếu thấy a2 < a1 thì chèn nó vào trước a1.Đối với a3, xét dãy gồm 2 khóa a1, a2 đã sắp xếp và tìm cách chèn a3 vào dãykhóa đó để được một thứ tự sắp xếp.Tổng quát, sắp xếp dãy a1, a2,…, ai trong điều kiện dãy ai-1 đã được sắpxếp rồi bằng cách chèn ai vào đúng vị trí dãy đó khi sắp xếp.- Ví dụ: Cho dãy số A gồm 5 số: 5 3 1 2 4.Sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán chèn được biểu diễnnhư sau:Lượt 1: Chèn 3 vào trước 553124Lượt 2: Chèn 1 vào dãy 3, 535124Lượt 3: Chèn 2 vào dãy 1, 3, 513524Lượt 4: Chèn 4 vào dãy 1, 2, 3, 512354Kết quả cuối cùng nhận được12345- Chương trình cài đặt:Var i, j: integer;tg: integer;BeginFor i:= 2 to n doBegintg := a[i];j := i – 1;while (j>0 ) and ( tg < a[j] ) dobegina[j+1] := a[j];j := j – 1;end;a[j+1] := tg;end;13end;Nhận xét:Trường hợp tốt nhất : Dãy ban đầu đã có thứ tự không cần phải vào vòng lặpwhile. Với i chạy từ 2 đến n thì số phép so sánh tổng cộng sẽ là n-1Độ phức tạp : O(n)Trường hợp xấu nhất : Dãy ban đầu có thứ tự ngượcVòng lặp while : i-1 lầnVòng lặp for: (n-1)+(n-2)+……+1=n(n − 1)2Độ phức tạp: O(n2)2.2.4. Thuật toán sắp xếp nhanh (Quick Sort).- Ý tưởng thuật toán:Sắp xếp dãy khóa a1, a2,…, aN. Có thể coi là sắp xếp đoạn chỉ số từ chỉ số1 tới chỉ số n trong dãy khóa đó. Để sắp xếp một đoạn trong dãy khóa, nếu đoạnđó ≤ 1 phần tử thì không cần phải làm gì.Nếu đoạn đó có 2 phần tử trở lên thì ta chọn một khóa ngẫu nhiên làmchốt, mọi khóa nhỏ hơn chốt thì được xếp vào vị trí trước chốt, còn mọi khóalớn hơn chốt thì được xếp vào vị trí sau chốt.Sau phép hoán chuyển như vậy thì đoạn đang xét được chia làm hai đoạnkhác rỗng mà mọi khóa trong đoạn đầu ≤ chốt, và mọi khóa trong đoạn sau đều≥ chốt.Vấn đề trở thành sắp xếp hai đoạn mới tạo ra (có độ dài ngắn hơn đoạnban đầu) bằng phương pháp tương tự.- Ví dụ: Cho dãy số A gồm 5 số: 5 3 1 2 4.Sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán sắp xếp nhanh đượcbiểu diễn như sau:(5 3 1 2 4)1 (3 5 2 4)1 (3 4 2) 51 (2) 3 (4) 512345- Chương trình cài đặt:Procedure QuickSort (L, H: longint);Var i, j: longint;x, tg: longint;Begini := L;j:= H;x := a[ (L+H) div 2 ];repeat14while a[i] < x do inc (i);while a[j] > x do dec (j);if i j;if L < j then QuickSort (L, j);if i < H then QuickSort (i, H);end;Nhận xét:Trường hợp chương trình ít gọi tới thủ tục sắp xếp và chỉ sắp xếp trên tậpdữ liệu nhỏ thì có thể sử dụng thuật toán đơn giản có độ phức tạp O(N 2) dễ càiđặt.Trường hợp sắp xếp trên tập dữ liệu lớn nên sử dụng thuật toán sắp xếpnhanh vì độ phức tạp của thuật toán là O(nlogn).2.2.5. Sắp xếp bằng đếm phân phối (Distribution Counting)- Ý tưởng thuật toánThuật toán dành cho trường hợp đặc biệt, khóa của các phần tử A 1, A2,…,AN là các số nguyên nằm trong khoảng từ 0 tới K (Tkey = 0..M).Xây dựng dãy C0, C1,…CM các biến đếm, trong đó CV là số lần xuất hiệngiá trị V trong dãy khóa.Dựa vào dãy biến đếm, ta sẽ biết được sau khi sắp xếp thì giá trị V nằm từvị trí nào tới vị trí nào. Tức là sau khi sắp xếp:+ Giá trị 0 đứng trong đoạn từ vị trí 1 tới vị trí C0+ Giá trị 1 đứng trong đoạn từ vị trí C0+1 tới vị trí C0+C1+ Giá trị 2 đứng trong đoạn từ vị trí C0+C1+1 tới vị trí C0+C1+C2…+ Giá trị v đứng trong đoạn từ vị trí C0+C1+…+Cv-1 +1 tới vị tríC0+C1+C2+…+Cv…Nếu ta tính lại dãy C như sau:For V:=1 to M do Cv := Cv-1+CvThì Cv là vị trí cuối của đoạn chứa giá trị V trong dãy khóa đã được sắpxếp.Dựng lại dãy khóa dắp xếp bằng cách thêm dãy khóa phụ X1, X2,.., Xn, sau15đó duyệt lại dãy khóa A, mỗi khi gặp khóa mang giá trị V ta đưa giá trị đó vàokhóa Xcv và giảm Cv đi 1. Và cuối cùng là gán giá trị dãy khóa X cho dãy khóaA.- Ví dụ: Cho dãy số A gồm 5 số: 6 3 6 2 4.Mô tả cách sắp xếp dãy số trên theo thứ tự tăng dần bằng thuật toán sắp xếpphân phối được biểu diễn như sau:V123456I12345Ai63624Số lần xuất hiện của V trong mảng C[a[i]]011102Vị trí của V012335Thứ tự sắp xếp trong mảng của Ai52413- Chương trình cài đặt:Procedure Sxphanphoi;VarC:array [0..M] of integer;X: Tarray;i: integer;v:Tkey;BeginFor V:=0 to M do C[v]:=0;For i:=1 to n do C[A[i]]:= C[A[i] ]+ 1;For V:=1 to M do C[v]:=C[v-1] +C[v];For i:=n downto 1 doBeginV:=A[i];X[C[v]]:=A[i];C[v]:=C[v]-1;End;A:=X;End;Nhận xét:Độ phức tạp của thuật toán là O(max(N, M)). Giá trị M càng nhỏ thì thuậttoán sắp xếp càng nhanh. Nhưng cần lưu ý là Distribution Counting Sort chỉ nênáp dụng khi ta biết rõ M, nếu M quá lớn mà N nhỏ thì nên lựa chọn các thuậttoán khác để xử lý.2.2.6. Thuật toán sắp xếp trộn (Merge Sort).- Ý tưởng:- Nếu chỉ có một phần tử trong dãy thì coi như dãy đã được sắp xếp. Ngược lại16thì chia dãy thành hai nửa cho tới khi không thể chia được nữa; sau đó kết hợpcác dãy nhỏ lại thành dãy mới đã được sắp xếp.- Ví dụ:Sắp xếp mảng A gồm các phần tử: 14 33 27 10 35 19 42 44Đầu tiên, giải thuật sắp xếp trộn chia toàn bộ mảng thành hai nửa.14 33 27 10 35 19 42 44Tiến trình chia này không làm thay đổi thứ tự các phần tử trong mảng ban đầu.Bây giờ chúng ta tiếp tục chia các mảng này thành 2 nửa.14 33 27 10 35 19 42 44Tiến hành chia tiếp cho tới khi không còn chia được nữa.14 33 27 10 35 19 42 44Tiếp theo sẽ tổ hợp chúng theo như đúng cách thức mà chúng được chia ra vớicách thức là so sánh hai phần tử trong mỗi dãy và sau đó tổ hợp chúng vàotrong một dãy khác theo cách thức đã được sắp xếp.14 33 10 27 19 35 42 44Tiếp tục kết hợp từng cặp dãy một ở trên.10 14 27 33 19 35 42 44Sau bước kết hợp cuối cùng ta sẽ được kết quả:10 14 19 27 33 35 42 44- Chương trình:procedure mergesort(1,r: integer);var i, j, k, m : integer;beginif r-1>0 thenbeginm:=(r+1) div 2; mergesort(1,m); mergesort(m+1,r);for i := m downto 1 do b[i] := a[j];for j :=m+1 to r do b[r+m+1-j] := a[j];for k :=1 to r doif b[i] < b[j] thenbegin a[k] := b[i] ; i := i+1 endelse begin a[k] := b[j]; j:= j-1 end;end;end;Nhận xét:Ta thấy ngay số lần lặp của bước 2 (phân phối) và bước 3 (trộn) bằnglog2n. Ta cũng thấy rằng chi phí thực hiện bước 2 và bước 3 tỉ lệ thuận với n.Như vậy, ta có thể ước tính độ phức tạp của thuật toán Merge Sort thuộcO(nlog2n)2.3. Một số thuật toán tìm kiếm cơ bản.17Trong ngành khoa học máy tính, một giải thuật tìm kiếm là một thuật toánlấy đầu vào là một bài toán và trả về kết quả là một lời giải cho bài toán đó,thường là sau khi cân nhắc giữa một loạt các lời giải có thể. Hầu hết các thuậttoán được nghiên cứu bởi các nhà khoa học máy tính để giải quyết các bài toánđều là các thuật toán tìm kiếm. Dưới đây là bài toán dạng đơn giản để chúng tacó thể hiểu rõ hơn về các thuật toán tìm kiếm.- Bài toán: Cho dãy A gồm N số nguyên khác nhau: a 1, a2,…, aN và một sốnguyên K. Cần biết có hay không chỉ số i (1 ≤ i ≤ N ) mà ai = k. Nếu có hãy chobiết chỉ số só đó.- Xác định bài toán:- Input: Dãy A gồm N số nguyên a1, a2,…, aN và số nguyên K.- Output: Đưa ra chỉ số i sao cho ai=k (nếu có).2.3.1. Thuật toán tìm kiếm tuần tự (Sequential Search)- Ý tưởng thuật toán:Tìm kiếm tuần tự được thực hiện một cách tự nhiên. Lần lượt từ số hạngthứ nhất, ta so sánh giá trị số hạng đang xét với khoá cho đến khi hoặc gặp mộtsố hạng bằng khoá hoặc dãy đã được xét hết và không có giá trị nào bằng khoá.Trong trường hợp thứ hai dãy A không có số hạng nào bằng khoá.- Ví dụ: Cho dãy số A gồm các phần tử: 4 5 6 9 2 1 và số k=9, thuật toán tìmkiếm tuần tự mô tả bằng bảng sau:I123456A[i]456921A[i]=k?SaiSaiSaiSaiĐúngThuật toán tìm kiếm tuần tự sẽ duyệt tuần tự từ phần đầu đến khi tìm thấyphần tử có giá trị bằng k thì dừng lại, như ví dụ trên ta sẽ tìm được i=5.- Chương trình cài đặt:Procedure Tktuantu;Var i: integer;Begini:=1;While(i a[j] thenBeginTg:= a[j];a[j]:= a[j-1];a[j-1]:= tg;End;End;20beginWrite('n,k='); readln(n,k);For i:=1 to n dobeginWrite('a[',i,']='); readln(a[i]);End;BubbleSort;Write('phan tu nho thu k la:',a[k]);readln;End.Tuy nhiên, nếu N lớn (N>5000) thì vận dụng thuật toán sắp xếp nổi bọt sẽmất rất nhiều thời gian để chạy chương trình, do đó thuật toán này chỉ áp dụngvới dữ liệu nhỏ.Với dữ liệu lớn (N>5000) ta có thể vận dụng thuật toán sắp xếp nhanh:+ Nếu K < L ≤ H thì không cần sắp xếp đoạn từ L đến H vì không ảnh hưởngđến vị trí thứ K.+ Nếu L ≤ H < K thì cũng không cần sắp xếp đoạn từ L đến H vì không ảnhhưởng đến vị trí thứ K+ Nếu L ≤ K ≤ H thì ta sẽ thực hiện việc sắp xếp.Sau khi sắp xếp thì số đứng thứ K chính là số nhỏ thứ K.Program mink;Var a:array[1..100] of integer;i,j,n,k:longint;Procedure QuickSort (L, H: longint);Var i, j: longint;x, tg: longint;BeginIf (L<=k) and (H>=k) thenBegini := L;j:= H;x := a[ (L+H) div 2 ];repeatwhile a[i] < x do inc (i);while a[j] > x do dec (j);if i j;if L < j then QuickSort (L, j);if i < H then QuickSort (i, H);end;end;beginWrite ('n, k='); readln(n,k);For i:=1 to n dobeginWrite('a[',i,']='); readln(a[i]);End;QuickSort(1,N);Write ('phan tu nho thu k la:',a[k]);readln;End.* Nhận xét: Qua ví dụ trên chúng ta thấy thuật toán sắp xếp không đơn thuầnchỉ dùng để sắp xếp mà còn dùng để giải quyết các bài toán khác nữa. Việc quantrọng là chúng ta phải hiểu được ý tưởng thuật toán và dựa vào ý tưởng đó vậndụng vào từng bài toán cụ thể.Ví dụ 2: Cho mảng số nguyên gồm N phần tử dương: a1, a2, …, aN (ai