Этюды для программистов

видимому, будет применить виртуальный хеш-код. Пространство, отведенное для хранения старых позиций, может переполняться, поэтому вы должны уметь время от времени освобождать его. Наилучший способ освобождения памяти состоит, пожалуй, в том, чтобы иметь при каждой позиции счетчик, показывающий, сколько раз к ней обращались, и отбрасывать каждый раз те позиции, которые участвовали реже всего. Другой способ, который можно использовать и в сочетании с первым, — хранить список всех старых позиций и всякий раз, когда ищется какая-либо позиция, перемещать ее в голову списка. Когда придет время отбросить часть позиций, то кандидатами на уничтожение будут позиции в хвосте списка, поскольку к ним дольше всего не было обращений. Принятый вами способ отбрасывания старых позиций окажет влияние на выбор стратегии поиска, и наоборот. Заметим, что, хотя алгоритм отбрасывания старых позиций и не влияет на правильность программы анализа пасьянсов, тем не менее он может существенно ее замедлить.

Инструментовка. Эта задача требует средств для удобной работы со структурами данных умеренной сложности. В интересах эффективности выделение и освобождение памяти не следует доверять системе, так что Снобол, видимо, не подойдет. Претендентами могут быть языки Алгол W, Паскаль, PL/I, Лисп и даже Кобол. Вы сможете оценить достоинства структур данных, определяемых программистом, если попытаетесь решить эту задачу сначала на одном из упомянутых выше языков, а потом еще раз на языке типа Фортран или XPL, в которых сложные структуры данных приходится представлять при помощи параллельных массивов.

Длительность исполнения. Одному исполнителю на 3 недели.

Развитие темы. Наиболее очевидное расширение задачи — применить этот метод анализа к другим пасьянсам. Осуществление этой идеи не связано с какими-либо трудностями, если только во время игры не происходит тасования карт. На свете существуют сотни пасьянсов, и ни один из них, насколько нам известно, не подвергался мало-мальски серьезному анализу. На этой задаче можно также изучать зависимости общего числа исследуемых позиций от объема памяти и критерия отбрасывания старых позиций. Иначе говоря, чем исследовать пасьянс при помощи методов поиска, используем задачу о пасьянсе для изучения методов поиска.

Литература

Гибсон (Gibson W. В.). How to Play Winning Solitaire. Frederick Fell, New York, NY, 1964.

Это единственная из известных автору книг о данном пасьянсе.

Кнут (Knuth D. E.). The Art of Computer Programming, Volume 3/Sorting and Searching. Addison-Wesley, Reading, MA, 1973. [Имеется перевод: Кнут Д. Искусство программирования. Т. 3. Сортировка и поиск.— М.: Мир, 1978.] Снова ссылка на книгу Кнута. На этот раз в гл. 6 вы сможете прочитать все о методах поиска, в частности о поиске по хеш-таблице. Разумеется, если вы внимательно изучите всю главу, то, возможно, обнаружите и лучший метод поиска.

* «Наука и жизнь», № 12, 1968; № 2, 1978.

* Гарднер М. Математические новеллы. — М.: Мир, 1974, с. 336.

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

20. Квадратный трехчлен, или Пакет Для Алгебраических Вычислений

Основная трудность, с которой сталкивается программист в большинстве языков программирования, — необходимость при записи вычислений разбивать свои уравнения на мелкие части. Так, если требуется производная, то программист должен записать исходную функцию, снять с полки учебник по математическому анализу, применить изложенные там правила и затем записать получившуюся производную. Однако многие операции можно выполнить на символьном уровне, по крайней мере в случае многочленов, если представлять их подходящим образом. Некоторые программы оказались бы совсем ненужными, если бы ЭВМ могла оперировать с многочленами.

Объекты, с которыми мы будем работать, — это рациональные функции. Их можно определить рекурсивно.

Пусть c — любая вещественная константа. Тогда c — рациональная функция.

Пусть x — любая переменная. Тогда x — рациональная функция.

Пусть р и q — любые рациональные функции. Тогда p + q, p ? q, ?p, pq, p/q и (p) все суть рациональные функции. При делении рациональных функций производится упрощение, так чтобы остался только один знак деления. Правила этого упрощения хорошо знакомы школьникам, изучающим алгебру. Пусть p — любая рациональная функция, а c — целочисленная константа. Тогда p^c — рациональная функция. Если с отрицательна, образуйте рациональную функцию 1/p|c| и упростите деление как выше.

Рациональными функциями являются только те объекты, которые получаются путем применения конечного числа приведенных выше правил.

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

Рациональные функции в качестве исходных данных будут похожи на выражения в стандартном языке программирования. Константы могут изображаться любой последовательностью десятичных цифр с десятичной точкой; если десятичная точка отсутствует, то константа автоматически будет целочисленной. В силу правил образования рациональных функций константы не имеют знака, за исключением констант в показателе степени. Переменная выглядит как идентификатор и может быть любой цепочкой из больших и малых литер алфавита. Из-за ограничений на выбор литер в ЭВМ умножение будет изображаться знаком *, а возведение в степень — знаком ^. Так, рациональную функцию

2xy + (х? + у?)?

можно записать как

2 * X * Y + (X ^ 2 + Y ^ 2) ^ 3

Некоторые другие имена, в частности имена функций, также будут идентификаторами.

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

Установить f равным р; Эта команда приводит к тому, что имя рациональной функции f (мы будем писать сокращенно — имя функции) получает в качестве значения рациональную функцию р. Эта операция — символьная; она не вызывает вычисления р. Если некоторый идентификатор f использован как имя функции, то его нельзя употреблять в последующих командах в качестве переменной; надо иметь в виду, что во время интерпретации потребуется таблица имен, значений и использований. Вместо рациональной функции р может стоять имя функции; в этом случае f получает значение, которое в данный момент имеет р. Все команды заканчиваются точкой с запятой. Примеры описываемой команды:

Установить Р равным z*x^2 + 3.5; Установить fpt равным Р;

Бо?льшая часть остальных команд выполняет некоторую операцию над своими операндами и помещает результат в качестве значения некоторого имени функции.

Установить f равным сумме р и q; Образовать алгебраическую сумму р и q и записать полученное значение под именем f. Во всех командах исходные данные записываются в свободном формате — границы строк (или перфокарт) несущественны; единственным разделителем команд служит точка с запятой. Операндами могут быть имена функций; в таком случае в операциях используются значения, приписанные этим именам.

Установить f равным разности р минус q; Образовать алгебраическую разность р и q и записать полученное значение под именем f.