Разгадываем задачки
Создана: 15 Апреля 2009 Срд 21:05:48.
Раздел: "Флейм"
Сообщений в теме: 726, просмотров: 194102
-
В порядке развлечения.
В этой теме я буду загадывать задачки, и мы все вместе будем пытаться их разгадать. Решение будет выкладыватся через несколько дней.
Если кому-то интересно, давайте договоримся играть честно.Т.е. никаких задачников, загугливаний, и проч. не использовать.
п.с. в перспективе можно будет первому решившему организовывать символический приз)
Задачка №1
"Три выключателя"
В одной комнате находятся три выключателя, а в другой — три лампочки. Каждый выключатель связан с одной лампочкой. Как узнать, какой выключатель связан с какой лампочкой, если в комнату с лампочками можно войти только один раз? -
karaganda писал : Фигура и ее цвет кодируется номером позиции в описании
Одноцветных пешек - восемь штук. Если каждой давать свой ID, понадобиться в восемь раз больше информации.
По вашему принципу на поле 32 разновидности фигуры. Для компьютера достаточно 12 - и это учитывая цвет.
Еще раз. В вашем случае при перестановке двух одинаковых фигур одного цвета вы получаете новую комбинацию, которую нужно запоминать. Но ведь визуально ничего не изменяется. -
Условие:сказали
1=дизайнер
2= не дизайнер
3= не программист
только один сказал правду.
найти профессию каждого
===============
решение:
если 1- прав, то и 2 прав => 1 лжёт, (ведь прав только один!)
об . вывод=>1 - либо прогр, либо админ
если 2 прав,то 2- либо прогр, либо админ =>3 прав ( админ и программист заняты 1 и 2)
об . вывод=>2 лжёт, Значит именно 2 = дизайнер,
Итак, два лгуна выявлены =>3 правдив,значит он либо дизайнер, либо админ, но дизайнер занят,
об.вывод: 3-й =админ.,
а
1- программист
решение ПДА -
karaganda писал : to Tenk-Weng
Принцип такой :
1. Первые шесть битов определяют положение белого короля
2. Вторые - королевы
3. Третья комбинация для слона первого
и так далее
Если так считать, то у меня получилось:
Белые фигуры.
король - 6 бит.
ферзь - 6 бит.
1 слон - 6 бит.
2 слон - 6 бит.
1 конь - 6 бит.
2 конь - 6 бит.
1 ладья - 6 бит.
2 ладья - 6 бит.
1 пешка - 6 бит. + если она превращается то 2 бита (ферзь, слон, конь, ладья 4 значения = 2 бита)
2 пешка тоже
.
.
8 пешка тоже
Равно 112 бит
На все фигуры 224 бита. Но тут все равно избыточная информация т.к. фигуры друг на друге не могут стоять.
Добавлено: А надо еще информцию, что она вне поле (срублена) -
-
Еще предлагают метод Хаффмана использовать
Вот расчет:
64 бита на наличие фигур на клетках
32 бита на цвет фигур
пешка-«1» =16 бит
конь-«01» =8 бит
ладья-«001» =12 бит
слон-«0001» =16 бит
ферзь-«00001» =10 бит
король-«000001» =12 бит
в сумме на фигуры уходит 16+8+12+16+10+12=74 бита
64+32+74=170 бит -
karaganda писал : Превращения не нужно учитывать.
Есть формула по которой рассчитывается количество бит для хранения уникальных значений.
После записи позиции первой фигуры нужно закодировать 63 комбинации.
Логарифм по основанию 2 от 63 равен 5.977 бита
И так далее
Тогда получается 184 бита для хранения комплекта,
185 бит, если не учитывать превращения фигур, но учитывать что их могут срубить,
204 бита для любой мыслимой расстановки с превращениями.
А это нормально - со 185-битовыми целыми вычисления делать?
Если уж идти на такие ухищрения, то лучше действительно сделать алгоритм арифметического кодирования с изменяющимся частотным словарём. Т.к. все белые фигуры будут тяготеть к нижней части доски, а чёрные к верхней, то будет явный дизбаланс, который можно реализовать в степени сжатия. По мере развития ситуации на доске, фигуры будут перемешиваться, но некоторые будут срублены, что компенсирует эффект. Коэффициент сжатия оцениваю минимум в 1.2 . -
karaganda писал : Еще предлагают метод Хаффмана использовать
Нечего там Хаффманом сжимать! Не нужно хранить информацию о цвете и типе фигуры - это закладывается в самой позиции данных.
64 варианта для белого короля, 63 для чёрного короля, 63 (62 клетки поля и 1 - срублено) для белого ферзя, 62 для чёрного ферзя, 61 для белой ладьи 1, и т.д.
Информацию о типе фигуры нужно хранить только для пешек, если мы учитываем их превращения. И состояний не 4, а 5: пешка, конь, слон, ладья, ферзь. А это, как я уже писал выше, укладывается в 19 бит. Их можно попытаться сжать Хаффманом, но одновременное превращение двух пешек сведёт эффект на нет: 14+2*3 уже равно 20.
И дерево у вас мягко говоря неоптимальное. -
karaganda писал :Для меня просто прелесть , а не дерево.
пешек - 16
коней - 4
слонов - 4
ладей - 4
ферзей - 2
королей - 2
Поэтому оптимальное дерево должно отводить:
для пешек - 1 бит
для коней, слонов и ладей - по 3 бита
для ферзей и королей - по 4 бита.
Пример оптимального дерева:
пешка - 0
конь - 100
слон - 101
ладья - 110
ферзь - 1110
король - 1111
Итого: 16*1+4*3*3+2*4*2=16+36+16=68 бит
Когда коэффициент сжатия важнее быстродействия, арифметическое кодирование предпочтительней.