Tài liệu Sử dụng phương pháp dạy học tích cực vào dạy thuật toán trong ngôn ngữ lập trình pascal nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi tin học thpt.

SỞ GIÁO DỤC VÀ ĐÀO TẠO VĨNH PHÚC TRƯỜNG THPT TAM ĐẢO =====***===== BÁO CÁO KẾT QUẢ NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN Tên sáng kiến: Sử dụng phương pháp dạy học tích cực vào dạy thuật toán trong ngôn ngữ lập trình Pascal nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi tin học THPT. Tác giả sáng kiến: Nguyễn Thị Dung * Mã sáng kiến: 10.62.01 Vĩnh Phúc tháng 2, năm 2020 1 SỞ GIÁO DỤC VÀ ĐÀO TẠO VĨNH PHÚC TRƯỜNG THPT TAM ĐẢO Các từ viết tắt=====***=====Ý nghĩa THCS Trung học cơ sở THPT Trung học phổ thông HSG Học sinh giỏi QHĐ QHĐ BÁO CÁO KẾT QUẢ NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN Tên sáng kiến: Sử dụng phương pháp dạy học tích cực vào dạy thuật toán trong ngôn ngữ lập trình Pascal nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi tin học THPT. Tác giả sáng kiến: Nguyễn Thị Dung * Mã sáng kiến: 10.62.01 Vĩnh Phúc tháng 2, năm 2020 2 MỤC LỤC NỘI DUNG 1. Lời giới thiệu TRANG 1 1.1. Lí do chọn đề tài 1.2. Mục tiêu đề tài 2. Tên sáng kiến 3. Tác giả sáng kiến 4. Chủ đầu tư tạo ra sáng kiến 5. Lĩnh vực áp dụng sáng kiến 6. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử 7. Mô tả bản chất của sáng kiến 7.1 Nội dung sáng kiến 7.1.1. Mục đích nghiên cứu 7.1.2. Nhiệm vụ nghiên cứu 7.1.3 Đối tượng nghiên cứu 1 2 2 2 3 3 3 3 3 3 3 4 7.1.4. Phạm vi nghiên cứu 4 7.1.5 Nội dung sáng kiến kinh nghiệm 4 7.1.5.1. Giới thiệu về PPDH tích cực 4 7.1.5.2. Nội dung dạy thuật toán bằng PPDH tích cực 5 7.1.5.3. Nội dung kiến thức 7.1.5.3.1. Các thuật toán về số học 7 7 7.1.5.3.2. Thuật toán QHĐ điển hình 10 7.1.5.4. Quy trình thực hiện dạy học theo PPDH tích cực 16 7.1.5.4.1. Các thuật toán về số học 16 7.1.5.4.2. Thuật toán QHĐ điển hình 7.2 Về khả năng áp dụng của sáng kiến 8. Những thông tin cần được bảo mật 9. Các điều kiện cần thiết để áp dụng sáng kiến 10. Đánh giá lợi ích thu được sau khi áp dụng sáng kiến 10.1. Đánh giá lợi ích thu được theo ý kiến của tác giả 10.2. Đánh giá lợi ích thu được theo ý kiến của tổ chức, cá nhân 11. Danh sách những tổ chức/cá nhân đã tham gia áp dụng thử sáng kiến 23 28 29 29 29 29 30 33 PHỤ LỤC TÀI LIỆU THAM KHẢO 3 DANH MỤC CÁC TỪ VIẾT TẮT SỬ DỤNG TRONG SÁNG KIẾN Các từ viết tắt Ý nghĩa THCS Trung học cơ sở THPT Trung học phổ thông PPDH Phương pháp dạy học HSG Học sinh giỏi QHĐ Quy hoạch động 4 BÁO CÁO KẾT QUẢ NGHIÊN CỨU, ỨNG DỤNG SÁNG KIẾN 1. Lời giới thiệu 1.1 Lý do chọn đề tài Kỳ thi chọn học sinh giỏi Trung học phổ thông cấp tỉnh là kỳ thi chọn HSG dành cho học sinh cấp trung học phổ thông do Sở Giáo dục và Đào tạo Vĩnh Phúc tổ chức vào tháng 12 với khối 12 và tháng 4 dành cho khối 10,11 hàng năm. Kỳ thi này có ý nghĩa rất quan trọng trong việc đánh giá chất lượng học tập giữa học sinh trong tỉnh. Công tác bồi dưỡng HSG là một nhiệm vụ quan trọng trong việc nâng cao chất lượng giáo dục. Trong quá trình giảng dạy bồi dưỡng HSG của trường, ngoài phương pháp truyền thống như kỹ thuật đặt câu hỏi trong đàm thoại, tôi cũng đã thử qua rất nhiều PPDH như dạy học tích hợp để cho học sinh hứng thú. Bản thân tôi cũng đã sử dụng vào dạy học kết hợp với các PPDH đổi mới, phát huy tính tích cực, sáng tạo của người học. Nhận thấy học sinh hào hứng tham gia, tích cực, làm việc nhóm và trao đổi với giáo viên, những giờ học bồi dưỡng học sinh sôi nổi và hào hứng hơn. Trong giảng dạy bồi dưỡng HSG theo phân phối và kế hoạch chương trình của nhà trường. Trong bậc THPT môn lập trình được sử dụng phổ biến là ngôn ngữ Pascal với hệ thống lập trình Free Pascal. Việc trang bị cho học sinh năng khiếu, phục vụ cho kì thi tin học là vấn đề xem xét và xử lý. Để việc học có hiệu quả và chất lượng cho môn thi các em tham gia, ngoài kiến thức cơ bản của lập trình, các em muốn giải quyết các bài toán khó và đạt kết quả tốt trong các kì thi thì các em cần được ôn luyện kiến thức thuật toán kĩ và bài bản. Thuật toán là nội dung kiến thức quan trọng giành cho cả ba khối học bồi dưỡng HSG ở trường. Nếu học sinh tham gia học bồi dưỡng HSG thì học sinh nhất định phải biết thuật toán từ cơ bản cho đến thuật toán kinh điển. Với thuật toán số học thì trong các đề thi không thể thiếu, và gần một nửa các bài thi trong các cuộc thi HSG môn Tin THPT cần đến QHĐ. Tất nhiên, có những cách khác để giải bài toán đó. Nhưng vì các cuộc thi HSG đều có giới hạn về thời gian, cũng như bộ nhớ của chương trình, nên một thuật toán hiệu quả là cực kỳ cần thiết. Và trong những trường hợp như vậy, QHĐ là một trong những thuật toán xuất hiện nhiều nhất. Thuật toán QHĐ được ưa chuộng bởi vì ban đầu, bài toán có muôn hình vạn trạng và học sinh suy nghĩ rất nhiều mới tìm ra được lời giải. Không có một công thức chuẩn mực nào áp dụng được cho mọi bài toán. Bởi vì sự phổ biến của nó, học sinh bắt buộc phải cực kỳ thuần thục thuật toán này nếu muốn có kết quả tốt trong các cuộc thi. Bám sát đề thi và nội dung chương trình ôn bồi dưỡng HSG tôi thấy được tầm quan trọng của nội dung này đối với học sinh khi học và phù hợp khi dùng PPDH tích cực nên tôi đã thiết kế hình thành kĩ thuật dạy học và chọn phương pháp này vào thử nghiệm dạy học làm phương pháp đổi mới trong giảng dạy để góp phần nâng cao hiệu quả chất lượng HSG. 5 Với những yêu cầu đổi mới giáo dục hiện nay, công tác bồi dưỡng HSG cũng có thêm nhiều nhiệm vụ nặng nề hơn về chất lượng. Trên cơ sở tự đổi mới, các nhà trường chủ động thay đổi các PPDH tích cực, phương thức và nội dung đào tạo HSG từ học cái gì sang học như thế nào và học để làm gì, triển khai các hoạt động dạy học tích cực, rèn luyện cho học sinh tính năng động, sáng tạo, năng lực, thay đổi hình thức bồi dưỡng từ truyền đạt sang tổ chức cho học sinh làm chuyên đề, luyện đề… Nhận thấy chất lượng công tác bồi dưỡng HSG có sự cải thiện đáng kể, số lượng giải cũng được tăng đều qua từng năm. Vì vậy tôi viết sáng kiến: “ Sử dụng phương pháp dạy học tích cực vào dạy thuật toán trong ngôn ngữ lập trình Pascal nhằm nâng cao hiệu quả bồi dưỡng học sinh giỏi tin học THPT”. Nội dung sáng kiến không thể tránh khỏi các sai sót. Tác giả mong nhận được những chia sẻ, đóng góp để sáng kiến được hoàn thiện hơn. 1.2 Mục tiêu đề tài - Dạy học theo PPDH tích cực là PPDH đổi mới vào dạy phần thuật toán trong lập trình Pascal nhằm tăng tính chủ động tìm tòi, sáng tạo, tư duy của học sinh, tích cực giải quyết vấn đề cho các bài toán góp phần nâng cao chất lượng bồi dưỡng HSG. - Nhằm hiểu rõ và nắm vững các PPDH đổi mới, áp dụng PPDH tích cực, thông qua đó tích lũy những kinh nghiệm dạy học. Đồng thời giúp học sinh không những có cách học chủ động mà còn tăng hứng thú, biết vận dụng các kiến thức đã học, kích thích được sự ham học hỏi của các em. Rèn luyện cho học sinh phát triển các kĩ năng tích cực liên quan đến nội dung học tập và cuộc sống. - Tạo sự đổi mới trong công tác bồi dưỡng HSG ở các giáo viên trong trường nhằm góp phần nâng cao chất lượng hiệu quả trong giảng dạy. - Giúp học sinh nắm chắc kiến thức từ cơ bản đến mở rộng và nâng cao. Điều này có được là do trong quá trình tìm hiểu, sáng tạo, tư duy và giải quyết vấn đề, học sinh hoàn toàn chủ động trong việc xác định những nội dung có liên quan để nghiên cứu, tìm hiểu và vận dụng. - Giúp học sinh phát triển năng lực đọc tài liệu, kĩ năng nghiên cứu kiến thức, kĩ năng giải quyết vấn đề, kĩ năng làm việc nhóm, thuyết trình, tranh luận, thương lượng… Những kĩ năng này được hình thành trong quá trình học sinh nghiên cứu, tìm tòi, vận dụng tài liệu, làm việc cùng với nhóm để giải quyết vấn đề và sau đó là trình bày báo cáo kết quả trước lớp học. Từ đó hình thành cho các em học sinh thấy đam mê, ý nghĩa và yêu thích môn học, thấy được những giá trị của hoạt động nhóm đối với bản thân. Sự thay đổi về thái độ như vậy sẽ diễn ra từng bước theo quá trình phát triển của PPDH nếu được tổ chức có hiệu quả. 2. Tên sáng kiến Sử dụng phương pháp dạy học tích cực vào dạy thuật toán trong ngôn ngữ lập trình Pascal nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi tin học THPT. 3. Tác giả sáng kiến - Họ và tên: Nguyễn Thị Dung 6 - Địa chỉ tác giả sáng kiến: Trường THPT Tam Đảo - Số điện thoại: 09777980 - Email: [email protected] 4. Chủ đầu tư tạo ra sáng kiến - Nguyễn Thị Dung - Trường THPT Tam Đảo - Vĩnh phúc. 5. Lĩnh vực áp dụng sáng kiến: - Lĩnh vực áp dụng sáng kiến: Đổi mới PPDH theo hướng phát huy năng lực, tính tích cực, hứng thú, chủ động sáng tạo và phát huy tư duy sáng tạo của học sinh. - Vấn đề sáng kiến giải quyết: Sử dụng PPDH tích cực vào dạy học nhằm tăng tính chủ động, khả năng sáng tạo để giải quyết vấn đề khi học phần “Thuật toán trong ngôn ngữ lập trình Pascal” từ đó nâng cao hiệu quả chất lượng học bồi dưỡng HSG. Qua đó học sinh nắm được những kiến thức trọng tâm của môn học, hứng thú khi học, say mê tìm tòi khi được giao nhiệm vụ, giúp học sinh tích cực, yêu thích và gắn bó học đội tuyển hơn. Và đạt kết quả cao nhất trong các kì thi HSG cấp trường và cấp tỉnh. - Giảng dạy bồi dưỡng HSG lớp 10,11,12 6. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử - Trong giảng dạy bồi dưỡng HSG tháng 09/2019 khối 12, lớp 10A1 (vượt cấp),12A1 trường THPT Tam Đảo, năm học 2019 - 2020. - Trong giảng dạy bồi dưỡng HSG tháng 09/2019 khối 12 , lớp 12A1,12A2 trường THPT A năm học 2019 - 2020. 7. Mô tả bản chất của sáng kiến 7.1 Nội dung sáng kiến 7.1.1. Mục đích nghiên cứu - Sử dụng PPDH tích cực, đưa ra những gợi mở cho một vấn đề và cùng học sinh bàn luận, tìm ra mấu chốt vấn đề cũng như những vấn đề liên quan. Thông qua những dẫn dắt sẽ kích thích học sinh tiếp tục tìm tòi và khám phá kiến thức. Nhằm tăng tính chủ động, khả năng sáng tạo, tìm tòi, tư duy của học sinh để vận dụng vào bài học khi học phần thuật toán trong lập trình Pascal môn Tin học. - Đặt vấn đề, tìm giải pháp, xây dựng thuật toán, phát hiện tình huống có vấn đề, tính toán logic, tìm giải pháp để giải quyết vấn đề, và hình thành chương trình tối ưu. 7.1.2. Nhiệm vụ nghiên cứu - Tìm hiểu cơ sở lý thuyết của PPDH tích cực. - Tìm hiểu nội dung, đặc điểm và việc dạy học phần kiến thức thuật toán trong ngôn ngữ lập trình Pascal của môn Tin - Tìm hiểu đặc điểm tâm lý học sinh học bồi dưỡng HSG 7 - Thực nghiệm sáng kiến ở trường THPT A để đánh giá tính khả thi và rút ra những bài học kinh nghiệm. - Đánh giá hiệu quả, chất lượng của giờ học bồi dưỡng HSG của trường THPT. 7.1.3. Đối tượng nghiên cứu - Sử dụng PPDH tích cực vào giảng dạy thuật toán trong lập trình Pascal - Hoạt động dạy và học bồi dưỡng HSG của giáo viên và học sinh ở trường THPT theo PPDH tích cực. 7.1.4. Phạm vi nghiên cứu Khi dạy bồi dưỡng HSG môn Tin, trong ngôn ngữ lập trình nói chung và ngôn ngữ lập trình Pascal nói riêng thì có rất nhiều thuật toán, rất phong phú và đa dạng. Tuy nhiên trong phạm vi sáng kiến kinh nghiệm này tôi chỉ trình bày một số thuật toán phạm vi nằm trong chương trình bồi dưỡng HSG cả ba khối 10,11,12 và tôi trình bày theo kế hoạch chương trình bồi dưỡng HSG khối 12 tại trường THPT Tam Đảo và tiến hành thực nghiệm ở trường THPT A trên cùng địa bàn. 7.1.5. Nội dung sáng kiến kinh nghiệm 7.1.5.1. Giới thiệu về PPDH tích cực * Tổng quan về PPDH tích cực - Phương pháp giảng dạy được gọi là tích cực nếu hội tụ được các yếu tố sau: + Thể hiện rõ vai trò của nguồn thông tin và các nguồn lực sẵn có + Thể hiện rõ được động cơ học tập của người học khi bắt đầu môn học + Thể hiện rõ bản chất và mức độ kiến thức cần huy động + Thể hiện rõ được vai trò của người học, người dạy, vai trò của các mối tương tác trong quá trình học + Thể hiện được kết quả mong đợi của người học - Đổi mới phương pháp: được hiểu là “đổi mới cách thực hiện phương pháp” - PPDH tích cực: được hiểu là “PPDH theo hướng tích cực hóa người học”; hoặc “PPDH phát huy tính tích cực của người học”. - Một số PPDH tích cực: Thảo luận nhóm (hợp tác nhóm nhỏ), quan sát, xử lý tình huống, nghiên cứu trường hợp điển hình, tổ chức trò chơi, dự án, . - Một số kĩ thuật dạy học tích cực: Động não, khăn trải bàn, trưng bày phòng tranh, công đoạn, trình bày 1 phút, hỏi chuyên gia, hoàn tất 1 nhiệm vụ, hỏi và trả lời, ... - Một số PPDH và kĩ thuật dạy tích cực khác : Nêu và giải quyết vấn đề, hỏi đáp trong giờ học , ghi ý kiến lên bảng, phỏng vấn nhanh, lựa chọn đúng sai, ... 8 - Nói đến PPDH tích cực chính là nói đến cách dạy học mà ở đó, giáo viên là người đưa ra những gợi mở cho một vấn đề và cùng học sinh bàn luận, tìm ra mấu chốt vấn đề cũng như những vấn đề liên quan. Không cho phép giáo viên truyền đạt hết kiến thức mình có đến với học sinh, mà thông qua những dẫn dắt sẽ kích thích học sinh tiếp tục tìm tòi và khám phá kiến thức đó. Phương pháp này lấy sự chủ động tìm tòi, sáng tạo, tư duy của học sinh làm nền tảng, giáo viên, chỉ là người dẫn dắt và gợi mở vấn đề. Cách dạy này đòi hỏi những giáo viên phải có bản lĩnh, vận dụng linh hoạt các PPDH, kĩ thuật dạy học tích cực tốt, chuyên môn tốt và cả sự nhiệt thành, hoạt động hết công suất trong quá trình giảng dạy. * Cách tiến hành PPDH tích cực - Dạy học thông qua hoạt động của học sinh là chủ yếu Trong tiết học, học sinh chính là đối tượng chính để khai phá kiến thức. Lấy người học là trung tâm và giáo viên có vai trò tổ chức, kiểm tra, hỗ trợ hoạt động học tập của học sinh một cách hợp lý sao cho học sinh tự chủ chiếm lĩnh tri thức. Chính vì thế, giáo viên phải làm sao đó, với những cách thức gợi mở vấn đề ở một mức độ nhất định sẽ tác động đến tư duy của học sinh, khuyến khích học sinh tìm tòi và cùng bàn luận về vấn đề đó. - Chú trọng đến phương pháp tự học Với PPDH tích cực, giáo viên sẽ chú trọng cho học sinh cách thức rèn luyện và tự học, tự tìm ra phương pháp học tốt nhất để có thể tự nắm bắt kiến thức mới. Giáo viên loại bỏ hoàn toàn suy nghĩ cầm tay chỉ việc, đọc - chép… như những cách thức giảng dạy thông thường khác. - Ưu tiên phương pháp học nhóm, tập thể Với phương pháp học tích cực, giáo viên phải biết cách chia đội, nhóm và giúp các học sinh phối hợp cùng với nhau để tìm ra phương pháp học tốt nhất. - Chốt lại kiến thức học Cuối mỗi buổi học, giáo viên sẽ cùng học sinh tổng hợp lại những kiến thức tìm hiểu được, đồng thời giải đáp những vấn đề học còn thắc mắc, cùng trao đổi và chốt lại kiến thức cho cả buổi học. 7.1.5.2. Nội dung dạy thuật toán bằng PPDH tích cực - Phần thuật toán trong ngôn ngữ lập trình Pascal môn Tin học ( Bồi dưỡng HSG tin 12). - Giáo viên lập kế hoạch tìm hiểu trước những nội dung liên quan đến phần học, đặt mục tiêu, giao nhiệm vụ cụ thể cho học sinh, cung cấp tài liệu hỗ trợ cho học sinh. - Giáo viên thiết kế các bước cho thực hiện dạy học theo PPDH tích cực, nêu những mục tiêu cụ thể giải quyết vấn đề và hướng dẫn học sinh thực hiện. - Nội dung dạy học theo PPDH tích cực : Chương trình bồi dưỡng HSG Tin 12 năm 2019 - 2020 9 Buổi Tên bài Thời lượng 2 Các thuật toán về số học 3 tiết 9 Thuật toán QHĐ điển hình 3 tiết * Mục tiêu phần thuật toán số học - Về kiến thức: + Xây dựng và trình bày thuật toán cho các bài toán kiểm tra số nguyên tố, tính tổng các chữ số của một số nguyên, tính UCLN, tính tổng các ước số của một số nguyên. +Viết chương trình cụ thể cho các bài toán. - Về kỹ năng: + Nhận biết được các thuật toán số học từ đó viết được chương trình cho các bài toán từ mức cơ bản cho tới mức vận dụng linh hoạt vào các bài toán mở rộng + Học sinh được rèn luyện các kĩ năng động não, so sánh, phân tích, kĩ năng thuyết trình, làm việc nhóm để giải quyết tình huống bài học, kĩ năng sử dụng công nghệ hiệu quả trong học tập. - Về thái độ: + Học sinh hứng thú tìm hiểu các thuật toán về số học bằng PPDH đổi mới. + Rèn luyện phẩm chất của người lập trình: cẩn thận, nghiêm túc và say mê với lập trình giải quyết bài toán đơn giản nhưng ngày một thực tế hơn. * Mục tiêu phần thuật toán QHĐ điển hình - Về kiến thức: + Xây dựng và trình bày thuật toán một số bài toán QHĐ kinh điển + Phân tích và giới thiệu mô hình, công thức thuật toán và một số gợi ý trong cài đặt ,viết chương trình cụ thể. - Về kĩ năng: + Xác định cấu trúc con tối ưu của bài toán. + Xây dựng công thức truy hồi thể hiện mối quan hệ giữa các bài toán con. + Học sinh được rèn luyện các kĩ năng động não, so sánh, phân tích, kĩ năng thuyết trình, làm việc nhóm để giải quyết tình huống bài học, kĩ năng sử dụng công nghệ hiệu quả trong học tập. - Về thái độ: + Học sinh chú ý và cẩn thận trong việc tiếp thu kiến thức mới, khó hơn để giải quyết các bài toán khó trong lập trình. 10 + Tiếp tục củng cố tư duy thuật toán và kĩ năng lập trình, kĩ năng tổ chức dữ liệu đối với các bài toán. 7.1.5.3. Nội dung kiến thức 7.1.5.3.1. Các thuật toán về số học 1. Thuật toán kiểm tra số nguyên tố Bài toán 1 : Cho 1 số nguyên dương p. Làm thế nào để biết được p có phải số nguyên tố hay không? Input: p nguyên dương Output: kết luận về tính nguyên tố của p Ý tưởng thuật toán: - p=0 hoặc p=1 thì p không phải số nguyên tố - Nếu p >1 không chia hết cho số nguyên nào trong tất cả các số từ 2 đến p thì p là số nguyên tố. Do đó ta sẽ kiểm tra tất cả các số nguyên từ 2 đến có round(sqrt(p)), nếu p không chia hết cho số nào trong đó thì p là số nguyên tố. Nếu thấy biểu thức round(sqrt(p)) khó viết thì ta có thể kiểm tra từ 2 đến p div 2. Hàm kiểm tra nguyên tố nhận vào một số nguyên p và trả lại kết quả là true (đúng) nếu p là nguyên tố và trả lại false nếu p không là số nguyên tố. Chương trình kiểm tra số nguyên tố : function ngto(p:integer):boolean; var i:integer; begin ngto:=false; if p<2 then exit; for i:=2 to trunc(sqrt(p)) do if p mod i=0 then exit; {nếu p chia hết cho i thì p không là nguyên tố => thoát luôn} ngto:=true; end; Mở rộng: Dựa trên hàm kiểm tra nguyên tố, ta có thể tìm các số nguyên tố từ 1 đến p bằng cách cho i chạy từ 1 đến p và gọi hàm kiểm tra nguyên tố với từng giá trị i. 2. Thuật toán tính tổng các chữ số của một số nguyên Bài toán 2 : Cho 1 số nguyên dương p. Tính tổng các chữ số của số nguyên p 11 Input: p nguyên dương Outphut: kết luận về tổng các chữ số của số nguyên p Ý tưởng thuật toán: - Ta chia số đó cho 10 lấy dư (mod) thì được chữ số hàng đơn vị, và lấy số đó div 10 thì sẽ được phần còn lại. Do đó sẽ chia liên tục cho đến khi không chia được nữa (số đó bằng 0), mỗi lần chia thì được một chữ số và ta cộng dồn chữ số đó vào tổng. - Hàm tính tổng chữ số nhận vào 1 số nguyên p và trả lại kết quả là tổng các chữ số của nó: function tongcs(p:integer): integer; var s : integer; begin s := 0; while p <> 0 do begin s := s + p mod 10; p := p div 10; end; tongcs := s; end; Mở rộng: Tính tích các chữ số cũng tương tự, chỉ cần chú ý ban đầu gán s là 1 và thực hiện phép nhân s với p mod 10. 3. Thuật toán EUCLIDE tính UCLN Bài toán 3 : Viết chương trình nhập vào 2 số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b. Input: a,b nguyên dương Outphut: kết luận về UCLN của 2 số a,b Ý tưởng thuật toán Euclide: là UCLN của 2 số a,b cũng là UCLN của 2 số b và a mod b, vậy ta sẽ đổi a là b, b là a mod b cho đến khi b bằng 0. Khi đó UCLN là a. Hàm UCLN nhận vào 2 số nguyên a,b và trả lại kết quả là UCLN của 2 số đó. function UCLN(a,b: integer): integer; var r : integer; 12 begin while b<>0 do begin r := a mod b; a := b; b := r; end; UCLN := a; end; Mở rộng: - Dựa trên thuật toán tính UCLN ta có thể kiểm tra được 2 số nguyên tố cùng nhau hay không. - Ngoài ra cũng có thể dùng để tối giản phân số bằng cách chia cả tử và mẫu cho UCLN. 4. Thuật toán tính tổng các ước số của một số nguyên Bài toán 4 : Viết chương trình nhập vào 1 số nguyên dương p. Tính tổng các ước số của số nguyên p Input: p nguyên dương Outphut: kết luận về tổng các ước số của số nguyên p Thuật toán của ta dựa trên ý tưởng: Để tính tổng các ước số của số p, ta cho i chạy từ 1 đến p div 2, nếu p chia hết cho số nào thì ta cộng số đó vào tổng. (Chú ý cách tính này chưa xét p cũng là ước số của p). function tongus(p : integer): integer; var i,s : integer; begin s := 0; for i := 1 to p div 2 do if p mod i = 0 then s := s + i; tongus := s; end; Mở rộng: Dựa trên thuật toán tính tổng ước số, ta có thể kiểm tra được 1 số nguyên có là số hoàn thiện không: số nguyên gọi là số hoàn thiện nếu nó bằng tổng các ước số của nó. 13 7.1.5.3.2. Thuật toán QHĐ điển hình * Kiến thức của thuật toán - Chúng ta đều biết rằng điều khó nhất để giải một bài toán QHĐ là biết rằng nó là một bài toán QHĐ và tìm được công thức QHĐ của nó. Rất khó nếu ta mò mẫm từ đầu, nhưng nếu chúng ta đưa được bài toán cần giải về một bài toán QHĐ kinh điển thì sẽ dễ dàng hơn nhiều. Do đó, tìm hiểu mô hình, công thức và cách cài đặt những bài toán QHĐ kinh điển là một việc rất cần thiết. - Để tránh tình trạng giải đi giải lại một bài toán, quy hoạch động thực hiện phương pháp lưu trữ kết quả của các bài toán con đó trên một bảng. Khi cần tìm kết quả của một bài toán con nào ta chỉ cần lấy trực tiếp từ bảng ra. Tuy nhiên, cái khó nhất để giải một bài toán QHĐ là ở chỗ, ta biết rằng nó là một bài toán QHĐ, nghĩa là cần phải xác định được cấu trúc con tối ưu (các bài toán con gối lên nhau) của bài toán đặt ra. Để giúp các em học sinh tiếp cận dễ dàng với thuật toán này, tôi đề xuất việc giải quyết thuật toán này theo 5 bước như sau: +Bước 1: Xác định cấu trúc con tối ưu của bài toán. +Bước 2: Xây dựng công thức truy hồi thể hiện mối quan hệ giữa các bài toán con. Trong các bài toán QHĐ thì nó có một tên gọi mới là công thức QHĐ. + Bước 3: Xác định trình tự tính toán như thế nào cho hợp lý? Nghĩa là: làm thế nào để trước khi giải bài toán con nào đó ta đã giải cái bài toán con nhỏ hơn nó rồi. Bước này là bước xác định đâu là bài toán con, đâu là bài toán lớn hơn. + Bước 4: Giải quyết trực tiếp các bài toán con cơ bản như thế nào? + Bước 5: Dựa trên giá trị tối ưu của các bài toán con xác định được từ công thức QHĐ tính toán, truy vết tìm ra nghiệm của bài toán ban đầu. Ở đây, bước 1 và bước 2 có mối quan hệ chặt chẽ với nhau. Để các em có thể hình dung cụ thể từng bước thực hiện như thế nào, tôi sẽ viết chi tiết nội dung giải các bài toán QHĐ cơ bản dưới đây * Một số bài toán điển hình Bài 1: Dãy con đơn điệu dài nhất Cho dãy a1,a2,..an. Hãy tìm một dãy con tăng có nhiều phần tử nhất của dãy. N=6 9 1 3 7 4 6 Các phần tử trong dãy kết quả chỉ xuất hiện 1 lần. Vì vậy phương pháp làm là ta sẽ dùng vòng For duyệt qua các phần tử ai trong dãy, khác với các bài toán của mô hình 4(đặc trưng là bài toán đổi tiền), các phần tử trong dãy có thể được chọn nhiều lần nên ta thực hiện bằng phương pháp cho giá trị cần quy đổi tăng dần từng đơn vị. 14 Thứ tự của các phần tử được chọn phải được giữ nguyên so với dãy ban đầu.Đặc trưng này có thể mất đi trong một số bài toán khác tùy vào yêu cầu cụ thể. Chẳng hạn bài Tam giác bao nhau. Công thức QHĐ Hàm mục tiêu : f = độ dài dãy con. Vì độ dài dãy con chỉ phụ thuộc vào 1 yếu tố là dãy ban đầu nên bảng phương án là bảng một chiều. Gọi L(i) là độ dài dãy con tăng dài nhất, các phần tử lấy trong miền từ a1 đến ai và phần tử cuối cùng là ai. Nhận xét với cách làm này ta đã chia 1 bài toán lớn (dãy con của n số) thành các bài toán con cùng kiểu có kích thước nhỏ hơn (dãy con của dãy i số). Vấn đề là công thức truy hồi để phối hợp kết quả của các bài toán con. Ta có công thức QHĐ để tính L(i) như sau: • L(1) = 1. (Hiển nhiên) • L(i) = max(1, L(j)+1 với mọi phần tử j: 0 L[i] then begin L[i]:= L[j] + 1; Truoc[i]:= j; end; end; end; procedure TruyVet(k: integer); begin if Truoc[k] = 0 then begin write(f, a[k]); exit; end; TruyVet(Truoc[k]); write(f, ' ', a[k]); end; procedure KetQua; 16 var i, k: integer; begin k:= 1; for i:= 2 to n do if L[i] > L[k] then k:= i; assign(f, fo); rewrite(f); writeln(f, L[k]); TruyVet(k); close(f); end; BEGIN Nhap; QHD; KetQua; END. Bài 2: Tìm mảng con liên tục có tổng lớn nhất (Bài toán mở rộng từ bài 1) N=7 -1 7 -2 -3 4 2 -3 Chúng ta sẽ tuần tự thực hiện 5 bước trên: Bước 1: Xác định cấu trúc con tối ưu của bài toán Bằng cách tiếp cận tự nhiên, chúng ta xác định được: mảng con liên tục có tổng lớn nhất cần tìm sẽ phải kết thúc tại một trong n vị trí: hoặc 1, hoặc 2,…, hoặc n. Vậy nếu ta gọi L(i) là độ dài mảng con liên tục có tổng lớn nhất lấy từ miền a1 đến ai và phần tử cuối cùng là ai thì độ dài của mảng con liên tục dài nhất là: max{L(i) với 1≤ i≤ n}. Ta đã đạt được việc xác định được cấu trúc con tối ưu cho bài toán, điều này được chứng tỏ bằng bước 2 ngay sau đây: Bước 2: Xây dựng công thức QHĐ Do mảng con liên tục lớn nhất từ a1 tới ai hoặc là chứa ai-1 hoặc là không chứa ai-1. Trường hợp không chứa ai-1 thì mảng con liên tục ñó chỉ chứa một phần tử là ai mà thôi (vì yêu cầu mảng phải liên tục). Vậy: L(i) = max{a[i], L(i-1) + a[i]} Bước 3: Xác định trình tự tính toán thế nào cho hợp lý? 17 Trường hợp đơn giản này chỉ cần tính toán theo trình tự tự nhiên. for i:= 2 to n do L[i]:= max(a[i], L[i-1] + a[i]); Bước 4: Xác định bài toán con cơ bản L[1]:= a[1]; Bước 5: Truy vết, tìm nghiệm max:= -∞; for i:= 1 to n do if L[i] > max then begin max:= L[i]; k:= i; end; i:= k; while max > 0 do begin writeln(i, a[i]); max:= max - a[i]; i:= i - 1; end; Chương trình Program ChuongTrinh; const fi = 'DAYSO1.INP'; fo = 'DAYSO1.OUT'; MAX =1000; var a: array [1..MAX] of integer; n: integer; L: array [1..MAX] of integer; f: text; procedure Nhap; 18 var i: integer; begin assign(f, fi); reset(f); readln(f, n); for i:= 1 to n do read(f, a[i]); close(f); end; procedure QHD; var i, j: integer; begin L[1]:= 1; for i:= 2 to n do begin L[i]:= 1; if a[i-1] <= a[i] then L[i]:= 1 + L[i-1]; end; end; procedure TruyVet(k: integer); var i: integer; begin for i:= k-L[k]+1 to k do write(f, ' ', a[i]); end; procedure KetQua; var i, k: integer; begin k:= 1; for i:= 2 to n do 19 if L[i] > L[k] then k:= i; assign(f, fo); rewrite(f); writeln(f, L[k]); TruyVet(k); close(f); end; BEGIN Nhap; QHD; KetQua; END. 7.1.5.4. Quy trình thực hiện dạy học theo PPDH tích cực Từ những kiến thức về mục tiêu, kĩ năng và thái độ của nội dung bài học, tôi xây dựng tiến trình PPDH theo PPDH tích cực tương ứng các tiến trình sau: 7.1.5.4.1. Các thuật toán về số học (Buổi 2 - Các thuật toán về số học. Chương trình bồi dưỡng HSG 12 năm 2019-2020) Bước 1. Tìm hiểu nội dung cần giải quyết: Giáo viên cho học sinh xem nội dung đề bài của các bài toán. Sau đó để học sinh xác định input, output, ý tưởng của bài toán. Kết thúc bước này giáo viên đưa ra câu hỏi dẫn dắt bài toán. - Bài toán 1 : Cho 1 số nguyên dương p. Làm thế nào để biết được p có phải số nguyên tố hay không? - Bài toán 2 : Cho 1 số nguyên dương p. Tính tổng các chữ số của số nguyên p - Bài toán 3 : Viết chương trình nhập vào 2 số nguyên dương a và b. Tìm ước số chung lớn nhất của a và b. - Bài toán 4 : Viết chương trình nhập vào 1 số nguyên dương p. Tính tổng các ước số của số nguyên p Bước 2. Khái quát vấn đề chính trong bài học: Từ việc đọc đề bài, ghi nhớ và làm việc với tư liệu minh họa học sinh đưa ra nội dung chính của bài học. Giáo viên đưa ra câu hỏi “ trình bày ý tưởng giải quyết cho bài toán”, để trả lời câu hỏi này học sinh sẽ tìm hiểu, động não qua các ví dụ minh họa… học sinh có thể đối chiếu với những vấn đề qua các ví dụ minh hoạ khác, so sánh, kiểm tra tính đúng đắn của thuật toán. 20