|
90 / 88 / 33
Регистрация: 20.07.2016
Сообщений: 403
|
||||||
Хитрое транспонирование матрицы12.08.2016, 20:09. Показов 4219. Ответов 33
Метки нет (Все метки)
Значится так, есть матрица загнанная в вектор... есть ли способ транспонировать ее не создавая новый вектор, то есть просто обменивая элементы в исходном?
P.S: Матрица не обязательно квадратная!!! Добавлено через 25 минут а задачка то не тривиальная)))) наведу простой пример, чтоб было понятней:
0
|
||||||
| 12.08.2016, 20:09 | |
|
Ответы с готовыми решениями:
33
Транспонирование матрицы
Транспонирование матрицы |
| 13.08.2016, 13:16 | |
|
0
|
|
|
90 / 88 / 33
Регистрация: 20.07.2016
Сообщений: 403
|
||
| 13.08.2016, 13:20 [ТС] | ||
|
0
|
||
| 13.08.2016, 13:28 | |
|
JIawliet, мне интересно, по какому алгоритму ты будиш писать свой код, я просто не оч понил про твой способ без хранения индексов
0
|
|
|
90 / 88 / 33
Регистрация: 20.07.2016
Сообщений: 403
|
||||||
| 13.08.2016, 16:36 [ТС] | ||||||
|
Ferrari F1, а я сам еще не знаю)))) как доделаю напишу)
Добавлено через 3 часа 0 минут Ferrari F1, И так, вот что получилось (+ еще один интересный вариант, такого не предлогали):
Другой вариант: создается map и каждому элементу из исходной матрицы присваивается индекс (где он будет стоять в транспонированной матрице), первый и последний элементы стоят на месте, поэтому их игнорируем. Далее просто запускаем цикл по всему map и переставляем элементы из вектора в нужные позиции. Без сохранения индексов (создания map) не осилил( Замечено, что для транспонирования матрицы-вектора с количеством элементов n, нужно всего n / 2 обменов элементов... оставим поиски этого мега-алгоритма людям, у которых больше свободного времени и есть невиданное желание транспонировать матрицы
0
|
||||||
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|||||||
| 13.08.2016, 17:50 | |||||||
Сообщение было отмечено JIawliet как решение
РешениеВот, сделал практически без использования памяти. Память выделяется только в vector<bool> по одному биту на элемент матрицы только для того, чтобы отмечать индексы уже обработанных элементов. Если быть принципиальным, то можно и без этого вектора обойтись, и хранить только первые индексы обработанных циклов. Но тогда работать будет дольше: каждый индекс вектора надо будет прогонять по циклу, пока он опять не перейдет в себя, и следить, не содержатся ли в цикле начальные элементы уже обработанных циклов. Мой вариант:
1
|
|||||||
| 13.08.2016, 19:22 | ||
|
Допустим есть такой вектор-матрица 4х2 1, 2, 3, 4, 5, 6, 7, 8 из него должен получиться вектор-матрица 2х4 1, 3, 5, 7, 2, 4, 6, 8таким образом, элемент со значением 2 переместиться с 1ого индекса на 4 если мы обменяем эти два значения, получится 1, 5, 3, 4, 2, 6, 7, 8Таким образом, мы потеряли ту связь с элементом со значением 5, теперь он по первому индексу, когда в оригинале он находится на четвертому, тем самым мы потеряли закономерность по которой надо переставлять элементы. Стоит еще заметить, что это и есть цена за обмен значений внутри матрицы, не выходя за ее пределы (т.е. без копирования ее элементов)
0
|
||
|
90 / 88 / 33
Регистрация: 20.07.2016
Сообщений: 403
|
|||||||||||
| 13.08.2016, 19:28 [ТС] | |||||||||||
|
Mr.X, ага - оно самое!) минимум обменов, лишней памяти не выделяется, сказка)))
Хочу вас кое о чем попросить, потому что за вами я поправлять код не решился :a) убрать из кода функцию:
b) в функцию execute_loop перед циклом do - while добавить следующую проверку:
Большое спасибо за то, что не пожалели время и довели решение задачи до ума, нет - до идеального состояния) Само собой я отмечу лучший ответ) Добавлено через 4 минуты Ferrari F1, да это ясно)) вон Mr.X, предложил пожалуй идеальный вариант решения... распечатайте код, не поленитесь разобраться, это реально круто) память выделялась только под std::vector<bool> в котором просто отмечалось обработан ли конкретный элемент или нет...
0
|
|||||||||||
| 13.08.2016, 19:43 | |
|
JIawliet, у меня еще есть такой вариант упрощения алгоритма:
о всякой матрице с обоими размерами хотя бы больше одного можно говорить, что она содержит в себе квадратную матрицу В таком случае эту кв. матрицу поменяем кодом, что кинул zss, а остатки, что выходят из квадратной области, шлифануть каким-нить другим алгоритмом. Хотя, могу и ошибиться что это будет верным для решения
0
|
|
|
90 / 88 / 33
Регистрация: 20.07.2016
Сообщений: 403
|
|
| 13.08.2016, 19:51 [ТС] | |
|
Ferrari F1, а я так уже пробовал, но до ума не довел... тут дело в том, что те элементы, которые не входят в квадратную матрицу, потом переставляют элементы, которые входили в квадратную матрицу, с их законных мест)
0
|
|
| 13.08.2016, 19:53 | |
|
JIawliet, вобщемя я уже задалбался чесна гря) моих сил хватило на этот код с картой
Пашел ка я рубиться в ксску_)
0
|
|
|
90 / 88 / 33
Регистрация: 20.07.2016
Сообщений: 403
|
|
| 13.08.2016, 20:02 [ТС] | |
|
Ferrari F1, ну задача решена - решена, причем было предложено множество вариантов решения)
0
|
|
|
245 / 139 / 53
Регистрация: 23.11.2015
Сообщений: 394
|
|
| 13.08.2016, 20:05 | |
|
0
|
|
|
3225 / 1752 / 436
Регистрация: 03.05.2010
Сообщений: 3,867
|
|||||||||
| 13.08.2016, 20:32 | |||||||||
1
|
|||||||||
|
245 / 139 / 53
Регистрация: 23.11.2015
Сообщений: 394
|
||||||
| 14.08.2016, 09:44 | ||||||
|
окей, вчера ночью это заработало. какая наивная идея у меня была
пусть есть у нас N=2 M=3 1 2 3 4 5 6 я начинаю с первого элемента и перемещаю его на новое место, на место тройки в данном случае. но куда девать тройку? повторяем процедуру и так до тех пор пока все не замкнется (так я думал) [1] -> [2] [2] -> [4] [4] -> [3] [3] -> [1] воот. но естественно на другом примере такое 'замыкание' совсем не означает, что все элементы пройдены и матрица транспонирована. пришлось ввести битовый вектор, который при таком дедлоке продолжал бы работу до победного конца. пытался писать аккуратно, но на многое забил, чтобы кода было поменьше.
1
|
||||||
| 14.08.2016, 09:44 | |
|
Транспонирование матрицы Транспонирование матрицы Транспонирование матрицы
Транспонирование матрицы Искать еще темы с ответами Или воспользуйтесь поиском по форуму: |
|
Новые блоги и статьи
|
|||
|
Как установить и настроить Windows 11 без подключения к Интернету и без аккаунта Microsoft
Maks 22.11.2026
Положу сюда, чтобы не искать постоянно.
• На экране «Давайте подключим вас к сети» во время установки Windows 11 нажмите комбинацию клавиш Shift+F10, чтобы открыть командную строку. Введите. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №5)
Maks 17.11.2026
Дабы оставить позади все споры о том, какая буква каким образом должна транслитерироваться на латиницу - решил таки доработать данное решение и довести его до мало-мальски логического завершения. . . .
|
Просмотровщик HLP и конвертер в CHM
Argus19 16.11.2026
Просмотровщик HLP и конвертер в CHM
Давно хотел переделать справку Microsoft® Win32® Programmer's Reference, чтобы иметь её под рукой.
Но использовать несколько программ не удобно. Искал другие. . .
|
BitTorrent (версия 7.11 English) и Меню Настройки
russiannick 15.11.2026
Пункты, отвечающие за отключение обновлений в BitTorrent версии 7. 11 (английской)
Options
Preferences
General
Language
|
|
Транслитерация текста с кириллицы на латиницу (вариант №4)
Maks 15.11.2026
Что-то я перемудрил с предыдущими версиями, в этот раз сделал всё проще, обратившись к функции "СтрокаЛатиницей" из типового общего модуля "СтроковыеФункцииКлиент".
В данной функции нет апострофов,. . .
|
BitTorrent (версия 4.3.9) и Меню Настройки
russiannick 15.11.2026
В меню Настройки можно отключить автоматическое обновление программы.
Карта этого меню приложена ниже.
Нужный пункт выделен красным.
Сервис
Настройки
Поведение
|
Транслитерация текста с кириллицы на латиницу (вариант №3)
Maks 15.11.2026
Обновленная версия предыдущей обработки.
Изменения коснулись букв: Ъ, Ы, Ь, Э, отображения которых зависят от положения реквизита "Транслитерация имён".
Изменено отображение буквы Й.
Добавлена. . .
|
Транслитерация текста с кириллицы на латиницу (вариант №2)
Maks 13.11.2026
Обновленная версия ранее созданной обработки.
Добавлено:
- Проверка исходного текста на кириллицу, через обращение к стандартной функции "ТолькоКириллицаВСтроке" из общего модуля. . .
|