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

Москва
Лаборатория знаний
2020

ПЕДАГОГИЧЕСКОЕ  ОБРАЗОВАНИЕ

Н. А. Давыдова
Е. В. Боровская

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

 4-е издание, электронное

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

УДК 004.4
ББК 32.973-018
Д13

С е р и я о с н о в а н а в 2007 г.
Давыдова Н. А.
Д13
Программирование
:
учебное
пособие
/
Н. А. Давыдова,
Е. В. Боровская. — 4-е изд., электрон. — М. : Лаборатория знаний,
2020. — 241 с. — (Педагогическое образование). — Систем. требования: Adobe Reader XI ; экран 10".— Загл. с титул. экрана. —
Текст : электронный.
ISBN 978-5-00101-788-2
В книге описаны теоретические положения и принципы, связанные
с методами разработки программ, критерии качества программ и этапы проектирования объектно-ориентированного программного продукта,
а также наиболее широко используемые алгоритмы поиска и сортировки
информации. Книга знакомит читателей с основными понятиями языков
программирования, основами программирования в Object Pascal и принципами визуального программирования, в том числе при работе с базами
данных и динамическими структурами.
Для студентов и преподавателей педагогических вузов, учителей общеобразовательных школ, гимназий и лицеев.
УДК 004.4
ББК 32.973-018

Деривативное издание на основе печатного аналога: Программирование : учебное пособие / Н. А. Давыдова, Е. В. Боровская. — М. : БИНОМ.
Лаборатория знаний, 2009. — 238 с. : ил. — (Педагогическое образование). —
ISBN 978-5-94774-481-1.

В соответствии со ст. 1299 и 1301 ГК РФ при устранении ограничений,
установленных
техническими
средствами
защиты
авторских
прав,
правообладатель вправе требовать от нарушителя возмещения убытков
или выплаты компенсации

ISBN 978-5-00101-788-2
c○ Лаборатория знаний, 2015

2

Глава 1

Основные понятия

1.1.
Алгоритм и его свойства

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

Глава 1. Основные понятия

Рис. 1.1. Процесс решения задачи исполнителем

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

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

Для выполнения любой работы или решения поставленной задачи
исполнитель на входе получает алгоритм и исходные данные, а на выход выдает требуемые результаты (рис. 1.1) [10].

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

1)Данное определение алгоритма является интуитивным, нестрогим. Более строгое
определение дается в курсе «Теория алгоритмов».

1.1. Алгоритм и его свойства
5

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

Рис. 1.2. Графическая
форма представления
алгоритма

Алгоритм, составленный для
некоторого
исполнителя, можно представить различными
способами: с помощью графического или словесного описания, в виде таблицы, последовательности формул или записи на алгоритмическом языке (языке программирования) [6, 9, 12].
Приведем пример представления различными способами алгоритма вычисления значения S — площади круга радиуса R.
1. Словесная форма представления
(применима для всех типов алгоритмов):
1) прочесть значение R;
2) умножить значение R на 3,14;
3) умножить
результат
второго
действия
на значение R;
4) записать полученный в предыдущей команде результат как значение S.

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

Глава 1. Основные понятия

их естественного следования друг за другом независимо от какихлибо условий (табл. 1.1).

Таблица 1.1
Табличная форма представления алгоритма

R, см
3,14*R, см
3,14*R*R, см

1
3,14
3,14

2
6,28
12,56

1.2.
Этапы решения задач на компьютере

Человек использует компьютер для решения разнообразных информационных задач: работы с текстами, создания графических
изображений, получения справок (запросов) из баз данных, табличных расчетов, решения математических задач, расчетов технических
конструкций и многого другого. Часто для решения поставленной
задачи на компьютере уже имеется готовая программа, которой можно
воспользоваться. Тогда, исходя из условия задачи, пользователь решает для себя вопрос — каким программным средством лучше всего
воспользоваться. Но если готовой программы для решения задачи нет,
то необходимо создать для этого свою, новую программу.
Можно ли указать некую общую для различных прикладных задач
последовательность действий, если для их решения предполагается
использовать компьютер?
Часто
задача,
которую
требуется
решить,
сформулирована
не на математическом языке, а, например, в терминах физики или экономики. Тогда для решения на компьютере ее сначала нужно привести
к форме математической задачи, а уже потом программировать.
Таким образом, при составлении программы процесс решения
задачи на компьютере включает в себя следующие основные этапы
[6, 9, 12].

1. Постановка задачи — точная формулировка ее условий и целей решения. На этом этапе должно быть четко определено, что дано и
что требуется найти. Если рассматривается конкретная задача, то под
постановкой этой задачи понимают ответы на два вопроса: какие
исходные данные известны и что требуется определить. Если задача —
обобщенная, то при постановке этой задачи также понадобится ответ
на третий вопрос: какие данные в ней допустимы. Таким образом,
постановка задачи включает в себя: сбор информации о задаче,
формулировку условия задачи, определение конечных целей решения

1.2. Этапы решения задач на компьютере
7

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

2. Выбор метода решения — построение математической модели (формулы, уравнения и т. д.). Математическая модель — это
система математических соотношений — формул, уравнений, неравенств и т. д., отражающих существенные свойства объекта или явления. Она всегда основана на некоторых упрощениях, поэтому
данный этап весьма ответственен: неправильно выбранная модель
с неизбежностью приводит к неверным результатам. Следует отметить, что при построении математических моделей далеко не всегда
удается найти формулы, явно выражающие искомые величины через
исходные данные. В таких случаях используются математические
методы, позволяющие дать ответы с той или иной степенью точности.
При большом количестве параметров, ограничений, возможных вариантов исходных данных модель явления может иметь очень сложное
математическое описание (правда, реальное явление — еще сложнее),
поэтому построение математической модели может вызвать необходимость упрощения требований задачи. Нужно выявить наиболее
существенные свойства и закономерности объекта, явления или процесса, внутренние связи, роль отдельных характеристик, пренебрегая
менее важными факторами. Таким образом, создавая математическую модель для решения задачи, нужно: выделить предположения,
на которых будет основываться математическая модель; определить,
что считать исходными данными, а что — результатами; записать
математические соотношения, связывающие результаты с исходными
данными.

3. Разработка алгоритма по выбранному методу решения.
Здесь необходимо четко зафиксировать, какие величины являются аргументами, а какие — результатами алгоритма, а также определить
тип этих величин. Затем строится алгоритм, который позволяет определять значения результатов при различных значениях аргументов.
Построенный алгоритм записывается в какой-либо форме (например,
в виде блок-схемы). Таким образом, разработка алгоритма включает
в себя выбор метода проектирования алгоритма, выбор формы записи
алгоритма (блок-схема, псевдокод и др.), выбор метода тестирования
и конкретных тестов, проектирование самого алгоритма.

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

Глава 1. Основные понятия

граммирование включает в себя следующие работы: выбор языка программирования, уточнение способов организации данных, собственно
запись алгоритма на выбранном языке программирования.

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

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

Рассмотрим процесс решения задачи на конкретном примере
решения квадратного уравнения Ax2 + Bx + C = 0.
1. Постановка задачи. На первом этапе строится описательная
информационная модель процесса.

Д а н о: A, B, C— коэффициенты уравнения.
Т р е б у е т с я
о п р е д е л и т ь: X1, X2 — корни уравнения.

2. Выбор метода решения. На втором этапе создается формализованная модель, т. е. описательная информационная модель записывается с помощью какого-либо формального языка (в данном случае —
с помощью языка математики):

x1 = — B—
√

B2— 4AC
2A
,
x2 = — B +
√

B2— 4AC
2A
.

1.3. История языков программирования
9

3. Разработка алгоритма по выбранному методу решения. Далее
необходимо разработать и представить в какой-либо форме алгоритм — например, построить блок-схему.

4. Запись алгоритма на языке программирования. На этом этапе
осуществляется создание компьютерной модели: составляется программа на языке программирования.

5. Отладка и тестирование программы на компьютере. Данный
этап исследования информационной модели состоит в проведении
компьютерного эксперимента. Если компьютерная модель существует
в виде программы на одном из языков программирования, то ее нужно
запустить на выполнение и получить результаты. Например:

A = 1
B = 2
C = −3
О т в е т :
X1 = 1
X2 = −3.
A = 1
B = −2
C = 1
О т в е т :
X1,2 = 1.
A = 1
B = 2
C = 3
О т в е т :
корней нет.

6. Анализ полученных результатов. Выполняется анализ полученных результатов и (при необходимости) корректировка исследуемой модели.

1.3.
История языков программирования

Прогресс в сфере вычислительной техники и информационных
и коммуникационных технологий предопределил появление разнообразных знаковых систем для записи алгоритмов — языков программирования.
Язык программирования служит двум взаимосвязанным целям:
предоставляет программисту аппарат для задания действий, которые
должны быть выполнены компьютером, и формирует концепции,
которыми пользуется программист, продумывая будущий алгоритм.
Первой цели идеально отвечает язык, который настолько «близок
к ЭВМ», что всеми основными машинными объектами можно легко
и просто оперировать достаточно очевидным для программиста
образом. Второй же цели идеально отвечает язык, который настолько
близок к решаемой задаче, что концепции ее решения можно выражать прямо и коротко.
Вначале рассмотрим классификацию языков программирования
по близости языка к аппаратному обеспечению (рис. 1.3) [14, 18].
Первые
языки
программирования
появились
сравнительно
недавно. Как и следовало ожидать, они (как и первые ЭВМ)
были
довольно
примитивны
и
ориентированы
на
различные
вычисления — как на чисто теоретические научные расчеты (прежде

Глава 1. Основные понятия

Рис. 1.3. Классификация языков программирования

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

Машинно-ориентированные языки программирования — это
языки, наборы операторов и изобразительные средства которых
существенно зависят от особенностей ЭВМ (ее системы команд,
структуры памяти и т. д.).

Машинно-ориентированные языки обеспечивают:
• высокое качество создаваемых программ (компактность и скорость выполнения);
• возможность максимально полного использования конкретных
аппаратных ресурсов;
• предсказуемость объектного кода и запросов на выделение памяти.

Недостатки машинно-ориентированных языков:
• для составления эффективных программ необходимо знать систему команд и особенности функционирования конкретной ЭВМ;
• процесс составления программ очень трудоемок, плохо защищен
от появления ошибок;
• низкая скорость программирования;
• невозможность
непосредственного
использования
программы
на ЭВМ других типов.