C/C++ - Сходства матриц разной размерности

C/C++ - Сходства матриц разной размерности

xNiSSaNx

Старожил

Сообщения: 160
Благодарности: 0

Однажды по программированию(в ВУЗе) препод спросил: "Кто ранее программировал?" Я поднял руку, и вот он мне дал пару задач для индивидуальной работы, первую я сделал, немного подумав, а вот со второй дела сложнее,
-=Нужно найти сходства в двух матрицах разной размерности=-
Препод сказал, что поиск сходства должен выполняться так как я понимаю само значение "сходства", тоесть могу элементы двух матриц с одинаковыми индексами проверить, н оэто будет детской задачей)))

Думаю нужно вот так:
Например есть матрици:
0 0 1 0
0 1 1 1
0 1 1 0
0 0 0 1

и

1 1
1 0

и определить есть ли в них сходства, в данном случае есть))

ну или с этой
0 1
0 1
0 0

Более часа раздумый и эксперементов привели к вот этому

-=-=-=-=-=-=-=-=-=-=-

#include "stdafx.h"
#include <iostream>
using namespace std;

int m1[9][9],m2[9][9];

int rand_m1_i=5,rand_m1_j=5,rand_m2_i=3,rand_m2_j=1;
int _tmain(int argc, _TCHAR* argv[])
{

for(int i=0;i<rand_m1_i;i++)
{
for(int j=0;j<rand_m1_j;j++)
{
cout << (m1[i][j]=rand()%2+1)<<" ";
}
cout << "\n";
}
cout << "\n";
for(int i=0;i<rand_m2_i;i++)
{
for(int j=0;j<rand_m2_j;j++)
{
cout << (m2[i][j]=rand()%2+1)<<" ";
}
cout << "\n";
}
cout << "\n";

for(int stroka=0;stroka<=rand_m1_i-rand_m2_i;stroka++)
{
for(int stolb=0;stolb<=rand_m1_j-rand_m2_j;stolb++)
{

for(int i=0+stroka;i<rand_m2_i+stroka;i++)
{
for(int j=0+stolb;j<rand_m2_j+stolb;j++)
{
if(m1[i][j]==m2[i-stroka][j-stolb])cout << "Y ";else cout << "N ";

}cout << "\n";
}cout << "\n";
}
}
return 0;
}

=-=-=-=-=-=-=-=-=-=-=

В данном случае получаем 2 матрицы заданой размерности(при чем вторая не должна быть больше первой) и, если визуально представить, перемещаем поверх первой матрицы вторую так, чтобы она прошлась по всем элементам первой.
"Лень со мной согласится", что задача выполнена, но возможно и нет))) Есть идея того, чтобы брать куски со второй матрицы и их так же таскать по первой, но это не сейчас.

Как думаете, этого достаточно?

Отправлено: 00:34, 05-10-2013

pva

Ветеран

Сообщения: 1180
Благодарности: 279

Профиль | Отправить PM | Цитировать

алгоритм решения любой задачи:
1. формализация постановки
2. выбор метода решения
3. решение
xNiSSaNx, озвучь 1 (какой критерий выбрал, ограничения) и 2 (известное в мире название метода), и оберни тегами "code" 3, а то не понятно

Например:
1. найти N максимально похожих подблока 2x2 двух матриц размерами не менее 2x2
критерий похожести - попарная корреляция http://ru.wikipedia.org/wiki/%D0%9A%...86%D0%B8%D1%8F
2. вычислить корреляционную функцию R двух матриц с окном 2x2
отсортировать координаты матриц по убыванию R, вывести первые N элементов с указанием значения.
3...

Если останутся силы, варианты усложнения:
* использовать гладкое окно (http://ru.wikipedia.org/wiki/%CE%EA%...D4%F3%F0%FC%E5, читать про оконные функции)
* использовать БПФ для ускорения вычислений на больших матрицах

Это сообщение посчитали полезным следующие участники:

Iska, lxa85

Отправлено: 19:24, 05-10-2013 | #2