Ищем в матрице количество повторяющихся элементов
Задача определения в двумерном массиве количества элементов, для которых есть элементы с такими же значениями - не столь уж тривиальная. Нам понадобится, во-первых, придумать, как организовать сравнение каждого элемента матрицы с каждым. Для вектора (одномерного массива) a
из n
элементов было бы элементарно - организовать двойной цикл вида
int i,j; for (i=0; i<n-1; i++) for (j=i+1; j<n; j++) { //Сравниваем a[i] и a[j] }
Но ведь к матрице тоже можно обращаться как к вектору, если организовать "сквозные" счётчики элементов i
и j
, меняющиеся в пределах [0,n*m-2]
, [i+1,n*m-1]
соответственно, и затем брать в двойном цикле элементы матрицы a[i/m][i%m]
и a[j/m][j%m]
.
Кроме того, нам придётся учесть, что подсчитать количество выполнений равенства a[i/m][i%m]==a[j/m][j%m]
недостаточно - некоторые элементы могут быть подсчитаны неоднократно. Поэтому перед обработкой очередного элемента a[i/m][i%m]
нужно проверить, не было ли перед ним в матрице таких же значений. Если да, элемент уже был обработан (флаг found
в программе).
Ну и количество выполнений равенства не есть искомое количество "элементов с повторами" - если в матрице 3 числа-двойки, с ними будет сделано только 2 сравнения (флаг found2
в программе корректирует проблему).
//Ищем в матрице количество повторяющихся элементов #include <stdio.h> int main () { const int n=3,m=4; int a[n][m] = { {1,2,3,3}, {5,5,7,8}, {9,9,11,9} }; //или ввод матрицы a[n][m] int i,j,l,i1,i2,j1,j2,k,kmax=0,imax,all=0,found,found2; for (i=0; i<n*m-1; i++) { found = 1; //надо ли искать "вниз" от текущего элемента i1 = i/m; j1 = i%m; for (l=0; l<i; l++) { //если раньше был такой элемент - искать с него не надо i2 = l/m; j2 = l%m; if (a[i1][j1]==a[i2][j2]) { found = 0; break; } } if (found) { found2 = 0; //найдено ли "вниз" от текущего элемента for (j=i+1; j<n*m; j++) { //ищем после элемента такие же по значению i2 = j/m; j2 = j%m; if (a[i1][j1]==a[i2][j2]) { all++; found2 = 1; } } if (found2) all++; } //ищем макс.количество повторов в строке kmax k = 0; for (j=0; j<m; j++) if (a[i1][j]==a[i1][j1]) k++; if (k>kmax) { kmax = k; imax = i1; } } if (all>0) { printf ("\nВсего элементов с повторами значений: %d\ \nСтрока с наибольшим числом одинаковых: ",all); for (j=0; j<m; j++) printf ("%d ",a[imax][j]); } else printf ("\nНет повторов!"); getchar(); return 0; }
Наверняка возможен алгоритм получше, просто нужно было быстрое "лобовое" решение.
Дополнительно в примере ищется номер первой из строк, содержащих наибольшее количество одинаковых элементов (переменная imax
).
Если мы хотим, наоборот, вывести все не-повторяющиеся элементы матрицы целых значений, программу можно изменить так, тоже особо не проверял:
//Выводим не-повторяющиеся элементы матрицы #include <cstdio> int main() { const int n = 3, m = 4; int a[n][m] = { { 1,2,3,3 }, { 5,5,7,8 }, { 9,9,11,9 } }; //или ввод матрицы a[n][m] int i, j, l, i1, i2, j1, j2, found, found2; for (i = 0; i < n * m - 1; i++) { found = 1; //надо ли искать "вниз" от текущего элемента i1 = i / m; j1 = i % m; for (l = 0; l < i; l++) { //если раньше был такой элемент - искать с него не надо i2 = l / m; j2 = l%m; if (a[i1][j1] == a[i2][j2]) { found = 0; break; } } if (found) { found2 = 0; //найдено ли "вниз" от текущего элемента for (j = i + 1; j < n*m; j++) { //ищем после элемента такие же по значению i2 = j / m; j2 = j%m; if (a[i1][j1] == a[i2][j2]) { found2 = 1; break; } } if (!found2) { printf("%d ", a[i1][j1]); } } } getchar(); return 0; }
Если работать с одномерным массивом, можно решить и за время O(n), но ценой "порчи" элементов массива или использования копии массива в памяти.
07.10.2014, 15:42 [20574 просмотра]