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

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

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

В. М. Зюзьков

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

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

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

1.2 Понятие алгоритма
11

различны). Требуется отсортировать, т. е. упорядочить, колоду карт так, чтобы зафиксированные на картах числа образовывали монотонную (возрастающую или
убывающую) последовательность.

3а. Сортировка путем предсортировки и слияния.
Заданная колода x сортируется с помощью следующего предписания:
• если x пуста или содержит одну карту, то x отсортирована;

• если x содержит более одной карты, то x разделить на две непустые колоды;
отсортировать каждую из них и затем слить (объединить) эти колоды в одну
отсортированную колоду.

3б. Сортировка путем вставок.
Заданная колода сортируется по убыванию с помощью следующего алгоритма,
который в соответствующее место отсортированной колоды y вставляет по очереди
карты, выбираемые из неотсортированной колоды x (процесс начинается с пустой
колоды y):

• если колода x пуста, то y — искомая отсортированная колода;

• если x не пуста, то из x берется любая карта и вставляется в подходящее
место колоды y, так, чтобы в результате колода y осталась отсортированной.

Этот алгоритм применяется к уменьшающейся колоде x и увеличивающейся
колоде y.

3в. Сортировка путем выбора.
Заданная колода x сортируется по убыванию по следующему алгоритму, который последовательно выбирает из x «наибольшую» карту и добавляет ее в конец
колоды y (процесс начинается с пустой колоды y).

Пусть даны две колоды x и y. Пусть колода y отсортирована по убыванию,
и пусть все карты из y больше любых карт из x. Колода x всортировывается в y по
следующему предписанию:

• если x пуста, то y — искомая отсортированная колода;

• если x не пуста, то из x выбирается «наибольшая» карта и добавляется в конец y.

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

• если в x не встречается ни одной неупорядоченной пары соседних карт, то
колода x отсортирована и тем самым является искомой колодой.

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

Глава 1. Введение в информатику

. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .

4. Алгоритм вычисления дроби (a + b)/(a − b).
Сначала вычисляем (используя алгоритмы сложения и вычитания) значения
выражений a + b и a − b (все равно, последовательно или одновременно), а потом
образуем частное от деления полученных результатов (используя алгоритм деления).
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .

5. Алгоритм, распознающий, можно ли получить последовательность знаков
a из последовательности знаков b посредством вычеркивания некоторых знаков.

Если a — пустая последовательность знаков, то ответом будет «да». В противном случае нужно посмотреть, не пуста ли последовательность b. Если это так,
то ответом будет «нет». Иначе нужно сравнить первый знак последовательности a
с первым знаком последовательности b. Если они совпадают, то надо снова применить тот же алгоритм к остатку последовательности a и остатку последовательности b. В противном случае нужно снова применить тот же алгоритм к исходной
последовательности a и остатку последовательности b.

Этот алгоритм выдает двузначный результат, «да» или «нет», т. е. он является алгоритмом распознавания свойства «быть частью данной последовательности
знаков».
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

Классические элементы описания алгоритмов:
• выполнение элементарных шагов;

• разветвление по условию;

• повторение и рекурсия.

1.3 Вычислительные структуры
13

1.3 Вычислительные структуры

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

. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .
Представление N вместе с сопоставленной ему информацией I
называется объектом (элементом данных), а во множественном
числе — данными. Итак, объект есть пара (N, I), при этом информацию I называют значением объекта, а представление N —
обозначением объекта.
. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . .

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

. . .. . . . . . . . . . . . . . . . . . . . . .
Пример
. . .. . . . . . . . . . . . . . . . . . . . . .

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

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

При составлении программы для решения какой-либо задачи необходимо сначала выделить подходящие вычислительные структуры, а затем решить, как эти
структуры представлять в языке программирования.