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

Кнут (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. Во всех командах исходные данные записываются в свободном формате — границы строк (или перфокарт) несущественны; единственным разделителем команд служит точка с запятой. Операндами могут быть имена функций; в таком случае в операциях используются значения, приписанные этим именам.