Разгадываем задачки
Создана: 15 Апреля 2009 Срд 21:05:48.
Раздел: "Флейм"
Сообщений в теме: 726, просмотров: 194152
-
В порядке развлечения.
В этой теме я буду загадывать задачки, и мы все вместе будем пытаться их разгадать. Решение будет выкладыватся через несколько дней.
Если кому-то интересно, давайте договоримся играть честно.Т.е. никаких задачников, загугливаний, и проч. не использовать.
п.с. в перспективе можно будет первому решившему организовывать символический приз)
Задачка №1
"Три выключателя"
В одной комнате находятся три выключателя, а в другой — три лампочки. Каждый выключатель связан с одной лампочкой. Как узнать, какой выключатель связан с какой лампочкой, если в комнату с лампочками можно войти только один раз? -
Какое минимальное кол-во бит необходимо чтобы сохранить расположение комплекта фигур на шамхматной доске?
Шахматная доска 8х8 полей, комплект фигур это 16 черных и 16 белых.
Расставлены не соблюдая правила, возможны нереальные для игры позиции.
Алгоритм сохранения сколь угодно сложный, главное чтобы потом можно было расставить фигуры обратно по местам. -
-
-
Teruro писал :Итого: 211 бит.
Чисто теоретически можно было бы попробовать "выжать" немножко битов из того факта, что сдвоенных пешек обычно не бывает много. Но т.к. требуется минимальное из самых плохих решений, то здесь это не поможет.
Отказ от хранения горизонтальной составляющей пешек с тем, чтобы при срубании ими фигур противника использовать освободившийся объект его фигуры для хранения появившейся горизонтальной координаты пешки (или превратившейся фигуры после прохода), потребует хранение четырёхбитового указателя на срубленную фигуру или пешку, а значит мы здесь опять ничего не выигрываем.
По идее, можно было бы оценить максимальный размер такого объекта поля после сжатия каким-нибудь LZW или алгоритмом арифметического кодирования, и я даже уверен что результат будет меньше 211 битов, но что-то мне подсказывает что задача не предполагала таких экстравагантных мер. :) -
-
-
-
-
-
Учтите количество одинаковых фигур: парные ладьи, слоны, кони и восемь пешек на одно лицо. Формула будет гораздо интереснее =)
Ведь если для наглядности выставить в поле пешки одного цвета и поменять некоторые местами, шахматная композиция не изменится, а вот битовая формула расстановки ID фигур претерпит изменение.