Hướng dẫn code đếm số phần tử xuất hiện trong ma trận?!

#1

Em có đoạn mã sau được dùng để truy xuất dữ liệu từ một file bên ngoài vào ma trận. Nhờ mọi người có thể hướng dẫn hoặc edit code đếm tổng số lần xuất hiện của từng phần tử trong ma trận.

Thanks mọi người :slight_smile:

#include <stdio.h>
#include <iostream>
using namespace std;
int main()
{
 //file handle
 FILE* file;
 //file open (mode = read)
 file = fopen("input.txt","r");
 int read, n, m;
 fscanf(file, "%d", &n);
 fscanf(file, "%d", &m);
 printf("Ma tran : %d x %d \n", n, m);
 printf("*******************************************\n");
 //khai bao mang 2 chieu a[n][m]
 int **a;
 //khai bao so dong
 a = new int*[n];
 //khai bao so cot
 for(int t = 0; t < m; t++)
  a[t] = new int[m];
 // nhap ma tran vao mang 2 chieu a[n][m]
 for(int i = 0; i<n; i++)
 {
  for(int j = 0; j<m ; j++)
  {
   fscanf(file, "%d", &a[i][j]);
   //xuat ma tran
   printf("%d\t", a[i][j]);
  }
  printf("\n");
 }
  fclose(file);
 // dung console, xem ket qua
 system("pause");
 return 1;
}
#2

Hi Việt Thắng.
Dùng từ điển sau đó khi gặp phần tử nào check xem có trong từ điển chưa. Có thì tăng trỉ số value lên. Chưa thì thêm mới key value = 1.

#3

Hi Phong,
Quả thật về phần này mình còn mơ hồ lắm. Bạn có thể edit thử một đoạn code ví dụ được không?! Thanks bạn :))

#4

Như mình làm thì sẽ có một mảng f[i] đếm số lần xuất hiện của giá trị i trong ma trận. Khi đọc a[i][j] thì tăng f[a[i][j]] lên 1. Thuật toán này gọi là thuật toán đếm phân phối. Nhược điểm của thuật toán này là khoảng giá trị của a[i][j] chỉ khoảng < 10^6.

#5

Hi Việt Thắng.
Bạn tìm hiểu cấu trúc dữ liệu từ điển.

#6

@Phong_Ky_Vo Ý bạn có phải std::map không?
Nhưng mà dùng std::map rất tốn bộ nhớ và thời gian thao tác khá chậm.

#7

Hi HK boy.
Tùy vào bài toán thôi bạn. Tuy nhiên dùng giải pháp key-valu mình thấy là ổn. Có thể cài đặt dựa trên struct key-value và danh sách liên kết hoặc mảng tùy bài toán.

P/S a[i][j] là số thực thì bạn định f[a[i][j]] như nào ? Thuật toán đêm phân phối có vẻ hơi lớn cho bài toán này @_@!

1 Like
#8

Mình đồng ý với bạn là tuỳ bài toán. Tuy nhiên theo mình thấy thì bài này a[i][j] chỉ là số nguyên thôi. Thực tế là dùng map trong bài này cũng là f[a[i][j]] với a[i][j] là số nguyên, thực, xâu,… tuỳ ý. Ý niệm như nhau cả mà.

#9

Hi HK boy.
Tuy nhiên trong bài toán phân phối bạn cần biết miền giá trị của a[i][j] để tạo mảng f[] phù hợp. Trong trường hợp này bạn không thể xác định miền giá trị a[i][j] vì nó là số và không có giới hạn. Trong trường hợp thống kê người theo tuổi thì bạn có thể giới hạn f[200] và nó hiệu quả hơn dùng map. Hoặc thống kê người cùng tỉnh thành phố.
Đại khái tập giá trị của a[i][j] là một tập hữ hạn đếm được.

P/S Cũng tùy bài toán nếu để tránh việc tạo ra mảng f[] lớn mà đa phần các phần tử bằng 0.

1 Like
#10

Cảm ơn mọi người đã tư vấn, mình sẽ cố gắng tìm hiểu.

#11

Nhưng trước hết, sau khi tìm hiểu trên mạng bước đầu mình có tạo ra đoạn code dùng để đếm số lần xuất hiện của một phần tử được xác định trong mảng. Mọi người có thể dựa theo đoạn code này mà tư vấn rõ hơn về cách thức có thể đếm được hết số lần xuất hiện của tất cả cả phần tử được không?!

#include <stdio.h>
#include <iostream>
#include <conio.h>
#include <string.h>
#include <stdlib.h>
#define size 100
#define input "input.txt"
using namespace std;
//Ham nhap mang 2 chieu
void nhap(int A[][size],int &m, int &n)
{
	FILE *fi;
	fi = fopen(input,"rt");
	if (fi == NULL)
	{
		printf("Khong tim thay file can doc!!!");
		exit(1);
	}
	fscanf(fi,"%d%d",&m,&n);
	for(int i=0; i<m; i++)
	for(int j=0; j<n; j++)
	fscanf(fi,"%d",&A[i][j]);
	fclose(fi);
}
//Ham xuat mang 2 chieu
void xuat(int A[][size], int m, int n)
{
 for(int i=0; i<m; i++)
  {
   for(int j=0; j<n; j++)
     {
      printf("%4d",A[i][j]);
 }
     printf("\n");
  }
}
//Ham dem so lan xuat hien cua mot phan tu xac dinh trong mang
int SoLanXuatHien(int A[][size],int m, int n, int x)
{
 int dem=0;
 for(int i=0;i<m;i++)
  {
   for(int j=0;j<n;j++)
      	{
       		if(A[i][j]==x) dem=dem+1;
  		}
  }
 return dem; 
}

int main()
{
	int A[size][size],m,n,x;
	nhap(A,m,n);
	printf("Ta co duoc ma tran nhu sau: \n");
	xuat(A,m,n);
	printf("Vui long nhap mot so bat ky: ");
 	scanf("%d",&x);
	printf("so lan xuat hien xua x la: %d", SoLanXuatHien(A,m,n,x));
	return 0;
}
#12

Như mình và @Phong_Ky_Vo đã nói, về ý tưởng là dùng một thứ gì đó để lưu trữ lại số lần xuất hiện của mỗi phần tử.
Trong trường hợp này, tuỳ vào dữ liệu a[i][j] bạn nhập vào thì bạn có thể dùng map hoặc là tạo một mảng f[] để lưu lại số lần xuất hiện của nó.
Khi bạn gặp một phần tử a[i][j] == x, giả sử trước đó bạn gặp m phần tử (chính là giá trị của f[x] hiện tại), bây giờ bạn tăng f[x] thêm một lần, tức là mỗi lần đọc a[i][j], bạn tăng f[a[i][j]] lên 1.

Còn trong code của bạn thì hàm SoLanXuatHien(A[][], m, n, x) thì đếm tất cả những phần tử trong mảng bằng x, tức là x phải xác định. Hàm này dùng 2 vòng lặp để duyệt tất cả các phần tử trong mảng A[][], sau đó so sánh với x để xem phần tử A[i][j] đang được duyệt có bằng với x hay không; và số số phần tử bằng x chính là số lần xuất hiện của x trong mảng (tức là giá trị của biến dem = số lần xuất hiện của x). Dĩ nhiên cách này sẽ có lợi về bộ nhớ trong trường hợp ta chỉ biết một số x, nhưng với nhiều số x thì cách này không có lợi về thời gian.

83% thành viên diễn đàn không hỏi bài tập, còn bạn thì sao?