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

С++ для начинающих

Войти
Регистрация
Восстановить пароль
 
 
ККирилл
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
#1

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

05.10.2010, 18:57. Просмотров 952. Ответов 16
Метки нет (Все метки)

Добрый день уважаемые форумчане.
Не сочтите за дерзость, но нужна помощь. Поставил перед собой одну задачку (условия ниже).
Сам не являюсь программистом, решение данной задачи математически я написал, а как реализовать его в виде программного когда я к сожалению не знаю. Если поможете буду очень вам признателен.
Вот условие задачки:
Имеется две плоскости А и В. На одной плоскости (A) заданы N точек своими координатами (хранится в текстовом файле), на другой (B) M точек своими координатами (хранится в текстовом файле) N>M.
Составить функцию для построения одной матрицы расстояний между всеми точками N и второй матрицы между всеми точками М.
Составить функцию, которая позволяла бы сопоставлять расстояния между точками в матрице N с расстояниями между точками в матрице M.
Получается одна строка в матрице соответствует всем расстояниям для одной точки.
Составить функцию, которая способна определить, принадлежит ли строка одной матрицы другой строке другой матрицы.

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

С уважением.
0
Similar
Эксперт
41792 / 34177 / 6122
Регистрация: 12.04.2006
Сообщений: 57,940
05.10.2010, 18:57
Здравствуйте! Я подобрал для вас темы с ответами на вопрос Сравнени двух матриц (NxN-1) и (MxM-1) (C++):

Вычисление степени матрицы, вычисления произведения двух матриц, вычисление суммы двух матриц - C++
Здравствуйте, помогите решить, пожалуйста: Заданы две квадратные матрицы А и В. Вычислить матрицу...

Сформировать произвольную матриц размерностью NxN.Найти наибольший и наименьший элемент выше побочной диагонали - C++
привет всем, помогите составить прогу. Дано натуральное число N. сформировать произвольную матриц размерностью NxN.Найти наибольший и...

Из двух квадратных матриц создать третью, перемножив элементы первых двух согласно условию - C++
Для двух квадратных матриц нужно создать третюю матрицу, элементы которой которой должны равняться произведению элементов соответствующей...

Перемножение двух матриц - C++
int Multiplication(int a, int b) { cout << "***********Result***********" << endl; int c; for(int i = 0; i < 5; i++) // i...

Сложение двух матриц - C++
помогите пожалуйста написать программу на языке С ++. даны два двумерных массива. нужно найти их сумму.

Умножение двух матриц - C++
Помогите написать перемножение двух матриц без создание третьей матрицы. Что-то написал, но не то очевидно... matrix*...

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

Для большего понимания, что за матрицы формируются, предлагаю пример:
Имеем отпечаток пальца полный, после ряда преобразований имеем 70 особенных точек (минуций). Это и есть точки, которые после соединения формируют нашу матрицу N.
Теперь имеем частичный отпечаток того же пальца (50 особых точек). Из этих точек и формируется наша матрица M.
1
Вложения
Тип файла: doc Условие задачи про сравнение матриц.doc (24.5 Кб, 24 просмотров)
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
06.10.2010, 13:03 #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
Вроде бы.
Сложность реализации от этого не страдает
Это самый обыкновенный полный перебор.

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

И, да, кстати. В том документе, что Вы прикрепили картинки расстянулись, читать уж очень неудобно
Еще я бы все таки хотел узнать, как именно будет храниться координаты точек в файлах.
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
06.10.2010, 13:13 #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;                                                  // Продвигаемся дальше по списку точек
        }
    }
}
Для простоты реализации сравнения всё же думаю, что удобнее хранить расстояния не в векторе, а в матрице. Да и нагляднее, когда есть матрица. Проще плоскость представлять.
0
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
06.10.2010, 13:20 #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 Посмотреть сообщение
Для простоты реализации сравнения всё же думаю, что удобнее хранить расстояния не в векторе, а в матрице. Да и нагляднее, когда есть матрица. Проще плоскость представлять.
Конечному пользователю в итоге будет пофигу, как храняться данные. А память сэкономить всегда приятно
Возможно, если повыситься точность данных, то точек станет еще больше, следовательно время перебора заметно ускориться.
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
06.10.2010, 13:33 #7
fasked,
Но по какому критерию тогда разделять вектор на строки матрицы, чтобы потом сравнивать именно строки?

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

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

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

Добавлено через 53 секунды
fasked,
Ну т.е. в два раза меньше))) Согласен, это ощутимо))
0
ККирилл
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
06.10.2010, 15:58  [ТС] #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). Получается, что у них общее расстояние.
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
06.10.2010, 16:09 #11
ККирилл,
Хм... В прикреплённом вами файле написано
Строчки матрицы N необходимо сравнивать со строчками матрицы M. Строка Nn считается равной строке Mm, если все расстояния из строки Mm содержатся в Nn.
А из вашего сообщения я понял, что нужно искать именно подпоследовательность в последовательности... Кому верить?)))
0
ККирилл
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
06.10.2010, 16:35  [ТС] #12
Приношу мзвинения если дезинформировал. Исходя из моих предполажений, необходимо искать подпоследовательность последовательности, ибо только тогда можно утверждать , что отпечаток (набор точек) принадлежит другому отпечатку.
0
silent_1991
Эксперт С++
4964 / 3040 / 149
Регистрация: 11.11.2009
Сообщений: 7,027
Завершенные тесты: 1
06.10.2010, 18:10 #13
ККирилл,
О чём вы, какая дезинформация))) Из моих умозаключений следует то же самое, что из ваших. Но просто когда появляются два варианта условия задачи, я начинаю очень неуютно себя чувствовать...
0
ККирилл
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
08.10.2010, 08:33  [ТС] #14
Очень понравилась идея, что данные могут храниться в виде половинчатой матрицы ((N*N - N)/2) что я так полагаю позволит сэкономить объём в два раз. Но для восстановления и получения полной матрицы нужна будет функция, которая её воостанавливает.
0
fasked
Эксперт С++
4936 / 2516 / 180
Регистрация: 07.10.2009
Сообщений: 4,311
Записей в блоге: 1
08.10.2010, 08:54 #15
Цитата Сообщение от ККирилл Посмотреть сообщение
Очень понравилась идея, что данные могут храниться в виде половинчатой матрицы ((N*N - N)/2) что я так полагаю позволит сэкономить объём в два раз. Но для восстановления и получения полной матрицы нужна будет функция, которая её воостанавливает.
Да и восстанавливать ее я тоже не вижу особого смысла. Тут проблема в том, что довольно сложно совершить обход такого массива.
0
MoreAnswers
Эксперт
37091 / 29110 / 5898
Регистрация: 17.06.2006
Сообщений: 43,301
08.10.2010, 08:54
Привет! Вот еще темы с ответами:

Умножение двух матриц на С++ - C++
Всем доброе время суток! с днём Математиков ВАС, коллеги) Мне надо реализовать умножение 2 матриц размерности NxM1, M1xN...

Перемножение двух матриц - C++
Приет.Ребята подскажите как перемножить две матрицы разных размеров используя динамический массив Вот код который получился у меня: ...

Умножение двух матриц - C++
Посмотрите, рабоает ли программа, которая должна умножить две матрицы. Буду очень благодарен за исправление... У меня ошибка где-то у...

Перемножение двух матриц - C++
Собственно задачка: Написать программу перемножения двух матриц. Найти вид функции сложности алгоритма. 2 пункт не обязателен, а...


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

Или воспользуйтесь поиском по форуму:
Yandex
Объявления
08.10.2010, 08:54
Ответ Создать тему
Опции темы

КиберФорум - форум программистов, компьютерный форум, программирование
Powered by vBulletin® Version 3.8.9
Copyright ©2000 - 2017, vBulletin Solutions, Inc.
Рейтинг@Mail.ru