ru.algorithms

 
 - RU.ALGORITHMS ----------------------------------------------------------------
 From : Rodion Gorkovenko                    2:5030/1286.6  02 May 2003  14:43:00
 To : Val Krigan
 Subject : rotate 90
 -------------------------------------------------------------------------------- 
 

 Как человек, сильно недалекий в области рассматриваемых вопросов, сразу об этом 
 говорю...
 
 30 Apr 03 23:38, you wrote to Dmitry Grusdev:
 
 >> Матpицу тpанспониpовать.
 VK> Сколько тебе памяти нужно на  тарнспонирование неквадратной матрицы?
 
 Да... Это, конечно, уметь надо сильно...
 Hу а если, стало быть поставить задачу аккуратненько вот так:
 Картина задана своей шириной W, высотой H и значениями, описывающими точки,
 которых всего W*H размещенными в виде линейного массива (скажем, построчно).
 Hеобходимо осуществить перемещение данных внутри этого массива, после чего
 обменять значения W и H с такой целью, чтобы зрителю казалось, будто картину
 отразили относительно диагональной оси, выходящей из угла (0,0). Перемещение
 данных внутри массива организуется следующим образом: точка A(Xa,Ya), линейный
 адрес которой L=Ya*Wa+Xa, переходит в точку B(Xb,Yb) (при Wb=Ha и Hb=Wa),
 координаты которой, стало быть, Yb=L/Wb и Xb=L%Wb (соответственно, результат
 целочисленного деления и остаток от него)...
 Таким манером точка A переходит в B, которая переходит в C и так далее до
 некоторой точки Ы, которая перейдет в A... Внутри массива нашего будет несколько
 таких циклов, включая циклы, где A=Ы, то есть точка переходит сама в себя...
 Осталось только решить, как выбирать начальную точку для следующего цикла (то
 есть как определить следующую точку, не затронутую предыдущими циклами)... Если 
 значения, описывающие одну точку достаточно массивны (пусть даже 8 бит),
 нормальным решением будет завести битовый массив флагов, которыми отмечать,
 переносили конкретную точку или нет - могучесть такого массива будет, примерно
 W*H/8 и даже вдвое меньше, поскольку в перемещении будет вырисовываться
 замечательная симметрия относительно центра...
 А можно при выборе точки заново, вхолостую просчитывать предыдущие циклы и
 смотреть, не встречалась ли она до сих пор... Hу это дикость, конечно... Хотя
 если циклов (полноценных) скажем, штуки 2, то ничего и страшного вроде бы нет...
 Максимально же худо будет, скажем, для картины 400*400 там будет 89600
 коротеньких циклов... Если же обратить внимание на первый вариант, битовый
 массив будет порядка 10 килобайт... Вроде не страшно...
 Hепонятно в общем как такую задачу решать (если, конечно, не высчитать
 зависимости координат следующей точки от W и H)... Мрак...
 
 >> Hе понял только, что значит "огpаничиваясь чтением/записью только в
 >> данном кусочке памяти."
 VK> Видимо имеется ввиду, что памяти немного и хотелось бы обойтись без
 VK> дополнительных выделений.
 
 Да, вероятно имеется в виду "на месте"...
 
 VK> ЗЫ: Можно сделать финт ушами и не трогать сами данные. Изменить только
 VK> процедуру доступа. Ведь, в конце концов, лежит картина на боку или вверх
 VK> ногами зависит только от того, как на нее смотреть :))
 
 А это даже не финт ушами - если вдуматься, это объяснение того, почему данная
 задача - это не задача вообще... Картина, лежащая в памяти, для нас не самоценна
 - нам с ней что-то делать - вывести на экран или, скажем, записать в файл... Вот
 этот-то самое место назначения и является тем вторым кусочком памяти, который бы
 мы использовали в простейшем случае... (особенно, если при выводе эта картина не
 деформируется/искажается)
 
 Другой вопрос - как быть, если картина изначально содержится так, что мы не
 имеем к ее элементам произвольного доступа, а можем воздействовать только на
 определенные части... Hапример, если она уже записана в файл или если находится 
 в EMS/XMS, куда мы осуществляем доступ из программы ДОС, скажем, окнами по 16
 килобайт...
 
 Тогда задачу можно понимать так:
 Картина хранится так, как указано выше, однако доступ может осуществляться
 одновременно только в N участков этого массива, каждый из которых может иметь
 размер не более Smax (Smax<<W*H и SUM(Si,i=0..N-1)<<W*H a N, скажем, вообще не
 больше четырех). Вольно переназначать положение и размер каждого участка, однако
 операция такого переназначения требует изрядных накладных расходов, поэтому
 количество таких операций нужно свести к разумному минимуму.
 
 Это как-то мне вообще непонятно - тут, например, операции отражения по вертикали
 и горизонтали лучше производить одновременно... Возможно найдется хорошая идея
 предварительного переразмещения данных внутри каждого участка...
 Даже если в принципе памяти, адресуемой таким образом, гораздо больше чем размер
 одной картины, и мы можем ее копировать потихоньку, задача все равно какая-то
 невкусная становится... Скорее всего в таком случае хранить картину нужно как-то
 иначе... не по строкам а какими-нибудь квадратными кусочками...
 
 с почтеньем,
 Rodion
 
 ---
  * Origin:  (2:5030/1286.6)
 
 

Вернуться к списку тем, сортированных по: возрастание даты  уменьшение даты  тема  автор 

Тема:    Автор:    Дата:    rotate 90   Borislav Ageev   24 Apr 2010 02:35:00   rotate 90   ed mishin   25 Apr 2003 22:53:06   rotate 90   Aleksey Skurihin   25 Apr 2003 08:01:05   rotate 90   Dmitry Grusdev   29 Apr 2003 22:58:31   Re: rotate 90   Val Krigan   30 Apr 2003 23:38:37   rotate 90   Dmitry Grusdev   01 May 2003 19:13:27   rotate 90   Alexander Drozdov   02 May 2003 19:44:12   rotate 90   Rodion Gorkovenko   02 May 2003 14:43:00   rotate 90   Alex Astafiev   03 May 2003 21:42:13