то в требуется в наихудшем случае? Этот вопрос непосредственно связан с вопросом о том, каково максимальное количество различных ходов может быть сделано в корректной шахматной позиции? Насколько мне известно, текущий известный максимум - 218 ходов в следующей позиции:

- - - Q - - • - 3Q4

-Q----Q - 1Q4Q1

• - - - Q - - - 4Q3 --Q----R 2Q4R Q----Q- - Q4Q2

• - - Q - - - - 3Q4 -Q----RP 1Q4RP -K-BBNNk iKlBBNNk

В ЭТОМ наихудшем случае для кодирования хода в виде обычного двоичного числа достаточно 8 битов. В среднем, по-видимому, 5 битов будет достаточно для того, чтобы хранить типичный ход. Начальная позиция имеет 20 возможных ходов; типичный эндшпиль, например, король, ладья и две пешки на пустой доске, имеет около 30 допустимых ходов - что также приводит к 5 битам при использовании описанного метода.

Если задуматься, то становится понятным, что описанный метод близок к оптимальному, поскольку он представляет точный и непосредственный ответ на вопрос: Какой разрешенный ход был сделан? Мы используем минимальное количество битов для представления всех возможных ходов в виде двоичного числа, располагая полной информацией о том, что происходило до этого хода.

Можно ли улучшить и этот результат? Да, но теперь результаты будут не столь впечатляющими, так как нам потребуются новые знания о шахматах, а речь идет об экономии долей битов. Для того чтобы проиллюстрировать возможность улучшения достигнутых нами результатов, обратимся еще раз к начальной позиции. В ней имеется 20 возможных ходов, что в нашей схеме требует ceiling(!og2(20)) = 5 битов. Теоретически же в этой ситуации имеется только log2(20) = 4.3 битов информации, если счи-тать все ходы равновероятными, так что в среднем нам должно хватить еще меньшего количества битов, если вспомнить о том, что большая часть всех партий начинается с одного из двух популярных ходов белых. Короче говоря, если мы располагаем дополнительной информацией об относительных вероятностях каждого хода (например, встраивая в механизм сжатия детерминистскую шахматную программу, которая может предположить, какие ходы в любой заданной позиции будут наиболее вероятны), то мы можем использовать кодирование с переменной длиной, такое как код Хаффмана или арифметическое сжатие, чтобы использовать меньшее количество битов для хранения более вероятных ходов. Цена такой высокой степени сжатия информации - повышенное время вычислений, использующих знания о предметной области.

Резюме

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

В результате даже без знаний о том, какие ходы наиболее вероятны в данной позиции, мы можем сохранить типичную 40-ходовую партию (80 полу ходов) примерно в 50 байтах. Это очень немного, и достичь этого можно только путем применения знаний о предмете задачи для се решения.

> Рекомендация

Оптимизация должна опираться на точные знания о том, что вы должны оптимизировать, и как вы должны это делать. Знания предметной области ничем невозможно заменить.

Ловушки, ошибки и головоломки

Перед тем как мы перейдем к заключительной части книги, содержащей конкретные примеры стиля программирования, давайте рассмотрим несколько других тем, связанных с языком С++, или просто головоломных ситуаций.

Почему С+ + , как и большинство других языков программирования, резервирует ключевые слова, так что вы не можете, например, использовать переменную с именем class? Почему строка кода, которая выглядит, как вполне правильная, выполняющая определенную работу, в результате не приводит ни к одной команде процессора, как будто она никогда и не существовала? И почему, казалось бы, вовсе некорректный текст нормально компилируется и работает? Почему при работе с числами с плаваю щей точкой желательно пользоваться double?

И наконец - мы когда-нибудь сможем разобраться с макросами?..

Задача 28. Ключевые слова,

не являющиеся таковыми Сложность: 3

Все ключевые слова равноценны для синтаксического анализатора, но некоторые оказываются равноценнее других. Здесь мы увидим, почему так важно резервирование ключевых слов, а также познакомимся с двумя ключевыми словами, которые вовсе не влияют на семантику программы на С++.

Вопрос для новичка

1. Почему большинство языков программирования имеют зарезервированные ключевые слова, которые не могут произвольно использоваться в программе?

Вопрос для профессионала

2. Как добавление ключевого слова auto изменяет семантику программы на С++?

3. Как добавление ключевого слова regi ster изменяет семантику программы на С++?

Решение

Зачем нужны ключевые слова

Для С++ очень важно наличие ключевых слов, зарезервированных языком, которые не могут использоваться в качестве имен, например, типов, функций или переменных.

1. Почему большинство языков программирования имеют зарезервированные ключевые слова, которые не могут произвольно использоваться в программе?

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

Пример 28-1(а): корректная программа на С++.

int main О {

if( true ) ; 1: OK

if( 42 ); 2: ок

В строках 1 и 2 выполняется проверка условий; если условия истинны (а в приведенном примере так оно и есть), выполняется пустая инструкция.

Вряд ли это самый захватывающий исходный текст всех времен и народов. Я даже думаю, что это не самый захватывающий текст из тех, что написаны вами на прошлой неделе. Но, тем не менее, это корректный исходный текст на С+ + , и простейший пример для иллюстрации проблем, которые бы свалились нам на голову, если бы ключевые слова С++ могли использоваться в качестве идентификаторов.

Рассмотрим следующий умозрительный исходный текст, только что прибывший в мой кабинет (без тихого хлопка и не сопровождаясь запахом серы) из альтернативного мира, в котором С++ не резервирует ключевые слова, а программисты счастливы использовать их и в качестве идентификаторов. Пока что не будем разбираться в том, как воспримет текст компилятор, и рассмотрим более простой вопрос; как воспримет текст примера 28-15 человек?