Sáng kiến kinh nghiệm THPT: 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++

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

Thêm vào BST

Báo xấu

18
lượt xem 10
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 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++.

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: 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++

MỤC LỤC PHẦN 1: MỞ ĐẦU ...................................................................................................... 1 I. Lý do chọn đề tài ........................................................................................................ 1 II. Mục tiêu, nhiệm vụ nghiên cứu. ................................................................................ 2 III. Đối tượng nghiên cứu. ............................................................................................. 2 IV. Phương pháp nghiên cứu. ........................................................................................ 2 4.1 Nhóm phương pháp nghiên cứu lý luận ................................................................... 2 4.2. Nhóm phương pháp nghiên cứu thực tiễn................................................................ 2 4.3. Phương pháp thực nghiệm ...................................................................................... 3 V. Tính mới và đóng góp của đề tài ............................................................................... 3 PHẦN 2: NỘI DUNG NGHIÊN CỨU ........................................................................ 4 I. CƠ SỞ LÝ LUẬN. .................................................................................................... 4 1. Ưu điểm của ngôn ngữ lập trình C++ ......................................................................... 4 2. Độ phức tạp của thuật toán......................................................................................... 5 II. THỰC TRẠNG......................................................................................................... 5 2.1. Thực trạng trước khi thực hiện các giải pháp sáng kiến ........................................... 5 2.2. Thực trạng trong dạy học đội tuyển học sinh giỏi .................................................... 5 III. BIỆN PHÁP ............................................................................................................ 8 1. CÁC PHÉP TOÁN XỬ LÍ SỐ NGUYÊN LỚN ......................................................... 8 1.1. Biểu diễn số nguyên lớn.......................................................................................... 8 1.2. Các phép toán xử lí số nguyên lớn .......................................................................... 8 2. BÀI TẬP VẬN DỤNG ............................................................................................ 14 2.1. Số FIBONACI……………………………………………………….. ............................................ 14 2.2. Tổng FIBONACI .................................................................................................. 15 2.3. Chuyển cơ số. ...................................................................................................... 17 2.4. Nguồn của một số. ................................................................................................ 20 2.5. Số các ước và tổng ước của N! Tên file: TONGUOC.CPP .................. 22 2.6. Cân đĩa Tên file: CANDIA.CPP ........................................................... 25 3. Một số bài tập về số nguyên lớp áp dụng trong đề thi học sinh giỏi tỉnh................... 29 3.1. Hoán vị xâu. Tên file: HOANVIXAU.CPP ............................................. 29 3.2. Đánh số trang sách Tên file: TRANGSACH.INP.................................... 31 3.3. Băng giấy Tên file: TAPE.CPP .............................................................. 34 4. Kết quả thực nghiệm ................................................................................................ 35 5. Khảo sát sự cấp thiết và tính khả thi của các giải pháp đề xuất ................................. 36 5.1. Mục đích khảo sát ................................................................................................. 36 5.2. Nội dung và phương pháp khảo sát ....................................................................... 36 5.3. Tổng hợp các đối tượng sau khảo sát. ................................................................... 37 5.4. Kết quả khảo sát về sự cấp thiết và tính khả thi của các giải pháp đã đề xuất......... 37 PHẦN 3: KẾT LUẬN VÀ ĐỀ XUẤT ....................................................................... 40 I. NHỮNG ĐÓNG GÓP CỦA ĐỀ TÀI ....................................................................... 40 1. Tính mới của đề tài .................................................................................................. 40 2. Tính khoa học. ......................................................................................................... 40 3. Tính khả thi. ............................................................................................................ 40 II. ĐỀ XUẤT ............................................................................................................... 40 1. Phạm vi áp dụng ...................................................................................................... 40 2. Đối với giáo viên và học sinh................................................................................... 40 TÀI LIỆU THAM KHẢO ......................................................................................... 41
PHẦN 1: MỞ ĐẦU I. 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 1
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. II. 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. III. Đố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. IV. 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++. 4.2. 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. 2
4.3. 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. V. 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. 3
PHẦN 2: NỘI DUNG NGHIÊN CỨU I. CƠ SỞ LÝ LUẬN. 1. Ưu điểm của ngôn ngữ lập trình C++ Trong quy định của các kỳ thi HSG Tin học, thí sinh có thể lập trình bằng ngôn ngữ PascaL, Python, C++… để giải các bài toán. Trong ba NNLT này, C++ là ngôn ngữ được lựa chọn nhiều nhất vì nó có những ưu điểm nổi bật hơn hẳn so với hai ngôn ngữ lập trình còn lại ở một số đặc điểm sau: - Là ngôn ngữ 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ó 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. - 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. - Là ngôn ngữ 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 C++ rất phù hợp để rèn luyện cho học sinh hiểu sâu về thuật toán cũng như phân tích, đánh giá chính xác hiệu suất thuật toán. Bên cạnh đó C++ cũng là một NNLT đang được sử dụng phổ biến hiện nay trong việc thiết kế, xây dựng các phần mềm ứng dụng thực tiễn. - Thư viện C++ có nhiều cấu trúc dữ liệu khác nhau cho học sinh linh hoạt lựa chọn cấu trúc phù hợp để lưu trữ và xử lý bài toán của mình. Bên cạnh đó C++ có hệ thống hàm có sẵn rất phong phú như tìm min, max, tính tổng, sắp xếp (với nhiều thuật toán khác nhau), thay thế các phần tử, tìm kiếm (tìm kiếm thường và tìm kiếm nhị phân)… Do đó tiết kiệm thời gian và tăng tốc độ viết code lên rất nhiều. - Và đặc biệt tốc độ thực thi chương trình rất nhanh do C++ sử dụng trình biên dịch, thời gian thực thi và thời gian biên dịch chương trình viết bằng ngôn ngữ C++ được đánh giá nhanh hơn bất kỳ ngôn ngữ lập trình nào khác. Đây là một tiêu chí cực kỳ quan trọng trong lập trình thi đấu cũng như trong các kỳ thi học sinh giỏi các cấp. Từ những ưu điểm trên mà ngôn ngữ C++ là lựa chọn hàng đầu trong lập trình thi đấu. 4
2. Độ phức tạp của thuật toán Khi chúng ta đánh giá độ phức tạp của một thuật toán nghĩa là chúng ta đang tìm ra một đánh giá về thời gian và không gian cần thiết để thực hiện thuật toán đó. Không gian ở đây được hiểu là các yêu cầu về bộ nhớ, thiết bị lưu trữ, … của máy tính để thuật toán có thể làm việc. Việc xem xét về không gian của thuật toán phụ thuộc phần lớn vào cách tổ chức dữ liệu của thuật toán. Ðánh giá về thời gian thực hiện thuật toán không phải là xác định thời gian tuyệt đối (chạy thuật toán mất bao nhiêu giây, bao nhiêu phút, …) để thực hiện thuật toán mà là xác định mối liên quan giữa dữ liệu đầu vào (input) của thuật toán và chi phí (số thao tác, số phép tính cộng, trừ, nhân, chia, căn, …) để thực hiện thuật toán. Sở dĩ người ta không quan tâm đến thời gian tuyệt đối của thuật toán vì thời gian chạy chương trình phụ thuộc vào rất nhiều yếu tố như: cấu hình máy tính, ngôn ngữ sử dụng, trình biên dịch, dữ liệu đầu vào, …Một cách tổng quát, thời gian thực hiện thuật toán là một hàm số phụ thuộc vào dữ liệu đầu vào T = f(input). Việc xây dựng một hàm T tổng quát trong mọi trường hợp của thuật toán là một việc rất khó khăn, nhiều lúc không thể thực hiện được. Chính vì vậy mà người ta chỉ xây dựng hàm T cho một số trường hợp đáng chú ý nhất của thuật toán, thường là trường hợp tốt nhất, xấu nhất hoặc trung bình. Đối với các bài toán xử lý số nguyên lớn, nếu như chúng ta sử dụng theo cách thông thường thì độ phức tạp sẽ rất lớn, sẽ không đảm bảo thời gian 1 giây mà các cuộc thi lập trình yêu cầu. II. THỰC TRẠNG 2.1. Thực trạng trước khi thực hiện các giải pháp sáng kiến Trong các kỳ thi lập trình, khi gặp các bài toán xử lý số nguyên lớn, học sinh có thể giải quyết bài toán với nhiều cách khác nhau nhưng để đảm bảo theo yêu cầu của đề và chạy 1 giây theo dữ liệu đề thì hầu như học sinh không thực hiện được. Vậy làm thế nào để có thể giải quyết bài toán tối ưu nhất? Có các giải pháp nào cho các bài toán đó? 2.2. Thực trạng trong dạy học đội tuyển học sinh giỏi 2.2.1. Những nguyên tắc cơ bản trong công tác bồi dưỡng học sinh giỏi môn Tin học. Bồi dưỡng học sinh giỏi là nhiệm vụ mũi nhọn quan trọng trong trường phổ thông. Để đạt kết quả tốt trong công tác bồi dưỡng học sinh giỏi môn Tin học yêu cầu mỗi giáo viên phải có trình độ chuyên môn vững vàng, kĩ năng ngôn ngữ, tổ 5
chức hợp lí các hoạt động dạy học, xử lí linh hoạt, sáng tạo các tình huống có vấn đề trong từng tiết học. Bằng những kiến thức, giáo viên bồi dưỡng cho học sinh một cách có hệ thống giúp học sinh có tình cảm đúng đắn đối với môn học. Ngược lại, tình cảm yêu mến môn học giúp các em có ý thức cao hơn trong quá trình bồi dưỡng. Các kỹ năng dạy học của tương lai sẽ bao gồm khả năng phát triển việc đổi mới phương pháp sử dụng công nghệ để cải thiện môi trường học tập, trợ giúp việc chiếm lĩnh tri thức, đào sâu tri thức và tạo lập tri thức. Việc học tập bồi dưỡng nghề nghiệp của giáo viên sẽ là thành phần quyết định cho sự tiến bộ giáo dục. Trong quá trình dạy học, hoạt động học đóng vai trò chủ đạo. Học sinh tự giác, tự lực tiếp thu kiến thức dưới tác động của giáo viên. Thông qua vai trò của người giáo viên, học sinh phát huy được tính tự giác, tích cực, ham mê tìm kiếm thức mới. Đảm bảo tính khoa học với tính vừa sức: đây là một nguyên tắc vô cùng quan trọng khi bồi dưỡng học sinh giỏi. Bởi yêu cầu, nhiệm vụ học tập phải phù hợp với trí tuệ học sinh. Dạy học phù hợp khả năng, năng lực, trình độ phát triển của đối tượng học sinh, đảm bảo học sinh đều được phát triển ở mức cao nhất. Những kiến thức chúng ta truyền tải đến học sinh phải được học sinh tiếp thu trên cơ sở phát huy hết khả năng của mình. Bồi dưỡng học sinh giỏi không phải là dạy những bài quá khó, những lý luận xa vời mà phải bắt đầu từ dạy chuẩn kiến thức, kỹ năng theo khung chương trình giới hạn mà kế hoạch của Sở Giáo dục đã ban hành từng khối lớp. Trên cơ sở chuẩn kiến thức, giáo viên có thể mở rộng, khắc sâu kiến thức cho học sinh. Nếu đưa những kiến thức quá cao đối với các em, các em không những không hiểu mà còn dẫn đến việc chán học, lâu dần các em sẽ cảm thấy quá áp lực, xa vời không hứng thú với việc bồi dưỡng học sinh giỏi. Hoặc nếu chỉ dừng lại ở việc cung cấp kiến thức theo chuẩn thì khó có học sinh giỏi và không phát huy được tính sáng tạo, tích cực học tập của học sinh. 2.2.2. Thực trạng về công tác bồi dưỡng học sinh giỏi môn Tin học ở trường THPT a. Về phía học sinh Có thể thấy công tác bồi dưỡng HSG Tin học ở các trường THPT hiện nay đang gặp một số khó khăn nhất định đó là công tác tuyển chọn học sinh bồi dưỡng, xây dựng chương trình, nội dung bồi dưỡng, quy trình bồ i dưỡng giả ng da ̣y, tà i liê ̣u bồ i dưỡng, công tá c kiể m tra, kiể m đinh chấ t lương... Bởi lẽ trong thực tế, theo ̣ ̣ quan niệm sai lầm của một số người: môn Toán, Văn, Ngoại ngữ mặc nhiên được coi là “chính”, các môn khác bị coi là “phụ”, riêng môn Tin học là “rất phụ”. Quan niệm “chính” - “phụ” không chỉ có ở phụ huynh, mà còn có trong cả người học, thậm chí ngay cả trong đội ngũ giáo viên. 6
Thực tế đã có nhiều trường hợp xảy ra đối với bản thân tôi và các đồng nghiệp khác trong quá trình lấy danh sách đội tuyển tham gia học sinh giỏi. Học sinh khi được giáo viên chọn thi môn Tin học tỏ ra không thích, đang còn dè chừng. Có học sinh đã nhận lời với giáo viên rồi nhưng vì đây không phải là môn khối, tâm lí thi môn này không bằng các môn Toán, Lí, Hóa,... nên các em đã từ chối sau khi tham gia một thời gian. Còn có những trường hợp phụ huynh khi biết con được giáo viên chọn đi thi môn Tin học phụ huynh cũng đã có phản ứng liền là không đồng ý vì sợ mất thời gian và làm ảnh hưởng đến các môn khối. Ngay cả trong đội ngũ giáo viên cũng có những người có sự tác động đến học sinh của mình không muốn cho tham gia thi môn Tin học. Cuối cùng đội tuyển môn tin học chỉ tuyển chọn được những học sinh còn sót lại của các môn như Toán, Lí, Hóa, Sinh, Anh,….. Ngoài ra học sinh đa số đã làm quen với ngôn ngữ Pacal, nên khi chuyển sang ngôn ngữ C++ các em còn bỡ ngỡ. Tài liệu để các em tham khảo còn rất hạn chế. b. Về phía giáo viên - Giáo viên dạy bồi dưỡng vừa phải bảo đảm chất lượng đại trà, vừa phải hoàn thành chỉ tiêu chất lượng mũi nhọn và công tác kiêm nhiệm do đó cường độ làm việc quá tải và việc đầu tư cho công tác bồi dưỡng HSG cũng có phần bị hạn chế. - Giáo viên dạy bồi dưỡng đều phải tự soạn chương trình dạy, theo kinh nghiệm của bản thân, tự nghiên cứu, tự sưu tầm tài liệu. - Học sinh học chương trình chính khóa phải học quá nhiều môn, lại phải học thêm nhiều môn khác, cộng thêm chương trình bồi dưỡng HSG nên rất hạn chế về thời gian tự học. Các em đầu tư ít thời gian cho việc học bồi dưỡng HSG, do đó kết quả không cao là điều tất yếu. - Sau các kỳ thi học sinh giỏi môn Tin thường không có đáp án. Nếu có đáp án tham khảo thì việc đọc và hiểu được đáp án cũng rất khó do đáp án thường không có ý tưởng thuật toán kèm theo. Thực tế, qua các kỳ thi HSG tỉnh Nghệ An đã có rất nhiều học sinh, giáo viên khó hiểu khi bài thi làm đúng nhưng điểm thi vẫn rất thấp và sự khó hiểu đó vẫn cứ kéo dài do đáp án tham khảo và test chấm ít được công bố. Khó khăn lớn nhất là nhà một số em trong đội tuyển bồi dưỡng học sinh giỏi chưa có máy tính để học ở nhà, vì thế giáo viên bồi dưỡng tin học phải nghĩ cách để các em có được công cụ học tập càng sớm càng tốt. Bằng cách mượn những bộ máy của đồng nghiệp mình. Có những em gia đình lại hết sức khó khăn không thể động viên gia đình học sinh mua máy tính được thì chính viên bồi dưỡng phải tự mua những máy vi tính cũ để các em có phương tiện học tập. 7
III. BIỆN PHÁP 1. CÁC PHÉP TOÁN XỬ LÍ SỐ NGUYÊN LỚN 1.1. Biểu diễn số nguyên lớn Thông thường người ta sử dụng các cách biểu diễn số nguyên lớn sau: * Xâu kí tự hoặc mảng xâu: Đây là cách biểu diễn tự nhiên và đơn giản nhất, mỗi ký tự của một xâu tương ứng với một chữ số của số nguyên lớn tính từ trái qua phải. * Mảng các số: Sử dụng mảng lưu các chữ số (hoặc nhóm chữ số), và một biến ghi nhận số chữ số để thuận tiện trong quá trình xử lí. * Danh sách liên kết các số: Sử dụng danh sách liên kết các chữ số (hoặc một nhóm chữ số), cách làm này sẽ linh hoạt hơn trong việc sử dụng bộ nhớ. 1.2. Các phép toán xử lí số nguyên lớn a. Khai báo số lớn. -. Khai báo theo kiểu xâu: Ta đã biết xâu có thể được hiểu như là mảng có thể chứa hàng triệu ký tự. - Khai báo theo kiểu mảng: Coi mỗi phần tử trong mảng là một kí tự. Để dễ dàng trong việc xử lý, ở đây chúng tôi sẽ sử dụng cách dùng theo kiểu xâu. Chúng ta sẽ định nghĩa số lớn là bignum #define bignum string bignum X,Y; // xâu X,Y kiểu bignum b. So sánh 2 số lớn. * Phân tích thuật toán Ở đây ta dùng 3 phép toán >, < = Cho bài toán: so sánh 2 số nguyên lớn X và Y. Nếu X>Y cho kết quả 1; X=Y cho kết quả 0; X
- Bước 2: So sánh hai chuỗi sử dụng trực tiếp các toán tử >,
* Hàm cộng xâu d. Trừ 2 số nguyên lớn (Trừ số lớn cho số bé) * Phân tích thuật toán Bước 1: Chuẩn hóa hai xâu X, Y để có độ dài bằng nhau. Nếu xâu nào có độ dài ngắn hơn thì thêm các ‘0’ vào đầu xâu đó. Bước 2: Duyệt từ cuối hai xâu về đầu xâu: + Tạo xâu kết quả Z=X; + Tách từng phần tử của hai xâu chuyển sang kiểu số + Tính hiệu: hiệu = số 1 – số 2 - mượn (ban đầu mượn bằng 0); Nếu hiệu0 thì mượn =0; + Chuyển đổi giá trị hiệu tính được sang ký tự rồi gán vào xâu kết quả. + Xử lý xâu kết quả nếu xâu có độ dài lớn hơn 1 mà phần tử đầu tiên của mảng xâu là ‘0’. 10
* Hàm trừ xâu e. Nhân một số nguyên lớn với một nguyên số nhỏ * Phân tích thuật toán Bước 1: Duyệt từ cuối xâu số lớn về đầu xâu Bước 2: + Tách từng phần tử của xâu chuyển sang kiểu số và tính tích tích = số nhỏ * tg + nhớ (tg là số được tách từ xâu số lớn); nhớ = tích /10; Tích = tích % 10; + Chuyển đổi giá trị tích tính được sang ký tự rồi gán vào xâu kết quả. + Lưu ý cộng thêm giá trị nhớ lần cuối nếu nhớ khác ‘0’ * Hàm nhân xâu 11
g. Nhân 2 số nguyên lớn * Phân tích thuật toán - Duyệt từ cuối xâu X về đầu xâu. - Tách từng phần tử của xâu X nhân với xâu Y (Thuật toán nhân với số nhỏ) - Cộng liên tiếp các kết quả thu được (lưu ý trước khi cộng 2 xâu thêm ký tự “0” vào sau xâu thứ 2) - Xử lý các ký tự ‘0’ trước xâu xau khi cộng. * Hàm nhân 2 số nguyên lớn h. Chia số nguyên lớn cho số nguyên nhỏ * Phân tích thuật toán Bước 1: Duyệt từ đầu xâu số nguyên lớn Bước 2: + Tách từng phần tử của xâu đem chia cho số nguyên nhỏ chia = số + dư * 10 (dư ban đầu bằng 0); thương= chia / số nhỏ; dư = chia % 10; + Cộng liên tiếp các thương được phần nguyên + Lưu lại giá trị dư cuối cùng được phần dư + Lưu ý: ở đây ta chỉ xét chia lấy phần nguyên 12
* Hàm chia xâu h. Chia hai số nguyên lớn * Phân tích thuật toán - Lấy số ký tự của xâu X bằng số ký tự của xâu Y lưu vào xâu chia - Chừng nào số xâu chia còn lớn hơn xâu Y thì tiến hành trừ liên tiếp xâu chia cho xâu Y, ghi lại số lần trừ có thể là thương tìm được - Hạ từng ký tự của xâu X xuống xâu chia - Lưu ý: ở đây chúng tôi chỉ xét trường hợp chia lấy phần nguyên. * Hàm chia xâu 13
2. BÀI TẬP VẬN DỤNG 2.1. Số FIBONACI Tên file: FIBONACI.CPP a. Bài toán: Dãy fibonaci là dãy số được xây dựng như sau: F1 = F2 = 1 Fi = Fi-1 + Fi-2 với i >= 3 Ví dụ: 1 1 2 3 5 8 13 21 34 55 89 .... Cho số nguyên dương N (1
2.2. Tổng FIBONACI Tên file: SUMFIBO.CPP a. Bài toán. Cho số nguyên dương N (N≤10100). Hãy phân tích N thành tổng của ít nhất các số Fibonaci? Input: SUMFIBO.INP:  Một dòng duy nhất chứa số nguyên dương N Output: SUMFIBO.OUT:  Đưa ra một dãy ít nhất các số nguyên Fibonaci (theo thứ tự tăng dần) sao cho tổng của chúng bằng N Ví dụ: SUMFIBO.INP SUMFIBO.OUT 8 8 9 18 b. Thuật toán. Bước 1. Tạo ra dãy số FIB gồm các số không vượt quá N Bước 2. Lặp lại bước 2.1 và 2.2 sau cho đến khi N=0 2.1. Tìm số FIB[i] lớn nhất nhỏ hơn N 2.2. Tách N theo FIB[i] 15
c. Chương trình 16
2.3. Chuyển cơ số. a. Bài toán Cho s là một xâu mô tả số nguyên không âm ở hệ cơ số a, hãy chuyển số đó sang hệ cơ số b (1
c. Chương trình 18
19