Читать онлайн «Методы программирования в примерах и задачах»

МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ имени М. В. ЛОМОНОСОВА Механико-математический факультет Кафедра вычислительной математики В. Д. Валединский, А. А. Корнев Методы программирования в примерах и задачах Москва 2000 год ББК 32. 973 В 37 УДК 681. 3 В. Д. Валединский, А. А. Корнев. Методы программирования в примерах и задачах. — М. : Изд-во ЦПИ при механико-математическом ф-те МГУ, 2000, - 152 с. Данное пособие является обобщением опыта преподавания курса программирования для студентов 1 и 2 курсов механико- математического факультета МГУ. Здесь предпринята попытка собрать и до некоторой степени систематизировать задачи, предлагавшиеся для самостоятельного решения во время семинарских занятий, лабораторных работ, на зачетах и экзаменах. Поскольку основной целью данного пособия является обучение программированию, то помимо формулировок задач здесь даются необходимые определения, обсуждаются идеи построения алгоритмов, для некоторых задач приводятся решения или отдельные фрагменты программ. Некоторые из приведенных задач совершенно конкретны — нужно выполнить ту или иную обработку данных по определенному алгоритму, другие наоборот, сформулированы нечетко и обрисовывают, скорее, круг задач и возможных подходов к решению. Отдавая отчет в том, что стиль программирования — неисчерпаемая тема тема для споров и дискуссий, авторы все же предлагают свои реализации как пример для подражания, надеясь, что при критическом отношении к приведенному коду читатель сможет вынести для себя много полезного из этой книги. Рецензент: Академик РАН Н. С. Бахвалов © В. Д. Валединский, А. А. Корнев, 2000 г. Оглавление Оглавление 1. Простейшие алгоритмические задачи 5 1. 1. Задачи на обработку последовательности 5 1. 2. Задачи на работу с массивами 12 1. 3. Поиск и сортировки 17 1. 4. Разбор чисел и битовые операции 24 1. 5. Задачи на обработку множества точек 26 1. 6. Алгоритмы работы с текстовыми строками 28 2. Простейшие вычислительные алгоритмы ... . 30 2. 1. Суммирование рядов и вычисление элементарных функций 32 2. 2. Численное интегрирование 35 2. 3. Работа с матрицами, решение систем линейных уравнений 37 2. 4. Решение нелинейных уравнений и систем 41 2. 5. Интерполяция и приближение функций 43 3. Базовые структуры данных 46 3. 1. Стек, дек, очередь 47 3. 2. Списки 55 3. 3. Деревья 63 3. 4. Графы 74 4. Контейнеры и множества 76 4. 1. Динамический массив 77 4. 2. Битовая реализация множества 78 4. 3. Хеш-реализации множеств 81 4. 4. Контейнеры 83 4. 5. Моделирование файловой системы 86 5. Словари, базы данных 92 5. 1. Толковый (двуязычный) словарь 92 3 Оглавление 5. 2. Модельная база данных 97 5. 2. 1. Модель базы данных "курс" 98 5. 2. 2. Модель базы данных "студент" 102 5. 2. 3. Модель базы данных "расписание" 103 5. 3. Модельная справочная система 113 5. 4. Гипертекстовая HTML-система 116 5. 5. Задачи со словами 117 6. Задачи на преобразование файлов 121 6. 1. Перекодировки, фильтры, преобразования текстов . 122 6. 2. Форматирование текстов 124 ] 6. 3. Сжатие и архивация 128 6. 3. 1.