MỤC LỤC ĐẶT VẤN ĐỀ. Lý do chọn đề tài. Cấu trúc nội dung. Mục đích nghiên cứu.
Phương pháp nghiên cứu. Giới hạn phạm vi nghiên cứu của đề tài. KIẾN THỨC VỀ MẢNG MỘT CHIỀU. Cách truy nhập đến phần tử mảng.
Cách nhập/xuất mảng. Một số thuật toán cơ bản trên mảng một chiều. Bài tập chủ đề tìm giá trị nhỏ nhất, lớn nhất. Bài tập chủ đề sắp xếp mảng.
Bài tập chủ tìm kiếm trên mảng. 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. 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 TÀI LIỆU THAM KHẢO. 45 PHỤ LỤC: HƯỚNG DẪN VÀ CHƯƠNG TRÌNH MẪU. Bài tập chủ đề tìm giá trị nhỏ nhất, lớn nhất. Bài tập chủ đề sắp xếp mảng.
Bài tập chủ đề tìm kiếm trên mảng. 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. 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. 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. 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.
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.
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. 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 skkn 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. 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. 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 skkn 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. Cách nhập/xuất mảng 4. 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. 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. 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ử. - 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 skkn Cách 2: Sử dụng hàm min, max Min = INT_MAX; Max = INT_MIN; for (i = 1; i < N; i++) { Min = min (Min, A[i]); Max = max (Max, A[i]) } Cout << Min <<Max; 5.
Sắp xếp trên mảng Bài toán: Cho mảng A gồm N phần tử, sắp xếp mảng theo thứ tự tăng dần 5. Thuật toán sắp xếp đơn giản (Selection Sort) Ý tưởng thuật toán: Duyệt mảng từ vị trí đầu đến hết mảng, nếu gặp phần tử nào của mảng bằng X thì in ra vị trí, nếu duyệt hết mảng mà không tìm thấy thì thông báo không tìm thấy. Chia mảng A thành hai mảng: Mảng chưa sắp(CS) và mảng đã sắp (DS). - Khởi tạo: CS chính là mảng A, DS bằng rỗng.
- Lấy phần tử đầu tiên của tập chưa sắp (CS), so sánh với mọi phần tử đứng sau nó, nếu thấy phần tử nào không thõa mãn điều kiện thì tráo đổi hai phần tử đó cho nhau. Đưa phần tử đầu tiên của mảng CS này vào mảng DS. - Lặp lại cho đến phần tử cuối cùng của mảng CS. Cuối cùng ta được mảng đã sắp xếp chính là mảng DS.
Thuật toán: for (i=1; i<= N-1; i++) for (j = i+1; j<= N; j++) if (A[i] > A[j]) swap(A[i], A[j]); for (i=1; i<= N;i++) cout << A[i]<< “ ”; 5. Thuật toán sắp xếp nhanh( Quick sort) Ý tưởng thuật toán: Chọn phần tử x ở giữa của dãy làm chuẩn để so sánh. Ta phân hoạch dãy này thành 3 dãy con liên tiếp nhau: - Dãy con thứ nhất gồm phần tử có khoá nhỏ hơn x. - Dãy con thứ hai gồm các phần tử có khoá bằng x.
6 skkn - Dãy con thứ ba gồm các phần tử có khoá lớn hơn x. Sau đó áp dụng giải thuật phân hoạch này cho dãy con thứ nhất nhất và dãy con thứ ba, nếu các dãy con có nhiều hơn một phần tử. Cụ thể là xét một doạn của dãy từ thành phần L đến thành phần thứ H. - Lấy giá trị của thành phần thứ (L+H) Div 2 gán vào biến X.
- Cho i ban đầu là L. - Cho j ban đầu là H. Chừng nào còn A[i] < X thì tăng i. Chừng nào còn A[j] > X thì giảm j.
i<=j thì + Hoán vị A[i] và A[j] + Tăng i + Giảm j Cho đến khi i>j + Sắp xếp đoạn từ A[L] đến A[j] + Sắp xếp đoạn từ A[i] đến A[H] Thuật toán 1. #include <bits/stdc++. using namespace std; 3. Sử dụng hàm sort trong C++ * Sắp xếp tăng Sort (tên mảng + chỉ số đầu, tên mảng + chỉ số cuối +1); Ví dụ: +) Sắp xếp n phần tử tăng từ a[1] đến a[n]: Sort (a +1, a+ n + 1); +) Sắp xếp n phần tử tăng từ a[0] đến a[n - 1]: Sort (a , a+ n); * Sắp xếp giảm: Sort (tên mảng + chỉ số đầu, tên mảng + chỉ số cuối +1, greater < int >( ) ); Ví dụ: +) Sắp xếp n phần tử giảm từ a[1] đến a[n]: Sort (a +1, a+ n + 1, greater < int >( )); +) Sắp xếp n phần tử giảm từ a[0] đến a[n - 1]: Sort (a , a+ n, greater < int >( )); 5.
Tìm kiếm trên mảng một chiều 5. Tìm kiếm tuần tự Bài toán: Cho mảng A gồm N phần tử và phần tử X. Tìm kiếm xem phần tử X có xuất hiện trong mảng A hay không? Nếu có thì xuất hiện ở những vị trí nào? 8 skkn Thuật toán: Timthay = false; for (i = 1; i<= N; i++) if (X = A[i]) { Cout << “xuất hiện ở vị trí:”<< i; timthay=true; } if not (timthay) cout<< “Khong tim thay”; Trong trường hợp chỉ cần xuất ra vị trí của một phần tử ta cải tiến lại chương trình để chương trình thực hiện nhanh hơn. Timthay = false; for (i = 1; i<= N; i++) if (X = A[i]) { Cout << “xuất hiện ở vị trí:”<< i; timthay=true; break; } if not (timthay) cout<< “Khong tim thay”; 5.
Tìm kiếm nhị phân a. Thuật toán tìm kiếm nhị phân cơ bản Bài toán: Với mảng A đã được sắp xếp tăng dần, độ phức tạp của tìm kiếm tuần tự không đổi. Tận dụng thông tin của mảng đã được sắp xếp để giới hạn vị trí của giá trị cần tìm trong mảng. Ý tưởng: Thuật toán tìm kiếm nhị phân So sánh x với phần tử chính giữa của mảng A.