Sáng kiến kinh nghiệm THPT: Sử dụng ngôn ngữ lập trình C++ và Python để giải quyết lớp bài toán dạng số trong bồi dưỡng học sinh giỏi

Chia sẻ: _ _ | Ngày: | Loại File: PDF | Số trang:54

Thêm vào BST

Báo xấu

59
lượt xem 18
download

Download Vui lòng tải xuống để xem tài liệu đầy đủ

Mục đích nghiên cứu sáng kiến nhằm tìm ra điểm khác biệt giữa 2 ngôn ngữ C++ và Python khi giải quyết bài toán; trao đổi cùng với các đồng nghiệp về việc vận dụng ngôn ngữ C++ và Python trong việc lập trình sau đó đưa ra quan điểm cái nhân về vấn đề lựa chọn ngôn ngữ trong bồi dưỡng học sinh giỏi; giải quyết được lớp bài toán dạng số với cả hai ngôn ngữ C++ và Python một cách tối ưu nhất.

Chủ đề:

Bình luận(0) Đăng nhập để gửi bình luận!

Lưu

Nội dung Text: Sáng kiến kinh nghiệm THPT: Sử dụng ngôn ngữ lập trình C++ và Python để giải quyết lớp bài toán dạng số trong bồi dưỡng học sinh giỏi

SỞ GIÁO DỤC & ĐÀO TẠO NGHỆ AN TRƯỜNG THPT ĐÔ LƯƠNG 1 ……………………………… SÁNG KIẾN KINH NGHIỆM Đề tài: “SỬ DỤNG NGÔN NGỮ LẬP TRÌNH C++ VÀ PYTHON ĐỂ GIẢI QUYẾT LỚP BÀI TOÁN DẠNG SỐ TRONG BỒI DƯỠNG HỌC SINH GIỎI” Lĩnh vực: Tin học Người thực hiện: Nguyễn Thị Hà (Giáo viên 1) Hoàng Thị Hương (Giáo viên 2) Tổ bộ môn: Toán - Tin Đơn vị: Trường THPT Đô Lương 1 Số điện thoại: 0855974950 hoặc 0983666458 Email: thuhadl1@gmail.com NĂM HỌC: 2022 – 2023 0
DANH MỤC CÁC TỪ VIẾT TẮT Viết tắt Viết đầy đủ HSG Học sinh giỏi GV Giáo viên THPT Trung học phổ thông THCS Trung học cơ sở 1
MỤC LỤC PHẦN I. ĐẶT VẤN ĐỀ ................................................................................................................. 2 1. Lý do chọn đề tài.................................................................................................................... 2 2. Mục đích nghiên cứu ............................................................................................................. 3 3. Nhiệm vụ và phạm vi nghiên cứu ......................................................................................... 3 3.1. Nhiệm vụ nghiên cứu ...................................................................................................... 3 3.2. Phạm vi nghiên cứu......................................................................................................... 3 4. Đối tượng nghiên cứu ............................................................................................................ 3 5. Phương pháp nghiên cứu. ..................................................................................................... 3 5.1. Nhóm phương pháp nghiên cứu lý luận ........................................................................... 3 5.2. Nhóm phương pháp nghiên cứu thực tiễn ........................................................................ 4 5.3. Phương pháp thực nghiệm................................................................................................ 4 6. Tính mới và đóng góp của đề tài .......................................................................................... 4 PHẦN II. NỘI DUNG ................................................................................................................... 4 1. Cơ sở lý luận........................................................................................................................... 4 1.1. Lý luận về chương trình phổ thông mới ........................................................................... 4 1.2. Lý luận dạy học về dạy học lập trình C++ ....................................................................... 5 1.3. Lý luận dạy học về dạy học lập trình Python ................................................................... 5 2. Cơ sở thực tiễn ....................................................................................................................... 6 2.1. Thực trạng trước khi thực hiện các giải pháp sáng kiến ................................................... 6 2.2. Thực trạng giáo viên và học sinh trong dạy học đội tuyển học sinh giỏi ......................... 6 2.3. Thực trạng dạy lập trình bằng ngôn ngữ C++ và Python của giáo viên ........................... 7 2.4. Thực trạng học tin lập trình của học sinh ở trường trung học phổ thông ......................... 7 3. Giải pháp thực hiện ............................................................................................................... 7 3.1. Một số kiến thức cơ bản về bài toán dạng số ................................................................... 7 3.2. Lớp các bài toán về dạng số ........................................................................................... 10 4. Khảo sát sự cấp thiết và tính khả thi của giải pháp đề xuất ............................................ 44 4.1. Mục đích khảo sát ........................................................................................................... 44 4.2. Nội dung và phương pháp khảo sát ................................................................................ 45 4.3. Đối tượng khảo sát.......................................................................................................... 45 4.4. Kết quả khảo sát về tính cấp thiết và tính khả thi của các giải pháp đã đề xuất ............. 45 5. Kết quả đạt được ................................................................................................................. 49 5.1. Đối với học sinh .............................................................................................................. 49 5.2. Đối với giáo viên ............................................................................................................ 49 5.3. Khả năng mang lại lợi ích thiết thực của sáng kiến ....................................................... 49 PHẦN 3: KẾT LUẬN ................................................................................................................... 50 0
1. Kết luận ................................................................................................................................ 50 2. Đề xuất phạm vi ................................................................................................................... 50 3. Những kiến nghị đề xuất ..................................................................................................... 50 PHẦN IV. TÀI LIỆU THAM KHẢO ........................................................................................ 51 1
PHẦN I. ĐẶT VẤN ĐỀ 1. Lý do chọn đề tài Bồi dưỡng học sinh giỏi luôn là một trong những mỗi quan tâm hàng đầu của các trường trung học sơ sở cũng như trung học phổ thông. Đối với môn tin học, trước đây thường sử dụng ngôn ngữ lập trình Passcal để bồi dưỡng học sinh giỏi là bởi vì nội dung trong sách giáo khoa đưa ra là ngôn ngữ lập trình Passcal. Tuy nhiên nhiều năm gần đây trong công tác bồi dưỡng học sinh giỏi hầu hết tất cả các trường đều giải quyết các bài toán lập trình bằng ngôn ngữ C++. Do ngôn ngữ này có rất nhiều điểm mạnh từ kiểu dữ diệu, thư viện hàm có sẵn và tốc độ xử lý phù hợp đáp ứng trong thi học sinh giỏi tỉnh. Chương trình giáo dục phổ thông mới 2018 có nhiều sự thay đổi về nội dung cũng như phương pháp dạy học. Nhưng sự thay đổi nhất phải nói đến môn tin học. Môn tin học là môn bắt buộc của bậc tiểu học và bậc trung học cơ sở. Đối bậc trung học phổ thông là giai đoạn giáo dục định hướng nghề nghiệp nên ngay từ lớp 10 đã đưa vào Chủ đề F: “Giải quyết vấn đề với sự trợ giúp của máy tính” trong đó có đưa ngôn ngữ lập trình Python để học sinh làm quen với cách lập trình bằng ngôn ngữ này. Python là ngôn ngữ lập trình bậc cao có rất nhiều ưu điểm trong lập trình cũng như trong xây dựng các thư viện đồ họa. Nó hoàn toàn có thể sử dụng để giải quyết các bài toán khó. Tuy nhiên băn khăn của giáo viên khi bồi dưỡng học sinh giỏi trường và tỉnh môn tin là khi giải quyết bài toán lập trình không những chỉ giải quyết được bài toán đó mà còn phải ràng buộc thời gian chạy 1 test lúc đó mới có khả năng ăn điểm tối đa. Với ngôn ngữ Python thì tốc độ xử lý như thế nào? Khi xử lý bài toán cùng thuật toán để có thể ăn điểm tối đa. Nhưng vấn đề hiện nay là học sinh khối 10 đang học chương trình mới với sách giáo khoa bằng ngôn ngữ Python. Vậy khi các bạn học lập trình bằng ngôn ngữ Python này tham gia học sinh giỏi trường, tỉnh thì các bạn sẽ giải quyết bài toán lập trình bằng ngôn ngữ nào để cùng thuật toán có thể đảm bảo thời gian chạy 1 giây cho 1 test? Đây luôn là nỗi bận tâm của tôi cũng như nhiều giáo viên khác. Trong quá trình giảng dạy chúng tôi luôn cố gắng tìm tòi, học hỏi, đúc rút kinh nghiệm để giúp các học sinh tiếp cận các nội dung một cách dễ dàng hơn, tạo nhiều đam mê cho học sinh. Với sự cố gắng không ngừng nhiều năm qua trong công tác bồi dưỡng học sinh giỏi bản thân đã có những thành tích đáng ghi nhận. Cụ thể năm học 2021-2022 chúng tôi mạnh dạn bồi dưỡng 2 em dự thi cấp tỉnh và đạt cả 2, trong đó có 1 em đạt 17/20. Năm học 2022 – 2023 này cũng có 3 em dự thi đều đạt kết quả: 2 giải ba và 1 giải khuyến khích. Với nhiều năm nghiên cứu cấu trúc đề thi học sinh giỏi của tỉnh Nghệ An cũng như các tỉnh thành khác, tôi thấy hầu hết trong tất cả các đề thi đều có đến 1 hoặc 2 bài dạng số học với độ phức tạp khác nhau. Với mong muốn giúp học sinh có thêm tài liệu để bồi dưỡng, biết được điểm mạnh và yếu của ngôn ngữ lập trình C++ và 2
Python từ đó học sinh cũng như giáo viên xác định và lựa chọn ngôn ngữ phù hợp khi tham gia ôn thi học sinh giỏi tỉnh. Chúng tôi đã giải quyết lớp các bài toán dạng số với cả hai loại ngôn ngữ. Với những lý do trên chúng tôi đã đưa ra đề tài “Sử dụng ngôn ngữ lập trình C++ và Python để giải quyết lớp bài toán dạng số trong bồi dưỡng học sinh giỏi” 2. Mục đích nghiên cứu - Thứ nhất, Tìm ra điểm khác biệt giữa 2 ngôn ngữ C++ và Python khi giải quyết bài toán - Thứ 2, Trao đổi cùng với các đồng nghiệp về việc vận dụng ngôn ngữ C++ và Python trong việc lập trình sau đó đưa ra quan điểm cái nhân về vấn đề lựa chọn ngôn ngữ trong bồi dưỡng học sinh giỏi. - Thứ 3, Giải quyết được lớp bài toán dạng số với cả hai ngôn ngữ C++ và Python một cách tối ưu nhất - Thứ tư, Đề tài có thể làm tài liệu cho giáo viên phục vụ giảng dạy, bồi dưỡng HSG. 3. Nhiệm vụ và phạm vi nghiên cứu 3.1. Nhiệm vụ nghiên cứu - Nghiên cứu sâu 2 loại ngôn ngữ lập trình C++ và Python - Đề tài nghiên cứu hệ thống lớp các bài toán dạng số - Giải và đánh giá các bài toán dạng số theo 2 ngôn ngữ C++ và Python 3.2. Phạm vi nghiên cứu Đề tài được nghiên cứu trong quá trình dạy đội tuyển học sinh giỏi tỉnh học tại trường THPT Đô Lương 1. Đề tài có khả năng áp dụng rộng rãi vào giảng dạy, bồi dưỡng học sinh giỏi Tin học cho giáo viên và học sinh THCS, THPT trên địa bàn toàn tỉnh Nghệ An. 4. Đối tượng nghiên cứu - Chương trình giáo dục phổ thông mới. - Ngôn ngữ lập trình C++ - Ngôn ngữ lập trình Python - Cấu trúc đề thi học sinh giỏi tỉnh môn tin tỉnh Nghệ An - Đối tượng học sinh đội tuyển tin học sinh giỏi trường và tỉnh. 5. Phương pháp nghiên cứu. 5.1. Nhóm phương pháp nghiên cứu lý luận - Nghiên cứu các Nghị quyết của Đảng, Nhà nước, Bộ giáo dục và đào tạo, Sở giáo dục và đào tạo của tỉnh liên quan đến đề tài nghiên cứu. - Các tài liệu về lý luận dạy học Tin học, tài liệu hướng dẫn chuyên môn. 3
- Các tài liệu dạy lập trình 5.2. Nhóm phương pháp nghiên cứu thực tiễn - Phân tích tổng hợp và rút kinh nghiệm từ thực tiễn. 5.3. Phương pháp thực nghiệm - Thực nghiệm tại các nhóm học sinh giỏi ở trường THPT nơi chúng tôi công tác giảng dạy. 6. Tính mới và đóng góp của đề tài - Giúp học sinh tiếp một dạng bài tập được làm rõ trên cả 2 loại ngôn ngữ C++ và Python, đáp ứng một phần yêu cầu trong kiến thức luyện thi học sinh giỏi. - Đánh giá, so sánh hai ngôn ngữ C++ và Python trong lập trình thi học sinh giỏi. - Giúp giáo viên đa dạng hóa về việc áp dụng các loại ngôn ngữ lập trình để giải quyết một bài toán phù hợp với tình hình thực tế hiện nay. - Nâng cao kiến thức bộ môn, đóng góp một phần nhỏ bé vào việc nâng cao được chất lượng dạy học bồi dưỡng học sinh giỏi. - Giúp học sinh đam mê học môn Tin học. PHẦN II. NỘI DUNG 1. Cơ sở lý luận 1.1. Lý luận về chương trình phổ thông mới Mục tiêu cấp trung học phổ thông: Chương trình môn Tin học ở cấp trung học phổ thông giúp học sinh củng cố và nâng cao năng lực tin học đã được hình thành, phát triển ở giai đoạn giáo dục cơ bản, đồng thời cung cấp cho học sinh tri thức mang tính định hướng nghề nghiệp thuộc lĩnh vực tin học hoặc ứng dụng tin học, cụ thể là: - Giúp học sinh có những hiểu biết cơ bản về hệ thống máy tính, một số kĩ thuật thiết kế thuật toán, tổ chức dữ liệu và lập trình; củng cố và phát triển hơn nữa cho học sinh tư duy giải quyết vấn đề, khả năng đưa ra ý tưởng và chuyển giao nhiệm vụ cho máy tính thực hiện. - Giúp học sinh có khả năng ứng dụng tin học, tạo ra sản phẩm số phục vụ cộng đồng và nâng cao hiệu quả công việc; có khả năng lựa chọn, sử dụng, kết nối các thiết bị số, dịch vụ mạng và truyền thông, phần mềm và các tài nguyên số khác. - Giúp học sinh có khả năng hoà nhập và thích ứng được với sự phát triển của xã hội số, ứng dụng công nghệ thông tin và truyền thông trong học và tự học; tìm kiếm và trao đổi thông tin theo cách phù hợp, tuân thủ pháp luật, có đạo đức, ứng xử văn hoá 4
và có trách nhiệm; có hiểu biết thêm một số ngành nghề thuộc lĩnh vực tin học, chủ động và tự tin trong việc định hướng nghề nghiệp tương lai của bản thân. 1.2. Lý luận dạy học về dạy học lập trình C++ - Học lập trình C++ cơ bản đang là một xu hướng của ngành lập trình hiện nay. Bởi vì C++ là ngôn ngữ phổ biến đứng thứ 5 hiện nay. Có rất nhiều ứng dụng phổ biến được viết bằng loại ngôn ngữ này như Photoshop, Chrome,.. Cho nên nó có sức ảnh hưởng rất lớn về xu hướng của ngôn ngữ lập trình hiện nay. - Điểm mạnh của C++ với những ngôn ngữ lập trình khác + Ngôn ngữ C++ là ngôn ngữ cấp trung. Nó có sự kết hợp các tính năng của cả 2 ngôn ngữ cấp cao và thấp. C++ có thể sử dụng cho lập trình để giúp người dùng có thể thâm nhập được vào phần cứng. Hỗ trợ các chức năng của ngôn ngữ lập trình bậc cao. + C++ là ngôn ngữ lập trình có cấu trúc cho phép một chương trình phức tạp được chia thành các chương trình đơn giản nhỏ hơn nó. Đó được gọi là các hàm. Nó còn cho phép di chuyển dữ liệu dễ dàng giữa các hàm. Mà bạn vẫn thường xuyên thấy ở các ngôn ngữ lập trình hiện đại ngày nay. + Có nhiều tính năng khác nhau. Nó cho phép người dùng truy cập trực tiếp vào các API phần cứng của máy, sự xuất hiện của phiên dịch. Đặc biệt là sử dụng tài nguyên của máy và cấp phát bộ nhớ. Đó là sự tối ưu của các ứng dụng và trình điều khiển các hệ thống nhúng. Ngôn ngữ lập trình vô cùng hiệu quả và tiện dụng. Nó được sử dụng cho các hệ thống. Nó nằm trong hệ thống lớn của hệ điều hành Windows, Unix,… + Là ngôn ngữ lập trình đa mục đích. Có thể ứng dụng được trực tiếp vào các ứng dụng của doanh nghiệp, game, đồ họa,… - Ngôn ngữ lập trình C++ nhanh hơn hầu hết những ngôn ngữ khác như Python, Java. Đó cũng chính là lý do mà người dùng thường thích sử dụng ngôn ngữ này hơn so với những ngôn ngữ khác. Vậy việc học lập trình C++ luôn là điều mà người lập trình nào cũng muốn hướng tới. 1.3. Lý luận dạy học về dạy học lập trình Python - Python là một ngôn ngữ lập trình kịch bản (scripting language) do Guido van Rossum tạo ra năm 1990. Python là một ngôn ngữ lập trình cấp cao, cực kỳ linh hoạt, có thể được sử dụng cho hầu hết mọi thứ mà không yêu cầu một ngôn ngữ cụ thể. Một số tính năng khiến Python trở nên thông dụng bao gồm: + Cú pháp Python rất đơn giản chính vì vậy mà nó khá dễ sử dụng. Một số người cho rằng cách tốt nhất để học Python cơ bản là bắt đầu viết luôn chương trình. Hầu hết những cú pháp Python có tính logic cao đủ để giúp bạn bắt đầu viết được luôn chương trình của mình. 5
+ Hầu hết những nhà lập trình viên cho rằng Python là một ngôn ngữ dễ học và nó được giảng dạy phổ biến nhất trong các trường học trên toàn thế giới. Những tính năng trên đã khiến Python trở nên phổ biến trên toàn thế giới. Nó được sử dụng trong nhiều lĩnh vực khác nhau như:  Phát triển trang web Back-end  Phát triển trò chơi.  Khoa học dữ liệu và phân tích.  Phát triển ứng dụng di động.  Robot và AI (Trí tuệ nhân tạo) Cùng với một số ưu điểm thì Python có một số hạn chế trong lĩnh vực hiệu suất. Sau đây là một một số nhược điểm của Python + Tốc độ thực thi chậm: Python là một ngôn ngữ thông dịch, có nghĩa là nó hoạt động với trình thông dịch, không phải với trình biên dịch. Do đó, nó thực thi tương đối chậm hơn C, C++, Java và nhiều ngôn ngữ khác. + Tiêu thụ bộ nhớ lớn: Các cấu trúc của Python đòi hỏi nhiều không gian bộ nhớ hơn. Ngôn ngữ này không thích hợp để sử dụng cho sự phát triển trong điều kiện bộ nhớ hạn chế. + Khó kiểm tra: Vì nó là một ngôn ngữ dựa trên trình thông dịch, rất khó để chạy các bài kiểm tra trên mã được viết bằng Python. Tất cả các lỗi chỉ xuất hiện trong thời gian chạy, điều này khiến việc kiểm tra các đoạn mã được viết bằng Python rất khó khăn. 2. Cơ sở thực tiễn 2.1. Thực trạng trước khi thực hiện các giải pháp sáng kiến Học sinh khối 10 đang áp dụng dạy học theo chương trình giáo dục phổ thông mới 2018 với môn tin có chủ đề F “’Giải quyết bài toán với sự trợ giúp máy tính” lập trình bằng ngôn ngữ lập trình Python. Chương trình giáo dục phổ thông mới khối THPT môn tin các em học lập trình bằng ngôn ngữ lập trình Python. Như vậy khi các em học bằng ngôn ngữ nào thì biết đến ngôn ngữ đó. Do đó học sinh không biết ngôn ngữ nào sẽ ưu việt hơn khi giải quyết bài toán vì các em chỉ tiếp cận ngôn ngữ mình được học. Vì vậy khi các em tham gia đội tuyển học sinh giỏi các em chỉ biết giải quyết bài toán bằng ngôn ngữ đã học là Python. Nhưng trong thi học sinh giỏi thì ngoài giải quyết bài toán còn phải đảm bảo thời gian xử lý dữ liệu (1 test/ 1 giây) 2.2. Thực trạng giáo viên và học sinh trong dạy học đội tuyển học sinh giỏi - Ơ cấp THCS các em đang học chương trình cũ nên một số trường có dạy tin học cho lớp 8 và lớp 9 với ngôn ngữ lập trình Pascal hoặc C++. Tuy nhiên một số trường cơ sở vật chất còn hạn chế nên lớp 8 và lớp 9 không lựa chọn học môn tin nên các em sẽ không biết đến ngôn ngữ lập trình bậc cao. Học sinh khối 10 học chương trình 6
mới các em đa số đã làm quen với ngôn ngữ Python. Vậy với học sinh đã biết một số ngôn ngữ như Pascal hay C++ khi tiếp cận ngôn ngũ Python các em thường đặt ra câu hỏi là khi giải quyết bài toán nên lựa chọn ngôn ngữ nào để dễ viết, dễ sử dụng. Còn đối với học sinh đội tuyển các em lại băn khoăn trong các ngôn ngữ trên thì ngôn ngữ nào giải quyết bài toán thời gian nhanh nhất. Đây cũng là băn khoăn của nhiều giáo viên hiện nay. - Giáo viên dạy đội tuyển cơ bản đã đầu tư tìm tòi. Tuy nhiên việc tiếp cận các ngôn ngữ Python hay C++ của giáo viên cũng chưa nhiều nên gặp khó khăn. - Dựa vào cấu trúc đề thi học sinh giỏi cấp huyện, cấp tỉnh. Có rất nhiều chuyên đề giáo viên cần bồi dưỡng cho học sinh. Một trong các chuyên đề thường có trong các đề thi học sinh giỏi môn tin là chuyên đề về dạng số. Đó là các lớp bài toán dạng số trong các đề thi. - Tài liệu về ôn thi đội tuyển thật sự rất khó tìm để phù hợp cả học sinh và giáo viên 2.3. Thực trạng dạy lập trình bằng ngôn ngữ C++ và Python của giáo viên Hiện nay đa số giáo viên đã tiếp cận với ngôn ngữ lập trình C++. Tuy nhiên để tìm hiểu sâu về ngôn ngữ này thì rất ít, chỉ những giáo viên tham gia bồi dưỡng đội tuyển mới tìm hiểu nhiều. Mặt khác qua các cuộc thi học sinh giỏi cấp huyện, cấp tỉnh giáo viên vẫn đang còn hướng dẫn cho học sinh giải quyết bài toán lập trình bằng ngôn ngữ Pascal. Bởi vì chương trình cũ đang chủ yếu dạy ngôn ngữ Pascal. Chương trình phổ thông mới đã lựa chọn ngôn ngữ lập trình Python để dạy và học lập trình. Nên giáo viên dạy đã được tiếp cận với ngôn ngữ này. Tuy nhiên giáo viên cơ bản trong quá trình vừa dạy, vừa tìm hiểu ngôn ngữ. 2.4. Thực trạng học tin lập trình của học sinh ở trường trung học phổ thông - Các em học sinh đều có cách nhìn chung là môn tin lập trình khó. Vừa phải biết ngôn ngữ, vừa phải hiểu bản chất toán học. Đồng thời biết tìm ra thuật toán tối ưu cho bài toán. - Môn tin học không áp dụng thi tốt nghiệp hay đại học nên các em cứ theo xu hướng là thi nào học đó. Nên chọn học sinh vào đội tuyển để các em dành thời gian học và nghiên cứu môn tin lập trình rất khó khăn. Muốn đạt kết quả cao trong các kì thi học sinh giỏi tỉnh và cấp huyện thì giáo viên ngoài cần phải trang bị đầy đủ, chi tiết kiến thức phần lí thuyết. Còn phải đưa ra các bài tập phù hợp để cũng cố, trang bị kiến thức, cũng như nâng cao kĩ năng vận dụng trong những bài cụ thể. Nhất là tìm ra được những lợi thế và điểm mạnh của ngôn ngữ lựa chọn để dạy đội tuyển. 3. Giải pháp thực hiện 3.1. Một số kiến thức cơ bản về bài toán dạng số Trong ngôn ngữ lập trình bài toán dạng số có một số dạng như sau: Số nguyên tố, số Fibonaxi, số chính phương, só cá tính, số tiêu chuẩn, số hoàn hảo, ước số, bội 7
số, Xử lý số lớn, số đảo ngược ... Mỗi một dạng số ta có các mức và cấp độ khác nhau. 3.1.1. Số nguyên tố Theo định nghĩa của Wikipedia thì số nguyên tố là số tự nhiên lớn hơn 1, chỉ có 2 ước là 1 và chính nó. Theo định nghĩa này thì các số 2, 3, 5, 7, 11, ... là các số nguyên tố, trong đó số 2 là số nguyên tố chẵn duy nhất. Cũng như tính chất của số nguyên dương, chúng ta chỉ tìm thấy số nguyên tố nhỏ nhất chứ không thể tìm thấy số nguyên tố lớn nhất. Khi nói đến số nguyên ta ta thường có bài toán đặc trưng là kiểm tra một số tự nhiên N có phải là số nguyên tố hay không? Thuật toán này tất cả giáo viên bồi dưỡng học sinh giỏi và các em học đội tuyển đã làm rất nhiều với các bài toán khác nhau liên quan đến số nguyên tố. Cụ thể:  Bước 1: Nhập vào n  Bước 2: Kiểm tra nếu n < 2 thì kết luận n không phải là số nguyên tố  Bước 3: Nếu n=2 hoặc n=3 là số nguyên tố  Bước 4: Lặp từ 2 tới phần nguyên căn bậc 2 của n(|√ 𝑛|, nếu trong khoảng này tồn tại số mà n chia hết thì kết luận n không phải là số nguyên tố, ngược lại n là số nguyên tố. Đoạn code như sau: bằng ngôn ngữ Đoạn code như sau: bằng ngôn ngữ C++ Python Bool kt(int n) def kt(n): { if(n
Ví dụ một dãy Fibonacci: F8 = 0 1 1 2 3 5 8 13 Ví dụ một dãy Fibonacci khác: F8 = 1 1 2 3 5 8 13 21 3.1.3 Ước số Một số x được gọi là ước của N khi N ⋮ 𝑥 (Nói một cách khác N chia cho xcos dư là 0). Liên quan đến bài toán ước số ta có các bài toán sau: Tìm ước chung lớn nhất của dãy số, tìm bội chung nhỏ nhất của dãy, liệt kê các ước của một số nguyên, đếm số lượng các ước của một số… 3.1.4. Xử lý số lớn Chúng ta đều biết rằng, việc giải bài toán bằng máy tính nói chung và lập trình thi đấu nói riêng luôn luôn đối mặt với dữ liệu có kích thước rất lớn. Hiển nhiên là vì những dữ liệu quá lớn vượt ra ngoài khả năng tính toán của con người, nên mới cần tới sự trợ giúp của máy tính. Với sự nâng cấp liên tục của máy tính điện tử, độ lớn dữ liệu mà máy tính có thể lưu trữ được cũng ngày càng tăng lên. Tuy nhiên, khả năng lưu trữ luôn luôn là hữu hạn, mà dữ liệu là vô hạn (dữ liệu dạng văn bản có thể dài vô hạn, dữ liệu dạng số có thể cực kỳ lớn,...). Ngôn ngữ lập trình đã có sẵn rất nhiều kiểu dữ liệu với khoảng giá trị rất lớn, nhưng cũng không phải luôn luôn lưu trữ được mọi giá trị. Riêng đối với kiểu số trong C++, chúng ta có sẵn kiểu dữ liệu nguyên thủy là long long với tầm lưu trữ lên tới khoảng 2020 chữ số. Nhưng nếu như có những dữ liệu số với độ dài nhiều hơn thế thì sao? Kĩ thuật xử lý số nguyên lớn ra đời nhằm giải quyết vấn đề đó. Trong chuyên đề này, chúng ta sẽ được học cách biểu diễn các số nguyên lên tới hàng trăm, hàng nghìn, thậm chí vài chục nghìn chữ số,...dựa vào khả năng lưu trữ chuỗi kí tự của máy tính. Các số nguyên sẽ được chuyển sang dạng chuỗi kí tự, sau đó thiết kế những phép toán cộng, trừ, nhân, chia, đồng dư tương ứng. Do độ dài của chuỗi kí tự phụ thuộc vào khả năng lưu trữ của trình biên dịch (mà thông thường rất lớn) nên ta dễ dàng giải quyết vấn đề. a, Biểu diễn bằng chuỗi kí tự Một cách hay để biểu diễn các số nguyên lớn trong C++ là sử dụng lớp chuỗi kí tự trong C++. Các chữ số sẽ tương ứng với các kí tự trong chuỗi, và độ dài của các số khi đó sẽ phụ thuộc vào chương trình biên dịch của ngôn ngữ. Phương pháp biểu diễn này khá được ưa chuộng vì nó đơn giản, dễ hiểu, tuy nhiên trong một số trường hợp cụ thể, thời gian chạy của chương trình cài đặt số lớn bằng string sẽ khá lâu. Tác giả sẽ giải thích cụ thể ở các thuật toán chi tiết. b, Biểu diễn bằng mảng các kí tự 9
Sử dụng một mảng để chứa các chữ số cũng là một phương án thường được sử dụng. Với phương pháp này, mỗi chữ số sẽ tương ứng với một kí tự trong mảng, đồng thời ta duy trì một biến đếm để kiểm soát số chữ số của số ban đầu. Với phương pháp này, tuy cài đặt có khó hơn, nhưng tốc độ chạy chương trình sẽ nhanh hơn, và chúng ta cũng không cần tới thao tác chuyển đổi giữa kí tự và chữ số như phương pháp đầu tiên. Các dạng bài toán về số nguyên lớn như so sánh, cộng, trừ, nhân, hai số nguyên lớn. 3.2. Lớp các bài toán về dạng số 3.21. Bài tập về số ở mức độ cơ bản (mức độ nhớ) Bài 1: Số lượng số nguyên tố Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Yêu cầu: Cho dãy số a1, a2,..., an. Hãy đếm số nguyên tố có mặt trong dãy đã cho. Dữ liệu: - Dòng đầu tiên ghi số nguyên không âm n (0 < n ≤ 103). - Dòng thứ 2 ghi n số nguyên không âm kiểu 64 – bit. Kết quả: in ra số lượng số nguyên tố có mặt trong dãy. Ví dụ input Output 10 6 1 2 3 4 5 6 7 9 11 13 Học sinh năm được thuật toán về kiểm tra 1 số có phải là số nguyên tố hay không. Duyệt các số nếu gặp số đó là sô nguyên tố thì đếm tăng lên. Được minh họa với 2 ngôn ngữ C++ và Python như sau Code bằng ngôn ngữ C++ int main() #include { long long n,m,t,a[10000005]; cin>>n; bool nt(long long x) for(int i=1;i>a[i]; { for(int i=1;i
if n==2 or n==3: return True return True n=int(input()) if n==1 or n%2==0 or n%3==0: a=[int(x) for x in input().split()] return False d=0 for i in for i in range(n): range(5,int(math.sqrt(n))+1,6): if nt(a[i]): if n%i==0 or n%(i+2)==0: d=d+1 return False print(d) Kết quả chấm Test #1, kết quả: ACCEPTED, thời gian: 62 ms, bộ nhớ: 1532 KB Input 10 1 2 3 4 5 6 7 9 11 13 Output 6 Đáp án 6 Kết quả chấm: Kết quả đúng Test #2, kết quả: ACCEPTED, thời gian: 62 ms, bộ nhớ: 4876 KB Input 100 14788 6181 15936 4713 25584 24834 16841 20655 9407 10491 21231 18762 260 25383 21438 25639 22221 29674 23384 20209 1001 19819 12439 7464 21927 12360 22516 11891 9697 25737 14504 20279 18745 32467 7441 18280 12963 1502 4694 19359 28708 3113 27470 1133 25817 4589 27294 8176 25658 17231 22562 8611 4768 26329 1423 25722 12037 4139 1622 815 10763 27374 7883 6870 11840 12810 11910 7096 32161 1000 ... Output 12 Đáp án 12 Kết quả chấm: Kết quả đúng  Test #3, kết quả: ACCEPTED, thời gian: 31 ms, bộ nhớ: 1528 KB Input 11
90 15432 26465 29002 26594 25939 11968 7402 1037 18158 11738 24862 27439 3474 8209 2382 603 29718 22195 23588 1513 21631 22140 21240 13083 15129 28252 25996 13569 12231 11131 15866 22681 10647 20091 26858 19515 24729 9725 22024 28212 29170 29286 15542 28338 2604 14051 14589 18656 2512 7082 13514 22353 22583 17795 29015 1954 22685 18055 17639 29019 13687 3112 24758 21527 30214 28274 13104 16613 ... Output 6 Đáp án 6 Kết quả chấm: Kết quả đúng Bài 2: Số hoàn hảo Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Số hoàn thiện (hay còn gọi là số hoàn chỉnh, số hoàn hảo hoặc số hoàn thành) là một số nguyên dương mà tổng các ước nguyên dương chính thức của nó (số nguyên dương bị nó chia hết ngoại trừ nó) bằng chính nó. Yêu cầu: Viết chương trình kiểm tra số nguyên n có phải là số hoàn hảo hay không. Dữ liệu: Một dòng ghi số nguyên n (0n; for(int i=1;i
Code bằng ngôn ngữ Python s=s+i n = int(input()) j=n//i s=0 if (j!=i):s=s+j can_bac_2 = int(n**(1/2)) if s==2*n: for i in range(1,1+can_bac_2): print("YES") if n %i ==0: else: print("NO")  Test #, kết quả: ACCEPTED, thời gian: 46 ms, bộ nhớ: 864 KB Input 1000000324 Output NO Đáp án NO Kết quả chấm: Kết quả đúng  Test #, kết quả: ACCEPTED, thời gian: 62 ms, bộ nhớ: 556 KB Input 1000000863 Output NO Đáp án NO Kết quả chấm: Kết quả đúng  Test #, kết quả: ACCEPTED, thời gian: 78 ms, bộ nhớ: 864 KB Input 10000000233 Output NO Đáp án NO Bài 3: Cùng chẵn - lẻ Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Ta nói hai số có cùng tính chẵn-lẻ nếu hai số đều là số chẵn hoặc đều là số lẻ. Yêu cầu: Viết chương trình xét xem hai số có cùng tính chẵn-lẻ hay không? 13
Dữ liệu: Hai số nguyên a, b kiểu 64 bit, mỗi số cách nhau một dấu cách trống. Kết quả: In ra 1 nếu hai số có cùng tính chẵn-lẻ, ngược lại in ra 0. Ví dụ input output 55 1 Code bằng ngôn ngữ C++ k1 = a%2 #include k2 = b%2 using namespace std; if k1==k2: int main() print(1) {long long a,b,h=0,s=0; else: print(0) cin>>a>>b; #include h=a%2; using namespace std; s=b%2; int main () if (s!=0&&h==0) cout
input 5 10 output YES Code bằng ngôn ngữ C++ else coutA>>X; print("YES") if(X%A==0) else: cout
Bài 1: Số nhỏ nhất lớn hơn K Giới hạn thời gian: 1.0 giây Giới hạn bộ nhớ: 128 megabyte Yêu cầu Cho một dãy N số nguyên và số nguyên k, hãy viết chương trình in ra số nhỏ nhất trong dãy số mà lớn hơn k. Dữ liệu * Dòng thứ nhất ghi hai số nguyên dương N và k ( N, k k. Thể hiện đoạn lệnh sau: if(a[i]>k) MIN=min(a[i],MIN); Chương trình hoàn thiện viết bằng Code C++ #include #define int long long using namespace std; long long n,k,MIN=INT_MAX,a[10000007]; main() { cin>>n>>k; for(int i=1; i>a[i]; if(a[i]>k) MIN=min(a[i],MIN); } if(MIN!=INT_MAX) cout
} Chương trình hoàn thiện viết bằng Code Python n,k=map(int,input().split()) a=[int(n) for n in input().split()] str=[] for i in range(0,len(a)): if a[i]>k: str.append(a[i]) if str==[]: print(-1) else: print(min(str)) Test #, kết quả: ACCEPTED, thời gian: 31 ms, bộ nhớ: 816 KB Input 85 30 76 197 192 104 58 62 138 48 200 105 199 181 35 95 31 116 90 128 46 41 52 62 196 80 173 159 59 30 194 170 24 62 114 32 98 56 127 125 109 63 60 196 168 146 91 113 59 160 62 156 48 39 37 182 169 153 53 159 152 76 171 97 189 129 138 103 191 190 118 82 31 88 57 40 158 200 153 67 146 181 181 49 200 84 81 Output 31 Đáp án 31 Kết quả chấm: Kết quả đúng Test #, kết quả: ACCEPTED, thời gian: 46 ms, bộ nhớ: 4960 KB Input 484 9924 97 178 219 244 317 356 436 516 569 650 684 758 857 945 976 1009 1086 1152 1225 1313 1388 1416 1514 1573 1626 1717 1766 1801 1828 1899 1980 2065 2140 2187 2259 2315 2374 2471 2511 2580 2644 2680 2703 2782 2876 2900 2950 2998 3020 3077 3139 3228 3328 3413 3453 3500 3580 3654 3713 3793 3883 3975 4006 4068 4122 4165 4252 4303 4387 4413 4462 4495 4559 4636 4718 4786 4814 4855 4928 4951 5040 ... Output 9964 17