max_shane
@max_shane
Javascript / Node.js dev

Как правильно понять, клетка в шахматах 1 бит или 13 бит?

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

1 вопрос:
Если в клетке шахматного поля может хранится 13 возможных вариантов состояния (12 разных фигур + отсутствие фигуры), описываемых одним уникальным символом (допустим в 16-ричной системе счисления) то как правильно описать эту клетку? Что "В данной клетке хранится 1 бит информации"?
И как на языке информатики можно описать, что в данной клетке доступно 13 разных вариантов?
Я просто не понимаю как грамотно словами данный факт назвать (количество возможных вариантов).

2 вопрос:
А если мы хотим еще хранить информацию о цвете клетки, то:
Цвет клетки это должен быть дополнительный бит информации (то-есть в клетке станет хранится 2 бита информации). Или это умножение всех вариантов состояния клетки на 2?
То-есть клетка хранит по-прежнему 1-бит информации, а возможных вариантов 26.
Или возможны оба варианта?
  • Вопрос задан
  • 1053 просмотра
Решения вопроса 3
Rsa97
@Rsa97
Для правильного вопроса надо знать половину ответа
Бит - минимальная единица информации. Он имеет два состояния, включено/выключено, истина/ложь, чёрное/белое, 0/1 и т.д.
Для того, чтобы закодировать N разных состояний необходимо ⌈log2N⌉ битов.
Таким образом, 13 состояний клетки потребуют ⌈log213⌉ = 4 бита.
Цвет клетки можно получить из её позиции на доске, отдельного бита для хранения при этом не требуется.
Ответ написан
wataru
@wataru
Разработчик на С++, экс-олимпиадник.
Если клетка может иметь 13 различных состояния, то надо log_2(13)=3.7004... бит. Т.е. если хранить каждую клетку отдельно, то она будет 4 бита.

Дополнительный цвет клетки удвоит количество возможных вариантов. Будет нужно на 1 бит больше (log2(13*2)=log2(13) + log2(2) = log2(13)+1).

Запомните, количество бит = логарифм от количества вохможных вариантов. Потому что каждый бит, имея 2 значения, умножает количество возможных вариантов значений на 2.
Ответ написан
saboteur_kiev
@saboteur_kiev Куратор тега Программирование
software engineer
Если в клетке шахматного поля может хранится 13 возможных вариантов состояния (12 разных фигур + отсутствие фигуры),

Адресовать в памяти можно только байты. Но можно обращаться к отдельным битам байта.
для 13 возможных состояния понадобится 4 бита, при этом будет еще два варианта неиспользуемых.
Итого на 64 клетки можно обойтись 32 байтами.

Но если у вас всего 12 разных фигур, то не проще хранить координаты 12-фигур, на что нужно 6 бит на каждую фигуру? Можно округлить и хватит 12 байт на 12 фигур, или 24 байта на 24 фигуры, что еще меньше, чем 32 байта.
Ответ написан
Пригласить эксперта
Ответы на вопрос 1
samodum
@samodum
Какой вопрос - такой и ответ
В случае с шахматной доской не нужно хранить 13 состояний для каждой клетки, т.к. в ней может стоять только одна фигура. Достаточно обозначить через 0-пусто, 1-пешка, 2-ладья, 3-конь и т.д. Всего разных фигур 6+1(пусто), это 3 бита плюс один бит на цвет фигуры. Итого 4 бита для клетки.
Цвет клетки тоже не нужно хранить в виде состояния. Его можно определить по координатам клетки (x,y). Достаточно сложить x+y и проверить эту сумму на чётность. Если чётное, то белая клетка, иначе - чёрная
Ответ написан
Комментировать
Ваш ответ на вопрос

Войдите, чтобы написать ответ

Похожие вопросы