Sáng kiến kinh nghiệm Những bài tập và code xử lý mảng một chiều bằng ngôn ngữ lập trình C++

giải các bài toán liên quan đến mảng một chiều.
- Đưa ra nội dung mục 1: Mảng một chiều, bài 11: Kiểu mảng, sách Tin học 11 để hướng dẫn học sinh nghiên cứu, thảo luận qua đó nắm vững kiến thức về kiểu mảng một chiều như khai báo, xử lý mảng một chiều  Từ đó hình thành ở học sinh khả năng phân tích, xử lý các vấn đề liên quan đến mảng một chiều trong việc lập trình giải các bài toán đơn giản.
Tính mới của đề tài
Đưa ra được nhiều bài tập mới về mảng một chiều và code viết bằng NNLT C++
Đưa ra một số định hướng để giải bài toán về mảng một chiều trong NNLT C++
Khả năng ứng dụng và triển khai đề tài
Đề tài có thể là tài liệu tham khảo bổ ích cho Học sinh, Giáo viên THPT đặc biệt là Học sinh khá, giỏi.
Đối tượng và phạm vi nghiên cứu
Đối tượng nghiên cứu
Học sinh THPT.
Giáo viên trường THPT.
Các bài toán về mảng một chiều.
Phạm vi nghiên cứu
Bám sát nội dung chương trình Tin học THPT.
Mở rộng phù hợp với nội dung thi Học sinh giỏi Tỉnh
Phương pháp và nhiệm vụ nghiên cứu
Phương pháp nghiên cứu
Kiểm tra đôn đốc việc học tập của học sinh.
Kiểm tra thường xuyên, định kỳ.
Hướng dẫn nghiên cứu, thảo luận nội dung đưa ra
Tham khảo các tài liệu về Ngôn ngữ lập trình C++
Nhiệm vụ nghiên cứu
Rút ra một số kinh nghiệm để giải các bài toán về mảng một chiều khi dạy tin học lớp 11 chương trình Tin học THPT.
NỘI DUNG
– CƠ SỞ LÝ LUẬN:
Để giải quyết các bài toán về mảng một cách tối ưu, học sinh phải biết khái niệm mảng, các thuật toán thông dụng ; Học sinh phải có kỹ năng nhận dạng bài toán khi được phát biểu dưới nhiều dạng khác nhau và lựa chọn thuật toán thích hợp để giải quyết.
*/Khái niệm:
Mảng một chiều là một tập hợp các phần tử cùng kiểu. Mảng được đặt tên, mỗi phần tử có một chỉ số.
*/ Một số dạng bài toán thường gặp:
Dạng 1: Tìm phần tử lớn nhất, nhỏ nhất trong mảng Dạng 2: Sắp xếp phần tử mảng
Dạng 3: Tìm phần tử
– THỰC TRẠNG CỦA VẤN ĐỀ:
Môn Tin học khá mới, nên đối với một số giáo viên việc tìm tòi tài liệu, bài tập phù hợp với trình độ học sinh đã gặp rất nhiều khó khăn, việc tổng hợp bài tập và đề thi thành các dạng bài tập phục vụ giảng dạy mất rất nhiều thời gian. Đặc biệt đối với những giáo viên tham gia bồi dưỡng lần đầu thì còn vất vả hơn nhiều và bản thân tôi cũng không phải là ngoại lệ.
– GIẢI QUYẾT VẤN ĐỀ:
Giáo viên lần lượt đưa ra từng dạng bài toán, phân tích đặc điểm bài toán, ý tưởng thuật toán và ví dụ minh họa cho mỗi dạng. Sau đó cho học sinh soạn thảo chương trình rồi tiến hành chấm bài tự động bằng phần mềm Themis của thầy Lê Minh Hoàng để thấy được hiệu quả của các phương pháp.
Giá trị lẻ nhỏ nhất
Viết chương trình nhập vào n(0<n<=100) số nguyên. In ra giá trị lẻ nhỏ nhất trong dãy số
Dữ liệu:
Dòng đầu tiên ghi số nguyên không âm n.
Dòng 2 ghi n số nguyên dương cách nhau một dấu cách trống
Kết quả: Đưa ra giá trị lẻ nhỏ nhất của n số nguyên
input
Ví dụ
5
1 2 3 4 5
output
1

code
#include #define nmax 100
using namespace std;
void nhap(long long a[],long long &n)
{
cin>>n;
for(long long i=0;i<n;i++)
cin>>a[i];
}
int main()
{
long long a[nmax],n,i; nhap(a,n);
long long minn; for(i=0;i<n;i++)
{
if(a[i]%2==1)
{
minn=a[i]; break;
}
}
for(i=0;i<n;i++)
{
if(a[i]%2==1)
{
if(minn>a[i]) minn=a[i];
}
}
cout<<minn; return 0;
}
Giá trị nhỏ nhất đến vị trí k
Viết chương trình nhập vào n(0<n<=100) số nguyên ai. Tìm giá trị nhỏ nhất của dãy số từ phần tử thứ 1 đến phần tử thứ k của dãy số.
Dữ liệu:
Dòng đầu tiên ghi số nguyên không âm n;
Dòng 2 ghi n ký tự cách nhau một dấu cách trống;
Dòng 3 ghi số câu hỏi t;
t dòng sau mỗi dòng ghi một số nguyên k;
Kết quả: Đưa ra t dòng, mỗi dòng ghi một số nguyên mink là giá trị nhỏ nhất trong các số a1 đến ak tương ứng.
input
Ví dụ
5
5 2 3 4 1
3
2
4
5
output

2
2
1

Code #include #define nmax 1000005 using namespace std;
long long a[nmax],b[nmax]={} ; int n,t,k,c=0; long long mink; int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0); cin>>n;
for(int i=0;i>a[i];
cin>>t;
for(int i=1;i<=t;i++)
{
mink=1e18; cin>>k;
for(int j=0;j<k;j++) mink=min(mink,a[j]);
cout<<mink<<endl;
}
return 0;
}
Số lần xuất hiện nhiều nhất
Viết chương trình nhập vào n(0<n<=100) số nguyên ai(0<=ai<=100). In ra số lần xuất hiện của số xuất hiện nhiều nhất trong dãy số trên.
Dữ liệu:
Dòng đầu tiên ghi số nguyên không âm n.
Dòng 2 ghi n số nguyên dương cách nhau một dấu cách trống
Kết quả: Đưa ra số lần xuất hiện của số xuất hiện nhiều nhất trong dãy số trên.
input
Ví dụ
5
1 3 2 4 1
output
2

Code #include using namespace std; void nhap(int a[],int &n)
{
cin>>n;
for(int i=0;i>a[i];
}
int dem(int a[],int n, int m)
{
int d=0;
for(int i=0;i<n;i++)
{
if(a[i]==m) d++;
}
return d;
}
int sln(int a[],int n)
{
int maxx; maxx=a[0];
for(int i=0;i<n;i++)
{
if(maxx<a[i]) maxx=a[i];
}
return maxx;
}
int main()
{
int a[100],b[100],n,i; nhap(a,n); for(i=0;i<n;i++)
{
b[i]=dem(a,n,a[i]);
}
cout<<sln(b,n); return 0;
}
Phần tử âm lớn nhất
Viết chương trình nhập vào một dãy các số nguyên. In ra phần tử âm lớn nhất
Dữ liệu vào:
Dòng đầu tiên ghi số nguyên dương n (0<=n<=105)
Dòng tiếp theo ghi n số nguyên ai
Dữ liệu ra:
In ra phần tử âm lớn nhất của dãy số. Nếu không tồn tại ghi ra NOSOL
Ví dụ
input
5
1 3 -3 0 -1
output
-1

Code #include #define nmax 100000 using namespace std;
void nhap(long long a[],long long &n)
{
cin>>n;
for(long long i=0;i>a[i];
}
int main()
{
long long a[nmax],n,i; nhap(a,n);
long long maxx; for(i=0;i<n;i++)
{
if(a[i]<0)
{
maxx=a[i]; break;
}
}
for(i=0;i<n;i++)
{
if(a[i]<0)
{
if(maxx<a[i]) maxx=a[i];
}
}
bool kt=true; for(i=0;i<n;i++)
{
if(a[i]<0)
{
kt=true; break;
}
else kt=false;
}
if(kt==false) cout<<"NOSOL";
else cout<<maxx; return 0;
}
Tổng bình phương lớn nhất
Viết chương trình nhập vào n(0<n<=100) số nguyên. In ra giá trị lớn nhất của tổng bình phương ai2+aj2,0<i<j<=nai2+aj2,0<i<j<=n trong dãy số.
Dữ liệu:
Dòng đầu tiên ghi số nguyên không âm n.
Dòng 2 ghi n số nguyên cách nhau một dấu cách trống
input
Kết quả: Đưa ra số lượng giá trị lớn nhất của tổng bình phương ai2+aj2,0<i<j<=nai2+aj2,0<i<j<=n trong dãy số. Ví dụ
5
1 3 2 4 5

output
41

code #include using namespace std; int main()
{
ios::sync_with_stdio(0); cin.tie(0); cout.tie(0);
long long a[105];long long n; cin>>n;
for(long long i=0;i<n;i++)
{
cin>>a[i];
}
long long maxk=-1e9; long long t; for (long long i=0;i<n-1;i++)
{
for(long long j=i+1;j<n;j++)
{
t=a[i]*a[i]+a[j]*a[j]; maxk=max(maxk,t);
}
}
cout<<maxk; return 0;
}
3.2. Vận dụng các định hướng trên để giải một số bài toán
Xóa phần tử trong mảng
Yêu cầu: Viết chương trình nhập vào n số nguyên (0 < n <=10^6). Xóa số thứ k trong n vừa nhập. In ra mảng sau khi xóa phần tử thứ k.
Dữ liệu:
Dòng đầu tiên ghi số nguyên không âm n, vị trí k cần xóa
Dòng 2 ghi n số nguyên dương cách nhau một dấu cách trống.
Kết quả: Đưa ra mảng các số nguyên sau khi xóa phần tử thứ k Ví dụ
input
5 3
-1 3 2 -3 8
output
-1 3 -3 8
Tổng mảng đến phần tử thứ K
Viết chương trình nhập vào một dãy số a1,a2,..,an . Tính tổng các phần tử của dãy từ phần tử thứ 1 đến phần tử thứ k nào đó của dãy.
Dữ liệu:
Dòng 1 ghi số nguyên dương n (n<105)
Dòng 2 ghi n số nguyên dương a1,a2,..,an là các số nguyên kiểu 64 - bit
Dòng 3 ghi số nguyên dương k
Kết quả:
- Tổng S = a1+a2+...+ak
input
Ví dụ
5
1 2 3 4 5
3
output
6

Mở quà
An và Bình là 2 anh em sinh đôi. Vào ngày sinh nhật, cả hai đều nhận được nhiều món quà chung.
Có n gói quà đặt trên bàn, được xếp theo thứ tự từ 1 đến n. An sẽ mở các hộp quà từ trái sang phải, còn Bình sẽ mở từ phải sang trái. Biết rằng, tốc độ mở hộp quà của 2 anh em là như nhau, nhưng mỗi hộp quà có kích thược khác nhau, vì vậy thời gian mở mỗi hộp quà cũng khác nhau. Ngay khi mở xong 1 hộp quà thì hai bạn sẽ ngay lập tức chuyển sang mở hộp quà tiếp theo, và không được bỏ dở hộp quà đang mở để mở hộp quà khác. Nếu hai người cùng bắt đầu mở 1 hộp quà, Bình sẽ nhường cho An.
Yêu cầu:
Cho biết thời gian cần thiết để mở xong các hộp quà. Các bạn hãy tính xem khi tất cả các hộp quà đã mở xong, An và Bình, mỗi người mở được tất cả bao nhiêu hộp quà?
Dữ liệu:
Dòng đầu tiên ghi số nguyên không âm n (1≤ n ≤ 105) – là số hộp quà có trên bàn.
Dòng 2 ghi n số nguyên t1, t2, , tn cách nhau một dấu cách trống (1≤ ti ≤ 1000), với ti tính theo giây, là thời gian cần thiết để mở hộp quà thứ i, theo thứ tự từ trái sang phải.
Kết quả:
In ra 2 giá trị là số hộp quà An và Bình đã mở được.
input
Ví dụ
5
10 10 7 6 9
output
2 3

Dãy đối xứng
Yêu cầu: Cho dãy số gồm n số nguyên a1, a2, ..., an là các số nguyên có giá trị tuyệt đối không vượt quá 104. Hãy tìm dãy con liên tiếp đối xứng dài nhất của dãy số nguyên trên (dãy con được quy ước là dãy có từ 2 phần tử trở lên).
Dữ liệu:
Dòng đầu tiên ghi số nguyên không âm n (n<=103).
Dòng 2 ghi n số nguyên cách nhau một dấu cách trống.
Kết quả: độ dài của dãy con liên tiếp đối xứng dài nhất
input
Ví dụ
5
1 2 3 2 1

output
5

Tổng bằng X
Yêu cầu: Viết chương trình nhập vào một mảng và số nguyên X. Đếm số lượng cặp (i,j) sao cho 0<i<j<=n sao cho ai + aj = X.
Dữ liệu:
Dòng 1 ghi số nguyên dương n(n<=100) và X
Dòng 2 ghi n số nguyên cách nhau một dấu cách trống.
Kết quả:
In ra số lượng cặp (i,j) thỏa mãn yêu cầu bài toán.
input
Ví dụ
5 4
1 2 5 3 4
output
1

4. Đánh giá và kết quả thực hiện
Sau khi dạy học về mảng một chiều và các dạng bài tập về mảng nói trên, đã thu được một số kết quả sau:
Hiệu quả chung:
Đối với học sinh đã có sự tiến bộ rõ rệt về các mặt sau:
Năng lực phân tích, nhận dạng và lựa chọn được thuật toán thích hợp để giải quyết các bài toán về mảng một chiều.
Khả năng đánh giá độ phức tạp của thuật toán, biết sử dụng phần mềm Themis