Версия для печати темы Нажмите сюда для просмотра этой темы в оригинальном формате

Форум программистов > C/C++: Общие вопросы > Игры в сжатие

Автор: Chaos A.D. 3.3.2006, 15:56

Есть в одной известной книге одно известное задание - написать программу, которая бы сохраняла результат шахматной партии. Причем, желательно, чтобы один ход занимал минимальное количество данных. Вот часть моего кода : Код class TurnRep {     /* ... */         union         {             unsigned non_contiguous_rep_ : 12;             struct             {                 unsigned letter_first  : 3;                 unsigned digit_first   : 3;                 unsigned letter_second : 3;                 unsigned digit_second  : 3;             };         } rep_;     public :         /* Много полезных функций */ } По логике вещей, TurnRep должен занимать 2 байта (с правильно поставленным выравниванием, естесственно). Но у меня он, блин, равен 4. Я несчастный обладатель BCB6, другого компилера сейчас под рукой нет. Буду очень признателен, если кто-нибудь проверит, мой код на своем компилере. Или, может, я где нибудь ошибся?

Автор: Romikgy 3.3.2006, 16:09

по идее твой код занимает 3 байта , без выравнивания 12+3+3+3+3=24 24/8=3

Автор: Дрон 3.3.2006, 16:13

Chaos A.D., Замени первый unsigned на short А оставшиеся 4 на char Во всяком случае в VC++ 7 сработало А вообще это выглядит ужасно... Совмещать класс С++ с битовым полем Добавлено @ 16:14 Цитата(Romikgy @ 3.3.2006, 16:09 ) по идее твой код занимает 3 байта , без выравнивания 12+3+3+3+3=24 Нет. Там же union. Общий объём 12 бит -- выделяется 2 байта.

Автор: Romikgy 3.3.2006, 17:19

Цитата(Дрон @ 3.3.2006, 15:13 ) Нет. Там же union. Общий объём 12 бит -- выделяется 2 байта. Точно проглядел , сорри

Автор: maxim1000 3.3.2006, 17:30

Цитата(Chaos A.D. @ 3.3.2006, 14:56 ) Причем, желательно, чтобы один ход занимал минимальное количество данных ну тогда, возможно, стоит рассмотреть еще и такое представление хода: на каждом ходу у текущего игрока есть не более, чем 16 фигур их можно упорядочить (например, сверху вниз, слева направо), таким образом, хранить координаты исходной клетки уже избыточно - можно хранить номер фигуры - 4 бита кроме того, каждая фигура имеет свои ограничения на ходы точно не считал, но на первый взгляд кажется, что их не может быть более, для ферзя, который стоит на одной из 4-х центральных клеток, и ходить ему никто не запрещает, тогда возможных ходов будет: (7+6)(по диагонали)+(7+7)(по вертикали и горизонтали)=27, т.е. достаточно 5 бит итого, для кодирования хода достаточно 9 бит... теперь вспомним, что не все фигуры могуделать такое большое количество ходов, для ладьи оно уже будет 14, а для пешек (которые будут составлять половину при максимальном количестве) - вообще 4 (на одну клетку, на две и два боя)... чтобы это использовать, можно перейти от независимого кодирования исходной и целевой клетки к просто записи номера хода а количество возможных ходов можно оценить сверху так: у ферзя - 27 у ладьи - 14 у остальных - не больше ладьи т.е. 27*1 ферзь + 14*7 остальных фигур+4*8 пешек=178 конечно же, реально возможных ходов будет меньше, причем, значительно... дальше остается как-то их упорядочить, т.е. пронумеровать например, сначала упорядочить по исходной клетке (а ту - сверху вниз, слева направо), а потом - по целевой из вышеописанных рассчетов мы можем быть уверены, что число будет не больше 178, а значит, вполне хватит и байта... P.S. вполне возможно, что при более точной оценке максимального количества ходов, выяснится, например, что оно не больше 128 - тогда можно использовать уже и 7 бит, но тогда ходы не будут удобно разделены побайтно, что не очень удобно... Добавлено @ 17:38 в конце концов, если уж минимировать, так минимизировать перед каждым ходом считаем количество возможных ходов (это можно сделать ина восстанавливающей стороне) смотрим, сколько бит надо для сохранения одного из этих ходов (т.е. берем двоичный логарифм и округляем вверх), и именно столько бит и используем... на принимающей (т.е. восстанавливающей) стороне тоже считаем количество бит и именно столько и читаем и уже декодируем сам ход ну а дальше - вопрос в том, как бы сэкономить на операции округления: на самом деле для сохранения десятка чисел от 0 до 5 требуется меньше бит, чем для сохранения десятка чисел от 0 до 7, а в нашем случае будет одинаково чтобы избавитсья и от этой расточительности, можно посмотреть в сторону арифметического кодирования... дальше, наверное, можно было бы привлечь сюда и вероятностное кодирование, чтобы еще уменьшить среднее количество бит, но это, пожалуй, уже слишком

Автор: Chaos A.D. 3.3.2006, 19:02

maxim1000, спасибо, очень любопытно. Плюс тебе. Был приятно удивлен твоей фантазией, но для меня и это слишком... Дрон, спасибо, помогло, правда непонятно, чем компилеру простой unsigned не понравился...

Автор: Дрон 3.3.2006, 19:11

Цитата(Chaos A.D. @ 3.3.2006, 19:02 ) Дрон, спасибо, помогло, правда непонятно, чем компилеру простой unsigned не понравился... Вероятно, для битового поля выделяется сколько байт, сколько нужно для указаного типа переменной. Любопытно было бы найти соответствующую главу в стандарте... Но это уже не ко мне. Я вообще на С++ больше не пишу

Powered by Invision Power Board (http://www.invisionboard.com)
© Invision Power Services (http://www.invisionpower.com)