1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
|
|
1 | |
Сравнени двух матриц (NxN-1) и (MxM-1)05.10.2010, 18:57. Показов 1374. Ответов 16
Метки нет (Все метки)
Добрый день уважаемые форумчане.
Не сочтите за дерзость, но нужна помощь. Поставил перед собой одну задачку (условия ниже). Сам не являюсь программистом, решение данной задачи математически я написал, а как реализовать его в виде программного когда я к сожалению не знаю. Если поможете буду очень вам признателен. Вот условие задачки: Имеется две плоскости А и В. На одной плоскости (A) заданы N точек своими координатами (хранится в текстовом файле), на другой (B) M точек своими координатами (хранится в текстовом файле) N>M. Составить функцию для построения одной матрицы расстояний между всеми точками N и второй матрицы между всеми точками М. Составить функцию, которая позволяла бы сопоставлять расстояния между точками в матрице N с расстояниями между точками в матрице M. Получается одна строка в матрице соответствует всем расстояниям для одной точки. Составить функцию, которая способна определить, принадлежит ли строка одной матрицы другой строке другой матрицы. Если нужны ещё какие-либо данные, прошу ссобщить. С уважением.
0
|
05.10.2010, 18:57 | |
Ответы с готовыми решениями:
16
Даны две матрицы А(nxn) и B(nxn). Написать программу получения коммутатора АВ этих матриц. Задать матрицы А и В размером Nxn и MxM. Найти их след (сумму элементов главных диагоналей) В двумерных массивах A[NxN] и В[MxM] рассортировать числа по возрастанию в каждой диагонали, параллельной главной диагонали Решение матриц NxN: С-А*В |
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
|
06.10.2010, 13:03 | 4 |
Понравилось условие. Завтра, как будет перерыв, посмотрю вложение и подумаю, что можно сделать.
Добавлено через 14 часов 39 минут Посмотрел и подумал, что использовать матрицы здесь не рационально. Если оставлять матрицу расстояний вида: Код
N1-2, N1-3, N1-4 ... N2-1, N2-3, N2-4 ... Ко всему прочему это не прибавляет простоты реализации, потому что исключается расстояние от точки до самой же себя. Если такое расстояние включить, то реализация будет в разы проще, просто на главная диагональ матрицы станет нулевой. Я не думаю, что это значительные потери памяти Чтобы сделать еще более эффективно и еще более просто, предлагаю воспользоваться вектором расстояний (хотя это не так наглядно). То есть вектор будет содержать следующие значения (для 4 точек): Код
N1-2, N1-3, N1-4, N2-3, N2-4, N3-4 Сложность реализации от этого не страдает Это самый обыкновенный полный перебор. Хотя есть очень большая вероятность того, что так тяжело будет сравнивать с частичным отображением отпечатка ... Тут я еще не обдумал. И, да, кстати. В том документе, что Вы прикрепили картинки расстянулись, читать уж очень неудобно Еще я бы все таки хотел узнать, как именно будет храниться координаты точек в файлах.
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
||||||
06.10.2010, 13:13 | 5 | |||||
Да нет, реализация не усложняется))) Только что написал сначала для нулевой главной диагонали, потом, посмотрев задание, исключил её. Даже одна строка кода ушла)))
Вот что пока вышло:
0
|
06.10.2010, 13:20 | 6 | |||||
Вот такой вот код на Си формирует для пяти точек соответствующую матрицу:
Код
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 минуты Конечному пользователю в итоге будет пофигу, как храняться данные. А память сэкономить всегда приятно Возможно, если повыситься точность данных, то точек станет еще больше, следовательно время перебора заметно ускориться.
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
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
|
06.10.2010, 14:23 | 8 |
Матрицы делится на две половины главной диагональю. Половины матрицы дублируют друг друга, следовательно одну из них можно смело отбрасывать.
Также мы знаем, что матрицу можно представить в виде одномерного массива, используя для доступа к конкретному объекту формулу вида [ROWS * i + j]. Исходя из этого, думаю, что к данной формуле можно присобачить обход верхнего (или нижнего) треугольника матрицы и вуаля. Добавлено через 3 минуты Размер такого массива будет равен (N*N - N)/2. Против N*N или N*(N-1) с использованием матриц.
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
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
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
06.10.2010, 16:09 | 11 |
ККирилл,
Хм... В прикреплённом вами файле написано
0
|
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
|
|
06.10.2010, 16:35 [ТС] | 12 |
Приношу мзвинения если дезинформировал. Исходя из моих предполажений, необходимо искать подпоследовательность последовательности, ибо только тогда можно утверждать , что отпечаток (набор точек) принадлежит другому отпечатку.
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
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
|
1 / 1 / 0
Регистрация: 05.10.2010
Сообщений: 7
|
|
08.10.2010, 09:42 [ТС] | 16 |
Сравнивать такие массивы между собой мне кажется гораздо сложнее, нежели матрицы. Значит ли сиё, что решение данной задачи (в программном коде) очень сложное и нереализуемо?
0
|
5055 / 3115 / 271
Регистрация: 11.11.2009
Сообщений: 7,044
|
|
08.10.2010, 11:20 | 17 |
Возможно всё, что возможно вообразить))) Можно поступить следующим образом (в теории): Завести трёхмерный массив. В первой строке хранить элементы так, как предложил fasked. В оставшихся двух строках хранить индексы этих элементов, какими они были бы, если бы мы представляли всё это дело в виде обычной матрицы. Почему трёхмерный? Потому что индекс может дублироваться либо 0 раз (единственное значение в матрице), либо один раз (два значения в исходной матрице). Таким образом достаточно составить функцию, генерирующую этот массив посредством вычисления индексов. Так память будет сокращена хоть и не в два раза, но всё же места займёт меньше, чем обычная матрица. А обход такого массива можно совершать точно так же, как и обход обычной матрицы, просто очередной элемент надо будет искать на основе списка индексов.
Добавлено через 2 минуты Вернее нет, не трёхмерный, а пятимерный, потому как у нас может быть либо два индекса (i, j), либо четыре (i1, j1; i2, j2). А можно поступить иначе и хранить всё это дело в связных списках. Тут и добавление проще будет, и обход, и лишней памяти на не дублирующиеся элементы не расходуется. Каждая запись списка - структура из двух полей - i и j.
0
|
08.10.2010, 11:20 | |
08.10.2010, 11:20 | |
Помогаю со студенческими работами здесь
17
Дано L матриц размером NxN Решение матриц NxN: Найти матрицу С = A*B Вычисление степени матрицы, вычисления произведения двух матриц, вычисление суммы двух матриц Найти максимальный элемент для каждого столбца матриц размерностью NxN Найти максимальный элемент для каждого столбца матриц размерностью NxN Используя функцию произведения двух матриц, найдите произведение трех матриц А(3,4) В(4,3) С(3,3) Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |