Несколько замечаний вместо предисловия

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

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

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

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

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

Уровень трудности задач и глав весьма различен. Мы старались
включить как простые задачи, которые могут быть полезны для на-
чинающих, так и трудные задачи, которые могут посадить в лужу
сильного школьника. (Хоть и редко, но это бывает полезно.)

В качестве языка для записи программ был выбран паскаль Паскаль
достаточно прост и естествен, имеет неплохие реализации (напри-
мер, Turbo Pascal 3.0 и 5.0 фирмы Borland) и позволяет записать
решения всех рассматриваемых задач. Возможно, Модула-2 или Обе-
рон были бы более изящным выбором, но пока что они менее доступ-
ны.

Неудачный опыт писания "популярных" учебников по программирова-
нию учит: никакого сюсюканья - писать надо так, чтобы потом са-
мим было не стыдно прочесть.

Практически все задачи и алгоритмы, разумеется, не являются но-
выми. (В некоторых редких случаях приведены ссылки на конкретную
книгу или конкретного человека. См. также список книг для
дальнейшего чтения.) Вместе с тем мы надеемся, что в некоторых
случаях алгоритмы (и особенно доказательства) изложены более ко-
ротко и отчётливо.

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

Об "авторских правах": право формулировать задачу и объяснять её
решение является неотчуждаемым естественным правом всякого, кто
на это способен. В соответствии с этим текст (в ASCII и TeX-вер-
сиях) является свободно распространяемым.
Адрес автора: 125384, Москва, ул. Беговая, 17, кв. 14.
Тел.: +7 (495) 945-82-16
shen@ium.ips.ras.ru, shen@landau.ac.ru
Сказанное относится к русскому тексту; все права на переводы пе-
реданы издательству Birkhauser.

Содержание
Глава 1. Переменные, выражения, присваивания.
Глава 2. Порождение комбинаторных объектов.
Глава 3. Обход дерева. Перебор с возвратами.
Глава 4. Сортировка.
Глава 5. Конечные автоматы и обработка текстов.
Глава 6. Типы данных.
Глава 7. Рекурсия.
Глава 8. Как обойтись без рекурсии.
Глава 9. Разные алгоритмы на графах.
Глава 10. Сопоставление с образцом.
Глава 11. Представление множеств. Хеширование.
Глава 12. Множества и деревья.
Глава 13. Контекстно-свободные грамматики.
Глава 14. Синтаксический разбор слева направо.

Глава 1. Переменные, выражения, присваивания

1.1. Задачи без массивов

1.1.1. Даны две целые переменные a, b. Составить фрагмент
программы, после исполнения которого значения переменных поменя-
лись бы местами (новое значение a равно старому значению b и на-
оборот).

Решение. Введем дополнительную целую переменную t.
t := a;
a := b;
b := t;
Попытка обойтись без дополнительной переменной, написав
a := b;
b := a;
не приводит к цели (безвозвратно утрачивается начальное значение
переменной a).

1.1.2. Решить предыдущую задачу, не используя дополни-
тельных переменных (и предполагая, что значениями целых перемен-
ных могут быть произвольные целые числа).

Решение. (Начальные значения a и b обозначим a0, b0.)
a := a + b; {a = a0 + b0, b = b0}
b := a - b; {a = a0 + b0, b = a0}
a := a - b; {a = b0, b = a0}

1.1.3. Дано целое число а и натуральное (целое неотрица-
тельное) число n. Вычислить а в степени n. Другими словами, не-
обходимо составить программу, при исполнении которой значения
переменных а и n не меняются, а значение некоторой другой пере-
менной (например, b) становится равным а в степени n. (При этом
разрешается использовать и другие переменные.)

Решение. Введем целую переменную k, которая меняется от 0
до n, причем поддерживается такое свойство: b = (a в степени
k).

k := 0; b := 1;
{b = a в степени k}
while k <> n do begin
| k := k + 1;
| b := b * a;
end;

Другое решение той же задачи:

k := n; b := 1;
{a в степени n = b * (a в степени k)}
while k <> 0 do begin
| k := k - 1;
| b := b * a;
end;

1.1.4. Решить предыдущую задачу, если требуется, чтобы чис-
ло действий (выполняемых операторов присваивания) было порядка
log n (то есть не превосходило бы C*log n для некоторой констан-
ты C; log n - это степень, в которую нужно возвести 2, чтобы по-
лучить n).

Решение. Внесем некоторые изменения во второе из предложен-
ных решений предыдущей задачи:

k := n; b := 1; c:=a;
{a в степени n = b * (c в степени k)}
while k <> 0 do begin
| if k mod 2 = 0 then begin
| | k:= k div 2;
| | c:= c*c;
| end else begin
| | k := k - 1;
| | b := b * c;
| end;
end;

Каждый второй раз (не реже) будет выполняться первый вариант
оператора выбора (если k нечетно, то после вычитания единицы
становится четным), так что за два цикла величина k уменьшается
по крайней мере вдвое.

1.1.5. Даны натуральные числа а, b. Вычислить произведение
а*b, используя в программе лишь операции +, -, =, <>.

Решение.

k := 0; c := 0;
{инвариант: c = a * k}
while k <> b do begin
| k := k + 1;
| c := c + a;
end;
{c = a * k и k = b, следовательно, c = a * b}