Содержание

Введение........................................ 7

От издательства...................................... 11

О технологии программирования.................. 12

Испытание, тестирование, отладка, защита разработки......... 12

Эффективность алгоритмов и программ..................... 14

Часть I. Задания для начинающих................. 17

1. Линейные алгоритмы................................... 18

Задачи по теме «Линейные алгоритмы»..................... 19

2. Разветвляющиеся алгоритмы............................. 25

Задачи по теме «Разветвляющиеся алгоритмы»............... 26

3. Циклические и итерационные алгоритмы.................... 33

Задачи по теме «Циклические и итерационные алгоритмы»...... 36

4. Простейшие операции над массивами...................... 45

Задачи по теме «Простейшие операции над массивами»........ 47

Часть II. Работа с массивами...................... 53

5. Векторы и матрицы.................................... 54

Задачи по теме «Векторы и матрицы»...................... 58

6. Линейный поиск...................................... 65

Задачи по теме «Линейный поиск»........................ 68

Часть III. Прикладные математические задачи ...... 73

7. Арифметика......................................... 74

Задачи по теме «Арифметика» ........................... 77

8. Геометрия и теория множеств............................ 84

9. Линейная алгебра и сжатие информации.................... 92

Задачи по теме «Линейная алгебра и сжатие информации»...... 96

6 Содержание

10. Комбинаторика и теория вероятностей .................... 100

Задачи по теме «Комбинаторика и теория вероятностей»....... 102

11. Элементы численного анализа........................... 106

Задачи по теме «Элементы численного анализа»............. 109

12. Алгоритмы обработки символьной информации.............. 113

Задачи по теме «Алгоритмы обработки символьной информации» 116

13. Элементарная машинная графика........................ 124

Задачи по теме «Элементарная машинная графика».......... 126

14. Элементы компьютерной мультипликации.................. 130

Задачи по теме «Элементы компьютерной мультипликации» .... 133

15. Сортировка и слияние массивов.......................... 140

Задачи по теме «Сортировка и слияние массивов»............ 143

16. Поиск с возвратом. Задачи на графах ..................... 151

Задачи по теме «Поиск с возвратом. Задачи на графах»........ 155

17. Разработка простейших АРМ и ИПС....................... 161

Задачи по теме «Разработка простейших АРМ и ИПС»......... 165

18. Электронные таблицы................................. 175

Введение

Основу книги составил материал, опубликованный в пособии [35], выпущенном автором в 1999 году в Алтайском государственном университете. Оно в основном было написано для нужд раздела «Классическое программирование» курса «Информатика», преподаваемого на математическом факультете. До этого на протяжении многих лет материал прошел все стадии испытаний: от раздаточного материала в виде карточек с заданиями до серии методических пособий. За это время накопилось немало замечаний к формулировкам задач, появились дополнительные задачи, накопился опыт их использования.

Что такое программирование: ремесло, наука или искусство? По-моему, в нем можно найти все три начала, все зависит от характера и уровня подготовки программиста: кодирование заданного алгоритма — ремесло; разработка эффективных приемов и технологий — наука; поиск уникальных по эффективности и возможностям алгоритмов — искусство.

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

Автор надеется помочь читателям продвинуться на каждом из этих уровней: от кодирования очевидных алгоритмов до пробуждения самолюбия в поисках эффективного решения сложных задач. При поиске задач для задачника проработан не один десяток сборников и учебников. Из них по крупицам отобраны наиболее интересные формулировки (например, Задача Иосифа: 5.11); многие задачи являются оригинальными и родились в длительных дискуссиях с коллегами (в частности с, А. Максимовым), за что им огромная признательность. Автор считает, что применение разнообразных по содержанию задач дает гораздо больший эффект, чем только лекционный курс и изучение многочисленных учебников.

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

К задачам при их подборе предъявлялись следующие требования:

■ типичность, то есть применение в решении часто используемых приемов программирования;

■ содержательность, то есть формулировка задач в терминах предметной области, с предложением самостоятельно провести математизацию задачи (вывести необходимые формулы) и алгоритмизацию (найти или разработать метод решения);

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

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

Часть I задачника содержит простейшие задачи для начинающих. Часть II посвящена типичным приемам при работе с массивами (то есть манипуляциям данными в оперативной памяти): линейному поиску, преобразованиям. В части III собраны разнообразные прикладные задачи: от геометрии и комбинаторики до элементов текстового анализа и компьютерной мультипликации, а также методы сортировки и задачи, приводящие к переборным и рекурсивным алгоритмам. Часть IV задачника посвящена базам данных и электронным таблицам. При этом задачи разбиты по темам так, чтобы в каждой теме было не менее 25-30 задач, что дает возможность преподавателю случайно или принудительно распределять их среди студенческой группы.

Задачи, как правило, не требуют математических или других специальных знаний: для решения большинства из них достаточно школьного курса и лишь в некоторых используются элементы аналитической геометрии, векторной алгебры, математического анализа либо других математических дисциплин (в последнем случае необходимые сведения приведены в условии задачи либо в ссылках на литературу). Это позволяет использовать приведенные задачи не только для математических, но и для других естественнонаучных и технических специальностей, а выборочно — для «гуманитариев» и школьников.

Задачи максимально свободны от привязки к языку программирования. Так, первые три части — классическое программирование — реализуются на любой версии Бейсика, Паскаля, С, Фортрана, Delphi и др. (при наличии разве что графических средств). Четвертая часть ориентирована на БД типа XBase, FoxPro, Delphi, Access (программы могут быть реализованы на любой другой СУБД), а также на электронные таблицы типа SuperCalc, Excel и др.

Задачи были испытаны более чем на десяти потоках студентов естественнонаучных специальностей АГУ; автор выражает им свою признательность за долготерпение и помощь в уточнении формулировок, в оценке сложности задач, в разработке некоторых примеров программ (отметим, что приведенные примеры реализованы в среде Turbo Pascal 7.0 фирмы Borland). Автор также глубоко признателен коллегам, участвовавшим в этой «обкатке», и конкретно — А. Максимову, Л. Смоляковой, Д. Иванову и др., — за помощь в подборе задач и устранении недостатков формулировок. Некоторые из студентов уже стали известными программистами и с благодарностью вспоминают первые навыки, полученные с помощью этих задач.

Несколько слов к преподавателям об использовании предлагаемой подборки в учебном процессе. Для первого курса выделяются первые 16 тем (случайным образом сформированные индивидуальные пакеты заданий на весь учебный год выдаются студентам в сентябре; дальше — самостоятельная работа с консультациями преподавателя и защита по мере реализации и испытания программ). Разная стартовая подготовка абитуриентов позволяет формировать индивидуальные требования, по результатам решения выставлять досрочные оценки либо назначать дополнительные консультации. На старте же оглашаются критерии оценок (например, для получения удовлетворительной оценки за год без устного экзамена достаточно своевременно решить 9 задач; результаты на экзамене прибавляются к накопленной сумме баллов, и оценка выставляется по итоговой сумме). При затягивании сроков защиты вклад задач в экзаменационную оценку уменьшается; при повышенном качестве реализации алгоритма — увеличивается.

Однако опыт показал, что, несмотря на все усилия, задачи не удалось сбалансировать по сложности в пределах одной темы. Поэтому была сделана попытка проранжировать сложность задач в баллах и изменить критерии итоговых оценок. Уровень сложности задач первых 16 тем оценен в баллах («вес» каждой задачи проставлен в скобках после ее номера). При этом ранжирование проведено относительное, в пределах каждого раздела. Разделы расположены, как правило, в порядке возрастания сложности задач, что подразумевает рост квалификации обучаемых при переходе от темы к теме. При оценке «весов» учитывались мнения как преподавателей, так и студентов. Хотелось бы получить критические отзывы коллег на нашу технологию.

Для второго курса предлагаются задачи из 17-й темы (близкий к реальным условиям проект информационно-поисковой системы (ИПС) вместе с умением описывать программные средства в среде Microsoft Office или на других платформах), а также знакомство с электронными таблицами — в 18-й теме.

Типографское соглашение: в условиях задач, если это не оговорено явно, БОЛЬШИМИ латинскими буквами обозначены агрегаты данных (массивы, структуры, множества, геометрические точки), малыми буквами — простые (скалярные) переменные. При этом, как правило, буквами I, J, К, L, М, N обозначаются целочисленные агрегаты; буквами i, j, k, l,m,n~ целочисленные переменные. Размерности массивов записываются в круглых скобках через запятую, например А(т, п) — матрица, содержащая т строк и п столбцов.