Index · Правила · Поиск· Группы · Регистрация · Личные сообщения· Вход

Список разделов Флейм
 
 
 

Раздел: Флейм Разгадываем задачки 

Создана: 15 Апреля 2009 Срд 21:05:48.
Раздел: "Флейм"
Сообщений в теме: 726, просмотров: 194113

На страницу: Назад  1, 2, 3 ... 26,
, 28 ... 47, 48, 49  Вперёд
  1. 15 Апреля 2009 Срд 21:05:48
    В порядке развлечения.

    В этой теме я буду загадывать задачки, и мы все вместе будем пытаться их разгадать. Решение будет выкладыватся через несколько дней.
    Если кому-то интересно, давайте договоримся играть честно.Т.е. никаких задачников, загугливаний, и проч. не использовать.


    п.с. в перспективе можно будет первому решившему организовывать символический приз)


    Задачка №1
    "Три выключателя"
    В одной комнате находятся три выключателя, а в другой — три лампочки. Каждый выключатель связан с одной лампочкой. Как узнать, какой выключатель связан с какой лампочкой, если в комнату с лампочками можно войти только один раз?
  2. 30 Июня 2011 Чтв 16:26:38
    karaganda писал : Фигура и ее цвет кодируется номером позиции в описании

    Одноцветных пешек - восемь штук. Если каждой давать свой ID, понадобиться в восемь раз больше информации.
    По вашему принципу на поле 32 разновидности фигуры. Для компьютера достаточно 12 - и это учитывая цвет.

    Еще раз. В вашем случае при перестановке двух одинаковых фигур одного цвета вы получаете новую комбинацию, которую нужно запоминать. Но ведь визуально ничего не изменяется.
  3. 30 Июня 2011 Чтв 16:29:19
    Teruro писал :
    karaganda писал ... :Представьте, что вы пришли устраиваться в маленькую, но подающую большие надежды компанию.

    Вообще-то решений два:
    ПДА и АПД.
    Но, т.к. задачка админская, то по косвенным данным последний скорее всего админ.

    А, ну да, на счёт АПД бычу.

    Условие:сказали
    1=дизайнер
    2= не дизайнер
    3= не программист
    только один сказал правду.
    найти профессию каждого
    ===============
    решение:
    если 1- прав, то и 2 прав => 1 лжёт, (ведь прав только один!)
    об . вывод=>1 - либо прогр, либо админ

    если 2 прав,то 2- либо прогр, либо админ =>3 прав ( админ и программист заняты 1 и 2)
    об . вывод=>2 лжёт, Значит именно 2 = дизайнер,


    Итак, два лгуна выявлены =>3 правдив,значит он либо дизайнер, либо админ, но дизайнер занят,
    об.вывод: 3-й =админ.,
    а
    1- программист

    решение ПДА
  4. 30 Июня 2011 Чтв 16:37:49
    to Tenk-Weng

    Принцип такой :
    1. Первые шесть битов определяют положение белого короля
    2. Вторые - королевы
    3. Третья комбинация для слона первого
    и так далее
  5. 30 Июня 2011 Чтв 16:43:54
    Тогда нужно считать кол-во сочетаний (или размещений? не помню, кто из них не чувствителен к перестановкам).
  6. 30 Июня 2011 Чтв 17:06:38
    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 бита. Но тут все равно избыточная информация т.к. фигуры друг на друге не могут стоять.

    Добавлено: А надо еще информцию, что она вне поле (срублена)
  7. 30 Июня 2011 Чтв 17:15:23
    Превращения не нужно учитывать.

    Есть формула по которой рассчитывается количество бит для хранения уникальных значений.

    После записи позиции первой фигуры нужно закодировать 63 комбинации.

    Логарифм по основанию 2 от 63 равен 5.977 бита

    И так далее
  8. 30 Июня 2011 Чтв 17:46:41
    Извиняюсь. Немного клинануло мозги, начал расчитывать способ расчета количества вариаций расположения фигур для запоминания. Не туда думал.
  9. 30 Июня 2011 Чтв 18:02:43
    Еще предлагают метод Хаффмана использовать

    Вот расчет:

    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 бит
  10. 30 Июня 2011 Чтв 18:20:36
    Это простое префиксное кодирование. Метод Хаффмана используется, когда есть распределение вероятностей по событиям.
  11. 30 Июня 2011 Чтв 18:21:10
    Смайлик :-)
  12. Teruro


    Хранитель


    Более 10 лет на форумеУчастнику дано предупреждение от модератораМуж.
    01 Июля 2011 Птн 7:35:14
    karaganda писал : Превращения не нужно учитывать.

    Есть формула по которой рассчитывается количество бит для хранения уникальных значений.

    После записи позиции первой фигуры нужно закодировать 63 комбинации.

    Логарифм по основанию 2 от 63 равен 5.977 бита

    И так далее

    Тогда получается 184 бита для хранения комплекта,
    185 бит, если не учитывать превращения фигур, но учитывать что их могут срубить,
    204 бита для любой мыслимой расстановки с превращениями.
    А это нормально - со 185-битовыми целыми вычисления делать?

    Если уж идти на такие ухищрения, то лучше действительно сделать алгоритм арифметического кодирования с изменяющимся частотным словарём. Т.к. все белые фигуры будут тяготеть к нижней части доски, а чёрные к верхней, то будет явный дизбаланс, который можно реализовать в степени сжатия. По мере развития ситуации на доске, фигуры будут перемешиваться, но некоторые будут срублены, что компенсирует эффект. Коэффициент сжатия оцениваю минимум в 1.2 .
  13. Teruro


    Хранитель


    Более 10 лет на форумеУчастнику дано предупреждение от модератораМуж.
    01 Июля 2011 Птн 8:05:22
    karaganda писал : Еще предлагают метод Хаффмана использовать

    Нечего там Хаффманом сжимать! Не нужно хранить информацию о цвете и типе фигуры - это закладывается в самой позиции данных.
    64 варианта для белого короля, 63 для чёрного короля, 63 (62 клетки поля и 1 - срублено) для белого ферзя, 62 для чёрного ферзя, 61 для белой ладьи 1, и т.д.
    Информацию о типе фигуры нужно хранить только для пешек, если мы учитываем их превращения. И состояний не 4, а 5: пешка, конь, слон, ладья, ферзь. А это, как я уже писал выше, укладывается в 19 бит. Их можно попытаться сжать Хаффманом, но одновременное превращение двух пешек сведёт эффект на нет: 14+2*3 уже равно 20.
    И дерево у вас мягко говоря неоптимальное.
  14. 01 Июля 2011 Птн 11:38:14
    Для меня просто прелесть , а не дерево. Люблю Хаффмана.

    Он мой кумир
  15. Teruro


    Хранитель


    Более 10 лет на форумеУчастнику дано предупреждение от модератораМуж.
    01 Июля 2011 Птн 11:43:16
    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 бит

    karaganda писал :Люблю Хаффмана.
    Он мой кумир

    Когда коэффициент сжатия важнее быстродействия, арифметическое кодирование предпочтительней.
  16. 01 Июля 2011 Птн 11:46:19
    Запомню
На страницу: Назад  1, 2, 3 ... 26,
, 28 ... 47, 48, 49  Вперёд