Sáng kiến kinh nghiệm THPT: Giúp học sinh rèn luyện và nâng cao kĩ năng lập trình qua việc lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán

Chia sẻ: Hương Hoa Cỏ Mới | Ngày: | Loại File: PDF | Số trang:47

Thêm vào BST

Báo xấu

33
lượt xem 5
download

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

Mục tiêu nghiên cứu của sáng kiến kinh nghiệm là nêu ra các định hướng giúp học sinh có thể lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán trong một số dạng bài toán quen thuộc trên ngôn ngữ lập trình C++. Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT hoặc thi vào các trường chuyên.

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: Giúp học sinh rèn luyện và nâng cao kĩ năng lập trình qua việc lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán

Së GIÁO DỤC VÀ ĐÀO TẠO NGHỆ AN TRƯỜNG THPT NGUYỄN DUY TRINH ---***--- SÁNG KIẾN KINH NGHIỆM “GIÚP HỌC SINH RÈN LUYỆN VÀ NÂNG CAO KỸ NĂNG LẬP TRÌNH QUA VIỆC LỰA CHỌN THUẬT TOÁN TỐI ƯU PHÙ HỢP VỚI DỮ LIỆU BÀI TOÁN” MÔN: TIN HỌC GIÁO VIÊN: NGUYỄN THỊ TÚ ANH TỔ: TOÁN TIN NĂM HỌC: 2020 – 2021 ĐT: 0942797783 NGHI LỘC, THÁNG 3/2021 1
MỤC LỤC I. ĐẶT VẤN ĐỀ ................................................................................................................. 3 1. Lý do chọn đề tài ............................................................................................................. 3 2. Mục đích nghiên cứu của SKKN..................................................................................... 3 3. Nhiệm vụ nghiên cứu của SKKN .................................................................................... 4 4. Đối tượng nghiên cứu của SKKN ................................................................................... 4 6. Phương pháp thực hiện .................................................................................................... 4 7. Đóng góp của SKKN ....................................................................................................... 4 II. NỘI DUNG .................................................................................................................... 5 1. Cơ sở lí luận của đề tài .................................................................................................... 5 2. Thực trạng của vấn đề trước khi áp dụng SKKN ............................................................ 5 2.1. Đặc điểm tình hình ................................................................................................... 5 2.2. Thực trạng trước khi nghiên cứu .............................................................................. 6 3. Các giải pháp giải quyết vấn đề ....................................................................................... 6 3.1. Cơ sở lý thuyết.......................................................................................................... 7 3.1.1. Độ phức tạp thuật toán ...................................................................................... 7 3.1.1.1. Tính hiệu quả của thuật toán ...................................................................... 7 3.1.1.2. Tại sao cần thuật toán có tính hiệu quả? .................................................... 7 3.1.1.3. Đánh giá thời gian thực hiện thuật toán ..................................................... 8 3.1.1.4. Các quy tắc đánh giá thời gian thực hiện thuật toán .................................. 9 3.1.1.5. Ước lượng độ phức tạp thuật toán tương ứng với độ lớn dữ liệu............. 10 3.1.2. Lựa chọn thuật toán ......................................................................................... 11 3.2. Lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán ....................................... 11 3.2.1. Dạng 1: Các bài toán liên quan đến số học ..................................................... 12 3.2.2. Dạng 2: Sử dụng thuật toán sắp xếp ............................................................... 20 3.2.2.1. Bài toán sắp xếp........................................................................................ 20 3.2.2.2. Bài tập ví dụ.............................................................................................. 23 3.2.3. Dạng 3: Sử dụng thuật toán tìm kiếm............................................................. 32 3.2.3.1. Bài toán tìm kiếm ..................................................................................... 32 3.2.3.2. Bài tập ví dụ.............................................................................................. 34 3.2.4. Bài tập luyện tập .............................................................................................. 40 4. Tính mới của SKKN ...................................................................................................... 43 5. Hiệu quả của SKKN ...................................................................................................... 44 6. Những hướng phát triển của đề tài ................................................................................ 44 III. KẾT LUẬN VÀ KIẾN NGHỊ .................................................................................. 45 1. Kết luận.......................................................................................................................... 45 2. Kiến nghị ....................................................................................................................... 45 TÀI LIỆU THAM KHẢO............................................................................................... 46 2
I. ĐẶT VẤN ĐỀ 1. Lý do chọn đề tài Khi giải các bài toán Tin học người lập trình luôn mong muốn viết chương trình với thuật toán tối ưu để có thể giải với dữ liệu lớn, thời gian thực hiện nhanh, bộ nhớ hạn chế…Tuy nhiên, bài toán Tin học thường đa dạng, phong phú nên để có thể tìm được thuật toán tối ưu phù hợp dữ liệu bài toán là việc không hề dễ dàng. Đây là vấn đề nhiều giáo viên gặp khó khăn trong việc giảng dạy học sinh học lập trình, cũng như công tác ôn thi học sinh giỏi để đạt kết quả cao. Ở trường phổ thông hàng năm thường diễn ra các cuộc thi học sinh giỏi các môn học trong đó có môn Tin học. Bồi dưỡng học sinh giỏi là một nhiệm vụ rất cần thiết và quan trọng đối với mỗi giáo viên. Do đó, việc nghiên cứu, tìm tòi, tích lũy kiến thức là công việc thường nhật của mỗi giáo viên nhằm nâng cao trình độ chuyên môn nghiệp vụ, tích lũy kinh nghiệm cho bản thân.Trong những năm gần đây mức độ yêu cầu của đề thi học sinh giỏi ngày càng nâng cao, môn Tin học cũng vậy. Các bài toán trong đề thi thường yêu cầu giải quyết dữ liệu vào lớn trong khi đòi hỏi thời gian thực hiện nhanh (thường không quá 1 giây). Những bài toán này thường khó đối với học sinh, chương trình của các em thường không thực hiện được hết các test yêu cầu, đặc biệt là đối với học sinh không chuyên. Bởi vì vừa giải quyết vấn đề dữ liệu, vừa phải giải quyết vấn đề thời gian. Do đó giáo viên bồi dưỡng thường phải giúp học sinh rèn luyện kĩ năng lập trình. Nghĩa là không chỉ dừng lại ở việc hướng dẫn học sinh giải được bài toán, mà còn phải giúp học sinh rèn luyện được thói quen tư duy, cải tiến thuật toán để chương trình tối ưu nhất có thể. Trong lập trình tin học đã có rất nhiều phương pháp giải các bài toán đã được nêu ra. Tuy nhiên rất ít tài liệu trình bày cụ thể về cách lựa chọn thuật toán thế nào sao cho phù hợp với dữ liệu bài toán để đạt độ tối ưu, đảm bảo giải quyết được yêu cầu của bài toán đặt ra. Qua quá trình giảng dạy, học tập, tìm tòi và đặc biệt là tham gia bồi dưỡng học sinh giỏi nhiều năm qua, tôi đã tích lũy được một số kinh nghiệm về vấn đề này. Do đó, tôi quyết định viết sáng kiến kinh nghiệm: “Giúp học sinh rèn luyện và nâng cao kĩ năng lập trình qua việc lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán” 2. Mục đích nghiên cứu của SKKN - SKKN nêu ra các định hướng giúp học sinh có thể lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán trong một số dạng bài toán quen thuộc trên ngôn ngữ lập trình C++ . - Từ đó bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, đồng thời rèn luyện và nâng cao kĩ năng lập trình cho các em. Đặc biệt là học sinh tham gia dự thi học sinh giỏi cấp tỉnh THCS, THPT hoặc thi vào các trường chuyên. 3
3. Nhiệm vụ nghiên cứu của SKKN - SKKN phân tích các thuật toán trong các dạng toán quen thuộc, so sánh độ phức tạp thuật toán và định hướng lựa chọn thuật toán tối ưu trong các trường hợp dữ liệu cụ thể nhằm giải bài toán hiệu quả nhất. - Minh họa bằng các ví dụ cụ thể, liên hệ các đề thi vào trường chuyên, đề thi học sinh giỏi tỉnh thời gian qua. 4. Đối tượng nghiên cứu của SKKN - Độ phức tạp thuật toán và giải pháp lựa chọn thuật toán tối ưu trong các dạng bài toán quen thuộc trên ngôn ngữ lập trình C++. - Phương pháp bồi dưỡng năng lực giải quyết vấn đề cho học sinh 5. Phạm vi nghiên cứu của SKKN - Chương trình Tin học THCS, THPT để bồi dưỡng học sinh giỏi Tin học và thi vào trường chuyên THPT. - Cách giải quyết vấn đề của học sinh. 6. Phương pháp thực hiện - Nghiên cứu tài liệu - Thực hiện bồi dưỡng học sinh giỏi - Trao đổi chuyên môn với bạn bè, đồng nghiệp để giải quyết vấn đề - Thực nghiệm sư phạm. 7. Đóng góp của SKKN - Sáng kiến trình bày được một số kinh nghiệm giúp học sinh rèn luyện và nâng cao kĩ năng lập trình qua việc lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán yêu cầu của các dạng bài toán quen thuộc, thường có trong các đề thi học sinh giỏi Tin học. - Là tài liệu tham khảo để bồi dưỡng học sinh giỏi Tin học, học sinh thi trường chuyên có hiệu quả. - Giúp bồi dưỡng học sinh năng lực giải quyết vấn đề trong giải toán Tin học, rèn luyện và nâng cao kỹ năng lập trình cho học sinh. 4
II. NỘI DUNG 1. Cơ sở lí luận của đề tài Nghị quyết hội nghị Trung ương VIII khóa XI đã nêu: “Đối với giáo dục phổ thông tập trung phát triển trí tuệ, thể chất, hình thành phẩm chất, năng lực công dân, phát hiện và bồi dưỡng năng khiếu, định hướng nghề nghiệp cho học sinh. Nâng cao chất lượng giáo dục toàn diện, chú trọng giáo dục lý tưởng truyền thống đạo đức, lối sống, ngoại ngữ, tin học, năng lực và kỹ năng thực hành, vận dụng kiến thức vào thực tiễn, phát triển khả năng sáng tạo và tự học, khuyến khích học tập suốt đời". Toàn ngành đang ra sức phấn đấu xây dựng chương trình sách giáo khoa mới, đổi mới phương pháp dạy học theo định hướng hình thành và phát triển năng lực. Mục tiêu của môn Tin học trong chương trình giáo dục phổ thông là giúp học sinh hình thành và phát triển năng lực Tin học, đổi mới phương pháp dạy học nhằm góp phần thực hiện tốt mục tiêu của ngành giáo dục trong giai đoạn mới. Môn Tin học là môn học đặc thù có nhiều kiến thức khó. Đặc biệt là phần học lập trình ở lớp 11. Đây cũng là phần kiến thức đề thi học sinh giỏi tỉnh môn Tin học. Trong một số năm gần đây do sự phát triển nhanh chóng của khoa học kỹ thuật, tốc độ xử lí của máy tính ngày càng cao. Các đề thi trong các cuộc thi lập trình cũng ngày càng đòi hỏi cao hơn về thời gian thực hiện, về độ lớn dữ liệu…Nên gây rất nhiều khó khăn trong việc ôn luyện cho thầy và trò. Một trong những vấn đề luôn đặt ra là làm thế nào để lựa chọn được thuật toán tối ưu đảm bảo đáp ứng toàn bộ yêu cầu dữ liệu vào của bài toán. Do đó đòi hỏi giáo viên cần có giải pháp để giúp học sinh giải quyết vấn đề này nhằm nâng cao chất lượng công tác bồi dưỡng học sinh giỏi bộ môn Tin học hiện nay. 2. Thực trạng của vấn đề trước khi áp dụng SKKN 2.1. Đặc điểm tình hình * Thuận lợi: - Với sự phát triển nhanh của ngành công nghệ thông tin, máy tính ngày càng có tốc độ xử lý cao đáp ứng được yêu cầu xử lý các bài toán có dữ liệu lớn trong thời gian thực hiện ngắn. - Học sinh và giáo viên có thể dễ dàng tìm hiểu nguồn tài liệu để học tập tham khảo. * Khó khăn: - Những kiến thức trong chương trình Tin học phổ thông còn hạn chế hoặc không đủ đáp ứng cho việc giải một số bài toán trong các kỳ thi học sinh giỏi Tỉnh khi có yêu cầu dữ liệu lớn cùng thời gian thực hiện ngắn. - Các tài liệu tổng hợp các cách để giải quyết các bài toán yêu cầu cao như vậy chưa có nhiều để học sinh tham khảo, ôn luyện. 5
2.2. Thực trạng trước khi nghiên cứu Với sự phát triển nhanh về tốc độ của máy tính hiện nay thì đề thi học sinh giỏi Tin học cũng đòi hỏi ngày càng nâng cao hơn. Đặc biệt về mặt thời gian thực hiện và độ lớn của dữ liệu đầu vào. Đa số giáo viên gặp khó khăn trong việc hướng dẫn học sinh giải bài toán thế nào để đạt được trọn vẹn yêu cầu của bài toán. Những năm trước đây khi bồi dưỡng học sinh thi học sinh giỏi tỉnh tôi cũng đã chú trọng nhiều hơn đến cải tiến chương trình tối ưu, tuy nhiên hiệu quả mang lại chưa cao. Nguyên nhân chủ yếu của thực trạng này là giáo viên chưa có phương pháp giảng dạy phù hợp với vấn đề này. Cụ thể giáo viên thường giúp học sinh cải tiến, làm mịn dần thuật toán của từng bài cụ thể. Chưa phân loại thành các dạng bài, định hướng học sinh đánh giá thuật toán và cải thiện thuật toán nhưng chưa ước lượng với mỗi mức dữ liệu thì cần phải xây dựng thuật toán có độ phức tạp tương ứng như thế nào để có thể đáp ứng được…Chính vì vậy, học sinh thường cố gắng tinh chỉnh, tìm cách giải tối ưu nhưng lại không chắc chắn rằng bài giải của mình đã đáp ứng trọn vẹn dữ liệu yêu cầu của bài toán hay chưa. Cho nên học sinh sẽ gặp khó khăn trong việc vận dụng vào các bài toán tương tự, cũng như không linh hoạt trong các bài toán mới. Kết quả là học sinh vẫn giải được các bài toán nhưng không đạt điểm số cao nên thường chỉ đạt giải khuyến khích trở xuống. Vì vậy, tôi vẫn luôn duy trì hướng dẫn, uốn nắn các em biết cách giải bài, rồi rèn luyện kĩ năng tinh chỉnh, làm mịn dần thuật toán, kết hợp biết cách nhận biết độ lớn dữ liệu bài toán và lựa chọn thuật toán phù hợp để đạt hiệu quả nhất. Trong quá trình giảng dạy tôi còn cho học sinh kiểm chứng qua đánh giá của phần mềm Themis để dễ dàng so sánh và ghi nhớ. Từ đó đạt hiệu quả cao hơn. 3. Các giải pháp giải quyết vấn đề Có những bài toán nhiều khi có vẻ đơn giản, đa số học sinh có thể giải được nhưng khi thực hiện với dữ liệu lớn thì không đáp ứng được thời gian yêu cầu hoặc không thể thực hiện được tất cả các test yêu cầu. Lúc này đòi hỏi phải tìm được thuật toán tối ưu nhất. Tối ưu hoá là một đòi hỏi thường xuyên trong quá trình giải quyết các bài toán tin học. Tối ưu hoá thuật toán là một công việc yêu cầu tư duy thuật toán rất cao, cùng với khả năng sử dụng thuần thục các cấu trúc dữ liệu. Vì vậy, việc tìm ra thuật toán tối ưu là không dễ chút nào. Tối ưu hoá thường được tiến hành theo 2 góc độ đó là tối ưu theo không gian có nghĩa là tối ưu không gian lưu trữ (bộ nhớ), và tối ưu theo thời gian có nghĩa là giảm độ phức tạp thuật toán, giảm các bước xử lý trong chương trình…Tuy nhiên không phải lúc nào ta cũng có thể đạt được đồng thời cả 2 điều đó, trong nhiều trường hợp tối ưu về thời gian sẽ làm tăng không gian lưu trữ, và ngược lại. Bài toán trong Tin học thì đa dạng, phong phú. Đa số giáo viên gặp khó khăn trong việc hướng dẫn học sinh thiết kế thuật toán hoặc lựa chọn thuật toán nào để có thể giảm độ phức tạp của thuật toán, đồng thời phù hợp với dữ liệu và yêu cầu của đề bài. Đa số khi chấm bài, dùng test chấm mới biết được chương trình đáp 6
ứng được bao nhiêu test so với yêu cầu của đề ra. Điều này chỉ thực hiện được khi ôn luyện cho các em, còn khi các em đi thi thì không tự ước lượng được bài làm đạt kết quả thế nào. Có một cách để ước lượng được chương trình giải được có thể đáp ứng được yêu cầu của đề hay không (nghĩa là đáp ứng được khoảng dữ liệu vào bao nhiêu), đó là đánh giá độ phức tạp của thuật toán trong chương trình. Như vậy để có thể tối ưu hóa thuật toán trước tiên chúng ta phải hiểu rõ về độ phức tạp của thuật toán và cách đánh giá ước lượng thuật toán so với dữ liệu đầu vào yêu cầu. 3.1. Cơ sở lý thuyết 3.1.1. Độ phức tạp thuật toán 3.1.1.1. Tính hiệu quả của thuật toán Khi giải một bài toán, chúng ta cần chọn trong số các thuật toán một thuật toán mà chúng ta cho là “tốt” nhất. Vậy dựa trên cơ sở nào để đánh giá thuật toán này “tốt” hơn thuật toán kia? Thông thường ta dựa trên hai tiêu chuẩn sau: 1. Thuật toán đơn giản, dễ hiểu, dễ cài đặt (dễ viết chương trình). 2. Thuật toán hiệu quả: Chúng ta thường đặc biệt quan tâm đến thời gian thực hiện của thuật toán (gọi là độ phức tạp tính toán), bên cạnh đó chúng ta cũng quan tâm tới dung lượng không gian nhớ cần thiết để lưu giữ các dữ liệu vào, ra và các kết quả trung gian trong quá trình tính toán. Khi viết chương trình chỉ để sử dụng một số ít lần thì tiêu chuẩn (1) là quan trọng, nhưng nếu viết chương trình để sử dụng nhiều lần, cho nhiều người sử dụng thì tiêu chuẩn (2) lại quan trọng hơn. Trong trường hợp này, dù thuật toán có thể phải cài đặt phức tạp, nhưng ta vẫn sẽ lựa chọn để nhận được chương trình chạy nhanh hơn, hiệu quả hơn. 3.1.1.2. Tại sao cần thuật toán có tính hiệu quả? Kĩ thuật máy tính tiến bộ rất nhanh, ngày nay các máy tính lớn có thể đạt tốc độ tính toán hàng nghìn tỉ phép tính trong một giây. Vậy có cần phải tìm thuật toán hiệu quả hay không? Chúng ta xem ví dụ bài toán kiểm tra tính nguyên tố của một số nguyên dương n (n ≥ 2). bool is_prime(int n) { for(int k=2;k
Dễ dàng nhận thấy rằng, nếu n là một số nguyên tố chúng ta phải mất n- 2 phép toán chia lấy dư (%). Giả sử một siêu máy tính có thể tính được trăm nghìn tỉ (1014) phép % trong một giây, như vậy để kiểm tra một số khoảng 25 chữ số mất khoảng ~ 3170 năm . Trong khi đó, nếu ta có nhận xét việc thử k từ 2 đến n - 1 là không cần thiết mà chỉ cần thử k từ 2 đến √𝑛 , ta có: bool is_prime(int n) { for(int k=2;k2) chỉ cần một lần thử chia 2 để kết luận n không phải là số nguyên tố. Nếu n (n>3) không chia hết cho 2 nhưng lại chia hết cho 3 thì cần 2 lần thử (chia 2 và chia 3) để kết luận n không nguyên tố. Còn nếu n là một số nguyên tố thì thuật toán phải thực hiện nhiều lần thử nhất. Trong tài liệu này, chúng ta hiểu hàm số T(n) là thời gian nhiều nhất cần thiết để thực hiện thuật toán với mọi bộ dữ liệu đầu vào cỡ n . Sử dụng kí hiệu toán học ô lớn để mô tả độ lớn của hàm. Giả sử n là một số nguyên dương, T(n) và f(n) là hai hàm thực không âm. Ta viết T(n)= O(f(n)) nếu và chỉ nếu tồn tại các hằng số dương c và n0 , sao cho T(n)≤ c x f(n), mọi n ≥ n0. Nếu một thuật toán có thời gian thực hiện T(n)= O(f(n)) chúng ta nói rằng thuật toán có thời gian thực hiện cấp f(n). 8
Ví dụ: Giả sử T(n) = n2 + 2n, ta có n2 + 2n ≤ 3n2 với mọi n ≥ 1. Vậy T(n) = O(n2) trong trường hợp này ta nói thuật toán có thời gian thực hiện cấp n2. 3.1.1.4. Các quy tắc đánh giá thời gian thực hiện thuật toán Để đánh giá thời gian thực hiện thuật toán được trình bày bằng ngôn ngữ C++, ta cần biết cách đánh giá thời gian thực hiện các câu lệnh của C++ Trước tiên, chúng ta hãy xem xét các câu lệnh chính trong C++. Các câu lệnh trong C++ được định nghĩa như sau: 1. Các phép gán, đọc, viết là các câu lệnh (được gọi là lệnh đơn). 2. Nếu S1, S2, ..., Sm là câu lệnh thì { S1; S2; …; Sm; } là câu lệnh (được gọi là lệnh hợp thành hay khối lệnh). 3. Nếu S1 và S2 là các câu lệnh và E là biểu thức lôgic thì If (E) S1; else S2; là câu lệnh (được gọi là lệnh rẽ nhánh hay lệnh If). 4. Nếu S là câu lệnh và E là biểu thức lôgic thì While (E) S; là câu lệnh (được gọi là lệnh lặp điều kiện trước hay lệnh While). 5. Nếu S1, S2,…,Sm là các câu lệnh và E là biểu thức lôgic thì Do S1; S2; …; Sm; While (E); là câu lệnh (được gọi là lệnh lặp điều kiện sau hay lệnh Do .. While) 6. Nếu S là lệnh, E1 và E2 là các biểu thức cùng một kiểu thứ tự đếm được Thì For (i=E1; i
O((f1(n)), O((f2(n)), …, O((fm(n)). Khi đó thời gian thực hiện của lệnh hợp thành là O(max(f1(n), f2(n), …, fm(n))). 3. Lệnh If: giả sử thời gian thực hiện của S1, S2 tương ứng là Khi đó thời gian thực hiện của lệnh If là: O((f1(n)), O((f2(n)). Khi đó thời gian thực hiện của lệnh If là O(max(f1(n), f2(n))) 4. Lệnh lặp While: giả sử thời gian thực hiện lệnh S (thân của lệnh While) là O(f(n)) và g(n) là số lần lặp tối đa thực hiện lệnh S. Khi đó thời gian thực hiện lệnh While là O(f(n)g(n)). 5. Lệnh lặp Repeat: giả sử thời gian thực hiện khối lệnh { S1; S2;…; Sm; } là O(f(n)) và g(n) là số lần lặp tối đa. Khi đó thời gian thực hiện lệnh Do..While là O(f(n)g(n)). 6. Lệnh lặp For: giả sử thời gian thực hiện lệnh S là O(f(n)) và g(n) là số lần lặp tối đa. Khi đó thời gian thực hiện lệnh For là O(f(n)g(n)). 3.1.1.5. Ước lượng độ phức tạp thuật toán tương ứng với độ lớn dữ liệu Độ phức tạp thuật toán là một hàm phụ thuộc đầu vào. Tuy nhiên trong những ứng dụng thực tiễn, chúng ta không cần biết chính xác hàm này mà chỉ cần biết một ước lượng đủ tốt của chúng. Việc ước lượng rất quan trọng trong việc giải quyết bài toán lập trình thi đấu, đòi hỏi nhanh nhạy và có quyết định chính xác ngay từ đầu. Độ phức tạp của thuật toán có thể có những giá trị là O(1), O(log n), O(n), O(nlogn), O(n2), O(n3)… Và thời gian thực hiện được so sánh như sau: O(1)< O(log n) < O(n) < O(nlogn) < O(n2) < O(n3)… Sau đây là bảng ước lượng (*) giới hạn dữ liệu vào tương ứng với độ phức tạp của thuật toán đảm bảo thực hiện trong thời gian tối đa 1 giây. Độ phức tạp O(1) O(logn) O(n) O(nlogn) O(n2) O(n3) Ước lượng n Không ảnh hưởng 108 4.107 104 500 tối đa thời gian, thường chỉ phụ thuộc giới hạn kiểu dữ liệu Với bảng ước lượng1 này giáo viên có thể hướng dẫn học sinh xác định độ phức tạp của thuật toán phải đạt được để đảm bảo thời gian thực hiện. Từ đó yêu cầu học sinh phải suy luận, tư duy để đạt được yêu cầu của bài toán. Hơn nữa, sau khi hoàn thành chương trình học sinh dù chưa chấm bằng test vẫn có thể dự đoán được kết quả hoàn thành bao nhiêu so với giới hạn yêu cầu của bài toán. 1 Theo https://vnoi.info/wiki/translate/topcoder/Computational-Complexity-Section-1.md 10
3.1.2. Lựa chọn thuật toán Các bước để giải một bài toán trên máy tính: Bước 1: Xác định bài toán Bước 2: Lựa chọn hoặc thiết kế thuật toán Bước 3: Viết chương trình Bước 4: Kiểm thử Bước 5: Viết tài liệu Để có chương trình đúng được thực hiện ở bước 3, 4, 5 thì người lập trình phải làm tốt ở bước 1, 2. Bước 1: Xác định bài toán Là xác định Input, Output của bài toán. Khi xác định Input của bài toán ta quan tâm đến độ lớn của dữ liệu vào vì nó ảnh hưởng nhiều đến việc lựa chọn hoặc thiết kế thuật toán phù hợp ở bước 2. Bước 2: Lựa chọn hoặc thiết kế thuật toán - Trường hợp 1: Trong trường hợp bài toán chưa có cách giải thì ta thiết kế thuật toán. Khi thiết kế thuật toán ngoài yêu cầu đảm bảo tính đúng đắn, còn phải phân tích dữ liệu vào để ước lượng độ phức tạp thuật toán cho phép phù hợp, có thể đảm bảo giải quyết yêu cầu của bài toán. Ví dụ: Dữ liệu vào yêu cầu cỡ 108 thì độ phức tạp của chương trình cho phép tối đa là O(n) - Trường hợp 2: Trong trường hợp bài toán có nhiều cách giải thì lựa chọn thuật toán tối ưu hơn về thời gian thực hiện, bộ nhớ, độ phức tạp… 3.2. Lựa chọn thuật toán tối ưu phù hợp với dữ liệu bài toán Trong giới hạn sáng kiến này tôi muốn trình bày kinh nghiệm về việc hướng dẫn học sinh lựa chọn một thuật toán của những dạng bài toán đã có nhiều thuật toán để giải. Sao cho sự lựa chọn đó phù hợp với độ lớn dữ liệu vào của bài toán để đảm bảo giải quyết bài toán tối ưu, hiệu quả nhất. Từ đó giúp học sinh rèn luyện và nâng cao kĩ năng lập trình. Khi hướng dẫn học sinh làm bài toán mới tôi thường yêu cầu học sinh làm theo các trình tự sau: Bước 1: Xác định bài toán (xác định Input, Output) Bước 2: Xác định đặc điểm dữ liệu (như số lượng phần tử, kiểu dữ liệu của phần tử, độ lớn của phần tử...). Bước 3: So sánh giữa các thuật toán có thể áp dụng cho bài toán (gồm đánh giá độ phức tạp, thời gian thực hiện, khả năng đảm bảo yêu cầu phù hợp với dữ liệu của bài toán). 11
Bước 4: Đánh giá và lựa chọn thuật toán hiệu quả nhất. Bước 5: Cài đặt thuật toán đã lựa chọn bằng ngôn ngữ C++. 3.2.1. Dạng 1: Các bài toán liên quan đến số học Trong nhiều bài toán tin học nếu biết suy luận dựa theo các định lí, công thức, kết quả… của toán học có thể cho ta cách giải rất tối ưu. Những cách giải đó có thể đáp ứng với dữ liệu lớn. Chúng ta xét các ví dụ sau: Ví dụ 1: TỔNG BÌNH PHƯƠNG2 Lại là tính tổng! Cô giáo yêu cầu Thắng phải hoàn thành một bài toán về tính tổng, nhưng do nghỉ phòng chống dịch Covid-19 thời gian dài, Thắng quên kiến thức về lĩnh vực này nên đành nhờ đến tài năng của các bạn với bài toán như sau: Cho số nguyên dương N (N ≤ 105). Yêu cầu: Tính tổng S(N) = 12 + 22 +…+ N2 Dữ liệu vào: Từ tệp văn bản TONGBP.INP gồm:  Dòng đầu chứa số nguyên dương T là số lượng test (T ≤ 105)  T dòng tiếp theo, mỗi dòng là một số nguyên dương N. Kết quả: Ghi ra tệp văn bản TONGBP.OUT gồm T dòng, với mỗi dòng là giá trị tổng S(N) tương ứng. Ví dụ: TONGBP.INP TONGBP.OUT 2 14 3 1015 14 Giải thích: T = 2 (có 2 test): Test 1: N = 3, S(3) = 12 + 22 + 32 = 14 Test 2: N = 14, S(14) = 12 + 22 + … + 142 = 1015 Giới hạn: - 80% số test với 1 ≤ N, T ≤ 103 - 20% số test với 103 < N, T ≤ 105 Bước 1: Xác định bài toán Input: số nguyên dương T là số lượng test (T ≤ 105),số nguyên dương N (N ≤ 105). Output: T dòng, với mỗi dòng là giá trị tổng S(N) tương ứng. 2 Đề thi vào lớp 10 Chuyên Phan Bội Châu –Năm học 2020-2021 12
Bước 2: Đặc điểm dữ liệu Dữ liệu vào yêu cầu tính tổng S(N) với N ≤ 105, hơn nữa lại có T ≤ 105 test Kiểu dữ liệu T, N nguyên dương Bước 3: Thuật toán có thể giải bài toán Cách 1: -Tính lần lượt mỗi test, với mỗi test tính tổng bình phương các số từ 1 đến n. Độ phức tạp sẽ là O(n2) Cách 2: Theo tính chất dãy số trong toán học thì: 12 + 22 +…+ N2 = N *(N+1) * (2*N +1) /6 Vận dụng tính chất này để tính mỗi Ti ta đã đưa độ phức tạp từ O(n2) xuống O(n) với n là số lượng test Bước 4: Đánh giá, lựa chọn thuật toán Với cách 1, độ phức tạp là O(n2). Đối chiếu theo bảng ước lượng (*) đã nêu với thời gian thực hiện tối đa 1 giây thì đáp ứng được giới hạn với 1 ≤ N, T ≤ 103 chiếm 80% số test theo yêu cầu của đề. Với cách 2, độ phức tạp O(n) đáp ứng được thời gian thực hiện tối đa 1 giây cho cả 20% số test còn lại với 103 < N, T ≤ 105 Kết luận: Lựa chọn cách 2 để giải được 100% số test theo yêu cầu của đề bài. Bước 5: Cài đặt chương trình Code tham khảo #include using namespace std; int main() { freopen ("tongbp.inp" , "r" , stdin); freopen ("tongbp.out" , "w" , stdout); ios_base::sync_with_stdio(false); cin.tie(0); cout.tie(0); long long n,t; cin >> n; for (long long i = 0 ; i < n ; i++) { 13
cin >> t; cout
Ta thấy độ phức tạp lúc này là O(n√𝑛), với 𝑛 cỡ 107 trường hợp trên đã có cỡ 1010 lệnh thực thi. Do đó việc sử dụng thuật toán ở trên sẽ vượt quá tốc độ xử lý của máy tính hiện nay vì tốc độ máy tính hiện tại chỉ có thể thực hiện tối đa 108 phép toán trên một giây. Theo bảng ước lượng đã nêu thì với dữ liệu vào 𝑛 cỡ 107 thì độ phức tạp phải là O(n). Vì vậy trong trường hợp này ta cần sử dụng thuật toán khác đó là sàng nguyên tố Eratosthenes Như vậy thuật toán kiểm tra nguyên tố theo cách này có: Ưu điểm: - Code đơn giản, dễ hiểu, độ phức tạp nhỏ O(√𝑛), thích hợp với bài toán chỉ dùng để kiểm tra ít số. Nhược điểm: - Hạn chế đối với bài toán liệt kê các số nguyên tố với số lượng phần tử lớn Cách 2: Kiểm tra nguyên tố bằng sàng nguyên tố Eratosthenes Sàng nguyên tố Eratosthenes là một thuật toán giúp nhanh chóng liệt kê các số nguyên tố. Đây là một thuật toán tìm số nguyên tố tối ưu khi muốn tìm tất cả các số nguyên tố nhỏ hơn một số N cho trước (N >=2) Ý tưởng của thuật toán sàng nguyên tố Eratosthenes Dựa theo lý thuyết về số nguyên tố: Một số nguyên tố là số chỉ có 2 ước là 1 và chính nó. Do vậy, nếu ta xác định được số x là số nguyên tố, ta có thể kết luận mọi số chia hết cho x đều không phải số nguyên tố. Do đó ta đã loại bỏ được rất nhiều số mà không cần kiểm tra. Ví dụ: Số 2 là số nguyên tố => các số 4, 6, 8, 10…không phải số nguyên tố. Số 3 là số nguyên tố => các số 9, 15, 21…không phải số nguyên tố (Do 6, 12, 18 đã bị loại ở số 2) Thuật toán sàng nguyên tố Eratosthenes 1. Tạo mảng đánh dấu cho tất cả các phần tử từ 2 đến N và mặc định tất cả đều là số nguyên tố 2. Xét số đầu tiên tìm được là số nguyên tố – giả sử x, đánh dấu tất cả các ước của x: 2x, 3x, 4x,… trong đoạn [x, N] không phải số nguyên tố. 3. Tìm số tiếp theo được đánh dấu là số nguyên tố trong [x, N]. Nếu không còn số nào, thoát chương trình. Nếu còn, gán nó bằng x và lặp lại bước 2. 4. Khi kết thúc giải thuật, các số không bị đánh dấu là các số nguyên tố Ta có hàm kiểm tra nguyên tố dùng sàng nguyên tố Eratosthenes như sau: 15
bool isPrime[nmax]; void sieve() { memset(isPrime, true, sizeof(isPrime)); isPrime[1] = false; for (long long i = 2; i*i
So sánh Kiểm tra nguyên tố Sàng nguyên tố Độ phức tạp O(√𝑛) O(nlogn) Đặc điểm Cài đặt đơn giản, dễ sử Cài đặt phức tạp hơn dụng Trường hợp nên sử dụng - Kiểm tra tính nguyên tố - Kiểm tra và liệt kê (thời gian thực hiện ≤1s) của ít số. Hoặc kiểm tra nhiều số nguyên tố số lượng phần tử khoảng -Kiểm tra số lượng phần n≤ 105 tử khoảng n≤ 107 Xét một số ví dụ để so sánh việc sử dụng 2 thuật toán trên: Bài 1: - Số lượng số nguyên tố3 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 10 1 2 3 4 5 6 7 9 11 13 output 6 Bước 1: Xác định bài toán - Input: dãy số a1, a2,..., an (0 < n ≤ 103). - Output: Số lượng số nguyên tố trong dãy a1, a2,..., an Bước 2: Đặc điểm dữ liệu: - Dữ liệu vào yêu cầu thực hiện đếm số nguyên tố với dãy số nguyên không âm có giá trị ai ≤ 108 và n≤103 trong thời gian ≤ 1 giây. Bước 3: Các cách giải có thể lựa chọn: - Cách 1: Với mỗi ai kiểm tra tính nguyên tố của nó bằng thuật toán kiểm tra nguyên tố thông thường. Độ phức tạp tính được là O(𝑛√𝑛) 3 Bài N1001A trên http://laptrinhphothong.vn/ 17
- Cách 2: Sử dụng sàng nguyên tố và kiểm tra từng ai có thuộc mảng đã sàng hay không. Độ phức tạp tính được O(max(nlogn,n) = O(nlogn) Bước 4: Đánh giá, lựa chọn: - Đối chiếu với bảng ước lượng (*) thì với độ phức tạp của cách 1 và cách 2 đều đáp ứng được thời gian thực hiện ≤ 1 giây. Như vậy ta có thể sử dụng cách nào cũng được. Tuy nhiên ta nên dùng thuật toán 1 vì tính đơn giản của nó. Bước 5: Viết chương trình: Code tham khảo: #include using namespace std; #define nmax 1009 int a[nmax]; bool check(long long x) {if (x==1) return false; for(long long i=2;i> n; for (int i = 1; i > a[i]; if (check(a[i])) dem++; } cout
Bài 2: Số nguyên tố trong đoạn4 Yêu cầu: Đếm số lượng số nguyên tố trong đoạn [a; b]. Dữ liệu: Một dòng ghi hai số nguyên a, b với 0 < a, b ≤ 107. Kết quả: Một dòng là số lượng số nguyên tố trong đoạn [a; b]. Ví dụ input 1 10 output 4 Bước 1: Xác định bài toán - Input: hai số nguyên a, b với 0 < a, b ≤ 107 - Output: số lượng số nguyên tố trong đoạn [a; b]. Bước 2: Đặc điểm dữ liệu: - Dữ liệu vào a, b ≤ 107, trường hợp lớn nhất là phải xét 107 số, với mỗi số ai≤107 Bước 3: Các cách giải có thể lựa chọn Với ai≤107 ta có thể sử dụng 2 cách giải - Cách 1: Với mỗi ai kiểm tra tính nguyên tố của nó bằng thuật toán kiểm tra nguyên tố thông thường. Độ phức tạp tính được là O(𝑛√𝑛) - Cách 2: Sử dụng sàng nguyên tố và kiểm tra từng ai có thuộc mảng đã sàng hay không. Độ phức tạp tính được O(max(nlogn,n) = O(nlogn) Bước 4: Đánh giá, lựa chọn - Đối chiếu với bảng ước lượng (*) thì với độ phức tạp của cách 1 (trường hợp xấu nhất là cỡ 1010) nên không thể thực hiện hết các test của đề bài trong thời gian yêu cầu. Cách 2 đáp ứng được thời gian thực hiện với mọi test. Vì vậy lựa chọn cách 2 để giải bài toán. Bước 5: Viết chương trình Code tham khảo #include #define nmax 10000009 using namespace std; 4 Bài N1002B trên http://laptrinhphothong.vn/ 19
bool isPrime[nmax]; void sieve() { memset(isPrime, true, sizeof(isPrime)); isPrime[1] = false; for (long long i = 2; i*i a >> b ; int dem = 0; for (long long i = a; i