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ất
mả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 ......... 42
KẾT QUẢ ÁP DỤNG.......................................................................................... 44
KẾT LUẬN.......................................................................................................... 44
TÀI LIỆU THAM KHẢO ................................................................................... 45
PHỤ 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ó được
sử 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ứu
cá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 thi
họ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ến
kinh 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ình
bằ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ên
có 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ậ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.
2
4. Phương pháp nghiên cứu.
Kinh nghiệm bản thân, thảo luận, sưu tầm tài liệu, thử nghiệm thực tế, rút kinh
nghiệm từ các tiết dạy trên lớp.
5. Giới hạn phạm vi nghiên cứu của đề tài
Đề tài chủ yếu nghiên cứu hệ thống lớp các bài toán cơ bản trên mảng 1 chiều và
lập trình bằng ngôn ngữ C++.
Đề 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.
3
NỘI DUNG
Việc nắm vững lý thuyết về mảng một chiều và các bài toán cơ bản trên mảng
một chiều là điều rất quan trọng, đó là cơ sở để các em học sinh vận dụng và giải
quyết các bài toán phức tạp và nâng cao. Sau đây, tôi xin trình bày các kiến thức và
các bài tập cơ bản về mảng 1 chiều sử dụng ngôn ngữ lập trình C++ mà tôi đã tìm
hiểu và vận dụng có hiệu quả trong quá trình giảng dạy.
PHẦN 1. KIẾN THỨC VỀ MẢNG MỘT CHIỀU
I. Khái niệm
Mảng một chiều là dãy hữu hạn các phần tử có cùng kiểu dữ liệu. Khi nói đến
mảng ta cần xác định được:
- Kiểu dữ liệu của các phần tử mảng .
- Số phần tử của mảng.
II. Cách khai báo
1. Khai báo không có khởi tạo
<Tên kiểu dữ liệu> <Tên biến mảng> [Số phần tử];
Ví dụ: int a[5]; float b[10];
2. Khai báo có khởi tạo
<Tên kiểu dữ liệu> <Tên biến mảng> [Số phần tử] = {dãy giá trị};
Hoặc: <Tên kiểu dữ liệu> <Tên biến mảng>[ ] = {dãy giá trị} ;
(Lưu ý: Trong trường hợp không khai báo số phần tử mảng thì mảng vừa đủ lớn
để giữ các giá trị được khởi tạo)
Trong đó: - Tên kiểu dữ liệu: là các kiểu dữ liệu cơ bản hoặc kiểu dữ liệu có cấu
trúc.
- Tên biến mảng: do người dùng đặt theo quy tắc đặt tên.
- Số phần tử: kích thước mảng.
Ví dụ: float x[5]={3,5,7,2,1};
int a[ ] = {0, 2, 4, 6, 8};
III. Cách truy nhập đến phần tử mảng
<Tên biến mảng> [Chỉ số]
Ví dụ: int a[5] 0 1 2 3 4
1 3 5 7 9
4
a[1] = 3; a[3]= 7;
Lưu ý: - Mảng trong C++ được đánh số bắt đầu từ 0
- Khi khai báo mảng cần khai báo số phần tử thừa ra.
IV. Cách nhập/xuất mảng
4.1. Nhập mảng
Cách 1: Biết số phần tử của mảng
cin>>n;
for (int i = 1 ; i < n; i++) cin>>a[i];
Cách 2: Chưa biết số phần tử của mảng
int x, n = 0;
while (cin >> x)
{
n++;
a[n] = x;
}
4.2. Xuất mảng:
for (int i=1 ; i <=n; i++) cout << a[i];
V. Một số thuật toán cơ bản trên mảng 1 chiều
5.1. Tìm giá trị nhỏ nhất, lớn nhất
Bài toán: Tìm Min, Max của mảng A gồm N phần tử.
Ý tưởng:
- Gán Min = A[1] (Max= A[1]).
- Ta duyệt từ phần tử thứ 2 đến cuối mảng, gặp phần tử A[i] nào bé hơn Min (lớn
hơn Max) gán lại Min = A[i]( Max = A[i]).
Thuật toán:
Cách 1:
Min = A[1]; Max = A[1];
for (i = 2 ; i <= N; i++)
{
if (Min > A[i]) Min = A[i];
if (Max < A[i]) Max = A[i];
}
Cout << “Min =” << Min << “ Max ”<< Max;
5
Cách 2: Sử dụng hàm min, max
Min = INT_MAX; Max = INT_MIN;
for (i = 1; i < N; i++)