Господа, можете помочь с поворотом матрицы?
Дано 16-битовое слово W=b0 b1…b15. Необходимо повернуть матрицу на 90 градусов по часовой стрелке (переставить биты в слове – b0 в b12, b1 в b8 и т.д.)
Требования – использование не более 1Кбайта и выполнение не более 10 операций таких как присваивание, логическая или арифметическая операция, извлечение из таблицы.
27 января 2009 в 21:01
> Еще одно замечание – как я уже сказал, число 16-битовое, а потому скорее всего имеет вид 1011011100…
я тоже так думаю. использованные мной символы – это просто номера битов (за исключением нуля, который может означать просто 0).
> И я к своему стыду все равно не понял. Под извлечением вами подразумевается симметрия по столбцам?
нет. извлечение – это получение данных из таблицы.
прошу прощения, выше я ошибся с подсчетом количества операций, но принцип от этого не меняется.
нижний байт 89abcdef преобразуется таблицей (512 байт = 256 записей по 2 байта) в слово 00bf00ae009d008c. стоимость – 2 операции (один сдвиг и одна индексация или, в других терминах, одно умножение и одно сложение). верхний байт стоит 2 (по аналогии) + 1 (сдвиг результата). объединение – еще одна операция. если разобраться, то достать таблицу, достать исходное слово и положить результат в память – еще 3 операции. итого: 9 операций + 512 байт в таблице + около полусотни байт кода.
27 января 2009 в 17:03
Еще одно замечание – как я уже сказал, число 16-битовое, а потому скорее всего имеет вид 1011011100…
И я к своему стыду все равно не понял. Под извлечением вами подразумевается симметрия по столбцам?
27 января 2009 в 8:04
извлечение совершает вот такую операцию:
cdef -> 000f000e000d000c
27 января 2009 в 6:04
Дмитрий: Язык без разницы – я понимаю Си и Паскаль.
Как то не совсем понял ваш алгоритм, можно поподробнее?
Леонид: Вот задача в том и состоит чтобы уложиться меньше чем в 128Кб
27 января 2009 в 1:01
требуемая битовая перестановка:
0123456789abcdef
37bf26ae159d048c
можно сделать одним извлечением из таблицы на 128килобайт
а вообще, имеется закономерность: для каждых четырех битов требуется одно извлечение и, возможно, сдвиг: 4 + 3 операций. оставшиеся 3 операции можно отдать под объединение четырех результатов. итого: 32 байта таблица + 10 операций.
27 января 2009 в 0:01
На каком языке написать требуется?