А. шень Издание шестое, дополненное Москва
 Скачать 1.62 Mb.
|
|
А. ШЕНЬ ðòïçòáííéòï÷áîéå ÔÅÏÒÅÍÙ É ÚÁÄÁÞÉ Издание шестое, дополненное Москва Издательство МЦНМО 2017 УДК 519.671 ББК 22.18 Ш47 Шень А. Ш47 Программирование: теоремы и задачи. | 6-е изд., дополнен- ное. | М.: МЦНМО, 2017. | 320 с.: ил. ISBN 978-5-4439-0685-0 Книга содержит задачи по программированию различной трудности. Большинство задач приводятся с решениями. Цель книги | научить основ- ным методам построения корректных и быстрых алгоритмов. Для учителей информатики, старшеклассников, студентов младших кур- сов высших учебных заведений. Пособие может быть использовано на круж- ковых и факультативных занятиях в общеобразовательных учреждениях, в школах с углублённым изучением математики и информатики, а также в иных целях, не противоречащих законодательству РФ. Предыдущее издание книги вышло в 2014 г. ББК 22.18 ISBN 978-5-4439-0685-0 c ○ А. Шень, 1995, 2017 Несколько замечаний вместо предисловия Книга написана по материалам занятий программированием со школьниками математических классов школы Ђ 57 г. Москвы и студентами младших курсов (Московский государственный университет, Независимый московский университет, университет г. Uppsala, Швеция). Книга написана в убеждении, что программирование имеет свой предмет, не сводящийся ни к конкретным языкам и системам, ни к методам построения быстрых алгоритмов. Кто-то однажды сказал, что можно убедить в правильности алгоритма, но не в правильности программы. Одна из целей книги | попытаться продемонстрировать, что это не так. В принципе, возможность практического исполнения программ не является непременным условием изучения программирования. Однако она является сильнейшим стимулом | без такого стимула вряд ли у кого хватит интереса и терпения. Выбранный жанр книги по необходимости ограничивает её «программированием в малом», оставляя в стороне необходимую часть программистского образования | работу по модификации больших программ. Автор продолжает мечтать о наборе учебных программных систем эталонного качества, доступных для модификации школьниками. Кажется, Хоар сказал, что эстетическая прелесть программы | это не архитектурное излишество, а то, что отличает в программировании успех от неудачи. Если, решая задачи из этой книги, читатель почувствует прелесть хорошо написанной программы, в которой «ни убавить, ни прибавить», и сомнения в правильности которой кажутся нелепыми, то автор будет считать свою цель достигнутой. Характер глав различен: в одних предлагается набор мало связанных друг с другом задач с решениями, в других по существу излагается один-единственный алгоритм. Темы глав во многом пересекаются, и мы предпочли кое-какие повторения формальным ссылкам. Уровень трудности задач и глав весьма различен. Мы старались включить как простые задачи, которые могут быть полезны для начинающих, так и трудные задачи, которые могут посадить в лужу сильного школьника. (Хоть и редко, но это бывает полезно.) В качестве языка для записи программ был выбран паскаль. Он достаточно прост и естествен, имеет неплохие реализации (например, старые компиляторы Turbo Pascal фирмы Borland были выложены для бесплатного скачивания) и позволяет записать решения всех рассматриваемых задач. Возможно, Модула-2 или Оберон были бы более изящным выбором, но они менее доступны. Практически все задачи и алгоритмы, разумеется, не являются новыми. (В некоторых редких случаях приведены ссылки на конкретную книгу или конкретного человека. См. также список книг для дальнейшего чтения.) Вместе с тем мы надеемся, что в некоторых случаях алгоритмы (и особенно доказательства) изложены более коротко и отчётливо. Это не только и не столько учебник для школьника, сколько справочник и задачник для преподавателя, готовящегося к занятию. Об «авторских правах»: право формулировать задачу и объяснять её решение является неотчуждаемым естественным правом всякого, кто на это способен. В соответствии с этим текст является свободно распространяемым. Адреса автора: shen@mccme.ru, sasha.shen@gmail.com, alexander.shen@lirmm.fr. Сказанное относится к русскому тексту; все права на переводы переданы издательству Springer. При подготовке текста использовалась (свободно распространяемая) версия L A TEXа, включающая стилевые файлы, составленные С. М. Львовским (см. ftp://ftp.mccme.ru/pub/tex/). Я рад случаю поблагодарить всех, с кем имел честь сотрудничать, препо- давая программирование, особенно тех, кто был «по другую сторону барри- кады», а также всех приславших мне замечания и исправления (специаль- ная благодарность | Ю. В. Матиясевичу). Автор благодарит В. Шувалова за хлопоты по вёрстке, а также издательство МЦНМО. Благодарю так- же Институт проблем передачи информации РАН, Американское матема- тическое общество (фонд помощи бывшему СССР), фонд Сороса, универ- ситет г. Бордо, фонд «Культурная инициатива», фонды STINT (Швеция), CNRS (Франция), Ecole Normale (Лион, Франция), LIF (Марсель, Франция), LIRMM (Монпелье, Франция), университет г. Уппсала (Швеция), агент- ство ANR (грант RaCAF, ANR-15-CE40-0016-01), Российский фонд фунда- ментальных исследований (гранты 02-01-22001 НЦНИа, 03-01-00475 и дру- гие), а также Совет поддержки научных школ при Президенте РФ (грант НШ-358.2003.1 ) за поддержку. Вместе с тем содержание книги отражает точку зрения автора, за ошибки которого указанные организации и лица ответственности не несут (и наоборот). Содержание 1. Переменные, выражения, присваивания 8 1.1. Задачи без массивов 8 1.2. Массивы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 1.3. Индуктивные функции (по А. Г. Кушниренко) . . . . . . . 38 2. Порождение комбинаторных объектов 43 2.1. Размещения с повторениями . . . . . . . . . . . . . . . . . 43 2.2. Перестановки . . . . . . . . . . . . . . . . . . . . . . . . . . 44 2.3. Подмножества . . . . . . . . . . . . . . . . . . . . . . . . . 45 2.4. Разбиения . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48 2.5. Коды Грея и аналогичные задачи . . . . . . . . . . . . . . 49 2.6. Несколько замечаний . . . . . . . . . . . . . . . . . . . . . 55 2.7. Подсчёт количеств . . . . . . . . . . . . . . . . . . . . . . . 57 3. Обход дерева. Перебор с возвратами 60 3.1. Ферзи, не бьющие друг друга: обход дерева позиций . . . 60 3.2. Обход дерева в других задачах . . . . . . . . . . . . . . . 70 4. Сортировка 72 4.1. Квадратичные алгоритмы . . . . . . . . . . . . . . . . . . 72 4.2. Алгоритмы порядка 𝑛 log 𝑛 . . . . . . . . . . . . . . . . . . 73 4.3. Применения сортировки . . . . . . . . . . . . . . . . . . . . 80 4.4. Нижние оценки для числа сравнений при сортировке . . . 82 4.5. Родственные сортировке задачи . . . . . . . . . . . . . . . 84 5. Конечные автоматы и обработка текстов 90 5.1. Составные символы, комментарии и т. п. . . . . . . . . . . 90 5.2. Ввод чисел . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92 6 Содержание 6. Типы данных 96 6.1. Стеки . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 96 6.2. Очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6.3. Множества . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.4. Разные задачи . . . . . . . . . . . . . . . . . . . . . . . . . 115 7. Рекурсия 117 7.1. Примеры рекурсивных программ . . . . . . . . . . . . . . 117 7.2. Рекурсивная обработка деревьев . . . . . . . . . . . . . . . 120 7.3. Порождение комбинаторных объектов, перебор . . . . . . 123 7.4. Другие применения рекурсии . . . . . . . . . . . . . . . . . 127 8. Как обойтись без рекурсии 135 8.1. Таблица значений (динамическое программирование) . . 135 8.2. Стек отложенных заданий . . . . . . . . . . . . . . . . . . 140 8.3. Более сложные случаи рекурсии . . . . . . . . . . . . . . . 143 9. Разные алгоритмы на графах 146 9.1. Кратчайшие пути . . . . . . . . . . . . . . . . . . . . . . . 146 9.2. Связные компоненты, поиск в глубину и ширину . . . . . 152 9.3. Сети, потоки и разрезы . . . . . . . . . . . . . . . . . . . . 157 10. Сопоставление с образцом 178 10.1. Простейший пример . . . . . . . . . . . . . . . . . . . . . . 178 10.2. Повторения в образце | источник проблем . . . . . . . . 181 10.3. Вспомогательные утверждения . . . . . . . . . . . . . . . . 183 10.4. Алгоритм Кнута { Морриса { Пратта . . . . . . . . . . . . 183 10.5. Алгоритм Бойера { Мура . . . . . . . . . . . . . . . . . . . 186 10.6. Алгоритм Рабина . . . . . . . . . . . . . . . . . . . . . . . . 188 10.7. Более сложные образцы и автоматы . . . . . . . . . . . . . 190 10.8. Суффиксные деревья . . . . . . . . . . . . . . . . . . . . . . 197 11. Анализ игр 210 11.1. Примеры игр . . . . . . . . . . . . . . . . . . . . . . . . . . 210 11.2. Цена игры . . . . . . . . . . . . . . . . . . . . . . . . . . . . 212 11.3. Вычисление цены: полный обход . . . . . . . . . . . . . . . 220 11.4. Альфа-бета-процедура . . . . . . . . . . . . . . . . . . . . . 223 11.5. Ретроспективный анализ . . . . . . . . . . . . . . . . . . . 227 Содержание 7 12. Оптимальное кодирование 230 12.1. Коды . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 230 12.2. Неравенство Крафта { Макмиллана . . . . . . . . . . . . . 231 12.3. Код Хаффмана . . . . . . . . . . . . . . . . . . . . . . . . . 235 12.4. Код Шеннона { Фано . . . . . . . . . . . . . . . . . . . . . . 237 13. Представление множеств. Хеширование 241 13.1. Хеширование с открытой адресацией . . . . . . . . . . . . 241 13.2. Хеширование со списками . . . . . . . . . . . . . . . . . . . 244 14. Деревья. Сбалансированные деревья 250 14.1. Представление множеств с помощью деревьев . . . . . . . 250 14.2. Сбалансированные деревья . . . . . . . . . . . . . . . . . . 258 15. Контекстно-свободные грамматики 269 15.1. Общий алгоритм разбора . . . . . . . . . . . . . . . . . . . 269 15.2. Метод рекурсивного спуска . . . . . . . . . . . . . . . . . 275 15.3. Алгоритм разбора для LL(1)-грамматик . . . . . . . . . . 286 16. Синтаксический разбор слева направо (LR) 294 16.1. LR-процессы . . . . . . . . . . . . . . . . . . . . . . . . . . 294 16.2. LR(0)-грамматики . . . . . . . . . . . . . . . . . . . . . . . 300 16.3. SLR(1)-грамматики . . . . . . . . . . . . . . . . . . . . . . 306 16.4. LR(1)-грамматики, LALR(1)-грамматики . . . . . . . . . 307 16.5. Общие замечания о разных методах разбора . . . . . . . . 310 Книги для чтения 312 Предметный указатель 313 Указатель имён 319 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. Задачи без массивов 9 1.1.3. Дано целое число а и натуральное (целое неотрицательное) число n. Вычислите an. Другими словами, необходимо составить про- грамму, при исполнении которой значения переменных а и n не меняют- ся, а значение некоторой другой переменной (например, b) становится равным an. (При этом разрешается использовать и другие переменные.) Решение. Введём целую переменную k, которая меняется от 0 до n, причём поддерживается такое свойство: b = ak). 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 (то есть не превосходило бы 𝐶 log n для некоторой константы 𝐶; 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; 10 1. Переменные, выражения, присваивания Каждый второй раз (не реже) будет выполняться первый вариант оператора выбора (если k нечётно, то после вычитания единицы ста- новится чётным), так что за два цикла величина k уменьшается по крайней мере вдвое. 1.1.5. Даны натуральные числа а, b. Вычислите произведение a · 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} 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 6 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. Задачи без массивов 11 1.1.8. Дано натуральное n, вычислите n! (0! = 1, n! = n · (n − 1)!). 1.1.9. Последовательность Фибоначчи определяется так: a0 = 0, a1 = 1, ak = ak-1 + ak-2 при k > 2. Дано n, вычислите an. 1.1.10. Та же задача, если требуется, чтобы число операций было пропорционально log n. (Переменные должны быть целочисленными.) [Указание. Пара соседних чисел Фибоначчи получается из предыду- щей умножением на матрицу ⃦ ⃦ ⃦ ⃦ 1 1 1 0 ⃦ ⃦ ⃦ ⃦ | так что задача сводится к возведению матрицы в степень n. Это можно сделать за 𝐶 log n действий тем же способом, что и для чи- сел.] 1.1.11. Дано натуральное n, вычислите 1 0! + 1 1! + . . . + 1 n! 1.1.12. То же, если требуется, чтобы количество операций (выпол- ненных команд присваивания) было бы порядка n (не более 𝐶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 = min (a,b)} {инвариант: никакое число, большее k, не является общим делителем (оно больше одного из чисел a,b)} while not ((a mod k = 0) and (b mod k = 0)) do begin k := k - 1; end; {k - общий делитель, большие - нет} 12 1. Переменные, выражения, присваивания Вариант 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; {m = 0 или n = 0} if m = 0 then begin k := n; end else begin {n = 0} 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. Даны натуральные a и b, не равные 0 одновременно. Найдите d = НОД(a,b) и такие целые x и y, что d = a · x + b · y. Решение. Добавим в алгоритм Евклида переменные p, q, r, s и впи- шем в инвариант условия m = p*a+q*b; n = r*a+s*b. m:=a; n:=b; p := 1; q := 0; r := 0; s := 1; {инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 m = p*a + q*b; n = r*a + s*b.} while not ((m=0) or (n=0)) do begin if m >= n then begin m := m - n; p := p - r; q := q - s; end else begin n := n - m; r := r - p; s := s - q; end; end; if m = 0 then begin k :=n; x := r; y := s; end else begin k := m; x := p; y := q; end; 1.1. Задачи без массивов 13 1.1.16. Решите предыдущую задачу, используя в алгоритме Евкли- да деление с остатком. 1.1.17. (Э. Дейкстра) Добавим в алгоритм Евклида дополнительные переменные u, v, z: m := a; n := b; u := b; v := a; {инвариант: НОД (a,b) = НОД (m,n); m,n >= 0 } while not ((m=0) or (n=0)) do begin if m >= n then begin m := m - n; v := v + u; end else begin n := n - m; u := u + v; end; end; if m = 0 then begin z:= v; end else begin {n=0} z:= u; end; Докажите, что после исполнения алгоритма значение z равно удвоен- ному наименьшему общему кратному чисел a, b: z = 2 · НОК(a,b). Решение. Заметим, что величина m · u + n · v не меняется в ходе вы- полнения алгоритма. Остаётся воспользоваться тем, что вначале она равна 2ab и что НОД(a, b) · НОК(a, b) = ab. 1.1.18. Напишите вариант алгоритма Евклида, использующий соот- ношения НОД(2a, 2b) = 2 · НОД(a, b), НОД(2a, b) = НОД(a, b) при нечётном b, не включающий деления с остатком, а использующий лишь деление на 2 и проверку чётности. (Число действий должно быть порядка log k для исходных данных, не превосходящих k.) Решение. m:= a; n:=b; d:=1; {НОД(a,b) = d * НОД(m,n)} while not ((m=0) or (n=0)) do begin if (m mod 2 = 0) and (n mod 2 = 0) then begin d:= d*2; m:= m div 2; n:= n div 2; end else if (m mod 2 = 0) and (n mod 2 = 1) then begin 14 1. Переменные, выражения, присваивания m:= m div 2; end else if(m mod 2 = 1) and (n mod 2 = 0) then begin n:= n div 2; end else if (m mod 2=1) and (n mod 2=1) and (m>=n) then begin m:= m-n; end else if (m mod 2=1) and (n mod 2=1) and (m<=n) then begin n:= n-m; end; end; {m=0 => ответ=d*n; n=0 => ответ=d*m} Оценка числа действий: каждое второе действие делит хотя бы одно из чисел m и n пополам. 1.1.19. Дополните алгоритм предыдущей задачи поиском x и y, для которых ax + by = НОД(a, b). Решение. (Идея сообщена Д. Звонкиным.) Прежде всего заметим, что одновременное деление a и b пополам не меняет искомых x и y. По- этому можно считать, что с самого начала одно из чисел a и b нечётно. (Это свойство будет сохраняться и далее.) Теперь попытаемся, как и раньше, хранить такие числа p, q, r, s, что m = ap + bq, n = ar + bs. Проблема в том, что при делении, скажем, m на 2 надо разделить p и q на 2, и они перестанут быть целыми (а станут двоично-рациональ- ными). Двоично-рациональное число естественно хранить в виде пары ⟨ числитель, показатель степени двойки в знаменателе⟩. В итоге мы по- лучаем d в виде комбинации a и b с двоично-рациональными коэффи- циентами. Иными словами, мы имеем |