Форум программистов, компьютерный форум CyberForum.ru

Сравнени двух матриц (NxN-1) и (MxM-1) - C++

Восстановить пароль Регистрация
 
ККирилл
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
05.10.2010, 18:57     Сравнени двух матриц (NxN-1) и (MxM-1) #1
Добрый день уважаемые форумчане.
Не сочтите за дерзость, но нужна помощь. Поставил перед собой одну задачку (условия ниже).
Сам не являюсь программистом, решение данной задачи математически я написал, а как реализовать его в виде программного когда я к сожалению не знаю. Если поможете буду очень вам признателен.
Вот условие задачки:
Имеется две плоскости А и В. На одной плоскости (A) заданы N точек своими координатами (хранится в текстовом файле), на другой (B) M точек своими координатами (хранится в текстовом файле) N>M.
Составить функцию для построения одной матрицы расстояний между всеми точками N и второй матрицы между всеми точками М.
Составить функцию, которая позволяла бы сопоставлять расстояния между точками в матрице N с расстояниями между точками в матрице M.
Получается одна строка в матрице соответствует всем расстояниям для одной точки.
Составить функцию, которая способна определить, принадлежит ли строка одной матрицы другой строке другой матрицы.

Если нужны ещё какие-либо данные, прошу ссобщить.

С уважением.
После регистрации реклама в сообщениях будет скрыта и будут доступны все возможности форума.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
05.10.2010, 19:04     Сравнени двух матриц (NxN-1) и (MxM-1) #2
ККирилл, нужен пример, того как координаты хранятся в файлах и какие матрицы из них должны получиться.
Что значит "строка одной матрицы принадлежит строке другой матрицы", в смысле идентичны ли они?
ККирилл
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
05.10.2010, 20:55  [ТС]     Сравнени двух матриц (NxN-1) и (MxM-1) #3
fasked добрый вечер,
К сожалению не умею прикреплять изображение (попробую прикрепить файл).

Для большего понимания, что за матрицы формируются, предлагаю пример:
Имеем отпечаток пальца полный, после ряда преобразований имеем 70 особенных точек (минуций). Это и есть точки, которые после соединения формируют нашу матрицу N.
Теперь имеем частичный отпечаток того же пальца (50 особых точек). Из этих точек и формируется наша матрица M.
Вложения
Тип файла: doc Условие задачи про сравнение матриц.doc (24.5 Кб, 24 просмотров)
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
06.10.2010, 13:03     Сравнени двух матриц (NxN-1) и (MxM-1) #4
Цитата Сообщение от ККирилл Посмотреть сообщение
Для большего понимания, что за матрицы формируются, предлагаю пример:
Имеем отпечаток пальца полный, после ряда преобразований имеем 70 особенных точек (минуций). Это и есть точки, которые после соединения формируют нашу матрицу N.
Теперь имеем частичный отпечаток того же пальца (50 особых точек). Из этих точек и формируется наша матрица M.
Понравилось условие. Завтра, как будет перерыв, посмотрю вложение и подумаю, что можно сделать.

Добавлено через 14 часов 39 минут
Посмотрел и подумал, что использовать матрицы здесь не рационально.
Если оставлять матрицу расстояний вида:
Код
N1-2, N1-3, N1-4 ...
N2-1, N2-3, N2-4 ...
Можно заметить, что часть расстояний продублируется, то есть матрица избыточна. Например расстояния N1-2 и N2-1 безусловно равны.
Ко всему прочему это не прибавляет простоты реализации, потому что исключается расстояние от точки до самой же себя. Если такое расстояние включить, то реализация будет в разы проще, просто на главная диагональ матрицы станет нулевой. Я не думаю, что это значительные потери памяти

Чтобы сделать еще более эффективно и еще более просто, предлагаю воспользоваться вектором расстояний (хотя это не так наглядно). То есть вектор будет содержать следующие значения (для 4 точек):
Код
N1-2, N1-3, N1-4, N2-3, N2-4, N3-4
Вроде бы.
Сложность реализации от этого не страдает
Это самый обыкновенный полный перебор.

Хотя есть очень большая вероятность того, что так тяжело будет сравнивать с частичным отображением отпечатка ... Тут я еще не обдумал.

И, да, кстати. В том документе, что Вы прикрепили картинки расстянулись, читать уж очень неудобно
Еще я бы все таки хотел узнать, как именно будет храниться координаты точек в файлах.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
06.10.2010, 13:13     Сравнени двух матриц (NxN-1) и (MxM-1) #5
Да нет, реализация не усложняется))) Только что написал сначала для нулевой главной диагонали, потом, посмотрев задание, исключил её. Даже одна строка кода ушла)))
Вот что пока вышло:

C
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
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
#include <stdio.h>
#include <stdlib.h>
#include <math.h>
 
#define A "A.txt"
#define B "B.txt"
 
// Связный список для хранения координат точек
struct plane
{
    double x;
    double y;
    struct plane *next;
};
 
struct plane *makePlane(char *filename, int *count);
void deletePlane(struct plane *start);
void distance(double **matrix, int dim, struct plane *start);
 
int main()
{
    struct plane *startA = NULL; // Начальный элемент списка точек первой плоскости
    struct plane *startB = NULL; // Начальный элемент списка точек второй плоскости
    double **distA;              // Матрица расстояний между всеми точками первой плоскости
    double **distB;              // Матрица расстояний между всеми точками второй плоскости
    int N, M;                    // Счётчики количества точек
    int i, j;
 
    startA = makePlane(A, &N); // Создаём список точек первой плоскости
    startB = makePlane(B, &M); // Создаём список точек второй плоскости
 
    distA = (double **)malloc(N * sizeof(double *));
 
    for (i = 0; i < N; i++)
        distA[i] = (double *)malloc((N - 1) * sizeof(double));
 
    distB = (double **)malloc(M * sizeof(double *));
 
    for (i = 0; i < M; i++)
        distB[i] = (double *)malloc((M - 1) * sizeof(double));
 
    distance(distA, N, startA);
    distance(distB, M, startB);
 
    for (i = 0; i < N; i++)
    {
        for (j = 0; j < N - 1; j++)
            printf("%lf  ", distA[i][j]);
 
        printf("\n");
    }
 
    printf("\n");
 
    for (i = 0; i < M; i++)
    {
        for (j = 0; j < M - 1; j++)
            printf("%lf  ", distB[i][j]);
 
        printf("\n");
    }
 
    for (i = 0; i < N; i++)
        free(distA[i]);
 
    free(distA);
 
    for (i = 0; i < M; i++)
        free(distB[i]);
 
    free(distB);
 
    deletePlane(startA); // Очищаем память, выделенную для списка точек первой плоскости
    deletePlane(startB); // Очищаем память, выделенную для списка точек второй плоскости
 
    getch();
    return 0;
}
 
// Функция, создающая список точек, считываемых из файла
// Принимаемые параметры:
// filename - имя файла, содержащего координаты точек
// count - указатель на счётчик количества точек (в результате работы функции количество точек будет записано в эту переменную)
// Возвращаемое значение:
// Указатель на начало списка точек плоскости
struct plane *makePlane(char *filename, int *count)
{
    struct plane *start = NULL; // Начальный элемент списка точек плоскости
    struct plane *current;      // Текущий элемент списка точек плоскости
    struct plane *temp;         // Временный элемент
 
    FILE *fin; // Указатель на входной файл
 
    if ((fin = fopen(filename, "r")) == NULL) // Октрываем входной файл, а если его не удалось открыть,
    {
        fprintf(stderr, "Error opening file \"%s\"!", filename); // сообщаем об ошибке
        getch();
        exit(1);                                                 // и выходим
    }
 
    *count = 0;
 
    while(!feof(fin)) // Продолжаем считывание, пока не достигнем конца файла
    {
        temp = (struct plane *)malloc(sizeof(struct plane)); // Выделяем память под очередной элемент списка
        fscanf(fin, "%lf %lf", &(temp->x), &(temp->y));      // и считываем в него координаты очередной точки
        temp->next = NULL;                                   // Устанавливаем указатель на следующий элемент в NULL
 
        if (start == NULL) // Если список ещё не был создан
        {
            start = temp;    // Созданный элемент делаем начальным
            current = start; // Начальный элемент делаем текущим
        }
        else // Если продолжаем создание списка, начатое ранее
        {
            current->next = temp; // В текущем элементе указатель на следующий элемент устанавливаем на созданный
            current = temp;       // Созданный элемент делаем текущим
        }
 
        (*count)++; // Увеличиваем счётчик точек плоскости
    }
 
    fclose(fin);
 
    return start;
}
 
// Функция, очищающая память, выделенную для списка точек
// Принимаемые параметры:
// *start - указатель на начало списка точек
void deletePlane(struct plane *start)
{
    struct plane *temp; // Временный элемент
 
    // в цикле пробегаем все элементы списка
    while (start != NULL)
    {
        temp = start;        // Устанавливаем указатель temp на элемент start
        start = start->next; // Устанавливаем указатель start на следующий элемент списка
        free(temp);          // Освобождаем память, на которую указывает temp
    }
}
 
// функция, рассчитывающая расстояния между всеми точками плоскости
// Принимаемые параметры:
// **matrix - указатель на матрицу расстояний (в результате матрица запишется в эту переменную)
// dim - количество точек плоскости
// *start - указатель на список точек
void distance(double **matrix, int dim, struct plane *start)
{
    struct plane *temp; // Временная переменная
    double x, y;        // Вершины очередной точки, от которой считается расстояние до остальных точек
    int i, j, k;
 
    // В цикле забиваем данными все ячейки матрицы
    for (i = 0; i < dim; i++)
    {
        temp = start; // Устанавливаем временный указатель на начало списка точек
        k = 0;
 
        // Ищем точку, от которой будем рассчитывать расстояние до остальных
        while (k < i)
        {
            temp = temp->next;
            k++;
        }
 
        x = temp->x; // Запоминаем вершины
        y = temp->y; // найденной точки
        temp = temp->next;
 
        for (j = i; j < dim - 1; j++)
        {
            matrix[i][j] = sqrt(pow(x - temp->x, 2.0) + pow(y - temp->y, 2.0)); // Рассчитываем расстояние от найденной точки до очередной
            matrix[j + 1][i] = matrix[i][j];                                    // Поскольку расстояния дублируются, сохраняем найденной расстояние в дублируемую ячейку
            temp = temp->next;                                                  // Продвигаемся дальше по списку точек
        }
    }
}
Для простоты реализации сравнения всё же думаю, что удобнее хранить расстояния не в векторе, а в матрице. Да и нагляднее, когда есть матрица. Проще плоскость представлять.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
06.10.2010, 13:20     Сравнени двух матриц (NxN-1) и (MxM-1) #6
Вот такой вот код на Си формирует для пяти точек соответствующую матрицу:
C
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
39
40
41
42
43
44
45
46
47
48
#include <stdlib.h>
#include <stdio.h>
#include <math.h>
 
typedef struct {
    double x;
    double y;
} point_t;
 
double distance(point_t *a, point_t *b) {
    return sqrt(pow(a->x - b->x, 2) + pow(a->y - b->y, 2));
}
 
#define NPOINTS 5
 
int main() 
{
    int i = 0;
    int j = 0;
    int k = 0;
    point_t points[NPOINTS];
    double distances[NPOINTS][NPOINTS];
    
    for(i = 0; i < NPOINTS; ++i) {
        points[i].x = (double)rand() / rand();
        points[i].y = (double)rand() / rand();
    }
    
    for(i = 0; i < NPOINTS; ++i) {
        printf("%d: [%f, %f]\n", i, points[i].x, points[i].y);
    }
    printf("\n");
    
    for(i = 0; i < NPOINTS; ++i) {
        for(j = 0; j < NPOINTS; ++j) {
            distances[i][j] = distance(&points[i], &points[j]);
        }
    }
    
    for(i = 0; i < NPOINTS; ++i) {
        for(j = 0; j < NPOINTS; ++j) {
            printf("%f ", distances[i][j]);
        }
        printf("\n");
    }
    
    return 0;
}
Код
0: [2.130386, 0.980787]
1: [4.614736, 0.436358]
2: [0.501426, 0.759134]
3: [0.710526, 1.039331] 
4: [0.886260, 0.233295]

0.000000 2.543305 1.643971 1.421067 1.451410 
2.543305 0.000000 4.125955 3.950498 3.734001 
1.643971 4.125955 0.000000 0.349619 0.651617 
1.421067 3.950498 0.349619 0.000000 0.824971 
1.451410 3.734001 0.651617 0.824971 0.000000
Остается сформировать еще одну матрицу, и найти подматрицу в матрице - что в принципе не очень то сложно. Вы только ответьте на вопрос насчет файлов. Сейчас точки генерируются случайным образом.

Добавлено через 2 минуты
Цитата Сообщение от silent_1991 Посмотреть сообщение
Для простоты реализации сравнения всё же думаю, что удобнее хранить расстояния не в векторе, а в матрице. Да и нагляднее, когда есть матрица. Проще плоскость представлять.
Конечному пользователю в итоге будет пофигу, как храняться данные. А память сэкономить всегда приятно
Возможно, если повыситься точность данных, то точек станет еще больше, следовательно время перебора заметно ускориться.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
06.10.2010, 13:33     Сравнени двух матриц (NxN-1) и (MxM-1) #7
fasked,
Но по какому критерию тогда разделять вектор на строки матрицы, чтобы потом сравнивать именно строки?

ККирилл,
А что должно быть результатом сравнения матриц? Я думал, может это реализовать в виде двумерного массива с двумя строками, в котором в первой строке будет номера строк в матрице N, а во второй - номера строк матрицы M, которые содержатся в соответствующей строке N? Т.е. примерно так:

Код
1 1 1 2 2 3 4 4
1 2 3 2 3 1 1 3
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
06.10.2010, 14:23     Сравнени двух матриц (NxN-1) и (MxM-1) #8
Цитата Сообщение от silent_1991 Посмотреть сообщение
Но по какому критерию тогда разделять вектор на строки матрицы, чтобы потом сравнивать именно строки?
Матрицы делится на две половины главной диагональю. Половины матрицы дублируют друг друга, следовательно одну из них можно смело отбрасывать.
Также мы знаем, что матрицу можно представить в виде одномерного массива, используя для доступа к конкретному объекту формулу вида [ROWS * i + j]. Исходя из этого, думаю, что к данной формуле можно присобачить обход верхнего (или нижнего) треугольника матрицы и вуаля.

Добавлено через 3 минуты
Размер такого массива будет равен (N*N - N)/2. Против N*N или N*(N-1) с использованием матриц.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
06.10.2010, 14:24     Сравнени двух матриц (NxN-1) и (MxM-1) #9
Ну если мы нули отбрасываем, то там уже несколько не так будет, матрица уже не делится главной диагональю на две треугольных... Она уже даже перестаёт быть квадратной. Но в целом я понял идею, думаю, предоставим ТСу два варианта на выбор)))

Добавлено через 53 секунды
fasked,
Ну т.е. в два раза меньше))) Согласен, это ощутимо))
ККирилл
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
06.10.2010, 15:58  [ТС]     Сравнени двух матриц (NxN-1) и (MxM-1) #10
Господа, не ожидал такого бурного осуждения. Очень приятно удивлён.
С вашего позволения постараюсь разъяснить более точно:
Имеется плоский отпечаток пальца. После всех преобразований, получаем множество точек N (особых точек – минуций). Для компьютера это просто точки. Далее каждая точка соединяется с каждой и расстояния между ними заносятся в матрицу NN. Как уже правильно было замечено, расстояния повторяются N12=N21. Таких матриц в БДЗ у нас много (может доходить до одного миллиона или даже больше). На данном этапе имеем БДЗ с матрицами.
Теперь предположим, у нас появился какой-то отпечаток пальца (полны или частичный – это не важно). Мы хотим понять, есть ли у нас в БДЗ такой. Для этого над ним проделываем такие же перобразования и получаем множество точек M (особых точек – минуций). Пускай M<N. Далее каждая точка соединяется с каждой и расстояния между ними заносятся в матрицу MM.
Полученную матрицу MM необходимо сравнить со всеми матрицами в БДЗ. Прозвучал вопрос - А что должно быть результатом сравнения матриц? Мне видится это так:
У нас есть строка матрицы NN (соответствует всем расстояния от одной точки до остальных). Выглядит примерно так (0; 1; 2; 3; 4; 5; 6; 7; 8). И есть сторка матрицы MM (0; 3; 4; 5). Как видно, если откинуть 0, то сторка из MM содержится в NN (у них общие расстояния (3; 4; 5). И так сравниваются все строки из ММ со всеми строками из NN. Если у нас все строки из MM содержатся в MM – тогда считаем что отпечатки совпадают.
Но может быть и такая ситуация, что отпечаток повернут. На расстояние между точками это никак не повлияет, но повлияет на их последовательность расположения. Например строка матрицы MM’ (0; 5; 3; 4). Как быть тогда???? Мне кажется нужно эту достроить, то есть справа от неё добавить такую же и у нас получится следующая строчка (0; 5; 3; 4; 0; 5; 3; 4). Убираю нули, получаем (5; 3; 4; 5; 3; 4). Получается, что у них общее расстояние.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
06.10.2010, 16:09     Сравнени двух матриц (NxN-1) и (MxM-1) #11
ККирилл,
Хм... В прикреплённом вами файле написано
Строчки матрицы N необходимо сравнивать со строчками матрицы M. Строка Nn считается равной строке Mm, если все расстояния из строки Mm содержатся в Nn.
А из вашего сообщения я понял, что нужно искать именно подпоследовательность в последовательности... Кому верить?)))
ККирилл
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
06.10.2010, 16:35  [ТС]     Сравнени двух матриц (NxN-1) и (MxM-1) #12
Приношу мзвинения если дезинформировал. Исходя из моих предполажений, необходимо искать подпоследовательность последовательности, ибо только тогда можно утверждать , что отпечаток (набор точек) принадлежит другому отпечатку.
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
06.10.2010, 18:10     Сравнени двух матриц (NxN-1) и (MxM-1) #13
ККирилл,
О чём вы, какая дезинформация))) Из моих умозаключений следует то же самое, что из ваших. Но просто когда появляются два варианта условия задачи, я начинаю очень неуютно себя чувствовать...
ККирилл
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
08.10.2010, 08:33  [ТС]     Сравнени двух матриц (NxN-1) и (MxM-1) #14
Очень понравилась идея, что данные могут храниться в виде половинчатой матрицы ((N*N - N)/2) что я так полагаю позволит сэкономить объём в два раз. Но для восстановления и получения полной матрицы нужна будет функция, которая её воостанавливает.
fasked
Эксперт C++
 Аватар для fasked
4924 / 2504 / 180
Регистрация: 07.10.2009
Сообщений: 4,306
Записей в блоге: 1
08.10.2010, 08:54     Сравнени двух матриц (NxN-1) и (MxM-1) #15
Цитата Сообщение от ККирилл Посмотреть сообщение
Очень понравилась идея, что данные могут храниться в виде половинчатой матрицы ((N*N - N)/2) что я так полагаю позволит сэкономить объём в два раз. Но для восстановления и получения полной матрицы нужна будет функция, которая её воостанавливает.
Да и восстанавливать ее я тоже не вижу особого смысла. Тут проблема в том, что довольно сложно совершить обход такого массива.
ККирилл
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
08.10.2010, 09:42  [ТС]     Сравнени двух матриц (NxN-1) и (MxM-1) #16
Сравнивать такие массивы между собой мне кажется гораздо сложнее, нежели матрицы. Значит ли сиё, что решение данной задачи (в программном коде) очень сложное и нереализуемо?
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.10.2010, 11:20     Сравнени двух матриц (NxN-1) и (MxM-1)
Еще ссылки по теме:

Произведение двух матриц C++
C++ Умножение двух матриц
Вычисление степени матрицы, вычисления произведения двух матриц, вычисление суммы двух матриц C++

Искать еще темы с ответами

Или воспользуйтесь поиском по форуму:
silent_1991
Эксперт C++
4938 / 3014 / 149
Регистрация: 11.11.2009
Сообщений: 7,024
Завершенные тесты: 1
08.10.2010, 11:20     Сравнени двух матриц (NxN-1) и (MxM-1) #17
Возможно всё, что возможно вообразить))) Можно поступить следующим образом (в теории): Завести трёхмерный массив. В первой строке хранить элементы так, как предложил fasked. В оставшихся двух строках хранить индексы этих элементов, какими они были бы, если бы мы представляли всё это дело в виде обычной матрицы. Почему трёхмерный? Потому что индекс может дублироваться либо 0 раз (единственное значение в матрице), либо один раз (два значения в исходной матрице). Таким образом достаточно составить функцию, генерирующую этот массив посредством вычисления индексов. Так память будет сокращена хоть и не в два раза, но всё же места займёт меньше, чем обычная матрица. А обход такого массива можно совершать точно так же, как и обход обычной матрицы, просто очередной элемент надо будет искать на основе списка индексов.

Добавлено через 2 минуты
Вернее нет, не трёхмерный, а пятимерный, потому как у нас может быть либо два индекса (i, j), либо четыре (i1, j1; i2, j2). А можно поступить иначе и хранить всё это дело в связных списках. Тут и добавление проще будет, и обход, и лишней памяти на не дублирующиеся элементы не расходуется. Каждая запись списка - структура из двух полей - i и j.
Yandex
Объявления
08.10.2010, 11:20     Сравнени двух матриц (NxN-1) и (MxM-1)
Ответ Создать тему
Опции темы

Текущее время: 16:45. Часовой пояс GMT +3.
КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2016, vBulletin Solutions, Inc.
Рейтинг@Mail.ru