Алгоритмы и программы. Язык С++ : учебное пособие для СПО [Елена Александровна Конова] (pdf) читать онлайн

Е. А. КОНОВА,
Г. А. ПОЛЛАК

АЛГОРИТМЫ
И ПРОГРАММЫ.
ЯЗЫК С++
УЧЕБНОЕ ПОСОБИЕ
ИЗДАНИЕ ТРЕТЬЕ, СТЕРЕОТИПНОЕ

САНКТПЕТЕРБУРГ
МОСКВА•КРАСНОДАР
2022

УДК 004.42
ББК 32.973.26018.1я723
К 64

Конова Е. А. Алгоритмы и программы. Язык С++ : учеб
ное пособие для СПО / Е. А. Конова, Г. А. Поллак. — 3е
изд., стер. — СанктПетербург : Лань, 2022. — 384 с. : ил. —
Текст : непосредственный.

ISBN 9785507449255
При изложении материала авторы используют методику обучения
от алгоритмов к программам, поэтому вначале излагаются сведения об
алгоритмах с примерами реализации типовых алгоритмов. Изучение
основ языка программирования С++ опирается на полученные знания,
приведены примеры кода на данном языке. Примеры можно решать в
любой среде разработчика, поддерживающей язык С++, но авторами
примеры отлажены в Visual Studio 2013. Коды программ соответствуют
стандарту С++ 11 (ISO/IEC 14882:2011), разработаны в консольных
приложениях на основе шаблона «Пустой проект». В практикуме пред
лагаются как задачи, использующие типовые алгоритмы, так и содержа
тельные, для которых приведено только вербальное описание. В типо
вых задачах оттачиваются навыки кодирования, в содержательных
требуются построение инфологической модели и выбор алгоритмов
решения.
Соответствует современным требованиям Федерального государст
венного образовательного стандарта среднего профессионального обра
зования и профессиональным квалификационным требованиям.
Пособие предназначено для студентов среднего профессионального
образования, обучающихся по направлению подготовки «Прикладная
информатика», может быть рекомендовано для самостоятельного изуче
ния, так как не требует предварительных знаний о языках программи
рования.

УДК 004.42
ББК 32.973.26018.1я723

Обложка
П. И. ПОЛЯКОВА

© Издательство «Лань», 2022
© Е. А. Конова, Г. А. Поллак, 2022
© Издательство «Лань»,
художественное оформление, 2022

Введение

А

вторы прекрасно понимают трудности, которые возникают у начинающего программиста, поэтому учебное пособие предназначено, в первую очередь, для тех,
кто только начинает изучать программирование.
В разработке методики изложения авторы придерживались определения, данного Н. Виртом [1]: Программа = Алгоритмы + Данные.
Согласно этому определению программы представляют собой конкретные формулировки абстрактных алгоритмов, основанные на конкретных представлениях
данных. Именно поэтому авторами уделяется большое
внимание как разработке алгоритмов, так и концепции
данных языка программирования.
Учебное пособие состоит из трех глав.
В первой главе приводятся сведения о типовых алгоритмах обработки данных безотносительно к языку программирования. Приведены примеры решения некоторых классов задач, где для каждой задачи разработан алгоритм в виде блок-схемы с пояснениями, набор тестовых
данных и таблица исполнения алгоритма. Приводимые
способы решения задач по возможности являются рациональными, но не претендуют на то, чтобы быть наилучшими.
В качестве языка программирования выбран классический С++. Краткое описание синтаксических правил
С++ и механизмов реализации приведено во второй главе. Материал разбит на темы, позволяющие изучать язык
по принципу «от простого к сложному». В изложении авторы опираются на материал первой главы, приводя программную реализацию всех алгоритмов. Добавлено мно-

4

Введение

го примеров, иллюстрирующих как особенности языка
С++, так и некоторые алгоритмические приемы решения
задач. В качестве методологии выбрано структурное программирование на основе функций.
Все приведенные программы проверены на работоспособность авторами в среде проектирования
Visual Studio 2013. Коды программ соответствуют стандарту C++11 (ISO/IEC 14882:2011) и разработаны в консольных приложениях на основе шаблона «Пустой проект».
Третья глава — это практикум, который содержит
задания для самостоятельного выполнения. В практикуме авторы опираются на материал второй главы. Третья
глава состоит из десяти основных тем. В каждой теме есть
краткое теоретическое введение, а также примеры программ решения некоторых задач. В каждом примере назван типовой алгоритм и приведен код программы с подробными комментариями.
Примеры и типовые решения помогут начинающим
в освоении практических приемов программирования
и выработке собственного стиля.
В каждой теме для самостоятельного решения предлагаются по 30 вариантов задач примерно одинакового уровня сложности. Особый интерес, по нашему мнению, представляют содержательные задачи, в которых постановка
задачи выполнена на вербальном уровне, т. е. не формализована. Здесь студент должен самостоятельно осмыслить
задачу, формализовать ее, предложить структуру данных
и выбрать или разработать алгоритм решения. Опыт показывает, что часто именно этот этап в практическом программировании является наиболее трудным.
Материал пособия консолидирует многолетний опыт
работы авторов в преподавании различных курсов программирования.
Соответствует ФГОС ВПО третьего поколения для направления «Прикладная информатика».
Не требуется каких-либо предварительных знаний
о языках программирования, поэтому пособие может
быть рекомендовано для самостоятельного изучения.

Гл ава 1

Основы алгоритмизации

1.1. Определение алгоритма
и его свойства

П

од алгоритмом понимается точное предписание, задающее последовательность действий, которая ведет
от произвольного исходного данного (или от некоторой совокупности возможных для данного алгоритма исходных
данных) к достижению полностью определяемого этим
исходным данным результата.
Алгоритм должен обладать определенными свойствами, наличие которых гарантирует получение решения задачи исполнителем.
Дискретность. Решение задачи должно быть разбито
на элементарные действия. Запись отдельных действий
реализуется в виде упорядоченной последовательности
отдельных команд, образующих дискретную структуру алгоритма. Это свойство непосредственно отражено
в определении алгоритма.
Понятность. На практике любой алгоритм предназначен для определенного исполнителя, и любую команду
алгоритма исполнитель должен уметь выполнить.
Определенность (детерминированность). Каждая команда алгоритма должна определять однозначные действия исполнителя. Результат их исполнения не должен
зависеть от факторов, не учтенных в алгоритме явно. При
одних и тех же исходных данных алгоритм должен давать
стабильный результат.
Массовость. Разработанный алгоритм должен давать
возможность получения результата при различных исходных данных для однотипных задач.

6

Гл а в а 1

Например, пользуясь алгоритмом решения квадратного уравнения, можно находить его корни при любых
значениях коэффициентов.
Свойство массовости полезное, но не обязательное
свойство алгоритма, так как интерес представляют и алгоритмы, пригодные для решения единственной задачи.
Результативность (конечность). Это свойство предполагает обязательное получение результата решения задачи за конечное число шагов. Под решением задачи понимается и сообщение о том, что при заданных значениях
исходных данных задача решения не имеет.
Если решить задачу при заданных исходных данных
за конечное число шагов не удается, то говорят, что алгоритм «зацикливается».
Смысл условий дискретности, понятности и определенности ясен: их нарушение ведет к невозможности
выполнения алгоритма. Остальные условия не столь
очевидны. Для сложных алгоритмов выполнить исчерпывающую проверку результативности и корректности
невозможно. Это равносильно полному решению задачи,
для которой создан алгоритм, вручную.
Можно сформулировать общие правила, руководствуясь
которыми следует записывать алгоритм решения задачи.
1. Выделить величины, являющиеся исходными данными для задачи.
2. Разбить решение задачи на такие команды, каждую
из которых исполнитель может выполнить однозначно.
3. Указать порядок выполнения команд.
4. Задать условие окончания процесса решения задачи.
5. Определить, что является результатом решения задачи в каждом из возможных случаев.
Хотя алгоритмы обычно предназначены для автоматического выполнения, они создаются и разрабатываются людьми. Поэтому первоначальная запись алгоритма обычно производится в форме, доступной для восприятия человеком.
Самой простой является словесная форма записи алгоритмов на естественном языке. В этом виде алгоритм
представляет собой описание последовательности этапов
обработки данных, изложенное в произвольной форме.

7

Ос н о в ы а л г о р и т м и з а ц и и

Словесная форма удобна для человеческого восприятия,
но страдает многословностью и неоднозначностью.
Когда запись алгоритма формализована частично, то
используется псевдокод. Он содержит как элементы естественного языка, так и формальные конструкции, описывающие базовые алгоритмические структуры. Эти конструкции называются служебными словами. Формального определения псевдокода или строгих правил записи
алгоритмов в таком формате не существует.
Графическая форма представления алгоритма является более компактной. Алгоритм изображается в виде
последовательности связанных между собой блоков, каждый из которых соответствует выполнению одного или
нескольких действий. Графическое представление алгоритма называется блок-схемой. Блок-схема определяет
структуру алгоритма.
Графические обозначения блоков стандартизованы.
Некоторые из часто используемых блоков представлены
в таблице 1.1.
Та блица 1.1

Изображение основных блоков на блок-схеме
Обозначение блока

Пояснение

Процесс (вычислительное действие, реализованное операцией присваивания)

Решение (проверка условия, реализующая условный переход)

Начало, конец алгоритма

Ввод-вывод в общем виде

Модификация (начало цикла с параметром)

8

Гл а в а 1

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

Базовая структура «следование» означает, что несколько операторов выполняются последовательно друг
за другом, и только один раз за время выполнения программы. Структура «следование» используется для реализации задач, имеющих линейный алгоритм решения.
Это означает, что такой алгоритм не содержит проверок

Ос н о в ы а л г о р и т м и з а ц и и

9

условий и повторений, действия в нем выполняются последовательно, одно за другим.
Пример 1.1. Построить блок-схему алгоритма вычисления высот треугольника со сторонами a, b, c по формулам:
2
ha =   ⋅ p ( p − a) ( p − b) ( p − c);
a
2
ha =   ⋅ p ( p − a) ( p − b) ( p − c);
b
2
ha =   ⋅ p ( p − a) ( p − b) ( p − c),
c
где p =
риметр.

(a + b + c)
— полупе2

Для того чтобы не вычислять три раза одно и то же
значение, введем вспомогательную величину:
t = 2 p ( p − a) ( p − b) ( p − c).
Блок 1. Ввод значений
сторон треугольника.
Блок 2. Вычисление полупериметра.
Блок 3. Вычисление вспомогательной величины t.
Блок 4. Вычисление высот, опущенных на стороны
а, b, c.
Блок 5. Вывод результатов.
1.2.2. Разветвляющиеся алгоритмы

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

10

Гл а в а 1

му выходу, так что работа алгоритма будет продолжаться
независимо от того, какой путь будет выбран.
Существует структура с полным и неполным ветвлением.
Структура с полным ветвлением (если — то — иначе)
записывается так:
Если < условие >
то
иначе
Все если

Команда выполняется так: если является истинным, то выполняются , записанные после
ключевого слова то, если является ложным, то
выполняются , записанные после слова иначе.
Структура с неполным ветвлением (если — то) не содержит части, начинающейся со слова иначе:
Если
то
Все если

Команда выполняется так: если является
истинным, то выполняются , записанные после ключевого слова то.
Блок-схема алгоритма с ветвлением выглядит так:

Полное ветвление. Структура
Если — То — Иначе

Неполное ветвление.
Структура Если — То

Пример 1.2. Вычислить значение функции
x + a, при x < 10;

y = x + b, при 10 ≤ x ≤ 20;
x + c, при x > 20.

11

Ос н о в ы а л г о р и т м и з а ц и и

Дано: x, a, b, c — произвольные числа.
Найти: y.
Представим задачу графически на числовой оси
10 ≤ x ≤ 20

x < 10
10
y=x+a
1 интервал

x > 20
20

y=x+b
2 интервал

y=x+c
3 интервал

Так как значение переменной x вводится произвольно, то оно может оказаться в любом из трех интервалов.
Приведем блок-схему.

Блок 1. Ввод исходных данных.
Блок 2. Проверка введенного значения. Если х < 10
(выход «Да»), то точка находится в первом интервале.
В противном случае х ≥ 10 (выход «Нет»), и точка может
оказаться во втором или третьем интервале.
Блок 4. Проверка ограничения значения х справа
(х < 20). Если условие выполняется (выход «Да»), то х находится во втором интервале, иначе х ≥ 20, и точка находится в третьем интервале.
Блоки 3, 5 и 6. Вычисление значения y.

12

Гл а в а 1

1.2.3. Циклические алгоритмы

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

Цикл с предусловием

Цикл с постусловием

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

13

Ос н о в ы а л г о р и т м и з а ц и и

вием), либо после тела цикла (цикл с постусловием). Тело
цикла с постусловием всегда выполняется хотя бы один
раз. Проверка необходимости выполнения цикла с предусловием делается до начала цикла, поэтому возможно,
что он не выполнится ни разу.
При конструировании циклов следует соблюдать обязательное условие результативности алгоритма (т. е. его
окончания за конечное число шагов). Практически это
означает, что в условии должна быть переменная, значение которой изменяется в теле цикла. Причем, изменяется таким образом, чтобы условие в конечном итоге перестало выполняться. Такая переменная называется управляющей переменной цикла или параметром цикла.
Еще один вид циклов — цикл с параметром, или
арифметический цикл. Тело цикла выполняется, пока
параметр цикла i пробегает множество значений от начального (In) до конечного (Ik).
Переменная i определяет количество повторений тела
цикла S. Если шаг изменения значения параметра цикла
обозначить через ∆I, то количество повторений тела цикла n можно вычислить по формуле
−
n = I k I n + 1.
∆I
Если параметр цикла i изменяется с шагом 1, то шаг
может не указываться.
Цикл выполняется так: начальное значение параметра
цикла i равно In. Если i ≤ Ik, выполняется тело цикла S, после
чего параметр цикла увеличивается на 1 с помощью оператора присваивания i = i + 1, и снова проверяется условие i ≤ Ik.
Пример 1.3. Дано целое положительное число n. Вычислить
факториал этого числа. Известно, что факториал любого целого
положительного числа n определяется как произведение чисел от 1 до заданного числа n:
n! = 1 ⋅ 2 ⋅ 3 ⋅ ... ⋅ n.

14

Гл а в а 1

По определению 0! = 1 и 1! = 1.
Задача решается с помощью циклического алгоритма. Введем следующие обозначения: N — заданное число,
F — факториал числа, R — параметр цикла. Составим два
варианта алгоритма: с использованием цикла с предусловием и цикла с параметром.
Правильность алгоритма можно проверить, если выполнить его формально «вручную». Выполним алгоритм
при n = 4.

Цикл с предусловием

Цикл с параметром

Цикл с предусловием

Цикл с параметром

R

R 0 выполняется (выход
«Да»), то вычисляется группа операторов в блоке 4:
k = k + 1; Y[k] = X[i].
Тест
Данные

Результат

n=5
X = (–1, 2, 0, 4, –3)

k=2
Y = (2, 4)

Выполнение алгоритма.
k

0

i

xi > 0?

1

x1 > 0? «Нет»

2

x2 > 0? «Да»

3

x3 > 0? «Нет»

4

x4 > 0? «Да»

yk = xi

y 1 = x2 = 2

1

y2 = x4 = 4

2
5

x5 > 0? «Нет»

6

Конец цикла

23

Ос н о в ы а л г о р и т м и з а ц и и

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

Пример 1.8. Вычислить сумму элементов одномерного
массива.
Дано: n — размер массива; массив А = (a1, a2, …, an).
Найти: S — сумму элементов массива.
Начальное значение суммы равно нулю. В предыдущих подпараграфах мы говорили о том, что значение суммы накапливается с каждым шагом выполнения алгоритма. Вычисляем сумму по формуле S = S + ai.
Тест
Данные

N=4

Результат

A = (3, 5, –2, 8) S = 14
Исполнение алгоритма

i

S

0
1
2
3
4

S + a1 = 0 + 3 = 3
S + a2 = a1 + a2 = 3 + 5 = 8
S + a3 = a1 + a2 + a3 = 8 – 2 = 6
S + a4 = a1 + a2 + a3 + a4 = 6 + 8 = 14

Фрагмент алгоритма

Пример 1.9. Найти количество положительных и отрицательных чисел в данном массиве.
Дано: n — размер массива; массив А = (a1, a2, …, an).
Обозначим k1 — количество положительных чисел, k2 —
количество отрицательных чисел.
Найти: k1, k2 — количество положительных и отрицательных чисел массива.
Математическая модель. Пусть k1 = 0 и k2 = 0. Если
a[i] > 0, то k1 = k1 + 1. Если a[i] < 0, то k2 = k2 + 1. Процесс
повторяется до окончания просмотра всех чисел массива.
Приведем фрагмент блок-схемы алгоритма и ее словесное описание.

24

Гл а в а 1

Блок 1. Задание начальных значений переменным k1
и k2.
Блок 2. Заголовок арифметического цикла.
Блок 3. Проверка условия. Если очередное значение
элемента массива положительное (выход «Да» блока 3), то
увеличиваем количество положительных чисел (блок 4).
Блок 5. Если очередное значение элемента массива отрицательное (выход «Да» блока 5), то увеличиваем количество отрицательных чисел массива (блок 6).
Указанные вычисления выполняем для всех n чисел
массива.
В примере нам понадобилось два условных оператора,
так как в массиве могут встретиться нулевые элементы,
количество которых нам считать не надо.
1.3.3. Определение наибольшего элемента массива

Пример 1.10. Дан массив произвольной длины. Найти
наибольший элемент массива и определить его номер.
Дано: n — размер массива; массив А = (a1, a2, …, an).
Найти: Amax — наибольший элемент массива, k — его
номер.
Математическая модель. Пусть Amax = a[1]; k = 1.
Если Amax < a[i], то Amax = a[i], k = i, для i = 2, 3, …, n.

25

Ос н о в ы а л г о р и т м и з а ц и и

Тест
Данные

n=5

Результат

A = (3, –1, 10, 1, 6) Amax = 10 k = 3

Приведем фрагмент блок-схемы алгоритма и его выполнение для тестового примера.

i

i ≤ n?

Amax < A[i]?

Amax

k

3

1

2 2 ≤ 5? «Да»

–1 < 3? «Да»

3 3 ≤ 5? «Да»

10 < 3? «Нет» 10

4 3 ≤ 5? «Да»

1 < 10? «Да»

5 5 ≤ 5? «Да»

6 < 10? «Да»

3

6 6 ≤ 5? «Нет» (кц)

1.3.4. Удаление и вставка элементов массива

Пример 1.11. Удалить из массива, в котором все элементы различны, наибольший элемент.
Дано: n — размер массива; A[n] — массив вещественных чисел.
Найти: новый массив А размера n – 1.
Для решения задачи необходимо:
1) найти номер k наибольшего элемента массива. Эта
задача решена в примере 1.10;
2) сдвинуть все элементы массива, начиная с k-го, на
один элемент влево.

26

Гл а в а 1

Для того чтобы разработать алгоритм, рассмотрим
конкретный пример. Пусть дан одномерный массив, состоящий из 7 элементов:
А = (6, 3, 7, 11, 2, 8, 1).
Номер наибольшего элемента равен 4 (k = 4), т. е. начиная с четвертого элемента будем сдвигать элементы на
один влево: четвертому элементу присвоим значение пятого, пятому — значение шестого, а шестому — значение
седьмого. На этом сдвиг заканчивается. Таким образом,
сдвиг начинается с k-го элемента и заканчивается элементом с номером n, где n — количество элементов в массиве. После сдвига массив будет такой: А = (6, 3, 7, 8, 1, 1).
Уменьшим количество элементов в массиве, так как после
удаления количество элементов в массиве станет на один
элемент меньше. Массив примет вид А = (6, 3, 7, 8, 1).
В примере 1.10 уже рассматривался алгоритм поиска наибольшего элемента в одномерном массиве. Так как
в данной задаче нас не интересует конкретное значение
наибольшего элемента, то модифицируем рассмотренный алгоритм и сохраняем только номер наибольшего
элемента.
Приведем фрагмент блок-схемы алгоритма и ее словесное описание.
Блок 1. Пусть первый элемент максимальный (k = 1).
Блок 2. В цикле просматриваем все элементы массива,
начиная со второго до последнего.
Блок 3. Сравниваем элемент с номером k с очередным
элементом массива.
Блок 4. Запоминаем номер элемента, который на очередном шаге выполнения цикла больше k-го.
По окончании цикла (блок 2) переменная k сохранит
номер наибольшего элемента.
Начинам сдвиг.
Блок 5. В цикле, начиная с k-го элемента по n – 1-й,
выполняем присваивание (блок 6), тем самым заменяя
элемент с номером i на элемент с номером i + 1.
Блок 7. Размер массива уменьшаем на 1, выполняя
присваивание n = n – 1.

27

Ос н о в ы а л г о р и т м и з а ц и и

Мы уже рассматривали подробно выполнение алгоритма нахождения наибольшего элемента массива и его
номера для тестового примера (см. пример 1.10). Покажем, как выполняется вторая часть (сдвиг элементов массива) для тестового примера.
Тест
Данные

n=7

Результат

A = (6, 3, 7, 11, 2, 8, 1)

A = (6, 3, 7, 2, 8, 1) n = 6

В массиве номер наибольшего элемента k = 4. Удаляем
этот элемент.
i

4
5
6
7
n=6

i ≤ n – 1?

ai = ai+1

4 ≤ 6? «Да»
а4 = а5
5 ≤ 6? «Да»
а5 = а6
6 ≤ 6? «Да»
а6 = а7
7 ≤ 6? «Нет» (кц)

Результат

А = (6, 3, 7, 2, 2, 8, 1)
А = (6, 3, 7, 2, 8, 8,1)
А = (6, 3, 7, 2, 8, 1,1)
А = (6, 3, 7, 2, 8,1)

Пример 1.12. Вставить произвольное число в одномерный массив A[n] после элемента с заданным номером.

28

Гл а в а 1

Дано: n — размер массива; A[n] — числовой вещественный массив; k — номер элемента, после которого
вставляется число, равное m.
Найти: новый массив A размера n + 1.
Словесное описание алгоритма. Вставка нового элемента осуществляется следующим образом:
1) первые k элементов массива остаются без изменения;
2) все элементы, начиная с (k + 1)-го необходимо сдвинуть вправо, чтобы освободить место для вставляемого
элемента;
3) элементу с номером (k + 1) присвоить значение m.
Количество элементов массива увеличить на 1.
Рассмотрим пример. Пусть дан массив A = (3, –12, 5,
14, 27), где n = 5.
Вставим элемент со значением 10 после второго элемента массива. Получим массив A = (3, –12, 10, 5, 14, 27).
Количество элементов n = 6.
Приведем
фрагмент
блок-схемы алгоритма и ее
словесное описание.
Блок 1. Начинаем просматривать массив с конца,
с n-го элемента до (k + 1)-го.
Блок 2. В цикле сдвигаем
все элементы массива вправо.
Блок 3. На освободившееся место вставляем новый
элемент.
Блок 4. Увеличиваем количество элементов в массиве.
Тест
Данные

n = 5; k = 2;
m = 10

Результат

А = (3, –12, 5, 14, 27) А = (3, –12, 10, 5, 14, 27); n = 6

Покажем выполнение алгоритма для тестового примера.

29

Ос н о в ы а л г о р и т м и з а ц и и

i

5
4
3

a[i + 1] = a[i]

a[k + 1] = m

a[6] = a[5]
a[5] = a[4]
a[4] = a[3] (кц)

n

5

a[3] = 10

6

Массив

А = (3, –12, 5, 14, 27, 27)
А = (3, –12, 5, 14, 14, 27)
А = (3, –12, 5, 5, 14, 27)
А = (3, –12, 10, 5, 14, 27)

В рассмотренных примерах мы использовали арифметический цикл, количество повторений которого всегда
известно до работы начала алгоритма.
1.3.5. Определение первого элемента массива,
имеющего заданное свойство

Пример 1.13. Определить, является ли заданная последовательность различных чисел a1, a2, …, an монотонно убывающей.
По определению последовательность монотонно убывает, если a[i] ≥ a[i + 1]. Если хотя бы для одной пары
чисел это условие нарушается, то последовательность не
является монотонно убывающей. Следовательно, при построении алгоритма мы должны зафиксировать именно
этот факт.
Пусть переменная Flag принимает значение равное 1,
если последовательность является монотонно убывающей, и 0 — в противном случае.
Дано: n — размер массива; A[n] — числовой вещественный массив.
Найти: Flag = 1, если последовательность монотонно
убывает; Flag = 0 в противном случае.
Словесное описание алгоритма. Предположим, что
последовательность монотонно убывает, и присвоим переменной Flag начальное значение, равное 1. В цикле последовательно сравниваем значения двух соседних элементов. Выход из цикла возможен в двух случаях:
• просмотрены все элементы заданной последовательности. Это означает, что условие а[i] ≥ а[i + 1] выполняется
для всех пар соединений элементов, и последовательность является монотонно убывающей. Тогда Flag = 1;
• условие а[i] ≥ а[i + 1] не выполнилось для пары соседних элементов, тогда Flag = 0. Цикл прерывается. Сле-

30

Гл а в а 1

довательно, последовательность не является монотонно
убывающей.
Приведем
фрагмент
блок-схемы алгоритма и ее
словесное описание.
Блок 1. Берем первое
число последовательности
i = 1. Предполагаем, что последовательность монотонно
убывает (Flag = 1).
Блок 2. Цикл с предусловием. Пока не проверены все
элементы и пока последовательность монотонно убывает
(проверка условия в блоке 2), выполняется тело цикла
(блоки 3–5).
Блок 3. Если последовательность не монотонная (выход «Нет»), то фиксируем это и Flag = 0 (блок 4).
Если условие не нарушается (выход «Да» блока 3),
то присваиваем номеру элемента следующее значение
(блок 5) и возвращаемся в цикл.
Система тестов
№
теста

1
2

Данные

Проверяемый
случай

Является
Не является

Результат

n

Массив А

Flag

3
3

(3, 2, 1)
(2, 3, 1)

1
0

Выполнение алгоритма.
№ теста

1

i

1
2
3

Flag

1

(i а[i + 1]?

а[1] > а[2]? «Да»
а[2] > а[3]? «Да»

«Нет»
Последовательность монотонно убывает

1
2

1

«Да»

0

«Нет»

а[1] > а[2]? «Нет»

Последовательность не монотонно убывающая

Пример 1.14. Определить, есть ли в одномерном массиве хотя бы один отрицательный элемент.

31

Ос н о в ы а л г о р и т м и з а ц и и

Пусть переменная Flag = 1, если в массиве есть отрицательный элемент, и Flag = 0 — в противном случае.
Дано: n — размер массива; A[n] — числовой вещественный массив.
Найти: Flag = 1, если отрицательный элемент есть;
Flag = 0 — в противном случае.
Словесное описание алгоритма. Начинаем просматривать массив с первого элемента (i = 1). Пока не просмотрен
последний элемент (i ≤ n) и не найден отрицательный элемент (a[i] >= 0), будем переходить к следующему элементу
(i = i + 1). Таким образом, мы закончим просмотр массива
в одном из двух случаев:
1) просмотрели все элементы и не нашли отрицательного, тогда Flag = 0 и i > n;
2) нашли нужный элемент, при этом Flag = 1.
Приведем фрагмент блок-схемы алгоритма и ее словесное описание.
Блок 1. Берем первый
элемент массива. Предполагаем, что в массиве нет отрицательных чисел и Flag = 0.
Блок 2. Пока не просмотрены все числа и пока не
встретилось отрицательное
число (выход «Да» блока 2)
выполняем тело цикла (блоки 3–5).
Блок 3. Если встретилось отрицательное число (выход
«Да» блока 3), запоминаем это и Flag = 1. Если очередное
число положительное или равно нулю (выход «Нет» блока 3), то увеличиваем номер числа (блок 5) и переходим
к следующему числу.
Система тестов
№ теста

1
2

Проверяемый
случай

Есть
Нет

Данные
n

3
3

Результат

Массив А

(3, –2, 1)
(2, 3, 1)

Исполнение алгоритма.

Flag

1
0

32

Гл а в а 1

(i ≤ n) и (Flag = 0)?

№ теста

i

Flag

1

1
2

0
0

(1 ≤ 3) и (Flag = 0)? «Да»
(2 ≤ 3) и (Flag = 0)? «Да»

1

Найдено отрицательное число (кц)

0
0
0
0

(1 ≤ 3) и (Flag = 0)? «Да»
(2 ≤ 3) и (Flag = 0)? «Да»
(3 ≤ 3) и (Flag = 0)? «Да»
(4 ≤ 3) и (Flag = 0)? «Нет» (кц)
Отрицательных чисел нет

2

1
2
3
4

а[i] < 0?

а[1] < 0? «Нет»
а[2] < 0? «Да»
а[1] < 0? «Нет»
а[2] < 0? «Нет»
а[3] < 0? «Нет»

1.4. Алгоритмы, использующие
двумерные массивы
1.4.1. Понятие двумерного массива

Понятие «двумерный массив» определим на примере.
Пусть имеются данные о продажах некоторого товара по
месяцам:
Месяц

Объем продаж, пар

Цена продажи, руб.

Себестоимость, руб.

1
2
3

4500
3900
3100

100
110
120

50
55
60

Таблица представляет собой множество из двенадцати
однородных величин — это массив. Ее элементы расположены в 3 строки по 4 столбца в каждой.
Подобного рода таблицы из нескольких строк с равным числом элементов в каждой называют в информатике двумерными массивами или матрицей.
Двумерный массив определяется именем, числом
строк и столбцов и обозначается, например, так: А[n, m],
где А — произвольное имя массива; n — число строк; m —
число столбцов. Обратите внимание на то, что сначала
всегда указывается количество строк, а потом — количество столбцов массива.
Если имеются данные о продажах за 3 мес., то нашу
таблицу можно обозначить так: А[3, 4], т. е. массив состоит из 3 строк и 4 столбцов.
Строки двумерных массивов нумеруются по порядку
сверху вниз, а столбцы — слева направо.

33

Ос н о в ы а л г о р и т м и з а ц и и

Элементы таблицы, представленной в примере, получат такие обозначения:
 A [1,1] A [1, 2] A [1, 3] A [1, 4] 
A [3, 4] =  A [2,1] A [2, 2] A [2, 3] A [2, 4] =


 A [3,1] A [3, 2] A [3, 3] A [3, 4]
1 4500 100 50 
= 2 3900 110 55  .


3 3100 120 60 
Каждый элемент двумерного массива определяется
номерами строки и столбца, на пересечении которых он
находится, и в соответствии с этим обозначается именем
массива с двумя индексами: первый — номер строки, второй — номер столбца. Например, А[1, 3] — элемент находится в первой строке и третьем столбце.
Таким образом, A[1, 1] = 1, A[2, 3] = 110 и т. д. Произвольный элемент двумерного массива мы будем обозначать A[i, j], где i — номер строки, j — номер столбца.
Поскольку положение элемента в двумерном массиве
описывается двумя индексами, алгоритмы для решения
большинства задач с их использованием строятся на основе вложенных циклов. Обычно внешний цикл организуется по строкам массива, т. е. в нем выбирается требуемая
строка, а внутренний — по столбцам, в котором выбирается элемент внутри строки.

Ввод двумерного массива

Вывод двумерного массива

34

Гл а в а 1

В отличие от одномерных массивов для ввода и вывода
данных в двумерные массивы необходимо использовать
вложенные циклы. Циклы являются арифметическими,
так как количество строк и столбцов известно.
Мы ввели и вывели элементы произвольного массива,
имеющего n строк и m столбцов. Понятно, что при вводе
необходимо задать количество строк и столбцов.
Напомним, что во всех задачах будем считать, что
элементы массива заданы тем или иным способом,
и показывать только реализацию алгоритма решения
задачи, опуская команды ввода данных и вывода результата.
Также не будем обозначать блоки начала и конца
выполнения алгоритма. Подразумевается, что все перечисленные блоки должны всегда присутствовать в алгоритме.
Следует понимать, что все алгоритмы, приведенные
ранее для одномерных массивов, можно использовать
и для двумерных массивов, применив вложенный цикл.
Приведем алгоритмы решения некоторых задач.
1.4.2. Вычисление суммы элементов двумерного
массива

Пример 1.15. Вычислить сумму элементов строк заданного двумерного массива.
Дано: n, m — количество строк и столбцов массива соответственно; массив А[n, m].
Найти: S[n] — сумму элементов строк массива.
Тест
Данные

Результат

N

M

A

S

2

2

2 1
 4 3

(3, 7)

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

35

Ос н о в ы а л г о р и т м и з а ц и и

Исполнение алгоритма.
i

i ≤ n?

1 1 ≤ 2? «Да»

2 2 ≤ 2? «Да»

j

j ≤ m?

S

S1 = 0
S1 = S1 + a1,1 = 0 + 2 = 2
S1 = S1 + a1,2 = 2 + 1 = 3

1
2
3

1 ≤ 2? «Да»
2 ≤ 2? «Да»
3 ≤ 2? «Нет» (кц)

1
2
3

S2 = 0
1 ≤ 2? «Да»
S2 = S2 + a2,1 = 0 + 4 = 4
2 ≤ 2? «Да»
S2 = S2 + a2,2 = 4 + 3 = 7
3 ≤ 2? «Нет» (кц)

3 3 ≤ 2? «Нет» (кц)

В этом примере мы нашли сумму элементов каждой
строки матрицы. Количество таких сумм равно количеству строк матрицы, поэтому для сохранения значений
сумм использован одномерный массив S[n], количество
элементов в котором равно количеству строк матрицы.
Обратите внимание на то, где присваивается начальное значение переменной S. Если находится сумма всех
элементов матрицы, то команда S = 0 записывается перед
началом внешнего цикла. В результате получается одно
значение S = 10. Если ставится задача нахождения суммы
элементов строк матрицы, то команда S[i] = 0 записывается внутри цикла по строкам матрицы, тогда результат
представляет собой одномерный массив, в котором количество элементов равно количеству строк матрицы, и тогда S = (3, 7). Если требуется найти сумму элементов столб-

36

Гл а в а 1

цов матрицы, то команда S[j] = 0 записывается внутри
цикла по столбцам матрицы, тогда результат представляет собой одномерный массив, в котором количество элементов равно количеству столбцов матрицы, и S = (6, 4).
1.4.3. Вычисление наибольшего элемента двумерного
массива

Пример 1.16. Найти наибольший элемент двумерного
массива и его индексы.
Дано: массив А[n, m], где n, m — количество строк
и столбцов массива соответственно.
Найти: max — наибольший элемент массива, а также
maxi и maxj — номер строки и столбца соответственно, на
пересечении которых находится искомый элемент.
Словесное описание алгоритма. Пусть первый элемент двумерного массива является наибольшим. Запоминаем его значение и индексы. Сравниваем наибольшее
значение со всеми оставшимися элементами. Если запомненное значение меньше очередного элемента массива, то
запоминаем новое значение и его индексы.
Так как значения элементов в массиве могут повторяться, то договоримся, что будем запоминать только индексы первого наибольшего элемента.
Приведем фрагмент блок-схемы алгоритма и ее описание.
Блок 1. Присваиваем начальные значения переменным max, maxi, maxj.
Блок 2. Берем очередную
строку матрицы.
Блок 3. На i-й строке матрицы последовательно выбираем каждый элемент.
Блок 4. Сравниваем выбранный элемент со значением переменной max.
Блок 5. Если значение
очередного элемента больше
max (выход «Да» блока 4),

37

Ос н о в ы а л г о р и т м и з а ц и и

то запоминаем его значение и индексы. Возвращаемся
в блок 3 и выбираем следующий элемент строки.
Блок 6. Если в строке нет элементов, то выбираем новую строку и повторяем вычисления (блоки 3–5).
Тест
Данные

Результат

n

m

A

2

3

1 3 5
 4 3 5 

max = 5
maxi = 1
maxj = 3

Выполните тестирование алгоритма самостоятельно.
1.4.4. Вставка и удаление строк и столбцов
двумерного массива

Мы уже рассматривали задачи вставки и удаления
элементов в одномерном массиве. Обобщим эти алгоритмы на двумерный массив.
Пример 1.17. Вставить в двумерный массив строку,
состоящую из нулей, после строки с номером k.
Для решения этой задачи необходимо:
1) первые k строк оставить без изменения;
2) все строки после k-й сдвинуть на одну вниз. Сдвиг лучше всего начать с последней строки и идти до (k + 1)-й строки;
3) присвоить новые значения элементам (k + 1)-й строки и увеличить количество строк в двумерном массиве.
Дано: массив А[n, m], где n, m — количество строк
и столбцов массива соответственно; k — номер строки, после которой вставляется новая строка.
Найти: новую матрицу А, содержащую n + 1 строку
и m столбцов.
Приведем фрагмент блок-схемы алгоритма.
В блоке 3 в цикле выполняется сдвиг строк матрицы
вниз, начиная со строки с номером k. В блоке 5 происходит вставка новой строки.
Тест
n

2

m

3

k

1

Исходная матрица

Результат

1 2 3 
 4 5 6 

1 2 3 
0 0 0


4 5 6 

38

Гл а в а 1

Так как k = 1, то необходимо сдвинуть строку 2 вниз
и вставить после первой строки новую строку, состоящую
из нулей.
Исполнение алгоритма.
i

j

A

Сдвигаем строки матрицы вниз
(блоки 1–3)
1
A[3, 1] = A[2, 1] = 4
2
2
A[3, 2] = A[2, 2] = 5
3
A[3, 3] = A[2, 3] = 6
Промежуточный результат
1 2 3
4 5 6


4 5 6
Вставка строки
1
A[2, 1] = 0
2
2
A[2, 2] = 0
3
A[2, 3] = 0

Примечания
1. Если необходимо вставить новую строку после строки, удовлетворяющей некоторому условию, то надо найти номер этой строки — и задача сведется к решению уже
рассмотренной.
2. Если надо вставить новые строки после всех строк
с заданным условием, то надо учесть это при описании
массива. Заметим, что удобнее рассматривать строки,
начиная с последней строки, и после вставки очередной
строки увеличивать количество строк.
3. Вставка новой строки перед строкой с номером k изменится только тем, что сдвигать назад надо не с (k + 1)-й
строки, а с k-й.
4. Если надо вставлять столбцы, то размерность массива увеличивается по столбцам, а все остальное практически не меняется: надо сдвинуть столбцы вправо и на
данное место записать новый столбец.
Пример 1.18. Удалить из двумерного массива строку
с номером k.
Для удаления строки с номером k необходимо:

39

Ос н о в ы а л г о р и т м и з а ц и и

1) сдвинуть все строки, начиная со строки с номером
k, вверх;
2) уменьшить количество строк в двумерном массиве.
Дано: массив А[n, m], где n, m — количество строк
и столбцов массива соответственно; k — номер удаляемой
строки.
Найти: новую матрицу А, содержащую (n – 1)-ую
строку и m столбцов.
Фрагмент блок-схемы алгоритма.
Тест
n

m

k

3 3 2

Исходная
матрица

1 2 3 
0 0 0


4 5 6 

Результат

1 2 3 
 4 5 6 

Исполнение алгоритма.
i

j

A

1 A[2, 1] = A[3, 1] = 4
2 2 A[2, 2] = A[3, 2] = 5
3 A[2, 3] = A[3, 3] = 6

После выполнения циклов (блоки 1 и 2) матрица имеет следующий вид:
1 2 3 
4 5 6 .


4 5 6 
Уменьшаем количество строк матрицы (блок 4), после
чего она примет искомый вид.
1.4.5. Нахождение строк или столбцов двумерного
массива, обладающих заданным свойством

Пример 1.19. Дан двумерный массив A[n, m]. Найти
количество строк, содержащих хотя бы один нуль.
Обозначим: k — количество строк, содержащих хотя
бы один нуль; Flag — признак наличия нулей в строке.
Flag = 1 означает, что нули в строке есть; Flag = 0 — нулей
в строке нет.

40

Гл а в а 1

Словесное описание алгоритма. Начинаем просматривать массив с первой строки. Берем первый элемент столбца (j = 1). Пока не просмотрен последний элемент столбца
(j ≤ m) и не найден отрицательный элемент (a[i, j] >= 0),
будем переходить к следующему элементу, увеличивая
индекс элемента j (j = j + 1). Таким образом, мы закончим
просмотр строки массива в одном из двух случаев:
1) просмотрели все элементы и не нашли отрицательного, тогда Flag = 0;
2) нашли нужный элемент, при этом Flag = 1. Увеличиваем значение количества строк k, содержащих нули.
Фрагмент блок-схемы алгоритма.
Блок 1. Присваиваем переменной k начальное значение.
Блок 2. Берем очередную строку i.
Блок 3. Для выбранной строки задаем первый элемент
строки и устанавливаем Flag = 0.
Блок 4. Выполняем итерационный цикл для всех элементов строки (блоки 5–7).
Блок 5. Сравниваем очередной элемент строки с нулем.
Блок 6. Если нулевой элемент найден (выход «Да»
блока 5), то Flag = 1, увеличиваем значение k и заканчиваем просмотр строки (выход «Нет» блока 4).
Блок 7. Если нулевой элемент не найден (выход «Нет»
блока 5), то продолжаем просмотр оставшихся элементов
в строке, увеличивая индекс
элемента j.
Покажем выполнение алгоритма на тестовом примере.
Тест
Данные

Результат

N M Матрица А

K

3

3

1 0 1 
2 4 7 


0 1 0

2

41

Ос н о в ы а л г о р и т м и з а ц и и

Исполнение алгоритма.
i

Flag

j

(j 9? «Да»
64 > 30? «Да»
64 > 87? «Нет»
87 > 14? «Да»
87 > 2? «Да»

получим

a[2] = 9
a[3] = 30

a[3] = 64
a[4] = 64

a[5] = 14
a[6] = 2

a[6] = 87
a[7] = 87

следующий

массив:

53

Ос н о в ы а л г о р и т м и з а ц и и

По выходе из внутреннего цикла m = 6 и Flag = 1, так
как выполнялись обмены элементов массива. Начинаем
внутренний цикл для нового значения переменной m.
Последний элемент находится на своем месте.
Продолжим сортировку для m = 5.
Flag

1
0
1
1
1
1

m

m > 1 и Flag = 1?

i

a[i] > a[i +1]?

1
2
3
4
5
6

32 > 9? «Да»
32 > 30? «Да»
32 > 64? «Нет»
64 > 14? «Да»
64 > 2? «Да»
64 > 87? «Нет»

a[i]

a[i+ 1]

«Да»

5

a[1] = 9
a[2] = 30

a[2] = 32
a[3] = 32

а[4] = 14
a[5] = 2

a[5] = 64
a[6] = 64

Теперь массив имеет вид 9 30 32 14 2 64 87, и два последних элемента находятся на своих местах.
Так как были перестановки элементов, то алгоритм
продолжается до полной сортировки массива.
Второе улучшение алгоритма связано с тем, что можно установить барьер: запоминать наименьшее значение
индекса массива, для которого на текущем шаге выполнялись перестановки. Очевидно, что верхняя часть массива до элемента с этим индексом уже отсортирована, и на
следующем шаге можно прекращать сравнения значений
соседних элементов при достижении такого значения индекса.
В-третьих, метод пузырька работает неравноправно
для так называемых «легких» и «тяжелых» значений.
Один неправильно расположенный «пузырек» в «тяжелом» конце рассортированного массива всплывет на место за один проход, а неправильно расположенный элемент в «легком» конце будет опускаться на правильное
место только за один шаг на каждом проходе. Например,
массив
12 18 42 44 55 67 94 6
будет рассортирован за один проход, а сортировка массива
94 6 12 18 43 44 55 76

54

Гл а в а 1

потребует семи проходов. Эта асимметрия подсказывает
третье улучшение: менять местами направление следующих один за другим проходов. Этот улучшенный алгоритм называется шейкер-сортировкой.
Шейкер-сортировка
При ее применении на каждом следующем шаге меняется направление последовательного просмотра. В результате на одном шаге «всплывает» очередной наиболее
легкий элемент, а на другом «тонет» очередной самый тяжелый.
Обозначим left — номер левой границы сортируемой
части массива, right — номер его правой границы.
Блок 1. Устанавка номеров начальных границ
сортируемого массива.
Блок 2. Вход в цикл.
Пока левая граница не превосходит правую границу
(выход «Да» блока 2) выполняем цикл.
Блок 3. Выполнение
прохода массива вниз.
Блок 4. Сравнение соседних элементов.
Блок 5. Если a[j – 1] >
> a[j] (выход «Да» блока 4),
производим обмен этих элементов и фиксируем номер
элемента j, с которым производился обмен.
По окончании прохода
вниз (выход блока 3) сдвигаем левую границу массива (блок 6) и выполняем проход вверх (блоки 7–9).
Покажем выполнение алгоритма для массива, состоящего из 7 элементов:
32 9 30 64 14 2 87.

55

Ос н о в ы а л г о р и т м и з а ц и и

left

2

right

Выполняем проход сверху вниз.

7

k

7
6
5
4
3
2

left left?

a[j – 1] > a[j]?

Обмен

7
6
5
4
3
2
1

«Да»
«Да»
«Да»
«Да»
«Да»
«Да»
«Нет»

2 > 87 «Нет»
14 > 2 «Да»
64 > 2 «Да»
30 > 2 «Да»
9 > 2 «Да»
32 > 2 «Да»

х = 14; a[5] = 2; a[6] = 14
х = 64; a[4] = 2; a[5] = 64
х = 30; a[3] = 2; a[4] = 30
х = 9; a[2] = 2; a[3] = 9
х = 32; a[1] = 2; a[2] = 32

Массив
после
этого
прохода
имеет
вид
2 32 9 30 64 14 87.
Меняем направление движения и выполняем проход
снизу вверх.
left

3

right

7

k

j

j a[j]?

32 > 9? «Да»
х = 32; a[2] = 9; a[3] = 32
32 > 30? «Да» х = 32; a[3] = 30; a[4] = 32
32 > 64? «Нет»
64 > 14? «Да» х = 64; a[5] = 14; a[6] = 64
64 > 87? «Нет»

Теперь массив имеет вид 2 9 30 32 14 64 87.
Опять меняем направление движения. Смена направления движения выполняется до тех пор, пока выполняется условие, записанное в блоке 2.
Анализ показывает [1], что сортировка обменом и ее
небольшие улучшения хуже, чем сортировка включениями и выбором. Алгоритм шейкер-сортировки рекомендуется использовать в тех случаях, когда известно, что массив «почти упорядочен».
В 1962 г. Чарльз Хоар предложил метод сортировки
разделением. Этот метод является развитием метода простого обмена и настолько эффективен, что его стали называть методом быстрой сортировки — QuickSort.
Метод требует использования рекурсивных функций
и в рамках данного пособия не рассматривается.

56

Гл а в а 1

1.5.4. Сравнение методов сортировки

На основании анализа, приводимого в [1], можно сделать следующие выводы об эффективности рассмотренных алгоритмов сортировки.
1. Преимущество сортировки бинарными включениями по сравнению с сортировкой простыми включениями
мало, а в случае уже имеющегося порядка вообще отсутствует.
2. Сортировка методом «пузырька» является наихудшей среди сравниваемых методов. Ее улучшенная версия — шейкер-сортировка — все-таки хуже, чем сортировка простыми включениями и простым выбором.
3. Сортировка простым выбором является лучшим из
простых методов.
1.6. Алгоритмы поиска
Алгоритмы поиска занимают очень важное место среди прикладных алгоритмов, и это утверждение не нуждается в доказательстве.
Все алгоритмы поиска разбиваются на две большие
группы в зависимости от того, упорядочен или нет массив
данных, в котором проводится поиск. Рассмотрим простые алгоритмы поиска заданного элемента в одномерном
массиве данных.
1.6.1. Последовательный поиск

Наиболее примитивный, а значит, наименее эффективный способ поиска — это обычный последовательный
просмотр массива.
Пусть требуется найти элемент Х в массиве из n элементов. Значение элемента Х вводится с клавиатуры.
В данном случае известно только значение разыскиваемого элемента, никакой дополнительной информации
о нем или о массиве, в котором его надо искать, нет. Поэтому для решения задачи разумно применить очевидный
метод — последовательный перебор элементов массива
и сравнение значения очередного элемента с заданным образцом.

Ос н о в ы а л г о р и т м и з а ц и и

57

Пусть Flag = 1, если значение, равное Х, в массиве найдено, в противном случае Flag = 0. Обозначим k — индекс
найденного элемента. Элементы массива — целого типа.
Элементы массива
Присвоим начальные значения переменным Flag и k
и возьмем первый элемент массива (блок 1).
Пока не просмотрены все элементы и пока элемент, равный Х, не найден (выход «Да» блока 2), выполняем цикл.
Сравниваем очередной элемент массива со значением
Х, и если они равны (выход «Да» блока 3), то запоминаем его индекс и поднимаем Flag = 1. Если элемент еще не
найден (выход «Нет» блока 2), продолжаем просмотр элементов массива.
Выход из цикла (блок 2) возможен в двух случаях:
1) элемент найден, тогда Flag = 1, а в переменной k сохранен индекс найденного элемента;
2) элемент не найден, тогда Flag = 0, а k также равен 0.

1.6.2. Бинарный поиск

Если известно, что массив упорядочен, то можно использовать бинарный поиск.
Пусть даны целое число Х и массив размера n, отсортированный в порядке неубывания, т. е. для любого k (1 =, !=, >.
5. Разделители (знаки пунктуации), например,
[ ], ( ), { }.

64

Гл а в а 2

2.1.2. Концепция данных в языке С++

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

65

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

нии переменной происходит выделение области памяти,
размер которой определен типом переменной и в которой
хранится значение переменной.
Классификация типов данных:
• простые типы (базовые, скалярные, внутренние,
предопределенные);
• конструируемые типы (массивы, строки, структуры,
функции и др.).
Основные типы данных определены ключевыми словами, список которых приведен в таблице 2.1.
Та блица 2.1

Ключевые слова, определяющие основные типы данных
Имя
типа

char
int
float
double
void

Значение типа

Размер

Диапазон значений

Символьный (целое)
Целый
С плавающей точкой (действительный)
Двойной точности (действительный)
Любой или никакой

1 байт
4 байта

–128–127
±2 147 483 649

4 байта

3.4e-38–3.4e38

8 байт

1.7e-308–1.7e308
Не ограничен

Замечания
1. В языке С++ для определения размера памяти, занимаемой объектом, есть операция sizeof(), например,
sizeof(int); sizeof(double); sizeof(My_obj).

В качества аргумента операции можно указать имя
типа (int, double) или имя объекта (My_obj).
2. Существует специальный тип данных void, который относится к базовым, но имеет существенные особенности. Про данное такого типа говорят, что оно «не
имеет никакого типа». На самом деле тип void используется при работе с динамическими данными и может адресовать пространство произвольного размера, где можно
разместить данное любого типа. Значит, можно считать,
что данное типа void может представлять «данное любого
типа».
3. Основные типы данных можно изменить (модифицировать) с использованием вспомогательных ключевых
слов long и unsigned:

66

Гл а в а 2

• long (длинный) увеличивает объем выделяемой памяти в 2 раза;
• unsigned (без знака) не использует знаковый бит, за
счет чего хранимое значение может быть увеличено.
2.1.3. Константы в языке С++

Синтаксис языка выделяет пять типов констант: целые, действительные (вещественные), символьные, перечислимые, нулевой указатель.
Целые константы
Синтаксис языка позволяет использовать константы
трех систем счисления: десятичные, восьмеричные, шестнадцатеричные. Основание определяется префиксом в записи константы. По умолчанию основание 10, префикс 0
предваряет восьмеричную константу, префикс 0х или 0Х
предваряет шестнадцатеричную константу. В остальном
запись целых констант соответствует общепринятой.
Примеры записи целых констант приведены в таблице 2.2.
Та блица 2.2

Примеры записи целых констант
Десятичные

Восьмеричные

Шестнадцатеричные

127
–256

012
–014

0xА
–0x10

Целые числа в памяти компьютера представлены
в форме с фиксированной точкой. Эта форма позволяет
представить значение с абсолютной точностью. На рисунке 2.1 показано представление целого числа в двухбайтовой ячейке памяти.

Рис. 2.1
Представление целых чисел

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

67

Действительные константы
Вещественные (действительные) числа представлены
в памяти компьютера в форме с плавающей точкой в виде
М ⋅ 10р, где М — мантисса вещественного числа; 10 —
основание системы счисления; р — показатель десятичной степени, целое число со знаком. Основание системы
счисления в языке С++ заменяется буквой е или Е. Некоторые из составляющих могут быть опущены.
Примеры записи действительных констант:
44. 3.1415926 44.е0 .31459Е1 0.0
На рисунке 2.2 показано представление вещественного числа в четырехбайтовой ячейке памяти.

Рис. 2.2
Представление вещественных чисел

Символьные константы
Символьная константа — это лексема, которая содержит произвольный символ, заключенный в одинарные кавычки (апостроф). Хранится в одном байте памяти
в виде целого числа, определяющего целочисленный код
символа. Символьной константой может быть любой символ, изображаемый на экране в текстовом режиме, или не
имеющий отображения (пробельный символ).
Примеры символьных констант: '!', '.', 's', 'А', '+', '2'.
Существуют также управляющие символы (ESCпоследовательности), которые используются в строковых константах и переменных. Они имеют признак '\'
(backslash или обратный слеш), который используется
для указания управляющего воздействия. Вот их неполный список:
'\0' — нулевой символ;
'\n' — перевод строки;
'\r' — возврат каретки;

68

Гл а в а 2

'\t' — табуляция;
'\' — апостроф;
'\\' — обратный слэш;
'\ddd' — восьмеричное представление символьной константы, где ddd — ее восьмеричный числовой код, например, '\017' или '\233';
'\xhh' или '\Xhh' — шестнадцатеричное представление

символьной константы, где hh — ее числовой код, например, '\x0b' или '\x1F'.
Символьные константы имеют целый тип и могут использоваться в выражениях.
Строковые константы
Формально строки не относятся к константам языка
С++, а представляют отдельный тип его лексем. Строковая константа определяется как набор символов, заключенных в двойные кавычки " ".
Например,
#define STR "Программа"

В конце строковой константы добавляется нулевой символ '\0'. В тексте строки могут встретиться ESCпоследовательности, которые будут выполнять управляющее воздействие.
Например,
"\nПри выводе \nтекст может быть \nразбит на строки."
Здесь "\n" выполняет управляющее воздействие, и вы-

вод будет таким:
При выводе
текст может быть
разбит на строки.

При хранении строки все символы, в том числе управляющие, хранятся последовательно, и каждый занимает
ровно один байт.
Типы числовых констант и модификаторы типов
Для модификации типа числовых констант используются префиксы и суффиксы, добавляемые к значению
константы. Суффикс l(L) от слова long увеличивает длину данного в два раза, суффикс u(U) от слова unsigned

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

69

используется для чисел, не содержащих знак, т. е. положительных, при этом увеличивается число разрядов,
отводимых под запись числа, а значит, и его возможное
значение.
Например, длинные константы 12345l, –54321L; константы без знака 123u, 123U; шестнадцатеричная длинная
константа 0xb8000000l; восьмеричная длинная константа
без знака 012345LU.
2.1.4. Переменные в языке С++

Одним из основных понятий в языках программирования является объект. Будем использовать это понятие
как объект программного кода.
Объект — это некоторая сущность, обладающая определенным набором свойств и способная хранить свое состояние.
Объектами программного кода являются константы,
переменные, функции, типы и т. д.
Переменная — это объект, для использования которого необходимо определить три характеристики:
• имя;
• тип;
• значение (не обязательно).
Имя переменной (идентификатор) обозначает в тексте
программы величину, изменяющую свое значение. Для
каждой переменной выделяется некоторая область памяти, способная хранить ее значение. Имя позволяет осуществить доступ к области памяти, хранящей значение
переменной.
Тип переменной определяет размер выделяемой памяти и способ хранения значения (см. рис. 2.1, 2.2).
Значение переменной не определено вначале, изменяется при присваивании переменной значения.
Имя переменной (идентификатор) включает в себя латинские буквы, цифры, знак подчеркивания "_". Первым
символом должна быть буква.
Примеры идентификаторов: x1, Price, My_file1, alpha,
PI. В качестве имен рабочих переменных используются
простые имена i, j, k1, k2 и им подобные.

70

Гл а в а 2

Ограничения:
• длина имени содержит не более 32-х символов;
• в качестве имен нельзя использовать ключевые слова
языка С++, например, названия операторов for, if, do;
• в качестве имен не рекомендуется использовать имена
объектов стандартных библиотек, например, имена
функций sin(), sqrt(), pow();
• имена, которые начинаются со знака подчеркивания, зарезервированы для использования в библиотеках и компиляторах, поэтому их не следует выбирать в качестве прикладных имен, например, _acm,
_AX, _BX.
Перечень основных, не всех служебных слов приведен
в таблице 2.3.
Та блица 2.3

Служебные слова в языке C++
Типы данных

char, double, enum, float, int, long, short, struct,
signed, union, unsigned, void, typedef

Квалификаторы типа const, volatile
Классы памяти

auto, extern, register, static

, do, for, goto, if…else, return,
Названия операторов break,,continue
switch while, case, default, sizeof
Модификаторы
asm, far, interrupt, pascal и др.
Псевдопеременные
Названия регистров _AH _DS _DX и др.

Замечания
1. Рекомендуется использовать имена переменных,
отражающие их первоначальный смысл, например, Count
(количество), X_coord (координата по х), Old_value_of_long
(предыдущее значение длины).
2. Заглавные и строчные буквы считаются различными. Так, разными объектами будут переменные, имеющие имена Alpha и alpha.
3. Идентификаторы, зарезервированные в языке,
являются служебными (ключевыми) словами. Следовательно, их нельзя использовать как имена свободных
объектов программы. К ним относятся типы данных, квалификаторы типа, классы памяти, названия операторов,
модификаторы, псевдопеременные.

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

71

2.1.5. Объявление переменных

Каждая переменная должна быть объявлена в тексте
программы перед первым ее использованием. Начинающим программистам рекомендуется объявлять переменные в начале тела программы перед первым исполнимым
оператором. Синтаксис объявления переменной требует
указать ее тип и имя:
Имя_типа Имя_переменной;

Можно одновременно объявить несколько переменных, тогда в списке имен они отделяются друг от друга
запятой, например:
int a, b, c;
char ch, sh;
long l, m, k;
float x, y, z;
long double u, v

// целые со знаком
// однобайтовые символьные
// длинные целые
// вещественные
// длинные двойные

На этапе компиляции для объявленных переменных
в ОЗУ будет выделена память для записи их значений.
Имя переменной определяет адрес выделенной для нее
памяти, тип переменной определяет способ ее хранения
в памяти. Как следствие, тип определяет диапазон ее возможных значений и операции, разрешенные над этой величиной.
2.1.6. Инициализация переменных

Переменные, объявленные в программе, не имеют
значения, точнее имеют неопределенные значения. Так
как память, выделенная под запись переменных, не очищается, то значением переменной будет «мусор» из того,
что находилось в этой памяти ранее.
Инициализация — это прием, который позволяет присвоить значения переменным при их объявлении. Синтаксис инициализации:
Имя_типа Имя_переменной = Начальное_значение;

Например,
float pi=3.1415;
unsigned Year=2014;

72

Гл а в а 2

2.1.7. Именованные константы

В языке C++, кроме переменных, можно использовать
именованные константы, т. е. константы, имеющие фиксированные названия (имена). Имена могут быть произвольными идентификаторами, не совпадающими с другими именами объектов. Принято использовать в качестве
имени константы большие буквы и знаки подчеркивания,
что визуально отличает имена переменных от имен констант. Способов определения именованных констант три.
Первый способ — это константы перечисляемого типа,
имеющие синтаксис:
enum тип_перечисления {список_именованных_констант};
Здесь «тип_перечисления» — это его название, необязательный произвольный идентификатор; «список_именованных_констант» — это разделенная запятыми последова-

тельность вида:
имя_константы = значение_константы

Примеры.
enum BOOL {FALSE, TRUE};
enum DAY {SUNDAY, MONDAY, TUESDAY, WEDNESDAY,
          THURSDAY, FRIDAY, SATURDAY};
enum {ONE=1, TWO, THREE, FOUR, FIVE};
Если в списке нет элементов со знаком «=», то значе-

ния констант начинаются с 0 и увеличиваются на 1 слева
направо. Так, FALSE равно 0, TRUE равно 1. SUNDAY равно
0 и так далее, SATURDAY равно 6. Если в списке есть элементы со знаком «=», то каждый такой элемент получает
соответствующее значение, а следующие за ним увеличиваются на 1 слева направо, так, значение ONE = 1, TWO = 2,
THREE = 3, FOUR = 4, FIVE = 5.
Второй способ — это именованные константы, заданные с ключевым словом const в объявлении типа:
const Имя_типа Имя_константы = Значение_константы;
Ключевое слово const имеет более широкий смысл

и используется также в других целях, но здесь его суть
в том, что значение константы не может быть изменено.
Примеры.
const float Pi=3.1415926;
const long M=999999999L;

73

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

Попытка присвоить значение любой из констант Pi,
M будет неудачной. Визуализация имен констант с помощью использования больших букв необязательна.
Третий способ ввести именованную константу дает
препроцессорная директива #define, подробный синтаксис
и механизм выполнения которой будет рассмотрен далее.
2.2. Операции и выражения языка C++
Операция — это символ или лексема вычисления значения. Операции используются для формирования и вычисления значений выражений и для изменения значений данных.
2.2.1. Классификация операций

Классифицировать операции можно по нескольким
признакам. Приведем два варианта: по типу возвращаемого значения и по числу операндов.
1. Тип возвращаемого значения является важным
свойством любой операции. В таблице 2.4 приведена классификация операций по типу возвращаемого значения.
Та блица 2.4

Классификация операций по типу возвращаемого значения
Арифметические

+ сложение
– вычитание
* умножение
/ деление (для целых операндов — целая часть
от деления)
% остаток от деления (только для целых)

Логические

> больше
< меньше
== равно
!= не равно
>= больше или равно
0;

Логическими являются операции, возвращающие логическое значение. Их можно, в свою очередь, разбить на
две группы.
Операции отношения. Связывают данные числовых
или символьных типов и возвращают логическое значение, например:
3>1
'a'>'b'
х>=0
y!=x

// истина, не равно 0
// ложь равна 0
// зависит от х
// зависит от х и от у

Значение операции отношения может быть присвоено
целой переменной или переменной логического типа, например:
int a=5, b=2;
bool c;
c=a>b;
c=ab);
// a > b = 1, 10 * 1 = 10, значит, с = 10
c=10*(10*a0 && y>0;
// хотя бы один операнд (x % 2==0 или y % 2==0) истинен
х%2==0||y%2==0;
// значение, обратное значению операнда
// (x*x+y*y (сдвиг)
< >= (отношения)
== != (отношения)
&
^ (поразрядное исключающее или)
|
&&
||
? : (условная операция)
= *= /= %= += –= &= ^= |= =
, (операция запятая)

→
←
→
→
→
→
→
→
→
→
→
→
←
←
→

ся в первую очередь. Операция присваивания и ее клоны
младше прочих, что позволяет выполнить присваивание
только после того, как значение выражения вычислено
полностью. Операции отношения младше арифметических операций, что позволяет использовать естественную
запись логических выражений, например, x>0 && y>0.
Здесь в первую очередь вычисляются значения отношений, которые затем являются операндами конъюнкции.
Пример 2.5.
int c, a=5, b=3;
c=a++;
c=a++*3;
с=––а/2;
c=a+++b;
c=a++ + ++b;

// c=5, а=6
// c=a*3=15, потом а=7
// ––a, a=6, потом c=а/2=3
// сначала с=a+b=9, потом а++, а=7
// ++b=4, потом c=а+b=11, потом а++8

Приведение типов
Под приведением типов понимаются действия, которые компилятор выполняет в случае, когда в выражении
смешаны операнды различных типов, чего, строго говоря,
не следует допускать. Механизм приведения типов в С++
заключается в том, что при вычислении значения выраже-

80

Гл а в а 2

ния компилятор, не изменяя внутреннего представления
данных, преобразует данное «меньшего» типа к «большему», где «величину» типа определяет размер выделенной
для него памяти. Такое преобразование выполняется без
ведома программиста и может привести к потере данных.
Пример 2.6. Известно, что целое значение представлено в памяти точно, а вещественное приближенно.
int a=5, b=2;
float c;
c=a*1.5;



// в выражении операнды разных типов
// автоматически включаются механизмы
// приведения типов, с=7.5

Преобразование типов
Под преобразованием типов в выражениях понимаются действия, выполняемые при присваивании.
Пример 2.7.
int a=5, b= 2;
float c;
с=a/b;

Хочется думать, что значение с будет равно 2.5, ведь
оно вещественное, но порядок операций таков, что деление старше присваивания и оно выполняется с операндами целого типа, и его результат с = 2, т. е. приведение типа
будет выполнено только при присваивании.
Для того чтобы избежать потери информации, в выражениях следует применять операцию явного преобразования типа, синтаксис которой:
(Имя_типа) Имя_переменной;

Эта запись включается в те выражения, в которых необходимо выполнить преобразование перед вычислением.
В этом случае программист явно указывает компилятору,
что тот должен сделать.
Пример 2.8.
Перепишем пример 2.7.
int a=5, b=2;
float c;
с=(float)a/2.0; // c=5.0/2.0=2.5
// b=2/2=1
b=(int)c/b;

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

81

При выполнении присваивания, если типы левой
и правой частей выражения не совпадают, происходит неявное преобразование. Компилятор С++ всегда пытается
это сделать, и упрощенно можно считать, что преобразование происходит без потери данных от меньшего типа
к большему, например от int к float или от char к int, и с потерей данных из большего типа к меньшему, например от
float к int. Это легко понять, если вспомнить, что тип данного — это объем занятой им памяти.
Рекомендуется строго относиться к типам данных, не
смешивать типы в выражениях, следить, чтобы тип левого операнда присваивания соответствовал типу выражения правой части.
2.3. Структура и компоненты простой
программы на языке C++
2.3.1. Функция main()

В современных средах программирования программа — это «проект». В состав проекта входят один или нескольких файлов с расширением «.с» или «.сpp». Все исходные файлы компилируются и собираются совместно.
Простейшие программы содержатся в одном текстовом
файле.
Программа может состоять из одной или нескольких
функций. Функция — это самостоятельный именованный
алгоритм решения некоторой законченной задачи. Одна
из функций должна иметь имя main(). С нее всегда начинается выполнение программы. Любая функция, кроме
main(), может быть вызвана из другой функции. При вызове функции могут быть переданы параметры (данные).
По окончании выполнения функции в вызывающую
функцию может быть возвращено значение (результат),
а может не быть возвращено ничего. Примером обращения к функциям являются библиотечные функции, например, sin(x), fabs(a).
Функция обладает типом, соответствующим возвращаемому значению. Если функция ничего не возвращает,

82

Гл а в а 2

ее тип void. Если функция не имеет аргументов, вместо
них в списке параметров записывается слово void.
Пример 2.9.
void main(void)
main()



// не имеет типа и не имеет параметров
// тип функции по умолчанию будет int,
// аргументов нет, значит, их может быть
// произвольное число

Пример функций, не возвращающих значения —
printf(), scanf().
2.3.2. Комментарии

Комментарии предназначены для записи пояснений
и примечаний к тексту программы и не влияют на выполнение программы. Они записываются на родном языке
программиста.
В языке С++ существуют два вида комментариев.
1. Многострочный комментарий записывается в любом
*/. Перевоместе текста программы в скобках вида /*
дит в разряд примечаний весь текст, заключенный между
ними. Такие комментарии удобны при отладке программы,
чтобы исключить фрагмент кода, или для пояснений.
2. Однострочный комментарий записывается в любой
строке программы после сочетания символов //. Комментирует весь текст до окончания строки. Используется для
пояснений к строкам.
Использование комментариев является признаком
хорошего стиля программирования. Так, необходимы
пояснения к смыслу объявленных объектов программного кода, к используемым алгоритмам, к структуре программного кода.
2.3.3. Структура файла программы из одной функции.
Блок операторов

Код программы, которая состоит из одной функции
main(), обычно содержит следующие составляющие, хотя

почти все они могут отсутствовать:
#Директивы препроцессора

// начинаются с символа # и
// записываются в одну строку
Тип_функции main(параметры) // заголовок функции

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

83

{ // блок тела функции;
определения объектов;
исполняемые операторы;
return выражение;
// если функция возвращает

значение
}

В C++ объявление переменной (объекта) возможно
не только в начале программы, но и в любом месте текста до первого обращения к ней. Областью действия объекта является только непосредственно охватывающий
его блок. Как правило, так объявляют рабочие переменные.
Блок (операторов) — это произвольная последовательность определений и операторов, заключенная в фигурные скобки:
{
// блок;
}

Блок используется для укрупнения структуры программы. Точка с запятой в конце блока не ставится.
Текст программы на языке C++ обладает структурой.
Существует система правил корректной записи текста
программ, которые просты, но улучшают зрительное восприятие и понимание кода.
1. Каждый оператор заканчивается знаком «;». Обычная ошибка начинающего — это знак «;», завершающий
заголовки функций или операторов цикла. В первом случае синтаксическая ошибка распознается как отсутствие
тела функции, во втором случае телом цикла является пустой оператор, что синтаксической ошибкой не является,
и программа выполняется.
2. Каждый оператор записывается в одну строку. Такая запись позволяет структурировать текст программы,
наглядно видеть ее алгоритм, и облегчает отладку при пошаговом исполнении.
3. Блок, т. е. произвольный фрагмент текста, заключенный в фигурные скобки {}, размещается в любом месте
программы. Использование блоков позволяет укрупнить
структуру алгоритма.

84

Гл а в а 2

4. Структура программы подчеркивается отступами.
Это позволяет визуально показать блоки, составляющие
структуру алгоритма.
5. Необходимо использовать разумное количество
комментариев.
6. Имена объектов программы выбираются осмысленно. Каждое имя подчеркивает назначение и логику
объекта, например, имена библиотечных функций sin(),
abs(), printf() и прочих говорят сами за себя. Имена объектов, введенные программистом, подчеркивают их абстрактный смысл, например, Count, Square, Point.x, Point.y
и т. д.
7. Пробелы в тексте являются значащими только в составе текстовых констант. В коде программы пробелы отделяют друг от друга элементы текста. В остальных случаях их использование произвольно, например, лишние
пробелы улучшают читабельность программы.
2.3.4. Директивы препроцессорной обработки

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

Механизм действия директивы — макроподстановки,
т. е. препроцессор сканирует весь текст программы и выполняет замены в тексте программы, везде вместо «Имени» подставляя «Выражение».
Замечание. Имена define определенных констант записываются большими буквами, чтобы визуально отличить их от имен переменных и других объектов.

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

85

Пример 2.10.
#define N 10
// по всему тексту вместо N число10
#define PI 3.1416926 // вместо PI его числовое значение
#define STR "Строковая константа, подставляется в текст\n"
Директива #define может не только определить имено-

ванную константу, но и выполнить макроподстановки.
Пример 2.11.
#define N1 N+1
#define int long


// вместо N1 текст N+1
// в тексте все описания int
// заменятся на long

Если в замещаемом имени есть скобки, следующие за
именем без пробела, то это макроопределение с параметрами:
#define Имя(список_параметров) Выражение

Например,
#define Cube(x) x*x*x

Имя здесь играет роль имени макроопределения,
а параметров может быть несколько, тогда они отделяются запятыми. Между именем и списком параметров
не должно быть пробела. Такое макроопределение может использоваться как функция, хотя макроподстановки не заменяют функции, и иногда могут привести
к ошибкам.
Пример 2.12.
#define Cube(x) x*x*x
// макроопределение возведения в степень
#include
void main(void)
{
int а=2;
printf("%d %d", a, Cube(a)); // выведено 2 8
}

Директива #include
Используется для замены в тексте путем добавления
текста из других файлов в точку нахождения #include.
Синтаксис.
#include “filename”
#include

86

Гл а в а 2

Механизм действия — включение текста указанного
файла в текущее место в программе. Включаемые файлы
называются заголовочными и содержат информацию, которая для программы глобальна.
Директива #include "filename" осуществляет поиск файла сначала в текущем каталоге, а затем в системных каталогах. Так подключаются личные файлы программиста,
содержащие произвольные тексты, например, определения констант, объявления или описания функций.
Директива #include осуществляет поиск
файла только в системных каталогах. Так подключаются
стандартные заголовочные файлы, поставляемые в комплекте со стандартными библиотеками функций.
Каждая библиотечная функция имеет свое описание
(прототип). Кроме того, в заголовочных файлах описаны
многие константы, определения типов и макроподстановки. Например, стандартный заголовочный файл
содержит описания библиотечных функций ввода и вывода, подключается при использовании математических функций. Их описание содержится в справочной
системе. Следует понимать, что использование #include
не подключает к программе соответствующую библиотеку, а только включает в текст программы на глобальном
уровне все нужные описания и объявления. Сами библиотечные функции подключаются к программе в виде объектного кода на этапе компоновки, когда компоновщик
обрабатывает все вызовы функций, определяет, какие
потребуются программе, и собирает исполнимый файл,
включая в него объектные (компилированные) коды тех
функций, к которым выполняется обращение.
2.3.5. Ввод и вывод данных. Начальные сведения

В этом подпараграфе описаны инструменты вводавывода данных в классическом языке С с использованием
библиотеки stdio.h (standard input output library).
Ввести данное — означает присвоить произвольное
значение переменной во время выполнения программы.
Вывести данное — означает напечатать на экране значение переменной при выполнении программы.

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

87

Простейший из способов обмена данных — это форматированный ввод-вывод с определением правил размещения данных во входном/выходном потоке. Для реализации такого обмена к программе директивой #include
подключается библиотека stdio.h.
Для ввода значения данного с клавиатуры с эхо повтором на экране используется функция scanf(), синтаксис
которой:
scanf("форматная строка", список_ввода);
Здесь «список_ввода» — имена переменных, значения

которых будут введены с клавиатуры при выполнении
функции scanf(). Имена переменных предваряются символом «&», который является признаком адресной операции и означает, что введенное значение пересылается
по адресу, определенному именем переменной. При вводе
данные отделяются пробелами или нажатием клавиши
[Enter].
Для вывода значения данного на экран используется
функция printf(), синтаксис которой:
printf("форматная строка", список_вывода);
Здесь «список_вывода» — список имен переменных

и выражений (в том числе констант), значения которых
появятся на экране при выполнении функции printf().
Форматная (управляющая) строка — это строка символов внутри двойных кавычек, содержащая управляющие символы и текст. При вводе данных функция scanf()
читает посимвольно текст из входного потока, распознает
лексемы и преобразует их в машинное представление в соответствии с признаком формата, сопоставленного переменной, ожидающей данное. При выводе функция printf()
берет машинное представление значения переменной, соответственно признаку формата преобразует в текстовое
представление и выводит на экран.
Число управляющих символов равно числу объектов
в списке ввода-вывода. Управляющий символ имеет признак % и может иметь одно из следующих значений:
%d — ввод-вывод целого десятичного числа
(int),
%u — ввод-вывод целого без знака
(unsigned),
%f — ввод-вывод числа с плавающей точкой
(float),

88

Гл а в а 2

%lf — ввод-вывод числа с плавающей точкой
(double),
%e — ввод-вывод числа в экспоненциальной форме

(double и float),
%c — ввод-вывод символа
(char),
%l — ввод-вывод длинного значения
(long),
и др.
При вводе и выводе необходимо строгое соответствие
типа данного управляющему символу формата.
Пример 2.13.
Приведем пример форматированного ввода и вывода:
#include
void main(void)
{
int my_int;
float my_float;
printf("\nВведите целое и дробное число\n");
scanf("%d", &my_int);
scanf("%f", &my_float);
printf("%d %f", my_int, my_float);
}
При запуске программы функция printf() выведет на

экран строку — приглашение к вводу данных, затем при
выполнении каждой функции scanf() будет ожидать ввода
данных. Пользователь должен ввести требуемое количество данных, отделяя их пробелами или нажатием клавиши
[Enter]. При завершении ввода данные тут же будут выведены на экран самым примитивным образом. Так, если ввести
целое 5 и дробное 9.9, то строка вывода будет иметь вид:
59.900000

Поскольку при вводе данного функция scanf() находится в состоянии ожидания ввода, рекомендуется каждый ввод предварять строкой, выводящей на экран приглашение к вводу данных, в котором пользователю подробно объясняют, что и как он должен сделать, чтобы
правильно ввести данные, например:
printf("Введите координаты центра и радиус круга\n");
scanf("%f%f%f", &x, &y, &R);

При выводе данных для улучшения вывода рекомендуется использовать некоторые приемы.

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

89

1. Управляющие символы, например:
"\n" для перевода строки при выводе;
"\t" для выполнения табуляции.
2. Произвольный текст в форматной строке для приглашения на ввод данного и для пояснений при выводе,
например, функция вывода может быть записана так:
printf("Целое = %d, Вещественное = %f\n", my_int, my_float);

Пробелы в строке текста являются значащими. Теперь, если ввести целое 5 и дробное 9.9, то строка вывода
будет иметь вид:
Целое = 5, Вещественное = 9.900000

3. Модификаторы форматов. Они используются для
оформления вывода. По умолчанию (без модификаторов)
данные выводятся в поле минимальной ширины с точностью 6 знаков после запятой, число прижимается к правому краю поля. Этим выводом можно управлять:
• можно задать ширину поля как строку цифр, определяющую наименьший размер поля вывода, которое
будет игнорировано, если число не входит в поле;
• можно задать точность вывода для вещественных чисел: это две цифры, определяющие общий размер поля
вывода и число знаков после запятой.
В следующих примерах обозначим знаком  пробелы,
которые будут значимыми в строке вывода.
Пример 2.14.
printf("Целое=%4d, Вещественное=%5.2f\n", my_int, my_float);

Если ввести значения 10 и 2.3, то строка вывода будет
иметь вид:
Целое = 10, Вещественное = 9.90

Если ввести значения 19951 и 12.9999, то строка вывода будет иметь вид:
Целое = 19951, Вещественное = 13.00

Можно сделать вывод, что число округляется.
4. Знак минус используется для выравнивания числа
влево внутри поля вывода:
printf("Целое=%–4d, Вещественное=%–5.2f\n", my_int,
my_float);

Если ввести значения 2 и 2.36666, то строка вывода
будет иметь вид:

90

Гл а в а 2

Целое = 2, Вещественное = 2.37

Если ввести значения –1999 и 12.9999, то строка вывода будет иметь вид:
Целое = –1999, Вещественное = 13.00

Пример 2.15. Приведем пример использования форматированного ввода-вывода.
В комментариях к строкам приведен вид выводимого
данного и пояснения.
#include
#define STR "Программа" // для иллюстрации вывода строк
void main (void)
{
// вывод целого числа 336
printf("%d\n", 336); // 336
printf("%2d\n", 336); // 336 формат 2d игнорируется
printf("%8d\n", 336); // 336 ширина поля 8
printf("%-8d\n", 336); // 336 прижато влево
printf("\n");
// пропуск строки при выводе
// вывод вещественного числа 12.345
printf("%f\n",
12.345); // 12.345000
printf("%e\n",
12.345); // 1.234500е+01
printf("%10.1f\n", 12.345); // 12.3
printf("%–12.1f\n", 12.345); // 12.3
printf("\n");
// вывод строки символов по формату s
printf("%s\n",
STR);
// Программа
printf("%12s\n",
STR);
// Программа
printf("%12.5s\n", STR);
// Прогр
printf("%-12.5s\n", STR);
// Прогр
printf("\n");
}

2.4. Управляющие конструкции языка C++
Оператор — это предложение, описывающее одно
действие по обработке данных или действия программы
на очередном шаге ее исполнения.

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

91

2.4.1. Классификация операторов

Все операторы языка С++ можно разделить на две
группы.
1. Операторы преобразования данных.
2. Операторы управления ходом выполнения программы.
Это разделение соотносится с определением алгоритма.
Операторами преобразования данных являются выражения. Оператора присваивания в языке С++ нет, его
заменяет выражение, в составе которого есть операция
присваивания.
Примеры операторов изменения данных:
y+4;
x=y+4;
x++;

// выражение
// выражение присваивания
// выражение – оператор

Операция присваивания правоассоциативна, поэтому
допускается запись цепочек присваиваний, например:
x=y=z=1;

// каждая переменная будет равна 1

К операторам преобразования данных можно отнести
оператор обращения к функции (вызов функции). Его
операцией являются круглые скобки, а операндами —
имя функции и список параметров, например:
scanf("%d%f", &a, &b);
printf("a=%d, b=%f", &a, &b);

При выполнении вызова функции scanf() значения
переменных a, b будут изменены. При выполнении вызова функции printf() выполняются действия попреобразованию данных из внутреннего представления в текстовое,
пригодное для вывода на экран.
Операторы управления предназначены для управления ходом выполнения программы. Обычно операторы
программы выполняются в том порядке, в котором записаны. Поскольку каждый оператор выполняет одно действие по обработке данных, тем самым управляя работой
компьютера, то порядок выполнения выражений называют потоком управления. Поток управления редко бывает
линейным. Изменить направление потока управления позволяют операторы управления, перечисленные в таблице 2.8.

92

Гл а в а 2
Та блица 2.8

Операторы управления C++
Ключевое
слово

Название оператора

Составной оператор
Условный оператор
Оператор цикла с проверкой условия до выполнения
Оператор цикла с проверкой условия после выполнения
Оператор цикла типа «прогрессия»
Оператор прерывания
Оператор продолжения
Оператор переключатель
Оператор перехода

{…}
if
while
do… while
for
break
continue
switch
goto

При описании каждого оператора языка С++ будем
придерживаться следующей схемы:
• назначение;
• синтаксис;
• семантика, механизм исполнения;
• пример;
• особенности.
2.4.2. Оператор присваивания

Назначение. Изменение значения данного в соответствии с выражением правой части.
Синтаксис.
Имя_переменной = Выражение;
Имя_переменной = (тип) Выражение;

// форма 1
// форма 2

Выполнение. В первую очередь вычисляется выражение правой части, во вторую вычисленное значение присваивается переменной левой части.
Примеры:
x=y=0;
x++;
y=sin(2*PI*x);
y+=0.2;

Особенности. Если в выражении встречаются операнды разных типов, то при вычислении значения выражения происходит неявное преобразование типов, как
правило, к большему типу. При несоответствии типа вы-

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

93

ражения правой части типу переменной в левой части
происходит приведение типа выражения к типу переменной, при этом неизбежна потеря данных при приведении
от большего типа к меньшему.
Приведем пример реализации линейного алгоритма
вычисления высот треугольника, блок-схема которого
приведена в примере 1.1 (глава 1).
Пример 2.16.
// вычислить высоты треугольника со сторонами a, b, c
#include
#include
#include
void main(void)
{
double a,b,c;
printf("Введите стороны треугольника");
scanf("%lf%lf%lf", &a, &b, &c);
double p,t;
// объявить переменные можно там, где они
// понадобились
double Ha,Hb,Hc;
p=0.5*(a+b+c);
// нет проверки условия существования треугольника
t=2*sqrt(p*(p-a)*(p-b)*(p-c));
Ha=t/a;
Hb=t/b;
Hc=t/c;
printf("Значения высот треугольника:\n
 Ha=%6.2lf,Hb=%6.2lf, Hc=%6.2lf\n",Ha, Hb, Hc);
}
2.4.3. Составной оператор

К составным операторам относятся собственно составные операторы и блоки. В обоих случаях это последовательность операторов, заключенная в фигурные скобки.
Блок отличается тем, что в его состав входят описания
каких-либо объектов программы.
Блоком является тело любой функции, в том числе
функция main().

94

Гл а в а 2

Назначение. Составной оператор используется для
объединения нескольких операторов в один. Составной
оператор, например, формирует ветвь условного оператора или тело цикла в операторах цикла.
Пример 2.17.
{// это составной оператор
n++;
S+=n;
}

{// это блок
int n=0;
n++;
S+=n;
}

2.4.4. Условный оператор if

В п. 1.2.2 (глава 1) приведены блок-схемы структуры
если — то — иначе с полным и неполным ветвлением.
В языке С++ эта структура реализуется условным оператором if.
Назначение. Выбор одного из двух возможных путей
исполнения программы в зависимости от условий, сложившихся при выполнении.
Для проверки условия формулируется некоторое
утверждение, которое может быть истинным или ложным. Это логическое выражение, которое может принять
одно из значений True либо False. В языке С++ они имеют форму выражений целого типа, принимая значения
«не 0», что соответствует истине, либо «0», что соответствует лжи, либо типа bool.
Синтаксис. Синтаксис условного оператора имеет две
формы.
Сокращенная форма.
if (Логическое_выражение)
Оператор;
Здесь «Логическое_выражение» — любое выражение
типа int или bool.
«Оператор» — это один или несколько операторов,

в общем случае составной оператор. Логическое выражение записывается в скобках.
Полная форма.
if(Логическое_выражение)

Ос н о в ы п р о г р а м м и р о ва н и я н а я з ы к е C + +

95

 Оператор1;
else
 Оператор2;
Здесь «Логическое_выражение» имеет тот же смысл,
что и ранее, а «Оператор1" или «Оператор2" — это, в общем

случае, блок.
Выполнение.
1. Вычисляется значение логического выражения.
2. Если оно не равно 0, выполняется «Оператор1",
а если оно равно 0, выполняется «Оператор2" (или ничего
в первой форме).
Пример 2.18. Первая форма условного оператора.
Стоимость товара равна произведению цены на количество. Если есть скидка, то стоимость уменьшается на
величину discount. Вычислить стоимость.
pay=cost*count;
// общая формула
// если есть скидка, то стоимость
if(discount!=0)

// уменьшается
pay=pay–(pay*discount)/100;
// вывод pay в любом случае
printf("Стоимость = %6.2f\n", pay);

Пример 2.19. Вторая форма условного оператора.
Оплата труда работника — это произведение количества отработанных часов на стоимость часа. Если отработано более 40 ч, то за каждый час работодатель платит
в полтора раза больше.
if(hour= 40
// печать одинакова
printf("К оплате %6.2f рублей.\n", pay);

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

96

Гл а в а 2

if(hour 20.
Блок-схема алгоритма решения задачи приведена
в примере 1.2 (глава 1).
void main(void)
{
float a,b,c;
float x,y;
printf("Введите параметры функции");
scanf("%f%f%f",&a,&b,&c);
printf("Введите аргумент функции");
scanf("%f",&x);
if(x\n ");
scanf("%d", &N);
// инициализация переменной S нулем обязательна
S=0;
// к нулю готовимся прибавить первое слагаемое
n=1;
do
{
   S+=n; // тело цикла
   n++; // приращение параметра цикла
} while(neps);
// еps достаточно мало
printf("Слагаемых %5.0f, Сумма %f8.5", n, S);
} // End of main

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

245

За д ач и и у п р аж н е н и я

Пример 4.3. Пусть требуется вычислить сумму ряда
по формуле
S=x+

x x x
x
+ + + ... + + ...
2 3 4
n

Очевидно, что значение суммы будет зависеть от значения x. Добавить сложность к этому алгоритму может
одно из следующих условий.
1. Вычислить суммы для различного числа слагаемых
(n1, n2, n3 и т. д.) в арифметическом цикле или цикле,
управляемом событием.
2. Вычислить суммы для различных значений x, например, для x ∈ [x0, xn] с шагом ∆x, или вводимых с клавиатуры.
3. Вычислить суммы для различных степеней точности, например, для ε ∈ [ε0, εn] в итерационном цикле.
Рассмотрим второй случай. Сумма заново вычисляется для каждого значения x, поэтому цикл вычисления
суммы должен быть внутренним, а цикл изменения переменной x внешним. Управляющей переменной внутреннего цикла является номер слагаемого n ∈ [1, N], ее шаг
равен 1. Число повторений N должно быть известно, его
можно ввести. Внешним циклом управляет переменная
x, которая изменяется по закону арифметического цикла,
пусть для определенности x ∈ [0; 1], шаг 0,1.
void main(void)
{
float x;
// параметр внешнего цикла
float n;
// параметр внутреннего цикла
float S;
int N; // число слагаемых, включенных в сумму
printf("Вычисление суммы чисел натурального ряда.\n");
printf("Введите число слагаемых>1\n");
scanf("%d", &N);
// управление внешним циклом
for(x=0; x