SKKN Phương pháp xử lý số nguyên lớn trong bồi dưỡng học sinh giỏi bằng ngôn ngữ lập trình C++

PHẦN 1: MỞ ĐẦU 

1. Lý do chọn đề tài 

Trong mỗi ngôn ngữ lập trình thường có một số kiểu dữ liệu chuẩn cho biết phạm vi giá trị có thể lưu trữ, dung lượng bộ nhớ cần thiết để lưu trữ và xác định các phép toán có thể tác động lên dữ liệu. Tuy nhiên khi thực hiện phép toán với số nguyên ngoài phạm vi biểu diễn được cung cấp ta cần thiết kế cách biểu diễn và các hàm thực hiện các phép toán cơ bản với các số nguyên 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 đề tài này, tôi sẽ đưa ra 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 đề. 

Nhằm nâng cao trình độ lập trình của học sinh nói chung và đáp ứng yêu cầu thi học sinh giỏi các cấp nói riêng học sinh trong lập trình luôn chú trọng đến tối ưu của thuật toán. Hay nói cách khác làm thế nào để độ phức tạp của bài toán càng nhỏ càng tốt. Thực tế về dạy học đội tuyển cấp tỉnh môn tin học giáo viên cũng như học sinh không chỉ lập trình được bài toán đó mà cần yêu cầu thời gian chạy ít nhất. Nói một cách khác là mỗi 1 test yêu cầu chạy tối đa không quá 1 giây thì lúc đó mới có kết quả cao. Tuy nhiên thực tế học sinh lập trình được bài toán nhưng cứ thường quá thời gian. Một trong những lỗi vượt quá thời gian thường xảy ra là thuật toán chưa tối ưu. Muốn như vậy thì độ phức tạp cho các bài toán với kiểu dữ liệu lớn thường từ 104 trở lên phải là O(n) hoặc O(logn). Do đó chúng ta cần biết vận dụng được các điểm mạnh của ngôn ngữ C++. 

Trong quá trình dạy bồi dưỡng học sinh giỏi ở trường phổ thông, tôi nhận thấy khả năng xử lý của học sinh để đưa ra được thuật toán tối ưu với bài toán xử lý số nguyên lớn còn gặp rất nhiều khó khăn. Nhằm khắc phục nhược điểm trên và để đáp ứng được yêu cầu của công tác bồi dưỡng học sinh giỏi của thầy và trò trong trường THPT, tôi mạnh dạn đưa ra đề tài “Phương pháp xử lý số nguyên lớn trong bồi dưỡng học sinh giỏi bằng ngôn ngữ lập trình C++” nhằm phục vụ công tác bồi dưỡng có hiệu quả hơn. 

• Mục tiêu, nhiệm vụ nghiên cứu. 

• Xây dựng được bộ công cụ lập trình trong quá trình tiếp xúc và làm việc với số nguyên lớn. 
• Giúp học sinh giải quyết được các bài toán về số nguyên lớn một cách tối ưu nhất. 
• Học sinh hiểu hơn về ngôn ngữ lập trình mà các em vừa mới tiếp cận, ngôn ngữ lập trình C++.  
• Từ đó đưa ra nhận xét, đánh giá và đề xuất giải pháp góp phần hoàn thiện công tác dạy và học lập trình đối với các bài toán mà dữ liệu vào hay kết quả ra có giá trị nguyên dương rất lớn.  
• Là tài liệu cho giáo viên bồi dưỡng, học sinh giỏi tham khảo. 

• Đối tượng nghiên cứu. 

• Ngôn ngữ lập trình C++  
• 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. 
• Các bài toán xử lý số nguyên lớn trong ngôn ngữ lập trình C++ với đối tượng học sinh khá giỏi. 

• Phương pháp nghiên cứu. 

4.1 Nhóm phương pháp nghiên cứu lý luận  

Nghiên cứu chương trình giáo dục phổ thông mới 2018. 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.  

Nghiên cứu, phân tích cấu trúc và nội dung chương trình tin học THPT đặc biệt là cấu trúc đề thi học sinh giỏi cấp trường và cấp tỉnh khối THCS và THPT môn tin học. Các tài liệu liên quan đến ngôn ngữ lập trình C++ và cấu trúc dữ liệu nâng cao trong C++.  

• Nhóm phương pháp nghiên cứu thực tiễn  

Thực tiễn qua các dạy học bồi dưỡng đội tuyển học sinh giỏi tỉnh và ôn luyện học sinh giỏi cấp trường.  

• Phương pháp thực nghiệm  

Thực nghiệm trong khi bồi dưỡng học sinh giỏi và kết quả đạt được của đội tuyển qua kỳ thi HSG tỉnh. 

• Tính mới và đóng góp của đề tài 

• Đưa ra được điểm mới của các bài toán xử lý số nguyên lớn trong ngôn ngữ lập trình C++ so với các ngôn ngữ khác. 
• Góp phần làm rõ cơ sở lí luận về vấn đề bồi dưỡng học sinh giỏi, làm rõ khái niệm, vai trò đặc điểm của các yếu tố ảnh hưởng đến chất lượng công tác bồi dưỡng học sinh giỏi.  
• Sáng kiến đã đưa ra một hệ thống các bài tập thích hợp, sắp xếp một cách logic, hợp lí từ dễ đến khó nhằm giúp học sinh củng cố kiến thức, rèn luyện kỹ năng phát triển tư duy và biết áp dụng Tin học vào thực tiễn.  
• Thông qua việc hướng dẫn giải các bài toán giáo viên đã rèn luyện kỹ năng lập trình cho học sinh bằng cách định hướng, hướng dẫn qua lời giải từng bài tập, qua đó góp phần tạo niềm tin và hứng thú học tập.