Алгоритмизация. Введение в язык программирования С++

Алгоритмизация. Введение в язык
программирования С++

2-е издание, исправленное

Белоцерковская И.Е.
Галина Н.В.
Катаева Л.Ю.

Национальный Открытый Университет “ИНТУИТ”
2016

2

Алгоритмизация. Введение в язык программирования С++/ И.Е. Белоцерковская, Н.В. Галина, Л.Ю.
Катаева - М.: Национальный Открытый Университет “ИНТУИТ”, 2016

Пособие ознакомит студентов с понятием алгоритма, его видами. В нем изложены принципы
использования и реализации разных видов алгоритмов графически и программно на языке
программирования С++.
Данный курс предназначен для студентов первых курсов непрофильных технических
специальностей, а также для учеников старших классов общеобразовательных школ и школ с
углубленным изучением математики и информатики. Особенностью курса является то, что язык
программирования С++ рассматривается как алгоритмический, а не как объектно-ориентированный.
Данный курс является необходимой базой для дальнейшего изучения языка С++. При создании курса
использовались программы Borland C++ и Microsoft Visual Studio, описаны принципы работы с этими
программами. Каждая задача рассмотрена в обеих средах, даются подробные комментарии и
результаты выполнения программ. После каждой лекции приводятся задания для самостоятельного
выполнения.

(c) ООО “ИНТУИТ.РУ”, 2015-2016
(c) Белоцерковская И.Е., Галина Н.В., Катаева Л.Ю., 2015-2016

3

Понятие алгоритма. Виды алгоритмов

Алгоритм является базовым понятием для тех, кто хочет начать программировать на
любом языке программирования. Любая задача может быть формализована
алгоритмически. Чтобы понять, с чего начать, рассмотрим основные виды алгоритмов.
Цель данной лекции – ознакомить студентов с понятием алгоритма; показать, что такая
абстрактная вещь как алгоритм окружает нас в повседневной жизни.

Существует несколько определений понятия алгоритма. Приведем два самых
распространенных.

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

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

Вообще говоря, первое определение не передает полноты смысла понятия алгоритм.
Используемое слово “последовательность” сужает данное понятие, т.к. действия не
обязательно должны следовать друг за другом – они могут повторяться или содержать
условие.

Свойства алгоритмов:

1. Дискретность (от лат. discretus — разделенный, прерывистый) – это разбиение

алгоритма на ряд отдельных законченных действий (шагов).

2. Детерминированность (от лат. determinate — определенность, точность) - любое

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

3. Конечность – каждое действие в отдельности и алгоритм в целом должны иметь

возможность завершения.

4. Массовость – один и тот же алгоритм можно использовать с разными исходными

данными.

5. Результативность – алгоритм должен приводить к достоверному решению.

Основная цель алгоритмизации – составление алгоритмов для ЭВМ с дальнейшим
решением задачи на ЭВМ.

Примеры алгоритма:

1. Любой прибор, купленный в магазине, снабжается инструкцией по его

использованию. Данная инструкция и является алгоритмом для правильной
эксплуатации прибора.

2. Каждый шофер должен знать правила дорожного движения. Правила дорожного

4

движения однозначно регламентируют поведение каждого участника движения.
Зная эти правила, шофер должен действовать по определенному алгоритму.

3. Массовый выпуск автомобилей стал возможен только тогда, когда был придуман

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

Существует несколько способов записи алгоритмов. На практике наиболее
распространены следующие формы представления алгоритмов:

1. словесная (запись на естественном языке);
2. псевдокоды (полуформализованные описания алгоритмов на условном

алгоритмическом языке, включающие в себя как элементы языка
программирования, так и фразы естественного языка, общепринятые
математические обозначения и др.);

3. графическая (изображения из графических символов – блок-схема);
4. программная (тексты на языках программирования – код программы).

Рассмотрим подробно каждый вариант записи алгоритмов на примере следующей
задачи. Требуется найти частное двух чисел.

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

Пример словесной записи:

1. задать два числа, являющиеся делимым и делителем;
2. проверить, равняется ли делитель нулю;
3. если делитель не равен нулю, то найти частное, записать его в ответ;
4. если делитель равен нулю, то в ответ записать “нет решения”.

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

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

5

этом получает человек, который выполняет команды согласно псевдокоду.

Приведем основные управляющие структуры псевдокода в табл. 1.1.

Таблица 1.1. Базовые управляющие

структуры псевдокода

Название структуры
Псевдокод

Присваивание

переменная = число

Ввод

ввод(переменная)

Вывод

вывод(переменная)
вывод("фраза")

Ветвление

если условие 
 
то действие1 

иначе действие2

Повторение

пока условие
начало пока
 
действие

конец пока

Пример псевдокода:

алг Нахождение частного двух чисел
начало
вывод ("задайте делимое и делитель")
ввод (делимое, делитель)
если делитель ≠ 0
то частное = делимое / делитель
 
вывод(частное)

иначе вывод("нет решения")
кон алг Нахождение частного двух чисел

В данном примере используется три переменные: делимое, делитель и частное.
Делимое и делитель задаются исполнителем произвольными числами. Частное
считается лишь в том случае, если делитель не равен нулю.

Графическая реализация алгоритма представляет собой блок-схему. Блок-схема
состоит из блоков определенной формы, соединенных стрелками. Ответ при этом
получает человек, который выполняет команды согласно блок-схеме. Более подробно о
блок-схемах будет рассказано в Лекции 2.

6

Программная реализация алгоритма – это компьютерная программа, написанная на
каком-либо алгоритмическом языке программирования, например: С++, Pascal, Basic и
т.д. Программа состоит из команд определенного языка программирования. Отметим,
что одна и та же блок-схема может быть реализована на разных языках
программирования. Ответ при этом получает ЭВМ, а не человек. Более подробно о
составлении программ на языке программирования С++ смотреть Лекцию 3.

Различают три основных вида алгоритмов:

1. линейный алгоритм,
2. разветвляющийся алгоритм,
3. циклический алгоритм.

Линейный алгоритм – это алгоритм, в котором действия выполняются однократно и
строго последовательно.

Самый простой пример реализации линейного алгоритма – путь из университета
домой.

Словесный способ записи данного алгоритма:

1. выйти из университета на остановку;
2. подождать нужный автобус;
3. сесть на нужный автобус;
4. оплатить проезд;
5. выйти на требуемой остановке;
6. дойти до дома.

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

Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от условия
выполняется либо одна, либо другая последовательность действий.

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

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

Циклический алгоритм – это алгоритм, команды которого повторяются некое
количество раз подряд.

Самый простой пример реализации циклического алгоритма – при чтении книги будут
повторяться одни и те же действия: прочитать страницу, перелистнуть и т.д.

Более подробно о линейном, разветвляющемся и циклическом алгоритмах смотреть
Лекцию 2.

7

Краткие итоги

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

Вопросы

1. Что такое алгоритм?
2. В чем состоит задача алгоритмизации?
3. Какими свойствами обладает алгоритм?
4. Какие виды алгоритма бывают?

Упражнения

1. Составьте алгоритмы по походу в магазин за яблоками. Используйте линейный и

разветвляющийся алгоритмы. Реализуйте их словесно.

2. Составьте алгоритм по нахождению корней квадратного уравнения через

дискриминант. Используйте разветвляющийся алгоритм. Реализуйте его
псевдокодом.

8

Блок-схемы. Графическая реализация алгоритмов

Блок-схемы представляют собой наглядную реализацию алгоритма. Рассмотрим, как
графически представлять разные виды алгоритмов на математических задачах и
ситуациях из жизни. Цель данной лекции – ознакомить студентов с понятием блок-
схемы; показать основные конструкции реализации разных видов алгоритма; показать
принципы проверки блок-схем и получения по ним ответа.

Занятие 1. Понятие блок-схемы. Основные виды блоков

Блок-схема – это графическая реализация алгоритма.

Блок-схема представляет собой удобный и наглядный способ записи алгоритма.

Блок-схема состоит из функциональных блоков разной формы, связанных между собой
стрелками. В каждом блоке описывается одно или несколько действий. Основные виды
блоков представлены в табл. 2.1.

Таблица 2.1. Виды блоков

Форма блока
Назначение блока

начало и конец блок-схемы

блок ввода данных

блок выполнения действия

блок условия

блок вывода данных

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

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

Математические выражения и логические высказывания должны быть описаны

9

математическим языком, т.к. блок-схема не должна иметь привязки к какому-то
определенному языку программирования. Одна и таже блок-схема может быть
реализована в программах на разных языках программирования. К примеру, функция в
блок-схеме будет выглядеть таким образом: 
, а не таким образом: 
.

Все три вида алгоритмов реализуются в блок-схеме названными выше типами блоков.
К примеру, в линейном алгоритме могут присутствовать все блоки, кроме блока
условия. В разветвляющемся и циклическом алгоритмах могут быть использованы все
названные виды блоков, но обязательным является блок условия. Внутри блока
условия записывается условие, про которое можно однозначно ответить, истинно оно
или ложно Если условие истинно, то выполняются действия, соответствующие стрелке
“да”, иначе стрелке “нет”.

Занятие 2. Графическая реализация линейного алгоритма

Приведем простейшие примеры, соответствующие линейному алгоритму.

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

Решение. Чтобы позвонить по городскому телефону, нужно знать номер Пети. Значит,
сначала надо найти номер телефона Пети, набрать его и поговорить с Петей. На этом
цель Васи (поговорить с Петей по телефону) будет достигнута. Результат блок схемы
представлен на рис. 2.1.

Рис. 2.1.  Блок-схема для примера 1

Пример 2. Ученику требуется купить учебник. Составить блок-схему, описывающую
порядок действий ученика.

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

10