программирование тусур. Программирование учебное пособие. Учебное пособие Томск Эль Контент
 Скачать 0.93 Mb.
|
|
Министерство образования и науки Российской Федерации ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР) В. М. Зюзьков ПРОГРАММИРОВАНИЕ Учебное пособие Томск «Эль Контент» 2013 УДК 004.42(075.8) ББК 32.973.26-018я73 З-981 Рецензенты: Старченко А. В., докт. физ.-мат. наук, профессор, зав. кафедрой вычислительной математики и компьютерного моделирования Национального исследовательского Томского государственного университета; Потапова Е. А., старший преподаватель кафедры компьютерных систем в управлении и проектировании ТУСУРа. Зюзьков В. М. З-981 Программирование : учебное пособие / В. М. Зюзьков. — Томск : Эль Контент, 2013. — 186 с. ISBN 978-5-4332-0141-5 Учебное пособие содержит теоретический материал, изучение которо- го предусмотрено программами курсов «Программирование». Изложение ориентировано на использование языка программирования Паскаль. Рас- смотрены алгоритмы, методы программирования и вопросы полного цикла разработки программ. УДК 004.42(075.8) ББК 32.973.26-018я73 ISBN 978-5-4332-0141-5 © Зюзьков В. М., 2013 © Оформление. ООО «Эль Контент», 2013 ОГЛАВЛЕНИЕ Введение 6 1 Введение в информатику 8 1.1 Информация и ее представление . . . . . . . . . . . . . . . . . . . . . . . 8 1.2 Понятие алгоритма . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9 1.2.1 Примеры неформальных описаний алгоритмов . . . . . . . . . 10 1.3 Вычислительные структуры . . . . . . . . . . . . . . . . . . . . . . . . . 13 1.3.1 Основные вычислительные структуры . . . . . . . . . . . . . . 14 1.4 Алгоритмические языки . . . . . . . . . . . . . . . . . . . . . . . . . . . . 15 1.5 Описание синтаксиса алгоритмических языков . . . . . . . . . . . . . . 16 1.6 Семантика программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18 1.7 Трансляция и выполнение . . . . . . . . . . . . . . . . . . . . . . . . . . . 19 1.8 Компьютеры фон Неймана . . . . . . . . . . . . . . . . . . . . . . . . . . 21 2 Азы языка Паскаль 24 2.1 Основные понятия языка Паскаль . . . . . . . . . . . . . . . . . . . . . . 24 2.1.1 Алфавит языка Паскаль . . . . . . . . . . . . . . . . . . . . . . . 24 2.1.2 Переменные . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 25 2.1.3 Операторы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.4 Описания данных . . . . . . . . . . . . . . . . . . . . . . . . . . . 26 2.1.5 Правила записи текста программы . . . . . . . . . . . . . . . . . 28 2.1.6 Система типов языка . . . . . . . . . . . . . . . . . . . . . . . . . 28 2.2 Основные вычислительные структуры в Паскале . . . . . . . . . . . . 30 2.2.1 Целые типы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30 2.2.2 Вещественные типы . . . . . . . . . . . . . . . . . . . . . . . . . . 31 2.2.3 Символьный (литерный) тип . . . . . . . . . . . . . . . . . . . . 33 2.2.4 Булевский (логический) тип . . . . . . . . . . . . . . . . . . . . . 34 2.3 Выражения и основные операторы . . . . . . . . . . . . . . . . . . . . . 34 2.3.1 Выражения . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 34 2.3.2 Оператор присваивания . . . . . . . . . . . . . . . . . . . . . . . . 36 2.3.3 Ввод-вывод . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38 2.3.4 Последовательное выполнение и составной оператор . . . . . 39 2.3.5 Условный оператор . . . . . . . . . . . . . . . . . . . . . . . . . . 39 2.3.6 Оператор цикла с предусловием . . . . . . . . . . . . . . . . . . 41 2.3.7 Оператор цикла с постусловием . . . . . . . . . . . . . . . . . . 42 2.3.8 Оператор цикла с параметром . . . . . . . . . . . . . . . . . . . . 43 2.4 Пустой оператор и ограниченные типы . . . . . . . . . . . . . . . . . . 45 4 Оглавление 2.5 Функции . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 47 2.6 Примеры программ без массивов . . . . . . . . . . . . . . . . . . . . . . 49 3 Процедурное программирование 55 3.1 Синтаксис подпрограмм . . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 3.1.1 Понятие подпрограммы . . . . . . . . . . . . . . . . . . . . . . . 55 3.1.2 Общая структура подпрограмм . . . . . . . . . . . . . . . . . . . 56 3.1.3 Тело подпрограммы. Области действия имен . . . . . . . . . . 57 3.2 Семантика подпрограмм . . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 3.2.1 Использование процедур и функций . . . . . . . . . . . . . . . . 58 3.2.2 Механизм параметров . . . . . . . . . . . . . . . . . . . . . . . . . 60 3.2.3 Побочный эффект . . . . . . . . . . . . . . . . . . . . . . . . . . . 64 3.2.4 Распределение памяти для переменных . . . . . . . . . . . . . . 64 4 Технология программирования 67 4.1 Оператор перехода . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 67 4.2 Структурное программирование . . . . . . . . . . . . . . . . . . . . . . . 68 4.3 Решение задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 70 4.4 Разработка программы . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 72 4.4.1 Метод пошаговой детализации . . . . . . . . . . . . . . . . . . . 73 4.4.2 Способы фиксирования результатов проектирования . . . . . 74 4.4.3 Пример разработки . . . . . . . . . . . . . . . . . . . . . . . . . . 77 4.5 Стиль программирования . . . . . . . . . . . . . . . . . . . . . . . . . . . 83 4.6 Тестирование и отладка . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.6.1 Тестирование . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 87 4.6.2 Отладка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 89 5 Массивы и строки 92 5.1 Регулярные типы данных (массивы) . . . . . . . . . . . . . . . . . . . . 92 5.1.1 Определение регулярного типа . . . . . . . . . . . . . . . . . . . 92 5.1.2 Примеры программ для работы с массивами . . . . . . . . . . 95 5.2 Строковый тип . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 98 5.2.1 Определение строкового типа . . . . . . . . . . . . . . . . . . . . 98 5.2.2 Строковые операции . . . . . . . . . . . . . . . . . . . . . . . . . 99 5.2.3 Стандартные процедуры и функции . . . . . . . . . . . . . . . . 101 5.3 Сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 5.3.1 Постановка задачи . . . . . . . . . . . . . . . . . . . . . . . . . . . 103 6 Перечислимый тип, множества, файлы 109 6.1 Перечислимый тип . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 109 6.1.1 Определение перечислимого типа . . . . . . . . . . . . . . . . . 109 6.1.2 Оператор варианта . . . . . . . . . . . . . . . . . . . . . . . . . . . 111 6.2 Множественный тип . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112 6.2.1 Определение множественного типа . . . . . . . . . . . . . . . . 112 6.2.2 Операции с множествами . . . . . . . . . . . . . . . . . . . . . . 114 6.3 Файловые типы и ввод-вывод . . . . . . . . . . . . . . . . . . . . . . . . 117 6.3.1 Файловые переменные и типы . . . . . . . . . . . . . . . . . . . 117 Оглавление 5 6.3.2 Установочные и завершающие операции над файлами . . . . 118 6.3.3 Операции ввода-вывода . . . . . . . . . . . . . . . . . . . . . . . 119 6.3.4 Текстовые файлы . . . . . . . . . . . . . . . . . . . . . . . . . . . . 119 6.3.5 Примеры работы с файлами . . . . . . . . . . . . . . . . . . . . . 120 7 Рекурсия 124 7.1 Понятие рекурсии . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 124 7.2 Как приходят к рекурсивным подпрограммам? . . . . . . . . . . . . . . 128 7.2.1 Органически рекурсивные определения . . . . . . . . . . . . . . 128 7.2.2 Извлечение рекурсии из постановки задачи . . . . . . . . . . . 128 7.2.3 Вложение . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 129 7.2.4 Использование характеристических свойств . . . . . . . . . . . 130 7.2.5 Разделяй и властвуй . . . . . . . . . . . . . . . . . . . . . . . . . . 130 7.3 Рекурсия и итерация. Метод накапливающего параметра . . . . . . . 131 7.4 Рекурсия в своем блеске и великолепии . . . . . . . . . . . . . . . . . . 133 7.4.1 Ханойские башни . . . . . . . . . . . . . . . . . . . . . . . . . . . 133 7.4.2 Поиск маршрута — алгоритм с возвратом . . . . . . . . . . . . . 135 7.4.3 Быстрая сортировка . . . . . . . . . . . . . . . . . . . . . . . . . . 136 8 Записи и динамические структуры данных 139 8.1 Записи . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139 8.1.1 Определение комбинированных типов . . . . . . . . . . . . . . 139 8.1.2 Оператор над записями with (оператор присоединения) . . . . 141 8.2 Динамические структуры данных . . . . . . . . . . . . . . . . . . . . . . 143 8.2.1 Ссылочный тип . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 143 8.2.2 Статические и динамические переменные . . . . . . . . . . . . 145 8.2.3 Линейные списки . . . . . . . . . . . . . . . . . . . . . . . . . . . 146 8.2.4 Проблема потерянных ссылок . . . . . . . . . . . . . . . . . . . . 150 8.2.5 Списки специального вида . . . . . . . . . . . . . . . . . . . . . . 151 8.2.6 Стеки и очереди . . . . . . . . . . . . . . . . . . . . . . . . . . . . 153 8.2.7 Деревья . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 155 9 Модули и графика 161 9.1 Модули . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 161 9.1.1 Модульное программирование . . . . . . . . . . . . . . . . . . . 161 9.1.2 Стандартные модули . . . . . . . . . . . . . . . . . . . . . . . . . 164 9.2 Графическое программирование . . . . . . . . . . . . . . . . . . . . . . . 166 9.2.1 Аппаратная и программная поддержка графики . . . . . . . . . 166 9.2.2 Инициализация графики . . . . . . . . . . . . . . . . . . . . . . . 167 9.2.3 Базовые процедуры и функции . . . . . . . . . . . . . . . . . . . 170 9.2.4 Построение графических фигур . . . . . . . . . . . . . . . . . . 174 9.2.5 Простые анимационные алгоритмы . . . . . . . . . . . . . . . . 179 Заключение 181 Глоссарий 182 ВВЕДЕНИЕ Знания достигаются не быстрым бегом, а медленной ходьбой. Томас Бабингтон Маколей (1800–1859) Предмет программирования, на наш взгляд, содержит много материала, не свя- занного с конкретным языком, на котором пишутся программы. Такие знания, несомненно, являются фундаментальными. Изложение материала построено по принципу от общего к частному. Основные понятия программирования вводятся в качестве исходных, вместо того чтобы выводить их из особенностей компьютера. Такое изложение не зависит от случайностей синтаксиса и семантики программи- рования. Но цель учебного пособия — научить практическому программированию, по- этому и выбор языка программирования важен. В первую очередь язык програм- мирования должен быть удобен для первоначального знакомства с программиро- ванием и хорош для обучения программированию. Именно для такой цели был и создан элегантный язык Паскаль. Остановимся на нескольких темах, рассматриваемых в пособии. Вторая глава «Введение в информатику» посвящена основным понятиям программирования, таким как алгоритмы, вычислительные структуры и программы. Содержание этой главы не зависит от конкретного языка программирования. После изучения главы 3 «Азы языка Паскаль» уже возможно создание неболь- ших и достаточно простых программ на Паскале. Дальнейшие главы расширяют наше знание Паскаля. Но преподавание основ программирования не ограничива- ется изучением синтаксиса и семантики программ. Вместе с освоением языковых конструкций обучаемый должен получить первые навыки разработки программ, трактуемые как процесс систематического и вполне познаваемого перехода от неал- горитмической постановки задачи к эффективной программе ее решения. Методо- логия такого перехода излагается в главе 5 «Технология программирования». В главе 8 рассматривается рекурсия. Можно, конечно, программировать на Паскале и без рекурсии. Но, по крайней мере, необходимо осознавать, что вы лишаетесь мощного и красивого инструмента программирования. Теоретическому обучению должна сопутствовать практика программирования. В частности, для контроля своего собственного понимания изученного вы должны ответить на вопросы после каждой главы и выполнить приведенные там задания. Соглашения, принятые в книге 7 И последнее замечание. Мы описываем стандарт Паскаля с некоторыми расши- рениями, принятыми в реализациях Паскаля: Турбо-Паскаль, Free-Pascal, PascalABC. Соглашения, принятые в книге Для улучшения восприятия материала в данной книге используются пикто- граммы и специальное выделение важной информации. Эта пиктограмма означает определение или новое понятие. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Эта пиктограмма означает внимание. Здесь выделена важная ин- формация, требующая акцента на ней. Автор здесь может поде- литься с читателем опытом, чтобы помочь избежать некоторых ошибок. Эта пиктограмма означает совет. В данном блоке можно указать более простые или иные способы выполнения определенной за- дачи. Совет может касаться практического применения только что изученного или содержать указания на то, как немного повысить эффективность и значительно упростить выполнение некоторых задач. Пример Эта пиктограмма означает пример. В данном блоке автор может привести прак- тический пример для пояснения и разбора основных моментов, отраженных в тео- ретическом материале. Контрольные вопросы по главе Рекомендуемая литература к главе Глава 1 ВВЕДЕНИЕ В ИНФОРМАТИКУ 1.1 Информация и ее представление Информатика — это наука и техника, связанные с машинной обработкой, хранением и передачей информации. Цель состоит в разработке способов решения задач информационной обработ- ки на вычислительных машинах (компьютерах), а также в разра- ботке, организации и эксплуатации вычислительных систем. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . В информатике информация понимается как абстрактное значение выражений, графических изображений, указаний (операторов) и высказываний. Мы различаем в связи с информацией: • ее представление или изображение (внешняя форма); • ее значение (собственно «абстрактная» информация); • ее отношение к реальному миру (связь абстрактной информации с действи- тельностью). Информацией называют абстрактное содержание («содержа- тельное значение», «семантика») какого-либо высказывания, опи- сания, указания, сообщения или известия. Внешнюю форму изобра- жения называют представлением (конкретная форма сообщения). . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Виды представлений: • условные знаки («сигналы»), • произносимые слова («акустическое представление»), 1.2 Понятие алгоритма 9 • рисунки (графическое представление, «пиктограммы», «иконки»), • последовательность символов («слова», «текст»), и т. д. Переход (часто только воображаемый, мыслимый) от представ- ления к абстрактной информации, т. е. к значению представления, называют интерпретацией. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Только в том случае, когда существуют единые, согласованные интерпретации, системы представления могут использоваться для обмена информацией. 1.2 Понятие алгоритма Под алгоритмом понимается способ преобразования представления информа- ции. Слово algorithm — произошло от имени аль-Хорезми — автора известного араб- ского учебника по математике. Алгоритм — свод конечного числа правил, задающих последова- тельность выполнения операций при решении той или иной спе- цифической задачи. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . Алгоритмы типичным образом решают не только частные задачи, но и классы задач. Подлежащие решению частные задачи, выделяемые по мере надобности из рассматриваемого класса, определяются с помощью параметров. Параметры играют роль исходных данных для алгоритма. Пять важных особенностей алгоритма: • Конечность (финитность). Алгоритм должен всегда заканчиваться после конечного числа шагов. • Определенность. Каждый шаг алгоритма должен быть точно определен. • Ввод. Алгоритм имеет некоторое (быть может, равное нулю) число входных данных, т. е. величин, заданных ему до начала работы. • Вывод. Алгоритм имеет одну или несколько выходных величин, т. е. вели- чин, имеющих вполне определенное отношение к входным данным. • Эффективность. Это означает, что все операции, которые необходимо про- извести в алгоритме, должны быть достаточно простыми, чтобы их можно было в принципе выполнить точно и за конечный отрезок времени с помо- щью карандаша и бумаги. Алгоритм должен быть практичным и хорошим с эстетической точки зрения. Для алгоритмов важно различать следующие аспекты: • постановку задачи, которая должна быть разрешена с помощью алгоритма; • специфичный способ, каким решается задача, при этом для алгоритма раз- личают: 10 |