1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 |
uses crt; const nmax=20; var a:array[1..nmax,1..nmax] of integer; n,i,j,p,q,m:byte; begin clrscr; repeat write('Размер матрицы до ',nmax,' n='); readln(n); until n in [1..nmax]; writeln('Введите ',n*n,' элементов матрицы:'); for i:=1 to n do for j:=1 to n do read(a[i,j]); readln; clrscr; writeln('Матрица:'); for i:=1 to n do begin for j:=1 to n do write(a[i,j]:5); writeln; end; writeln; m:=0; writeln('Одинаковые элементы в матрице:'); for i:=1 to n do for j:=i to n do for p:=1 to n do for q:=1 to n do if (a[i,j]=a[p,q])and((p<>i)or(q<>j)) then begin m:=1; writeln('a[',i,',',j,']=a[',p,',',q,'] = ',a[i,j]); end; if m=0 then write('Все числа разные!'); readln end. |
Ищем в матрице количество повторяющихся элементов
Задача определения в двумерном массиве количества элементов, для которых есть элементы с такими же значениями — не столь уж тривиальная. Нам понадобится, во-первых, придумать, как организовать сравнение каждого элемента матрицы с каждым. Для вектора (одномерного массива) 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 [19411 просмотров]
К этой статье пока нет комментариев, Ваш будет первым
Матрица содержит два одинаковых элемента. Найдите эти элементы и их индексы (никакой элемент матрицы не должен сравниваться сам с собой).
не работает
#include <iostream>
using namespace std;
int main()
{
int m, n;
cout << "enter row ";
cin >> m;
cout << "enter cols ";
cin >> n;
int **A = new int*[m];
for(int i = 0; i < m; i++)
{
A[i] = new int [n];
}
for(int i = 0; i < m; i++)
{
for(int k = 0; k < n; k++)
{
cout << "vvedite element" << "[" << i << "]" << "[" << k << "]" << " = " ;
cin >> A[i][k];
}
cout << endl;
}
for(int i = 0; i < m; i++)
{
for(int k = 0; k < n; k++)
{
cout << A[i][k] <<' ';
}
cout << endl;
}
for (int i = 0; i < m; i++)
for (int k = 0; k < n; k++)
for (int s = i; s < m; s++)
for (int t = k + 1; t < n; t++)
if (A[i][k] == A[s][t])
cout << "A[" << i << "][ " << k << "] == A[ " << s << "][" << t << "]" << endl;
for(int i = 0; i < m; i++)
{
delete [] A[i];
}
delete [] A;
system("pause");
return 0;
}
задан 3 дек 2019 в 20:17
const int n = 4;
const int m = 5;
int mass[n][m];
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
mass[i][j] = rand() % 90;
std::cout << mass[i][j] << " ";
}
std::cout << std::endl;
}
for (int i = 0; i < n; i++)
{
for (int j = 0; j < m; j++)
{
for (int s = i; s < n; s++)
{
for (int t = j + 1; t < m; t++)
if (mass[i][j] == mass[s][t])
{
std::cout << "mass[" << i << "][ " << j <<
"] == mass[ " << s << "][" << t << "]" << std::endl;
}
}
}
}
ответ дан 3 дек 2019 в 20:51
ANGRY SHARKANGRY SHARK
4662 серебряных знака14 бронзовых знаков
3
int c, r, i, j, m[100][100], el, c_el, r_el, i_el, j_el; //Объявление переменных
cout<<"Размер двумерного массива"<<endl;
cout<<"Введите количество столбцов-->";
cin>>c;
cout<<endl;
cout<<"Введите количество строк-->";
cin>>r;
cout<<endl;
For (i=0; i<c; i++) //Заполнение массива
{
For (j=0; j<r; i++)
{
cout<<"Введите элемент M["<<i<<"]["<<j<<"] -->";
cin<<M[i][j];
}
}
cout<<"Заполненная матрица:"<<endl;
For (i=0; i<c; i++)
{
For (j=0; j<r; i++)
{
cout<<"M[i][j]";
}
cout<<endl;
}
c_el = c;
r_el = r;
For (i_el=0; i_el<c_el; i_el++)
{
el = M[i_el][j_el];
For (j_el=0; j_el<0; j_el++)
{
For (i=0; i<c; i++)
{
For (j=0;j<r;i++)
{
if (el==M[i][j] && c_el<>i && r_el<>j) //Сравниваем значения, если разные индексы
{
cout<<"Элемент M["<<i<<"]["<<j<<"] и Элемент M["<<c_el<<"]["<<r_el<<"] имеют одинаковое значение ="<< M[i][j]<<endl;
break;
}
}
}
}
}
ответ дан 3 дек 2019 в 21:43
A BA B
3621 серебряный знак8 бронзовых знаков
К сожалению не нашел ничего такого же красивого в пхп как в питоне (пост выше )
Но у меня вот что получилось, если кому интересно
$a = array(
array(1,2,4,5,6,7),
array(2,5,7,1),
array(1,2),
array(1,'a','g',2),
);
$res = array();
for($i=0; $i<count($a[0]); $i++){
$flag = 0;
for($j=1; $j<count($a); $j++){
for($k=0; $k<count($a[$j]); $k++){
if($a[0][$i] == $a[$j][$k]){
$flag ++ ;
if($flag == 3){ array_push($res, $a[0][$i]); }
}
} // k
} // j
} // for i
print_r($res);Здравствуйте,подскажите пожалуйста, каким образом можно сравнить и найти соответствия всех строк в матрице.
Матрица двумерный массив n*m. Сравнить одну строку со следующей получается, т.е посимвольно, делаю так:
Код:
int n, // число строк
m; // число элементов в строке
for(i=0; i<n-1; i++)
{
for(j=0; j<m; j++)
{
if(nm[j]==nm[i+1][j])
{
// j элемент i ой строки совпадает с
// j элементом i+1 ой строки
}
}
}
Но мне необходимо найти одинаковые строки, и вывести соответственно какие строки и сколько раз совпали.
Подскажите пожалуйста, а то никак не могу сообразить. Заранее спасибо за все советы.
upd:
Код:
for(i=0; i<n-1; i++)
{
count=0;
fprintf(out,» n»);
for(j=0; j<m; j++)
{
fprintf(out,»%2d»,nm[j]);
}
fprintf(out,»-«);
for (x=i;x<n-1;x++)
{
key=0;
for(j=0; j<m; j++)
{
if(nm[j]==nm[x+1][j])
{
key=key+1;
if(key==m)
{
hit=true;
fprintf(out, «%d,»,x+1);
}
}
}
}
Теперь проблема в том что, после сравнения первой строки и нахождения всех соответствий ей, когда цикл переходит на следующую строчку, он заново проверяет туже самую строку и говорит что она совпала еще несколько раз.
Как исключить из поиска уже идентичную строку которая уже проверена?
9 ответов
360
01 мая 2008 года
P*t*
474 / / 15.02.2007
Вариант 1:
Перебрать все пары строк и сравнить.
сложность — O(n*n*m)
Вариант 2:
Определить для строк сравнение (больше / меньше).
Отсортировать строки.
За один проход цикла найти повторяющиеся.
сложность — O(n*m* log n)
37K
01 мая 2008 года
netloger
5 / / 01.05.2008
Спасибо. Мне бы хотелось сделать так, чтобы бралась первая строка, сравнивалась со всеми остальными строками, потом соответственно должна сравниваться вторая строка с остальными. Не могу написать цикл, которыйбы проходил вначале по всей матрице и срванивал все с первой строкой, потом переходил на вторую строку и опять срванивал со всеми строками матрицы.
если строки типа char* то подойдет ф-я strcmp(char*, char*)
в принципе если и string то тоже подойдет
37K
01 мая 2008 года
netloger
5 / / 01.05.2008
матрица из целых чисел int
320
01 мая 2008 года
m_Valery
1.0K / / 08.01.2007
Операция == проверяет на равенство векторы. Сделай матрицу как вектор векторов,где каждая строка вектор целых чисел и проверяй.Это ж С++ ?
37K
01 мая 2008 года
netloger
5 / / 01.05.2008
Если я правильно понял, нужно создать класс вектор?
да,с++
А без классов можно реализовать?
320
01 мая 2008 года
m_Valery
1.0K / / 08.01.2007
Если я правильно понял, нужно создать класс вектор?
да,с++
А без классов можно реализовать?
Не надо ничего создавать.Вот матрица на основе вектора.Используется контейнер vector.
Код:
#include <iostream>
#include <ctime>
#include <iomanip>
#include <vector>
using namespace std;
typedef vector< vector<int> > T;
ostream &operator<<(ostream &output,const T &mass)
{
for(size_t i = 0;i<mass.size();++i){
for(size_t j = 0;j<mass.size();++j)
output<<setw(5)<<mass[j];
output<<«nn»;
}
return output;
}
int _tmain(int argc, _TCHAR* argv[])
{
srand((unsigned)time(0));
unsigned int row,col;
do{
cout<<«Enter rows > 0″<<endl;
cin>>row;
}while(row <= 0);
do{
cout<<«Enter col > 0″<<endl;
cin>>col;
}while(col <= 0);
T mass(row, vector<int>(col));
for(size_t i = 0;i < row;++i){
for(size_t j = 0;j < col;++j)
mass[j] = rand()%10;
}
cout<<mass;
return 0;
}
37K
01 мая 2008 года
netloger
5 / / 01.05.2008
Всем спасибо большое за советы, задача решена.
87
01 мая 2008 года
Kogrom
2.7K / / 02.02.2008
Ну вот…. я ожидал тут короткое решение с использованием STL… У самого получается только что-то типа:
Код:
#include <iostream>
#include <sstream>
#include <vector>
using namespace std;
int main()
{
string s;
vector<string> coll, bufColl;
stringstream os;
int oldSize;
// Ввод строк
cout << «Input strings» << endl;
getline(cin, s, ‘n’);
os << s;
while(!os.eof()) {
os >> s;
coll.push_back(s);
}
// Сам подсчет строк
cout << «Result:» << endl;
bufColl = coll;
while (bufColl.size())
{
vector<string>::iterator pos;
s = bufColl[0];
oldSize = bufColl.size();
pos = remove(bufColl.begin(), bufColl.end(), s);
bufColl.erase(pos, bufColl.end());
cout << s << » : » << oldSize — bufColl.size() << endl;
}
return 0;
}