Tiếp tục với bài tập luyện lập trình C/C++ số 19 một bài toán rất hay, tìm phần tử xuất hiện nhiều nhất trong mảng. Đừng bỏ lỡ bài toán này nhé!
Mục lục bài viết
1.Giới thiệu bài toán
Đây là một bài toán tìm kiếm trong mảng, một bài toán kết hợp việc tìm số lớn nhất và tìm số phần tử trong mảng. Một bài toán có chút nâng cao tư duy của bạn một chút.
Đề bài:
Viết hàm tìm phần tử xuất hiện nhiều nhất trong mảng một chiều a có n phần tử các số nguyên.
Bài toán lập trình này tuy ngắn nhưng có lẽ là hóc búa nhất trong số các bài toán trước đây mình giới thiệu. Đừng lo, nếu bạn đã làm những bài trước đó, thì việc giải quyết bài này là đơn giản.
2.Giải quyết bài toán
Để làm được bài tập yêu cầu bạn đọc phải nắm vững kiến thức về vòng lặp, mảng và thuật toán tìm số lớn nhất. Đương nhiên các cấu trúc cơ bản bạn cũng phải nắm được và quên thì xem lại ngay nhé!
2.1 Ý tưởng giải quyết bài toán
Ý tưởng giải bài toán này của mình như sau:
- Đầu tiên, ta tạo ra một mảng b, chỉ gồm các phần tử khác nhau giống ở bài 18.
- Sau đó tạo thêm mảng c lưu giá trị khi đếm số lần xuất hiện của mỗi phần tử ở mảng b trong mảng a
- Giá trị lớn nhất của mảng c chính là số lần xuất hiện nhiều nhất. và với b[i] tương ứng ta biết được phần tử nào xuất hiện nhiều nhất
- Tuy nhiên mình giải thêm trường hợp có các phần tử có cùng số lần xuất hiện nhiều nhất?
Do đó, mình đã đếm số phần tử có cùng lần xuất hiện nhiều nhất
Nếu có từ 2 phần tử xuất hiện nhiều nhất, tạo mảng d để lưu vị trí của các phần tử cùng xuất hiện nhiều nhất - In ra màn hình kết quả.
2.2 Hàm tìm phần tử xuất hiện nhiều nhất
Với ý tưởng đưa ra ở phần trên, mình code hàm tìm phần tử xuất hiện nhiều nhất trong mảng cho các bạn tham khảo:
Code C++:
(Nếu bạn đang viết code C chỉ cần sửa câu lệnh cout<< ; cin>> là được).
void Count(int a[], int n){
int b[n];
int x=1;
b[0]=a[0];
//tach mang chi gom cac phan tu khac nhau
for(int i=1;i<n;i++){
int dem=0;
for(int j=0;j<x;j++){
if(a[i]==b[j])
dem++;
}
if(dem==0){
b[x]=a[i];
x++;
}
}
//tao mang chua so lan xuat hien cua moi phan tu
int c[x];
for(int i=0;i<x;i++)
c[i]=0;
//dem so lan xuat hien cua moi phan tu
for(int i=0;i<x;i++){
for(int j=0;j<n;j++){
if(a[j]==b[i])
c[i]++;
}
}
//tim so lan xuat hien nhieu nhat
//bien max luu so lan xuat hien nhieu nhat
//bien y dung de dem so lan xuat hien bang nhau
int max=c[0], vtri=0, y=1;
//tim so lan xuat hien nhieu nhat va vi tri cua no
for(int i=1;i<x;i++){
if(c[i]>max){
max=c[i];
vtri=i;
y=1;
}
if(c[i]==max){
y++;
}
}
//neu chi co mot phan tu xuat hien nhieu nhat
if(y==1){
cout<<"\nPhan tu xuat hien nhieu nhat la: "<<b[vtri];
cout<<" xuat hien "<<max<<" lan"<<endl;
}
//neu co tu hai phan tu xuat hien nhieu nhat
else{
int d[y]; //mang dung luu vi tri cua phan tu xuat hien nhieu nhat
int z=0;
for(int i=0;i<x;i++)
if(c[i]==max){//lay vi tri cua phan tu xuat hien nhieu nhat
d[z]=i;
z++;
}
//in ket qua ra man hinh
cout<<"\nPhan tu xuat hien nhieu nhat la: ";
for(int i=0;i<z;i++ )
cout<<b[d[i]]<<" ";
cout<<" xuat hien "<<max<<" lan";
}
}
Code hàm này hơi phức tạp một xíu, bạn đọc chú ý tên và công dụng của từng biến, từng mảng thì mới hiểu được.
Khuyến khích bạn dựa vào ý tưởng của mình.
2.3 Chương trình C++
Bạn thêm phần nhập xuất mảng để làm việc với mảng, thêm cấu trúc cơ bản của một chương trình là có thể chạy.
Chương trình của mình:
#include<bits/stdc++.h>
using namespace std;
void nhap(int a[], int &n){
do{
cout<<("Nhap n: ");
cin>>n;
}
while(n<2||n>99);
for(int i=0; i<n; i++){
cout<<"a["<<i<<"]: ";
cin>>a[i];
}
}
void xuat(int a[], int n){
for(int i=0;i<n;i++){
cout<<" "<<a[i];
}
}
void Count(int a[], int n){
int b[n];
int x=1;
b[0]=a[0];
//tach mang chi gom cac phan tu khac nhau
for(int i=1;i<n;i++){
int dem=0;
for(int j=0;j<x;j++){
if(a[i]==b[j])
dem++;
}
if(dem==0){
b[x]=a[i];
x++;
}
}
//tao mang chua so lan xuat hien cua moi phan tu
int c[x];
for(int i=0;i<x;i++)
c[i]=0;
//dem so lan xuat hien cua moi phan tu
for(int i=0;i<x;i++){
for(int j=0;j<n;j++){
if(a[j]==b[i])
c[i]++;
}
}
//tim so lan xuat hien nhieu nhat
//bien y dung de dem so lan xuat hien bang nhau
int max=c[0], vtri=0, y=1;
//tim so lan xuat hien nhieu nhat va vi tri cua no
for(int i=1;i<x;i++){
if(c[i]>max){
max=c[i];
vtri=i;
y=1;
}
if(c[i]==max){
y++;
}
}
//neu chi co mot phan tu xuat hien nhieu nhat
if(y==1){
cout<<"\nPhan tu xuat hien nhieu nhat la: "<<b[vtri];
cout<<" xuat hien "<<max<<" lan"<<endl;
}
//neu co tu hai phan tu xuat hien nhieu nhat
else{
int d[y]; //mang dung luu vi tri cua phan tu xuat hien nhieu nhat
int z=0;
for(int i=0;i<x;i++)
if(c[i]==max){//lay vi tri cua phan tu xuat hien nhieu nhat
d[z]=i;
z++;
}
//in ket qua ra man hinh
cout<<"\nPhan tu xuat hien nhieu nhat la: ";
for(int i=0;i<z;i++ )
cout<<b[d[i]]<<" ";
cout<<" xuat hien "<<max<<" lan";
}
}
int main(){
int a[100];
int n;
nhap(a,n);
cout<<"Ket qua"<<endl;
Count(a,n);
return 0;
}
Kết quả khi chạy chương trình trên:
Trường hợp có 1 phần tử xuất hiện nhiều nhất
Ví dụ trường hợp có nhiều phần tử xuất hiện nhiều nhất:
Bài viết của mình đến đây là hết. Cảm ơn bạn đã quan tâm bài viết. Đừng bỏ lỡ những bài tập tiếp theo nhé!
Xem tiếp bài 20: Kiểm tra tính đối xứng của mảng
Xem lại bài 18: Đếm số phần tử khác nhau trong mảng
Tải về 67 bài tập đề cương lập trình C/C++
Mọi vướng mắc trong quá trình tham khảo bài viết, bạn đọc comment xuống dưới nhé!. Rất mong nhận được ý kiến đóng góp của bạn đọc đề bài chia sẻ của mình hoàn thiện hơn.
