Kỹ thuật giải bài toán số học nâng cao trong bồi dưỡng học sinh giỏi cấp tỉnh môn Tin học

Nội dung tài liệu: Kỹ thuật giải bài toán số học nâng cao trong bồi dưỡng học sinh giỏi cấp tỉnh môn Tin học

1. SỞ GIÁO DỤC VÀ ĐÀO TẠO BẮC GIANG TRƯỜNG THPT CHUYÊN BẮC GIANG -------***------- SÁNG KIẾN KỸ THUẬT GIẢI BÀI TOÁN SỐ HỌC NÂNG CAO TRONG BỒI DƯỠNG HỌC SINH GIỎI CẤP TỈNH MÔN TIN HỌC Hồ sơ gồm: 1. Đơn yêu cầu công nhận sáng kiến 2. Thuyết minh mô tả giải pháp và kết quả thực hiện sáng kiến 3. Báo cáo hiệu quả áp dụng và khả năng nhân rộng của sáng kiến Nhóm tác giả: 1. Đỗ Minh Thuấn – Tổ phó chuyên môn 2. Phan Quang Hương – Giáo viên Năm học: 2024 - 2025 Bắc Giang, tháng 3 năm 2025
2. PHỤ LỤC THUYẾT MINH MÔ TẢ GIẢI PHÁP VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN.........................3 1. Tên sáng kiến: Kỹ thuật giải bài toán số học nâng cao trong bồi dưỡng học sinh giỏi. .....3 2. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: Tháng 9 năm 2024 ...................3 3. Các thông tin cần được bảo mật (Nếu có): không ..............................................................3 4. Mô tả các giải pháp cũ thường làm.....................................................................................3 5. Sự cần thiết phải áp dụng giải pháp sáng kiến....................................................................3 6. Mục đích của giải pháp sáng kiến.......................................................................................3 7. Nội dung..............................................................................................................................5 7.1. Thuyết minh giải pháp mới hoặc cải tiến.....................................................................5 7.2. Thuyết minh về phạm vi áp dụng sáng kiến ................................................................9 7.3. Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến ................................................10 PHỤ LỤC SỐ 1: MỘT SỐ BÀI TOÁN SỐ HỌC SỬ DỤNG KỸ THUẬT NÂNG CAO ............11 I. Bài toán liệt kê các số nguyên tố trong đoạn [1..N] ..........................................................11 II. Bài toán đếm các số nguyên tố.........................................................................................12 III. Bài toán tìm ước nguyên tố nhỏ nhất..............................................................................13 IV. Đếm ước..........................................................................................................................15 V. Bài toán tính tổng các ước................................................................................................18 VI. Ước số.............................................................................................................................19 PHỤ LỤC SỐ 2: MỘT SỐ BÀI TẬP SỐ HỌC SỬ DỤNG KỸ THUẬT NÂNG CAO .................21 I. Bài toán số nguyên tố đặc biệt...........................................................................................21 II. Bài toán tìm số nguyên tố lớn nhất (đề thi HSG tỉnh năm 2023).....................................23 III. Bài toán số tứ quý ...........................................................................................................26 IV. Bài toán nguyên tố (đề thi HSG tỉnh năm 2021) ............................................................28 V. Bài toán ước nguyên tố lớn nhất ......................................................................................33 VI. Bài toán số nguyên tố song sinh (đề thi HSG tỉnh năm 2024) .......................................36 PHỤ LỤC SỐ 3: MỘT SỐ BÀI TẬP SỐ HỌC KHÓ SỬ DỤNG KỸ THUẬT NÂNG CAO.......40 I. Bài toán khóa số ................................................................................................................40 II. Bài toán số DMT (Đề thi Hùng Vương 2016) .................................................................42 III. Bài toán ước chung và bội chung....................................................................................44 IV. Bài toán đoạn nguyên tố (đề thi trại hè Hùng Vương năm 2023).......................................49 V. Bài bảng nguyên tố ..........................................................................................................51 VI. Bài toán số lượng ước.....................................................................................................53 TÀI LIỆU THAM KHẢO ......................................................................................................................55 Trang 2
3. SỞ GD&ĐT BẮC GIANG CỘNG HÒA XÃ HỘI CHỦ NGHĨA VIỆT NAM TRƯỜNG THPT CHUYÊN Độc lập - Tự do - Hạnh phúc THUYẾT MINH MÔ TẢ GIẢI PHÁP VÀ KẾT QUẢ THỰC HIỆN SÁNG KIẾN 1. Tên sáng kiến: Kỹ thuật giải bài toán số học nâng cao trong bồi dưỡng học sinh giỏi cấp tỉnh môn Tin học. 2. Ngày sáng kiến được áp dụng lần đầu hoặc áp dụng thử: Tháng 9 năm 2024 3. Các thông tin cần được bảo mật (Nếu có): không 4. Mô tả các giải pháp cũ thường làm Trong những năm qua trong đề thi học sinh giỏi cấp tỉnh có các bài toán số học có cấu trúc từ cơ bản đến nâng cao. Trước đây, việc hướng dẫn học sinh giải một bài toán về dạng này các thày cô thường hướng học sinh tiếp cận bài toán bằng phương pháp sử dụng các kỹ thuật xử lí số học cơ bản, duyệt, sử dụng các công thức đơn giản để cài đặt. Với phương pháp này các em dễ cài đặt. Chương trình đơn giản, ít sai sót tuy nhiên việc thực hiện chương trình thường quá thời gian với bộ dữ liệu Dữ liệu vào lớn. Do đó phương pháp này thường chỉ phù hợp với các yêu cầu đơn giản của bài toán. Thường chỉ làm được với yêu cầu kích thước bài toán nhỏ. Những năm gần đây yêu cầu trong đề thi học sinh giỏi: đòi hỏi một thuật toán thỏa mãn được giới hạn bộ nhớ, giới hạn thời gian thực hiện thì phương pháp sử dụng các kỹ thuật cơ bản, đơn giản sẽ không được điểm tối đa. 5. Sự cần thiết phải áp dụng giải pháp sáng kiến Qua nhiều năm bồi dưỡng học sinh giỏi tin học cấp trung học phổ thông và một số cuộc thi Duyên Hải, Hùng Vương, tôi tìm hiểu nhiều tài liệu, tìm các dạng bài tập để hướng dẫn cho học sinh. Với những bài toán số học đòi hỏi kỹ thuật nâng cao học sinh gặp rất nhiều khó khăn. Cấu trúc đề thi học sinh giỏi hiện nay phân hóa học sinh bằng các thuật toán từ đơn giản đến phức tạp. Bài thi của thí sinh được chấm bằng phần mềm Themis: - Bài thi được chấm bằng các test, có so sánh thời gian chạy chương trình của các thí sinh để đánh giá. Các test của mỗi câu được chỉ rõ về số lượng, giới hạn dữ liệu, số điểm tương ứng đạt được. - Các bài toán trong đề có tỉ lệ % theo yêu cầu mức độ mục tiêu của đề. Trong một bài toán thường có phần vận dụng cao đòi hỏi học sinh phải sử dụng thuật toán tối ưu mới đảm bảo thời gian thực hiện chương trình Để đạt được điểm cao, học sinh không những phải giải hết các bài toán mà với mỗi bài toán học sinh còn cần lựa chọn được thuật toán sao cho đáp ứng hết các bộ test trong bài. Học sinh cần tiếp cận thuật toán mới có thể đạt giải cao trong kỳ thi học sinh giỏi cấp tỉnh. 6. Mục đích của giải pháp sáng kiến Các giải pháp của sáng kiến là tài liệu tham khảo rất phù hợp cho giáo viên trong bồi dưỡng học sinh giỏi. Cụ thể: Giải pháp 1: Lựa chọn các bài tập số học có sử dụng kỹ thuật nâng cao ở mức độ áp dụng trực tiếp để giúp học sinh làm quen với dạng bài tập này Giải pháp này nhằm mục đích hệ thống một số bài tập số học có sử dụng kỹ thuật nâng cao, làm tài liệu tham khảo cho giáo viên, giúp giáo viên có cái nhìn tổng quan về các dạng Trang 3
4. bài tập số học có sử dụng kỹ thuật nâng cao; đồng thời sử dụng để bồi dưỡng học sinh giỏi giúp học sinh giải các bài toán số học sử dụng kỹ thuật nâng cao. Giải pháp 2: Lựa chọn các bài tập số học sử dụng kỹ thuật nâng cao và áp dụng vào giảng dạy để củng cố, rèn luyện kỹ năng giải bài toán số học bằng sử dụng các kỹ thuật nâng cao cho học sinh. Giải pháp này nhằm mục đích củng cố, rèn kỹ năng giải các bài toán số học bằng sử dụng kỹ thuật nâng cao cho học sinh. Học sinh được thực hành, ôn luyện các bài toán cùng dạng, giúp học sinh biết phân tích bài toán, điểm khác biệt và điểm chung của bài tập tương tự với sử dụng kỹ thuật nâng cao qua đó giúp học sinh cải tiến thuật toán. Giải pháp 3: Lựa chọn các bài toán sử dụng kỹ thuật nâng cao để giải các bài toán số học khó Với mỗi bài toán có thể có nhiều cách giải khác nhau, giải pháp đưa ra một số cách giải bài toán, trong đó có ứng dụng kỹ thuật nâng cao để giải các bài toán khó giúp học sinh lựa chọn thuật toán tối ưu: Giải pháp 4: Thực nghiệm và đánh giá hiệu quả của sáng kiến khi áp dụng với một số trường THPT Đánh giá tính khả thi của giải pháp với điều kiện trường THPT Chuyên Bắc Giang, trường THPT Việt Yên 2, THPT Hiệp Hòa số 3 và THPT Tân Yên số 2. Đánh giá hiệu quả của giải pháp đối với học sinh trong việc củng cố, rèn kỹ năng giải toán số học bằng sử dụng kỹ thuật nâng cao nhằm giúp học sinh yêu thích môn học, chọn được cách tối ưu khi giải các bài toán tin học, phát triển tư duy, phẩm chất và năng lực của học sinh. Kết hợp 4 giải pháp trên, sáng kiến kinh nghiệm góp phần giúp nhận diện bài toán số học có sử dụng kỹ thuật nâng cao khi lựa chọn thuật toán tối ưu, góp phần tổng kết kinh nghiệm của bản thân, chia sẻ, giúp đỡ đồng nghiệp trong việc tìm hiểu và thực hiện bồi dưỡng học sinh giỏi đạt hiệu quả cao nhất. Trang 4
5. 7. Nội dung 7.1. Thuyết minh giải pháp mới hoặc cải tiến * Giải pháp 1: - Tên giải pháp: Lựa chọn các bài tập số học có sử dụng kỹ thuật nâng cao ở mức độ áp dụng trực tiếp để giúp học sinh làm quen với dạng bài tập này - Nội dung: Chọn một số bài tập số học có sử dụng kỹ thuật nâng cao ở mức độ áp dụng trực tiếp + Liệt kê các số nguyên tố trong đoạn [1; N]: Viết chương trình nhập vào số nguyên dương N. Liệt kê các số nguyên tố trong đoạn [1..N]; + Đếm các số nguyên tố: Viết chương trình nhập vào số nguyên dương n và n số nguyên dương A1, A2, , An. Đếm và đưa ra các số là số nguyên tố; + Tìm ước nguyên tố nhỏ nhất: Viết chương trình nhập vào số nguyên dương n. In ra n số nguyên dương A1, A2, ..., An với Ai là số nguyên tố nhỏ nhất là ước của i (qui ước A1=1); + Đếm ước: Viết chương trình nhập vào số nguyên dương N. Đếm các ước số nguyên dương của N; + Tính tổng các ước: Viết chương trình nhập vào số nguyên dương N. Tính tổng các ước số nguyên dương của N; + Ước số: Cho đoạn số nguyên . Hãy tính là số lượng các ước của tất cả các số nguyên trọng đoạn và là tổng tất cả các ước số của các số nguyên trong đoạn . - Các bước tiến hành thực hiện giải pháp: Bước 1: Thu thập tài liệu từ nhiều nguồn khác nhau. Bước 2: Lựa chọn một số bài toán số học sử dụng kỹ thuật nâng cao áp dụng trực tiếp. Bước 3: Với mỗi dạng nêu bài toán, thuật toán và cài đặt. - Kết quả khi thực hiện giải pháp: Đã lựa chọn được một số dạng bài toán số học sử dụng kỹ thuật nâng cao áp dụng trực tiếp (Chi tiết tại phụ lục số 1) * Giải pháp 2: - Tên giải pháp: Lựa chọn các bài tập số học sử dụng kỹ thuật nâng cao. - Nội dung: Với mỗi bài toán số học sử dụng kỹ thuật nâng cao, các bài tập tương tự cùng dạng được đưa ra và áp dụng giảng dạy bồi dưỡng học sinh giỏi để củng cố, rèn kỹ năng giải bài toán số học sử dụng kỹ thuật nâng cao cho học sinh nhằm nâng cao chất lượng bồi dưỡng học sinh giỏi. + Số nguyên tố đặc biệt: Số tự nhiên x là số nguyên tố đặc biệt nếu x là số nguyên tố và số được viết ngược lại của x cũng là số nguyên tố. Viết chương trình nhập vào hai số nguyên dương A, B. Đếm số nguyên tố đặc biệt trong đoạn [A; B] + Tìm số nguyên tố lớn nhất: Tìm số P trong xâu ký tự T là số nguyên tố lớn nhất. Số P là tất cả các ký tự số liên tiếp trong xâu ký tự T và không có số 0 vô nghĩa. Ví dụ trong xâu ký tự T=“aB0011cd230d124ab17” có các số P là 11, 230, 124, 17. Số nguyên tố P lớn nhất là 17; + Số tứ quý: Số tự nhiên N được gọi là số tứ quý khi N là số có đúng 4 ước số nguyên dương. Viết chương trình nhập vào hai số nguyên dương A, B. Đếm các số tứ quý trong đoạn [A;B]; + Nguyên tố: Cho số nguyên dương M. Hãy đếm số lượng các ước của M và phân tích M ra thành tích các thừa số nguyên tố; + Ước nguyên tố lớn nhất: Cho số nguyên dương N. Em hãy tìm số nguyên tố lớn nhất là ước của N; + Số nguyên tố song sinh (đề thi học sinh giỏi tỉnh năm 2024): Số tự nhiên x1 gọi là số nguyên tố song sinh nếu tồn tại số tự nhiên x2 thỏa mãn đồng thời: Trang 5
6. - Số x2 khác số x1; - Số x1 và số x2 là các số nguyên tố; - Khi viết ngược lại số x1 ta được x2 và ngược lại. Cho 2 số tự nhiên a và b. Tính tổng các số nguyên tố và đếm số lượng số nguyên tố song sinh thuộc đoạn [a, b]. - Các bước tiến hành thực hiện giải pháp: Bước 1: Thu thập tài liệu từ nhiều nguồn khác nhau. Bước 2: Lựa chọn một số bài toán số học sử dụng kỹ thuật nâng cao. Bước 3: Với mỗi dạng nêu bài toán, thuật toán và cài đặt. - Kết quả khi thực hiện giải pháp: Đã lựa chọn được một số dạng bài toán số học sử dụng kỹ thuật nâng cao (Chi tiết tại phụ lục số 2) * Giải pháp 3: - Tên giải pháp: Lựa chọn các bài toán số học khó có sử dụng kỹ thuật nâng cao. - Nội dung: Sử dụng kỹ nâng cao vào giải các bài toán số học khó. - Các bước tiến hành thực hiện giải pháp: Với mỗi bài toán, phân tích bài toán, đưa ra một số cách giải quyết bài toán đó, sau đó so sánh với việc sử dụng kỹ thuật nâng cao vào giải, đánh giá độ phức tạp thuật toán. + Khóa số; + Số DMT; + Ước chung và bội chung; + Đoạn nguyên tố (đề thi trại hè Hùng Vương năm 2023); + Bảng nguyên tố; + Số lượng ước; - Kết quả khi thực hiện giải pháp: + Sản phẩm được tạo ra từ giải pháp: Phân tích thuật toán kỹ thuật nâng cao vào giải bài toán và cài đặt (Chi tiết tại phụ lục số 3) * Giải pháp 4: - Tên giải pháp: Thực nghiệm và đánh giá hiệu quả của sáng kiến khi áp dụng với một số trường THPT - Nội dung: Áp dụng giải pháp cho công tác bồi dưỡng HSG cấp tỉnh đối với trường THPT Chuyên, Trường THPT Việt Yên 2, Trường THPT Hiệp Hòa số 3, Trường THPT Tân Yên số 2. Đánh giá kết quả thực hiện các trường trên - Các bước tiến hành thực hiện giải pháp: Bước 1: Chọn các bài toán số học sử dụng kỹ thuật nâng cao đã tiến hành trong giải pháp 1, 2 và 3. Bước 2: Giới thiệu sáng kiến đến giáo viên đang bồi dưỡng học sinh giỏi tại trường THPT: + Năm học 2024-2025: giới thiệu sáng kiến kinh nghiệm tới GV bồi dưỡng học sinh giỏi tại trường THPT Việt Yên 2. Trình độ TT Họ và tên Nơi công tác Số điện thoại Chức vụ chuyên môn 1 Nguyễn Văn Hồng THPT Việt Yên 2 0399586993 Đại học TPCM + Năm học 2024-2025: giới thiệu sáng kiến kinh nghiệm tới giáo viên bồi dưỡng học sinh giỏi tại trường THPT Hiệp Hòa 3. Trang 6
7. Trình độ TT Họ và tên Nơi công tác Số điện thoại Chức vụ chuyên môn 1 Nguyễn Thị Bình THPT Hiệp Hòa 3 0977126319 Đại học Giáo viên + Năm học 2024-2025: giới thiệu sáng kiến kinh nghiệm tới giáo viên bồi dưỡng học sinh giỏi tại trường THPT Tân Yên số 2. Trình độ TT Họ và tên Nơi công tác Số điện thoại Chức vụ chuyên môn Tổ trưởng 1 Phạm Thị Chiên THPT Tân Yên số 2 0982564538 Cử nhân Tin học chuyên môn Bước 3: Tổ chức thực hiện sáng kiến kinh nghiệm. Chọn học sinh khá, giỏi, học sinh trong đội tuyển làm bài kiểm tra trước khi thực hiện sáng kiến kinh nghiệm, sau đó lấy 1 số học sinh để tham gia bồi dưỡng nội dung trong sáng kiến kinh nghiệm, cuối cùng cho bài kiểm tra sau khi thực hiện sáng kiến kinh nghiệm gồm cả học sinh được tham gia và không tham gia bồi dưỡng nội dung sáng kiến kinh nghiệm: Kiểm tra kiến thức trước khi thực hiện sáng kiến kinh nghiệm (Bài KT 1): Thực hiện sáng kiến kinh nghiệm: triển khai dạy trong 3 tuần Kiểm tra kiến thức sau quá trình bồi dưỡng (Bài KT 2) Bước 4: Đánh giá tính khả thi của phương pháp, đánh giá hiệu quả của phương pháp. Tổ chức rút kinh nghiệm sau khi áp dụng sáng kiến. Đánh giá tính khả thi của phương pháp, đánh giá hiệu quả của phương pháp. Đối tượng học sinh tham gia bồi dưỡng sáng kiến kinh nghiệm là các học sinh có lực học khá, giỏi ở các lớp chọn và học sinh đội tuyển. Ở phần này để đánh giá hiệu quả của hệ thống bài tập tương tự các bài toán về sử dụng kỹ thuật nâng cao đã đưa ra, tác giả sử dụng kết quả kiểm tra trước khi thực hiện sáng kiến và kiểm tra sau khi thực hiện sáng kiến, đối chiếu những học sinh không tham gia bồi dưỡng sáng kiến với những học sinh có tham gia bồi dưỡng sáng kiến qua các năm học: 2024 - 2025 tại Trường THPT Chuyên Bắc Giang. Năm học 2024-2025 tại trường THPT Việt Yên 2 và THPT Hiệp Hòa số 3 và Trường THPT Tân Yên 2. Bên cạnh việc đánh giá hiệu quả sáng kiến qua cách thức kiểm tra học sinh trước và sau khi thực hiện sáng kiến còn đánh giá hiệu quả của sáng kiến qua bảng kết quả thi học sinh giỏi của các học sinh các trường đã áp dụng sáng kiến từ năm 2023 đến nay. Sau khi hoàn thành nội dung 3 giải pháp đưa ra, tôi cùng các đồng nghiệp áp dụng sáng kiến trong giảng dạy bồi dưỡng học sinh giỏi môn tin theo các bước đã trình bày để tiếp tục hoàn thiện, phát triển Sáng kiến áp dụng cho việc giảng dạy và học tập của giáo viên và học sinh tại trường THPT Chuyên Bắc Giang và một số trường THPT trong tỉnh trong những năm học tiếp theo. - Kết quả khi thực hiện giải pháp: Sau quá trình thực hiện và tổng kết, rút kinh nghiệm tác giả đã đạt được kết quả như sau: Các bảng số liệu, biểu đồ so sánh kết quả trước và sau khi thực hiện giải pháp: Trang 7
8. Bảng 1: Đối sánh kết quả trước và sau khi thực hiện sáng kiến kinh nghiệm năm học 2024-2025 Điểm Điểm Có vận TT Họ và tên học sinh Trường THPT bài KT bài KT dụng SK số 1 số 2 1 Nguyễn Đức Anh Chuyên Bắc Giang 7.5 9 2 Ngô Mạnh Cường Chuyên Bắc Giang 6.5 8.5 3 Đồng Nguyên Đức Chuyên Bắc Giang 6 8 x 4 Trần Trí Kiên Chuyên Bắc Giang 7 9 x 5 Thân Ngọc Mai Chuyên Bắc Giang 7.5 8 6 Cao Trần Kim Ngân Chuyên Bắc Giang 8 9 7 Nguyễn Thế Pháp Chuyên Bắc Giang 8 8.5 8 Thân Thị Nhân Tâm Chuyên Bắc Giang 8 8.5 x 9 Tạ Thanh Tùng Chuyên Bắc Giang 7.5 9.5 10 Nguyễn Ngọc Việt Chuyên Bắc Giang 8 8.5 11 Hoàng Hà Chuyên Bắc Giang 8 9.5 x 12 Nguyễn Minh Hiếu Chuyên Bắc Giang 7.5 9 13 Nguyễn Đắc Hưng Chuyên Bắc Giang 6.5 8.5 14 Đỗ Thành Vinh Chuyên Bắc Giang 8 9.5 x 15 Nguyễn Đình Quang Anh Chuyên Bắc Giang 6 8.5 x 16 Nguyễn Gia Huy Chuyên Bắc Giang 6 6.5 17 Nguyễn Việt Hưng Chuyên Bắc Giang 7 6 18 Mai Đan Lê Chuyên Bắc Giang 7 6.5 19 Ngô Đức Minh Chuyên Bắc Giang 6.5 7 x 20 Nguyễn Việt Phương Chuyên Bắc Giang 7.5 9 21 Nguyễn Nhật Minh THPT Việt Yên 2 6.5 9 x 22 Hoàng Quốc Tiến THPT Việt Yên 2 6 8 x 23 Thân Ngọc Tâm THPT Việt Yên 2 7 7.5 24 Lê Minh Vũ THPT Hiệp Hòa 3 7.5 9.5 x 25 Tạ Văn Ninh THPT Hiệp Hòa 3 7 9 x 26 Nguyễn Đăng Tuân THPT Hiệp Hòa 3 7 7.5 27 Thạch Bảo Khánh THPT Tân Yên 2 5 6.5 x 28 Trần Tiến Minh THPT Tân Yên 2 6.5 7 x 29 Nguyễn Tiến Hợi THPT Tân Yên 2 6 8 (ghi chú “x”: là học sinh tham gia bồi dưỡng sáng kiến - nhóm đối chứng) Các em học tại các trường THPT không chuyên được áp dụng sáng kiến đã đạt thành tích tốt như em Lê Minh Vũ, Tạ Văn Ninh, Nguyễn Nhật Minh, Trang 8
9. Bảng 2: Bảng kết quả của các em học sinh trong các kì thi chọn HSG các cấp sau khi thực hiện sáng kiến kinh nghiệm năm học 2023-2024 TT Họ và tên học sinh Trường THPT Điểm Giải Ghi chú 1 Tạ Thanh Tùng Chuyên Bắc Giang 19.10 Nhất 2 Hoàng Hà Chuyên Bắc Giang 18.60 Nhì 3 Đỗ Thành Vinh Chuyên Bắc Giang 18.00 Nhì 4 Nguyễn Đình Quang Anh Chuyên Bắc Giang 16.30 Ba 5 Đồng Nguyên Đức Chuyên Bắc Giang 16.00 Ba 6 Trần Trí Kiên Chuyên Bắc Giang 16.00 Ba 8 Nguyễn Đắc Hưng Chuyên Bắc Giang 15.40 KK 9 Nguyễn Minh Hiếu Chuyên Bắc Giang 14.48 KK 10 Ngô Mạnh Cường Chuyên Bắc Giang 14.5 KK 11 Nguyễn Nhật Minh THPT Việt Yên 2 15.80 Nhì 12 Hoàng Quốc Tiến THPT Việt Yên 2 14.00 Ba 13 Thân Ngọc Tâm THPT Việt Yên 2 12.40 Ba 14 Lê Minh Vũ THPT Hiệp Hòa 3 20.00 Nhất 15 Tạ Văn Ninh THPT Hiệp Hòa 3 18.90 Nhất 16 Nguyễn Đăng Tuân THPT Hiệp Hòa 3 13.00 Ba 17 Thạch Bảo Khánh THPT Tân Yên 2 11.00 KK 18 Trần Tiến Minh THPT Tân Yên 2 8.80 KK 19 Nguyễn Tiến Hợi THPT Tân Yên 2 8.40 KK 7.2. Thuyết minh về phạm vi áp dụng sáng kiến - Sáng kiến đã được áp dụng trong giảng dạy bồi dưỡng học sinh giỏi trong năm 2024- 2025 (Kết quả 1 giải nhất, 2 giải nhì, 3 giải ba và 4 giải khuyến khích), cho trường THPT Chuyên Bắc Giang. - Năm học 2024-2025: áp dụng giảng dạy bồi dưỡng học sinh giỏi cho trường THPT Việt Yên 2, kết quả được 1 giải Ba. - Năm học 2024-2025: áp dụng giảng dạy bồi dưỡng học sinh giỏi cho trường THPT Hiệp Hòa 3 kết quả 3 học sinh đi thi được 2 giải nhất và 1 giải ba. - Năm học 2024-2025: áp dụng giảng dạy bồi dưỡng học sinh giỏi cho trường THPT Tân Yên 2 kết quả 3 học sinh đi thi được 3 giải khuyến kích. Trang 9
10. 7.3. Thuyết minh về lợi ích kinh tế, xã hội của sáng kiến -Về lợi ích kinh tế: Tiết kiệm thời gian, công sức của giáo viên khi dạy chuyên đề số học nâng cao trong bồi dưỡng học sinh giỏi. Giải pháp trong sáng kiến kinh nghiệm có thể tiếp tục xây dựng mở rộng các dạng bài tương tự của các ứng dụng như duyệt nâng cao, quy hoạch động để thành tư liệu tham khảo cho giáo viên, tự nghiên cứu, xây dựng của những năm học sau. Qua đó tiết kiệm được các chi phí khác như: chi phí đi lại, mua tài liệu tham khảo, - Về lợi ích xã hội: Sáng kiến kinh nghiệm này là tài liệu tham khảo hữu ích, giúp giáo viên nâng cao năng lực chuyên môn, đóng góp hiệu quả cho công tác giảng dạy mũi nhọn bồi dưỡng học sinh giỏi ở trường phổ thông, đồng thời góp phần định hướng phát triển năng lực tư duy, năng lực tự học cho học sinh, giúp học sinh nhận diện được bài toán số học sử dụng kỹ thuật nâng cao. * Cam kết: Chúng tôi xin cam đoan những điều khai trên là trung thực, đúng sự thật và không sao chép hoặc vi phạm bản quyền. Trên đây chỉ là một vài kinh nghiệm của chúng tôi. Chúng tôi rất mong nhận được sự đóng góp của Hội đồng sáng kiến cấp cơ sở và các thầy cô đồng nghiệp, để giải pháp của chúng tôi có hiệu quả hơn trong những năm dạy học tiếp theo! XÁC NHẬN CỦA TÁC GIẢ SÁNG KIẾN TRƯỜNG THPT CHUYÊN BẮC GIANG Đỗ Minh Thuấn Phan Quang Hương Trang 10
11. PHỤ LỤC SỐ 1: MỘT SỐ BÀI TOÁN SỐ HỌC SỬ DỤNG KỸ THUẬT NÂNG CAO ÁP DỤNG TRỰC TIẾP I. Bài toán liệt kê các số nguyên tố trong đoạn [1..N] 1. Phát biểu bài toán Viết chương trình nhập vào số nguyên dương N. Liệt kê các số nguyên tố trong đoạn [1..N]. * Dữ liệu vào: đọc vào từ file văn bản SANGNT.INP gồm một số nguyên dương N (N 106) * Kết quả ra: ghi ra file văn bản SANGNT.OUT gồm nhiều dòng, mỗi dòng ghi 1 số nguyên tố trong đoạn [1..N] * Ví dụ: SANGNT.INP SANGNT.OUT 15 2 3 5 7 11 13 2. Thuật toán * Thuật toán 1: - Viết hàm kiểm tra số nguyên tố; - Duyệt các số k từ 1 đến N, với mỗi số k kiểm tra nếu k là số nguyên tố thì đưa ra số k * Thuật toán 2: - Viết hàm sàng nguyên tố, lọc ra các số nguyên tố trong đoạn [1..N]; - Với mỗi số k kiểm tra nếu d[k]=1 (k là số nguyên tố) đưa ra k. * Đánh giá: - Với thuật toán 1 độ phức tạp thuật toán là O(N*| |) nên bị quá thời gian với N lớn khoảng 106 - Với thuật toán 2 độ phức tạp thuật toán là O(NlgN) nên không bị quá thời gian. Sử dụng kỹ thuật nâng cao sàng nguyên tố để kiểm tra số nguyên tố với độ phức tạp thuật toán là O(1). 3. Cài đặt #include const int nmax=1000005; using namespace std; int d[nmax],n,a[nmax],dem=0; void sangnt(int k) { int i,j; d[1]=0; for(i=2;i*i<=k;i++){ if(d[i]==1){ j=i*i; Trang 11
12. while(j<=k) {d[j]=0; j+=i;} } } } int main() { freopen("SANGNT.INP","r",stdin); freopen("SANGNT.OUT","w",stdout); cin>>n; for(int i=1;i<=1000001;i++) d[i]=1; sangnt(1000001); for(int i=1;i<=n;i++) if(d[i]==1) cout<<i<<endl; return 0; } II. Bài toán đếm các số nguyên tố 1. Phát biểu bài toán Viết chương trình nhập vào số nguyên dương n và n số nguyên dương A 1, A2, , An. Đếm và đưa ra các số là số nguyên tố. * Dữ liệu vào: đọc vào từ file văn bản COUNTNT.INP gồm - Dòng 1: ghi số nguyên dương n≤106; 6 - Dòng 2: ghi n số A1, A2, , An (Ai 10 , i=1..n) * Kết quả ra: ghi ra file văn bản COUNTNT.OUT gồm - Dòng 1: ghi số lượng số nguyên tố; - Dòng 2: ghi lần lượt các số nguyên tố theo thứ tự của dãy ban đầu (nếu có) * Ví dụ: COUNTNT.INP COUNTNT.OUT 5 3 1 3 2 8 5 3 2 5 2. Thuật toán * Thuật toán 1: - Viết hàm kiểm tra số nguyên tố; - Duyệt các số i từ 1 đến n, với mỗi số A[i] kiểm tra nếu A[i] là số nguyên tố thì đưa ra số A[i] * Thuật toán 2: - Viết hàm sàng nguyên tố, lọc ra các số nguyên tố trong đoạn [1..106]; - Với mỗi số A[i] kiểm tra nếu d[A[i]]=1 (A[i] là số nguyên tố) đưa ra A[i]. * Đánh giá: - Với thuật toán 1 độ phức tạp thuật toán là O(n*103) nên bị quá thời gian với n lớn khoảng 106 - Với thuật toán 2 độ phức tạp thuật toán là O(nlg106) nên không bị quá thời gian. Sử dụng kỹ thuật nâng cao sàng nguyên tố để kiểm tra số nguyên tố với độ phức tạp thuật toán là O(1). Trang 12
13. 3. Cài đặt #include const int nmax=1000005; using namespace std; int d[nmax],n,a[nmax],dem=0; void sangnt(int k) { int i,j; d[1]=1; for(i=2;i*i<=k;i++) { if(d[i]==0){ j=i*i; while(j<=k) {d[j]=1; j+=i;} } } } int main() { int i; freopen("COUNTNT.INP","r",stdin); freopen("COUNTNT.OUT","w",stdout); cin>>n; for(i=1;i >a[i]; for(i=1;i<=1000001;i++)d[i]=0; sangnt(1000001); for(i=1;i<=n;i++) if(d[a[i]]==0) dem++; cout<<dem<<endl; for(i=1;i<=n;i++)if(d[a[i]]==0)cout<<a[i]<<" "; return 0; } III. Bài toán tìm ước nguyên tố nhỏ nhất 1. Phát biểu bài toán Viết chương trình nhập vào số nguyên dương n. In ra n số nguyên dương A 1, A2, ..., An với Ai là số nguyên tố nhỏ nhất là ước của i (qui ước A1=1) * Dữ liệu vào: đọc vào từ file văn bản NTUOC.INP gồm một số nguyên dương n≤106. * Kết quả ra: ghi ra file văn bản NTUOC.OUT gồm n số nguyên của dãy trên (các số trên cùng dòng cách nhau ít nhất một dấu trống) * Ví dụ: NTUOC.INP NTUOC.OUT 9 1 2 3 2 5 2 7 2 3 Trang 13
14. 2. Thuật toán * Thuật toán 1: - Viết hàm kiểm tra số nguyên tố; - Duyệt các số i từ 1 đến n, với mỗi số A[i] tìm ước nguyên dương nhỏ nhất của A[i] là số nguyên tố thì đưa ra * Thuật toán 2: - Viết hàm sàng nguyên tố trong đoạn [1..10 6]. Cải tiến sàng nguyên tố, với d[i] là ước nguyên tố nhỏ nhất của i; - Với mỗi số A[i] đưa ra d[A[i]]. * Đánh giá: - Với thuật toán 1 độ phức tạp thuật toán là O(n*103) nên bị quá thời gian với n lớn khoảng 106 - Với thuật toán 2 độ phức tạp thuật toán là O(nlg106) nên không bị quá thời gian. 3. Cài đặt #include const int nmax=1000005; using namespace std; int a[nmax],n; void sangnt(int n) { int i,j; for(i=2; i<=sqrt(n);i++) if(a[i]==0){ j=i*i; while(j<=n) { if(a[j]==0)a[j]=i; j+=i; } } } int main() { int i; freopen("NTUOC.INP","r",stdin); freopen("NTUOC.OUT","w",stdout); cin>>n; sangnt(n); cout<<1<<" "; for(i=2;i<=n;i++) if(a[i]==0)cout<<i<<" ";else cout<<a[i]<<" "; return 0; } Trang 14
15. IV. Đếm ước 1. Phát biểu bài toán Viết chương trình nhập vào số nguyên dương N. Đếm các ước số nguyên dương của N. * Dữ liệu vào: đọc từ file văn bản COUNT.INP gồm 1 số nguyên dương N (N≤1018) * Kết quả ra: ghi ra file văn bản COUNT.OUT gồm 1 số duy nhất là kết quả tìm được. * Ví dụ: COUNT.INP COUNT.OUT 10 4 2. Thuật toán * Thuật toán 1: Duyệt các i=1 đến phần nguyên căn bậc 2 của N. Nếu N chia hết cho i thì đếm ước; * Thuật toán 2: Phân tích N thành tích các thừa số nguyên tố dạng N=aibj ck thì tổng các ước của N là: (i+1)(j+1) (k+1) * Đánh giá: - Thuật toán 1 có độ phức tạp thuật toán là O(| |) nên với N khoảng 1018 sẽ bị quá thời gian. - Thuật toán 2 cải tiến phân tích N thành tích các thừa số nguyên tố với độ phức tạp thuật toán O(N1/3) Sử dụng kỹ thuật nâng cao phân tích thành thừa số nguyên tố. 3. Cài đặt #include using namespace std; const int MAXN = 1e6; long long N; vector primes; vector isPrime; void sieve() { isPrime.assign(MAXN + 1, 1); isPrime[0] = isPrime[1] = 0; for (int i = 2; i <= MAXN; i++) { if (!isPrime[i]) continue; primes.push_back(i); for (int j = i + i; j <= MAXN; j += i) { isPrime[j] = 0; } } } long long binaryPower(long long a, long long k, long long n) { a = a % n; long long res = 1; while (k) { if (k & 1) Trang 15
16. res = (res * a) % n; a = (a * a) % n; k /= 2; } return res; } bool test(long long a, long long n, long long k, long long m) { long long mod = binaryPower(a, m, n); if (mod == 1 || mod == n - 1) return 1; for (int l = 1; l < k; ++l) { mod = (mod * mod) % n; if (mod == n - 1) return 1; } return 0; } bool isPrimeRabinMiller(long long n) { vector checkSet = {2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37}; if (n <= 37) { for (int i : checkSet) { if (i == n) return 1; } return 0; } long long k = 0, m = n - 1; while (m % 2 == 0) { m /= 2; k++; } for (auto a : checkSet) if (!test(a, n, k, m)) return 0; return 1; } bool isSquare(long long n){ long long c = sqrt(n); return c * c == n; } int countDiv(long long n) { if (n == 1) return 1; Trang 16
17. vector powV; for (auto p : primes) { int cnt = 0; while (n % p == 0) { n /= p; ++cnt; } if (cnt) powV.push_back(cnt); } if (n != 1) { if (isPrimeRabinMiller(n)) powV.push_back(1); else if (isSquare(n)) powV.push_back(2); else { powV.push_back(1); powV.push_back(1); } } int ret = 1; for (auto i : powV) ret *= (i + 1); return ret; } void solution() { sieve(); cout << countDiv(N); } int main() { freopen("COUNT.INP","r",stdin); freopen("COUNT.OUT","w",stdout); cin>>N; solution(); return 0; } Trang 17
18. V. Bài toán tính tổng các ước 1. Phát biểu bài toán Viết chương trình nhập vào số nguyên dương N. Tính tổng các ước số nguyên dương của N. * Dữ liệu vào: đọc từ file văn bản SUM.INP gồm 1 số nguyên dương N (N≤1012) * Kết quả ra: ghi ra file văn bản SUM.OUT gồm 1 số duy nhất là kết quả tìm được. * Ví dụ: SUM.INP SUM.OUT 10 4 2. Thuật toán * Thuật toán 1: Duyệt các i=1 đến phần nguyên căn bậc 2 của N. Nếu N chia hết cho i thì tính tổng các ước của N; * Thuật toán 2: Phân tích N thành tích các thừa số nguyên tố dạng N=aibj ck thì tổng ai 1 1 b j 1 1 ck 1 1 các ước của N là: ... a 1 b 1 c 1 * Đánh giá: - Thuật toán 1 có độ phức tạp thuật toán là O(| |) nên với N khoảng 1018 sẽ bị quá thời gian. - Thuật toán 2 cải tiến phân tích N thành tích các thừa số nguyên tố với độ phức tạp thuật toán O(N1/3) Sử dụng kỹ thuật nâng cao phân tích thành thừa số nguyên tố. 3. Cài đặt #include using namespace std; long long N,Sum=1; int main() { freopen("SUM.INP","r",stdin); freopen("SUM.OUT","w",stdout); cin>>N; int i=2; while(N>1) { int k=0; while(N%i==0) { k++;N=N/i;} long long tg=1; for(int j=1;j<=k+1;j++) tg*=i; Sum*=(tg-1)/(i-1); i++; } cout<<Sum; return 0; } Trang 18
19. VI. Ước số 1. Phát biểu bài toán Cho đoạn số nguyên . Hãy tính là số lượng các ước của tất cả các số nguyên trọng đoạn và là tổng tất cả các ước số của các số nguyên trong đoạn . * Dữ liệu vào: đọc vào từ file văn bản US.INP gồm: - Dòng đầu ghi số nguyên dương là số bộ dữ liệu; - dòng tiếp theo, mỗi dòng ghi hai số nguyên thể hiện một bộ dữ liệu. * Kết quả ra: đưa ra file văn bản US.OUT gồm dòng, mỗi dòng ghi hai số nguyên thể hiện kết quả của bộ dữ liệu tương ứng. * Ví dụ: US.INP US.OUT 2 3 4 1 2 5 13 4 5 * Giới hạn: - Subtask 1: - Subtask 2: - Subtask 3: 2. Thuật toán * Thuật toán 1: - Duyệt T bộ test; - Duyệt các i từ a đến b, với mỗi i đếm các ước của i và tính tổng các ước của i. Đếm tất cả các ước của mỗi i và tính tổng các ước của mỗi i là kết quả số lượng các ước và tổng tất cả các ước của các số trong đoạn [a, b]. * Thuật toán 2: - Duyệt T bộ test; - Tạo mảng Duoc[i] là số lượng các ước của các số từ 1 đến i. Số lượng các ước của các số trong đoạn [a, b] là: Duoc[b]-Duoc[a-1] - Tạo mảng Tuoc[i] là tổng các ước của các số từ 1 đến i. Tổng các ước của các số trong đoạn [a, b] là: Tuoc[b]-Tuoc[a-1] * Nhận xét: - Thuật toán 1: duyệt T bộ test, với mỗi bộ test duyệt đoạn [a, b] để đếm ước và tính tổng ước. Độ phức tạp thuật toán là O(T*(b-a)), chương trình sẽ quá thời gian với Subtask 3. - Thuật toán 2: Sử dụng kỹ thuật tổng tiền tố để tạo mạng duoc[i] và Tuoc[i]. Với mỗi truy vấn T thì ta tính được số lượng các ước và tổng các ước trong đoạn [a,b] có độ phức tạp là O(1). Vậy độ phức tạp thuật toán là O(T). Sử dụng kỹ thuật nâng cao tổng tiền tố trong số học. 3. Cài đặt #include using namespace std; const int N=1e6+7; int T,a,b; long long Duoc[N], Tuoc[N], d1, d2; void sang() Trang 19
20. { for(int i=1; i<=1e6+5; i++) for(int j=i; j<=1e6+5; j+=i) Tuoc[j]+=i, Duoc[j]++; for (int i=1; i<=1e6+5; i++) { Duoc[i]=Duoc[i]+Duoc[i-1]; Tuoc[i]=Tuoc[i]+Tuoc[i-1]; } } main() { ios_base::sync_with_stdio(0); cin.tie(0);cout.tie(0); freopen("us.inp","r",stdin); freopen("us.out","w",stdout); sang(); cin>>T; while(T--) { cin>>a>>b; d1=Duoc[b]-Duoc[a-1]; d2=Tuoc[b]-Tuoc1[a-1]; cout<<d2<<" "<<d1<<"\n"; } return 0; } Trang 20