Tìm phần tử xuất hiện nhiều nhất trong mảng

tim phan tu xuat hien nhieu nhat trong mang 1

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é!

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 &amp;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

tim phan tu xuat hien nhieu nhat trong mang 2

Ví dụ trường hợp có nhiều phần tử xuất hiện nhiều nhất:

tim phan tu xuat hien nhieu nhat trong mang 3

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.

LEAVE A REPLY

Please enter your comment!
Please enter your name here