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

Министерство образования и науки Российской Федерации

ТОМСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ
СИСТЕМ УПРАВЛЕНИЯ И РАДИОЭЛЕКТРОНИКИ (ТУСУР)

В. М. Зюзьков

ПРОГРАММИРОВАНИЕ

Учебное пособие

Томск
«Эль Контент»
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

Оглавление

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 — произошло от имени аль-Хорезми — автора известного арабского учебника по математике.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Алгоритм — свод конечного числа правил, задающих последовательность выполнения операций при решении той или иной специфической задачи.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Алгоритмы типичным образом решают не только частные задачи, но и классы
задач. Подлежащие решению частные задачи, выделяемые по мере надобности
из рассматриваемого класса, определяются с помощью параметров. Параметры
играют роль исходных данных для алгоритма.

Пять важных особенностей алгоритма:
• Конечность (финитность). Алгоритм должен всегда заканчиваться после
конечного числа шагов.

• Определенность. Каждый шаг алгоритма должен быть точно определен.

• Ввод. Алгоритм имеет некоторое (быть может, равное нулю) число входных
данных, т. е. величин, заданных ему до начала работы.

• Вывод. Алгоритм имеет одну или несколько выходных величин, т. е. величин, имеющих вполне определенное отношение к входным данным.

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

Алгоритм должен быть практичным и хорошим с эстетической точки зрения.
Для алгоритмов важно различать следующие аспекты:
• постановку задачи, которая должна быть разрешена с помощью алгоритма;

• специфичный способ, каким решается задача, при этом для алгоритма различают:

Глава 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. Сортировка колоды карт.
Постановка задачи. Имеется колода карт. Пусть на каждой карте зафиксировано одно натуральное число (ради простоты будем считать, что все числа попарно