Книжная полка Сохранить
Размер шрифта:
А
А
А
|  Шрифт:
Arial
Times
|  Интервал:
Стандартный
Средний
Большой
|  Цвет сайта:
Ц
Ц
Ц
Ц
Ц

Программирование

Покупка
Артикул: 769622.01.99
Доступ онлайн
120 ₽
В корзину
Учебное пособие содержит теоретический материал, изучение которого предусмотрено программами курсов «Программирование». Изложение ориентировано на использование языка программирования Паскаль. Рассмотрены алгоритмы, методы программирования и вопросы полного цикла разработки программ.
Зюзьков, В. М. Программирование : учебное пособие / В. М. Зюзьков. - Томск : Эль-Контент, 2013. - 186 с. - ISBN 978-5-4332-0141-5. - Текст : электронный. - URL: https://znanium.com/catalog/product/1845901 (дата обращения: 20.11.2026). – Режим доступа: по подписке.
Фрагмент текстового слоя документа размещен для индексирующих роботов
Министерство образования и науки Российской Федерации
ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)
В. М. Зюзьков
ПРОГРАММИРОВАНИЕ
Учебное пособие
Томск
«Эль Контент»
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


ОГЛАВЛЕНИЕ
Введение
Введение в информатику
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


Оглавление
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


Оглавление
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 рассматривается рекурсия. Можно, конечно, программировать на
Паскале и без рекурсии. Но, по крайней мере, необходимо осознавать, что вы
лишаетесь мощного и красивого инструмента программирования.
Теоретическому обучению должна сопутствовать практика программирования.
В частности, для контроля своего собственного понимания изученного вы должны
ответить на вопросы после каждой главы и выполнить приведенные там задания.


Соглашения, принятые в книге
И последнее замечание. Мы описываем стандарт Паскаля с некоторыми расширениями, принятыми в реализациях Паскаля: Турбо-Паскаль, Free-Pascal, PascalABC.
Соглашения, принятые в книге
Для улучшения восприятия материала в данной книге используются пиктограммы и специальное выделение важной информации.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает определение или новое понятие.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает внимание. Здесь выделена важная информация, требующая акцента на ней. Автор здесь может поделиться с читателем опытом, чтобы помочь избежать некоторых
ошибок.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает совет. В данном блоке можно указать
более простые или иные способы выполнения определенной задачи. Совет может касаться практического применения только что
изученного или содержать указания на то, как немного повысить
эффективность и значительно упростить выполнение некоторых
задач.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .
Эта пиктограмма означает пример. В данном блоке автор может привести практический пример для пояснения и разбора основных моментов, отраженных в теоретическом материале.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Контрольные вопросы по главе
. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Рекомендуемая литература к главе
. . .. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .


Глава 1
ВВЕДЕНИЕ В ИНФОРМАТИКУ
1.1 Информация и ее представление
Информатика — это наука и техника, связанные с машинной
обработкой, хранением и передачей информации. Цель состоит
в разработке способов решения задач информационной обработки на вычислительных машинах (компьютерах), а также в разработке, организации и эксплуатации вычислительных систем.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
В информатике информация понимается как абстрактное значение выражений,
графических изображений, указаний (операторов) и высказываний.
Мы различаем в связи с информацией:
• ее представление или изображение (внешняя форма);
• ее значение (собственно «абстрактная» информация);
• ее отношение к реальному миру (связь абстрактной информации с действительностью).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Информацией называют абстрактное содержание («содержательное значение», «семантика») какого-либо высказывания, описания, указания, сообщения или известия. Внешнюю форму изображения называют представлением (конкретная форма сообщения).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Виды представлений:
• условные знаки («сигналы»),
• произносимые слова («акустическое представление»),


1.2 Понятие алгоритма
• рисунки (графическое представление, «пиктограммы», «иконки»),
• последовательность символов («слова», «текст»), и т. д.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Переход (часто только воображаемый, мыслимый) от представления к абстрактной информации, т. е. к значению представления,
называют интерпретацией.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Только в том случае, когда существуют единые, согласованные интерпретации,
системы представления могут использоваться для обмена информацией.
1.2 Понятие алгоритма
Под алгоритмом понимается способ преобразования представления информации. Слово algorithm — произошло от имени аль-Хорезми — автора известного арабского учебника по математике.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Алгоритм — свод конечного числа правил, задающих последовательность выполнения операций при решении той или иной специфической задачи.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Алгоритмы типичным образом решают не только частные задачи, но и классы
задач. Подлежащие решению частные задачи, выделяемые по мере надобности
из рассматриваемого класса, определяются с помощью параметров. Параметры
играют роль исходных данных для алгоритма.
Пять важных особенностей алгоритма:
• Конечность (финитность). Алгоритм должен всегда заканчиваться после
конечного числа шагов.
• Определенность. Каждый шаг алгоритма должен быть точно определен.
• Ввод. Алгоритм имеет некоторое (быть может, равное нулю) число входных
данных, т. е. величин, заданных ему до начала работы.
• Вывод. Алгоритм имеет одну или несколько выходных величин, т. е. величин, имеющих вполне определенное отношение к входным данным.
• Эффективность. Это означает, что все операции, которые необходимо произвести в алгоритме, должны быть достаточно простыми, чтобы их можно
было в принципе выполнить точно и за конечный отрезок времени с помощью карандаша и бумаги.
Алгоритм должен быть практичным и хорошим с эстетической точки зрения.
Для алгоритмов важно различать следующие аспекты:
• постановку задачи, которая должна быть разрешена с помощью алгоритма;
• специфичный способ, каким решается задача, при этом для алгоритма различают:


Глава 1. Введение в информатику
а) элементарные шаги обработки, которые имеются в распоряжении;
б) описание выбора отдельных подлежащих выполнению шагов.
Для алгоритмически разрешимой постановки задачи всегда имеется много различных способов ее решения, т. е. различных алгоритмов.
1.2.1 Примеры неформальных описаний алгоритмов
. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .
1. Арифметические операции над десятичными числами.
В начальной школе мы на неформальном уровне изучаем правила вычисления
суммы двух чисел и умножения («вычисления в столбик»).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .
2. Алгоритм Евклида для вычисления наибольшего делителя (НОД).
Постановка задачи. Пусть даны два положительных целых числа a и b, надо
найти наибольший общий делитель НОД(a, b) чисел a и b.
2а. Первая версия алгоритма:
• если a = b, то справедливо НОД(a, b) = a;
• если a < b, то применяем алгоритм НОД к числам a и b −a;
• если b < a, то применяем алгоритм НОД к числам a −b и b.
Используется математическое свойство: для любых положительных целых чисел x и y если x < y, то НОД(x, y) = НОД(y −x, x).
2б. Вторая версия алгоритма:
1) если a < b, то меняем местами значения (так, чтобы стало a ⩾b);
2) делим a на b, пусть r — остаток от деления (имеем a ⩾b > r ⩾0);
3) если r = 0, то b — выход;
4) положить (заменить) a на b, b на r и вернуться к шагу 2.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .
3. Сортировка колоды карт.
Постановка задачи. Имеется колода карт. Пусть на каждой карте зафиксировано одно натуральное число (ради простоты будем считать, что все числа попарно


Доступ онлайн
120 ₽
В корзину