SKKN 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++

 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
I– CƠ SỞ LÝ LUẬN:
Để giải quyết các bài toán về mảng một chiều 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ố.
Cách khái báo
 [Số lượng phần tử] ; Ví dụ: int a [100];
Cách truy nhập đến phần tử mảng
[chỉ số] Ví dụ: a[5]
Cách nhập xuất phần tử mảng
+) Nhập phần tử mảng
- Khi biết trước số lượng phần tử mảng
cin>>n;
For(int i=0; i>a[i];
- Nhập khi chưa biết số lượng phần tử mảng
int i, n=0; while (cin>>i)
{
n++;
a[n]=i;
}
+) xuất mảng
for(int i=0; i<n; i++) cout<<a[i];
Một số dạng bài toán thường gặp:
Dạng 1: Tìm phần tử
Dạng 2: Sắp xếp phần tử mảng
– THỰC TRẠNG CỦA VẤN ĐỀ:
Dạy học lập trình bằng NNLT C++ còn 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.
– 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.
Dạng các bài toán tìm phần tử trong mảng
*/ Các bài toán tìm giá trị nhỏ nhất, lớn nhất
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
5
1 2 3 4 5
output
1
Ví dụ
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
5
5 2 3 4 1
3
2
4
5
output
2
2
1
Ví dụ
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;
}
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
input
5
1 3 -3 0 -1
output
-1
Ví dụ
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
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ố.
input
5
1 3 2 4 5
output
41
Ví dụ
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;
}
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;
}
Dạng các bài toán sắp xếp trong mảng một chiều
Sắp xếp là quá trình bố trí lại các phần tử trong một tập hợp theo một trình tự nào đó nhằm mục đích giúp quản lý và tìm kiếm các phần tử dễ dàng và nhanh chóng hơn.
Sắp xếp dãy số theo thứ tự tăng dần hay giảm dần là 1 bài toán sắp xếp cơ bản đối với người học lập trình. Bài toán sắp xếp dãy số là bài tập điển hình trong phần kiến thức về mảng 1 chiều.
Khi làm bài tập mà có các cụm từ khóa sau:
Sắp xếp dãy số tự nhiên tăng dần/giảm dần
Sắp xếp mảng số thực tăng dần/ giảm dần
Sắp xếp mảng 1 chiều các số tự nhiên tăng/giảm dần
Thì cả 3 đề bài này đều là bài toán sắp xếp dữ liệu trên mảng 1 chiều. Khi nhắc tới “dãy số” thì chúng tanghĩ ngay tới mảng 1 chiều.
Code về sắp xếp mảng tăng dần, giảm dần
#include using namespace std;
// Ham doi vi tri hai phan tu
void swap(int &a, int &b){ int temp =a;
a=b; b=temp;
}
// Ham sap xep tang
void sortArrTang(int a[], int n){ for(int i=0;i<n-1;i++)
for(int j=i;ja[j]){
swap(a[i], a[j]);
}
}
}
// Ham sap xep giam
void sortArrGiam(int a[], int n){ for(int i=0;i<n-1;i++)
for(int j=i;j<n;j++){ if(a[i]<a[j]){
int temp=a[i]; a[i]=a[j]; a[j]=temp;
}
}
}
// Ham nhap mang
void inputArr(int a[], int n){ for(int i=0;i>a[i];
}
// Ham xuat mang
void printArr(int a[], int n){ for(int i=0;i<n;i++) cout<<" "<<a[i];
}
int main(){ int n;
// Nhap so luong phan tu mang do{
cout>n;
}
while(n<=0); // Neu n<=0 thi nhap lai int a[n]; // khai bao mang a co n phan tu inputArr(a,n); // Goi ham nhap mang sortArrTang(a, n); // Goi ham sap xep
cout<<"Mang sau khi sap xep tang dan: "<<endl; printArr(a, n);
return 0;
}
– Bài tập áp dụng:
Để học sinh có năng lực phân tích, vận dụng các phương pháp. Học sinh cùng giáo viên giải một số bài tập
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
5
1 2 3 4 5
3
output
6
Ví dụ
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
5
10