Разгадываем задачки 

Какое минимальное кол-во бит необходимо чтобы сохранить расположение комплекта фигур на шамхматной доске?

Шахматная доска 8х8 полей, комплект фигур это 16 черных и 16 белых.
Расставлены не соблюдая правила, возможны нереальные для игры позиции.
Алгоритм сохранения сколь угодно сложный, главное чтобы потом можно было расставить фигуры обратно по местам.

karaganda писал : Какое минимальное кол-во бит необходимо чтобы сохранить расположение комплекта фигур на шамхматной доске?

Если тупо "в лоб", то 32*6=192. Дальше надо думать. :)

Teruro писал :Если тупо "в лоб", то 32*6=192. Дальше надо думать. :)

И это неправильное решение, потому что не учитывает превращение пешек в фигуры.
Поэтому надо докинуть INT(ln(5)/ln(2)*8+0.9999)=19 бит. Итого: 211 бит.

Teruro писал :Итого: 211 бит.

Чисто теоретически можно было бы попробовать "выжать" немножко битов из того факта, что сдвоенных пешек обычно не бывает много. Но т.к. требуется минимальное из самых плохих решений, то здесь это не поможет.
Отказ от хранения горизонтальной составляющей пешек с тем, чтобы при срубании ими фигур противника использовать освободившийся объект его фигуры для хранения появившейся горизонтальной координаты пешки (или превратившейся фигуры после прохода), потребует хранение четырёхбитового указателя на срубленную фигуру или пешку, а значит мы здесь опять ничего не выигрываем.
По идее, можно было бы оценить максимальный размер такого объекта поля после сжатия каким-нибудь LZW или алгоритмом арифметического кодирования, и я даже уверен что результат будет меньше 211 битов, но что-то мне подсказывает что задача не предполагала таких экстравагантных мер. :)

А если ещё немножко подумать, то нужно добавить по 15 бит на каждую из фигур, кроме королей, для хранения их статуса (активен/срублен).
Тогда правильный ответ: 241 бит.

Что то много получается

karaganda писал : Что то много получается

Ну, чисто теоретически, можно координаты срубленной фигуры приравнивать к координатам короля. Тогда хватит 211 бит.

log 2 (64) * 32 = 192. По-моему, все просто.

Groudin писал: log 2 (64) + log 2 (32) + log 2 (кол-во типов фигур). По-моему, все просто.

На одну фигуру? На поле это получается 435 бит.

Groudin писал: log 2 (64) * log 2 (32) = 30. По-моему, все просто.

Это тоже в рассчёте на одну фигуру (координаты клетки и тип фигуры).
На поле получается 30*32=960 бит.

Туплю сегодня :)

6 * 32 - думаю, это правильный ответ. На каждую фигуру - 6 бит информации о ее координате. Тип фигуры, ее цвет и т.п. совершенно не имеют значения, т.к. все фигуры можно просто пронумеровать от 1 до 32.

Groudin писал:6 * 32
...
т.к. все фигуры можно просто пронумеровать от 1 до 32.

Но:
1. пешки могут превращаться в другие фигуры,
2. фигуры могут быть срублены.

Вариант превращения не нужен из условий.
Просто в динамике если посмотреть количество свободных ячеек уменьшается.
Все фигуры считаются активными.

Учтите количество одинаковых фигур: парные ладьи, слоны, кони и восемь пешек на одно лицо. Формула будет гораздо интереснее =)

Ведь если для наглядности выставить в поле пешки одного цвета и поменять некоторые местами, шахматная композиция не изменится, а вот битовая формула расстановки ID фигур претерпит изменение.

Фигура и ее цвет кодируется номером позиции в описании