Sáng kiến kinh nghiệm THPT: Lớp các bài toán cơ bản trên mảng một chiều lập trình bằng ngôn ngữ C++

Mục tiêu nghiên cứu của sáng kiến kinh nghiệm là nhận thấy ngôn ngữ lập trình C++ cung cấp nhiều thư viện nên rất tiện lợi trong quá trình lập trình giải các bài toán, đồng thời lớp các bài toán trên mảng 1 chiều cũng được vận dụng nhiều trong lập trình. Vì vậy, tôi viết đề tài này với mục đích: Thứ nhất, trao đổi cùng với các đồng nghiệp về việc vận dụng ngôn ngữ C++ trong việc lập trình. Thứ hai, là tài liệu cho giáo viên phục vụ giảng dạy, bồi dưỡng HSG.
Nội dung trích xuất từ tài liệu:
Sáng kiến kinh nghiệm THPT: Lớp các bài toán cơ bản trên mảng một chiều lập trình bằng ngôn ngữ C++ MỤC LỤCĐẶT VẤN ĐỀ ....................................................................................................... 1 1. Lý do chọn đề tài........................................................................................... 2 2. Cấu trúc nội dung.......................................................................................... 2 3. Mục đích nghiên cứu..................................................................................... 2 4. Phương pháp nghiên cứu............................................................................... 3 5. Giới hạn phạm vi nghiên cứu của đề tài ........................................................ 3 NỘI DUNG............................................................................................................ 4 PHẦN 1. KIẾN THỨC VỀ MẢNG MỘT CHIỀU.............................................. 4 I. Khái niệm................................................................................................... 4 II. Cách khai báo .............................................................................................. 4 III. Cách truy nhập đến phần tử mảng .............................................................. 4 IV. Cách nhập/xuấtmảng................................................................................. 5 V. Một số thuật toán cơ bản trên mảng một chiều ............................................ 5 PHẦN II. BÀI TẬP........................................................................................... 12 1. Bài tập chủ đề tìm giá trị nhỏ nhất, lớn nhất ............................................... 12 2. Bài tập chủ đề sắp xếp mảng ...................................................................... 17 3. Bài tập chủ tìm kiếm trên mảng.................................................................. 24 4. Bài tập chủ đề tìm đoạn con dài nhất của thỏa mãn điều kiện cho trước. .... 36 5. Bài tập chủ đề cắt mảng thành K đoạn thỏa mãn điều kiện cho trước ......... 42KẾT QUẢ ÁP DỤNG.......................................................................................... 44KẾT LUẬN.......................................................................................................... 44TÀI LIỆU THAM KHẢO ................................................................................... 45PHỤ LỤC: HƯỚNG DẪN VÀ CHƯƠNG TRÌNH MẪU ................................... 46 1. Bài tập chủ đề tìm giá trị nhỏ nhất, lớn nhất .................................................. 46 2. Bài tập chủ đề sắp xếp mảng ......................................................................... 53 3. Bài tập chủ đề tìm kiếm trên mảng ................................................................ 60 4. Bài tập chủ đề tìm đoạn con dài nhất thỏa mãn điều kiện cho trước. ............. 80 5. Bài tập chủ đề cắt mảng thành K đoạn thỏa mãn điều kiện cho trước ............ 89 1 ĐẶT VẤN ĐỀ 1. Lý do chọn đề tài Mảng 1 chiều là cấu trúc dữ liệu đầu tiên và cũng là cấu trúc dữ liệu đơn giản vàphổ biến nhất. Mảng 1 chiều giúp giải quyết được nhiều lớp bài toán. Vì vậy, nó đượcsử dụng nhiều trong các kỳ thi học sinh giỏi Tin học. Với nhiều năm tham gia giảng dạy, bồi dưỡng học sinh giỏi và việc nghiên cứucác vấn đề về lập trình theo từng dạng bài tập từ cơ bản đến phức tạp của ngôn ngữlập trình C++, các tài liệu về phương pháp giảng dạy phục vụ cho việc học tập, ôn thihọc sinh giỏi của học sinh cũng như giảng dạy của giáo viên. Từ đó, tôi viết sáng kiếnkinh nghiệm với đề tài “Lớp các bài toán cơ bản trên mảng một chiều lập trìnhbằng ngôn ngữ C++”. Với mong muốn phần nào giúp học sinh cũng như giáo viêncó tài liệu tham khảo phục vụ cho việc học tập và giảng dạy. 2. Cấu trúc nội dung Phần 1. Kiến thức về Mảng 1 chiều 1. Khái niệm về mảng một chiều 2. Khai báo mảng 3. Truy nhập phần tử mảng 4. Nhập/xuất mảng 5. Một số thuật toán cơ bản trên mảng 1 chiều Phần 2. Bài tập 1. Tìm giá trị nhỏ nhất, giá trị lớn nhất 2. Sắp xếp trên mảng 3. Tìm kiếm trên mảng 4. Tìm đoạn con dài nhất thỏa mãn điều kiện cho trước 5. Cắt mảng thành K đoạn thỏa mãn điều kiện cho trước 3. Mục đích nghiên cứu Trong quá trình nghiên cứu và giảng dạy, tôi nhận thấy ngôn ngữ lập trình C++cung cấp nhiều thư viện nên rất tiện lợi trong quá trình lập trình giải các bài toán,đồng thời lớp các bài toán trên mảng 1 chiều cũng được vận dụng nhiều trong lậptrình. Vì vậy, tôi viết đề tài này với mục ...