ПРОГРАММИРОВАНИЕ: ТЕОРЕМЫ И ЗАДАЧИ
НЕСКОЛЬКО ЗАМЕЧАНИЙ ВМЕСТО ПРЕДИСЛОВИЯ
Книга написана по материалам занятий программированием со
школьниками математических классов школы N 57.
Книга написана в убеждении, что программирование имеет свой
предмет, не сводящийся ни к конкретным языкам и системам, ни к
методам построения быстрых алгоритмов.
Кто-то однажды сказал, что можно убедить в правильности алгорит-
ма, но не в правильности программы. Одна из целей книги - попы-
таться продемонстрировать, что это не так.
В принципе, возможность практического исполнения программ не яв-
ляется непременным условием изучения программирования. Однако
она является сильнейшим стимулом - без такого стимула вряд ли у
кого хватит интереса и терпения.
Выбранный жанр книги по необходимости ограничивает ее "програм-
мированием в малом", оставляя в стороне необходимую часть прог-
раммистского образования - работу по модификации больших прог-
рамм. Автор продолжает мечтать о наборе учебных программных сис-
тем эталонного качества, доступных для модификации школьниками.
Кажется, Хоар сказал, что эстетическая прелесть программы - это
не архитектурное излишество, а то, что отличает в программирова-
нии успех от неудачи. Если, решая задачи из этой книги, читатель
почувствует прелесть хорошо написанной программы, в которой "ни
убавить, ни прибавить", и сомнения в правильности которой кажут-
ся нелепыми, то автор будет считать свою цель достигнутой.
Характер глав различен: в одних предлагается набор мало связан-
ных друг с другом задач с решениями, в других по существу изла-
гается один-единственный алгоритм. Темы глав во многом пересека-
ются, и мы предпочли кое-какие повторения формальным ссылкам.
Уровень трудности задач и глав весьма различен. Мы старались
включить как простые задачи, которые могут быть полезны для на-
чинающих, так и трудные задачи, которые могут посадить в лужу и
сильного школьника. (Хоть и редко, но это бывает полезно.)
В качестве языка для записи программ был выбран паскаль Паскаль
достачно прост и естествен, имеет неплохие реализации (например,
Turbo Pascal 3.0 и 5.0 фирмы Borland) и позволяет записать реше-
ния всех рассматриваемых задач. Возможно, Модула-2 или Оберон
были бы более изящным выбором, но пока что они труднее доступны.
Неудачный опыт писания "популярных" учебников по программирова-
нию учит: никакого сюсюканья! писать надо так, чтобы потом самим
было не стыдно прочесть.
Практически все задачи и алгоритмы, разумеется, не являются но-
выми. (В некоторых редких случаях приведены ссылки на конкретную
книгу или конкретного человека. См. также список книг для
дальнейшего чтения.) Вместе с тем мы надеемся, что в некоторых
случаях алгоритмы (и особенно доказательства) изложены более ко-
ротко и отчетливо.
Это не только и не столько учебник для школьника, сколько спра-
вочник и задачник для преподавателя, готовящегося к занятию.
Об "авторских правах": право формулировать задачу и объяснять её
решение является неотчуждаемым естественным правом всякого, кто
на это способен. В соответствии с этим текст (в ASCII и TeX-вер-
сиях) является свободно распространяемыми. С ним можно делать
всё, что угодно, и если Вы внесли в него ошибки, не указав, что
они принадлежат Вам, или использовали текст в коммерческих це-
лях, не поделившись прибылью - Бог Вам судья.
Благодарности. Я рад случаю поблагодарить всех, с кем имел честь
сотрудничать, преподавая программирование, особенно тех, кто был
"по другую сторону баррикады".
Н Е П О К У П А Й Т Е Э Т У К Н И Г У !
(Предупреждение автора)
В этой книге ничего не говорится об особенностях BIOSа,
DOSа, OSа, GEMа и Windows, представляющих основную сложность при
настоящем программировании.
В ней нет ни слова об объектно-ориентированном программиро-
вании, открывшем новую эпоху в построении дружественных и эффек-
тивных программных систем.
Из нее Вы не узнаете о графических возможностях компьютера,
без которых немыслимо современное программирование, о богатстве
и разнообразии мира видеоадаптеров.
Не рассказано в ней и о написании резидентных программ,
тонкости взаимодействия которых должен знать каждый.
Искусственный интеллект, открывший новые рынки сбыта для
программного обеспечения, обойден презрительным молчанием.
Экспертные системы, которые в скором будущем займут место
на рабочем столе каждого, даже не упоминаются.
Логическое программирование, постепенно вытесняющее уста-
ревший операторный стиль программирования, не затронуто.
Драматический поворот от баз данных к базам знаний, вызвав-
ший в жизни новую профессию -- инженер знаний -- остался незаме-
ченным автором.
Проблемы отладки и сопровождения программ, занимающие, по
общему мнению профессионалов, 90% в программировании, игнориру-
ются.
В книге используются лишь самые элементарные возможности
паскаля. Обширные возможности, предоставляемые современными ин-
тегрированными программными средами, остаются невостребованными.
(Не говоря уже о том, что паскаль уже вообще устарел, вытеснен-
ный языком Си.)
Игрушечные головоломки, которым посвящена книга, никому не
нужны. Если же перед Вами встанет действительно важная задача,
неужели Вы не справитесь с ней сами, без непрошеных учителей и
советчиков?
Короче говоря, покупать эту книгу глупо - особенно теперь,
когда выходит столько переводных руководств, написанных в циви-
лизованных странах настоящими профессионалами.
Глава 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, используя в программе лишь операции +, -, =, <>.
Решение.
var a, b, c, k : integer;
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}
1.1.6. Даны натуральные числа а и b. Вычислить их сумму
а+b. Использовать операторы присваивания лишь вида
<переменная1> := <переменная2>,
<переменная> := <число>,
<переменная1> := <переменная2> + 1.
Решение.
...
{инвариант: c = a + k}
...
1.1.7. Дано натуральное (целое неотрицательное) число а и
целое положительное число d. Вычислить частное q и остаток r при
делении а на d, не используя операций div и mod.
Решение. Согласно определению, a = q * d + r, 0 <= r < d.
{a >= 0; d > 0}
r := a; q := 0;
{инвариант: a = q * d + r, 0 <= r}
while not (r < d) do begin
| {r >= d}
| r := r - d; {r >= 0}
| q := q + 1;
end;
1.1.8. Дано натуральное n, вычислить n!
(0!=1, n! = n * (n-1)!).
1.1.9. Последовательность Фибоначчи определяется так:
a(0)= 1, a(1) = 1, a(k) = a(k-1) + a(k-2) при k >= 2. Дано n,
вычислить a(n).
1.1.10. Та же задача, если требуется, чтобы число операций
было пропорционально log n. (Переменные должны быть целочислен-
ными.)
Указание. Пара соседних чисел Фибоначчи получается из пре-
дыдущей умножением на матрицу
|1 1|
|1 0|
так что задача сводится к возведению матрицы в степень n. Это
можно сделать за C*log n действий тем же способом, что и для чи-
сел.
1.1.11. Дано натуральное n, вычислить 1/0!+1/1!+...+1/n!.
1.1.12. То же, если требуется, чтобы количество операций
(выполненных команд присваивания) было бы не более C*n для не-
которой константы С.
Решение. Инвариант: sum = 1/1! +...+ 1/k!, last = 1/k!
(важно не вычислять заново каждый раз k!).
1.1.13. Даны два натуральных числа a и b, не равные нулю
одновременно. Вычислить НОД (a,b) - наибольший общий делитель а
и b.
Решение (1 вариант).
if a > b then begin
| k := a;
end else begin
| k := b;
end;
{k = max (a,b)}
{инвариант: никакое число, большее k, не является об-
щим делителем}
while not (((a mod k)=0) and ((b mod k)=0)) do begin
| k := k - 1;
end;
{k - общий делитель, большие - нет}
(2 вариант - алгоритм Евклида). Будем считать , что НОД
(0,0) = 0. Тогда НОД (a,b) = НОД (a-b,b) = НОД (a,b-a); НОД
(a,0) = НОД (0,a) = a для всех a,b>=0.
m := a; n := b;
{инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 }
while not ((m=0) or (n=0)) do begin
| if m >= n then begin
| | m := m - n;
| end else begin
| | n := n - m;
| end;
end;
if m = 0 then begin
| k := n;
end else begin
| k := m;
end;
1.1.14. Написать модифицированный вариант алгоритма Евкли-
да, использующий соотношения НОД (a, b) = НОД (a mod b, b) при
a >= b, НОД (a, b) = НОД (a, b mod a) при b >= a.
1.1.15. Даны натуральные а и b, не равные 0 одновременно.
Найти d = НОД (a,b) и такие целые x и y, что d = a*x + b*y.
Решение. Добавим в алгоритм Евклида переменные p, q, r, s
