Алгоритмизация и программирование

-¬¡ ©¡¡
«¬ª°¡--¤ª©œ§¸©ª¡
ª¬œ£ªžœ©¤¡
-ÁÌÄÛ
ÊÍÉʾ¼É¼
¾

¿ÊÀÏ
С.А. Канцедал
АЛГОРИТМИЗАЦИЯ 
И ПРОГРАММИРОВАНИЕ
Допущено Министерством образования и науки Российской Федерации 
в качестве учебного пособия для студентов учреждений среднего 
профессионального образования, обучающихся по группе специальностей 
«Информатика и вычислительная техника»
Москва 
ИД «ФОРУМ» — ИНФРА-М
2021

УДК  519.6(075.32) 
ББК 32.973-018я723 
 
К19
Р е ц е н з е н т ы:
зав. кафедрой «Информатика и программное обеспечение вычислительных систем» Московского государственного института электронной техники (технического университета), доктор технических наук, 
профессор Л.Г. Гагарина; зав. кафедрой «Программное обеспечение 
вычислительной техники» Житомирского государственного технологического университета, кандидат технических наук А.М. Данильченко
Канцедал С.А.
К19  
Алгоритмизация и программирование : учебное пособие / C.А. Канцедал. — Москва : ИД «ФОРУМ» : ИНФРА-М, 2021. — 352 с. — (Среднее профессиональное образование).
 
ISBN 978-5-8199-0727-6 (ИД «ФОРУМ») 
ISBN 978-5-16-013490-1 (ИНФРА-М, print) 
ISBN 978-5-16-100506-4 (ИНФРА-М, online)
В учебнике рассмотрены основы проектирования технологических процессов, а также технологического оснащения применительно к производству летательных аппаратов. Описаны специфика этой отрасли машиностроения, технологическая подготовка серийного производства и методика 
разработки оптимального варианта технологических процессов. Приведены основные положения о надежности и технологичности машин, описаны методы их достижения. Указаны основные направления обеспечения 
экономической эффективности технологических процессов — снижения 
себестоимости машин, увеличения производительности труда и сроков 
окупаемости капитальных вложений на технологическое оснащение.
Для студентов учреждений среднего профессионального образования 
по специальности «Производство летательных аппаратов».
УДК 519.6(075.32) 
ББК 32.973-018я723
ISBN 978-5-8199-0727-6 (ИД «ФОРУМ») 
ISBN 978-5-16-013490-1 (ИНФРА-М, print) 
ISBN 978-5-16-100506-4 (ИНФРА-М, online)
© Канцедал С.А., 2014 
© ИД «ФОРУМ», 2014

Предисловие
Программирование для компьютеров — это профессиональное занятие, состоящее в разработке программ обработки информации на электронных вычислительных машинах (ЭВМ). На
заре
интенсивного
строительства
и
использования
ЭВМ
—
в США в середине 1940-х, а в СССР в середине 1950-х годов прошлого столетия — специалистов, составляющих программы для
компьютеров, стали называть программистами. Следует однако
отметить, что этот вид деятельности возник значительно раньше,
когда более чем сто пятьдесят лет назад первые две программы
для аналитической счетной машины Ч. Бебиджа составила Ада
Лавлейс, дочь поэта Байрона, известный в то время математик.
В память об этой женщине и этом событии универсальный язык
программирования, созданный по заказу военного ведомства
США в начале 80-х годов прошлого столетия, был назван Ада.
Программирование как занятие сочетает в себе и элементы
ремесла, и элементы творчества, что, впрочем, свойственно многим профессиям. Возможность творческого подхода обусловлена
прежде всего тем, что для одной и той же задачи обработки информации можно составить разные программы. Каждая из этих
программ является плодом как воображаемого метода решения
задачи, так и разнообразных манипуляций элементарными действиями — командами компьютера. Именно эти обстоятельства
порождают возможность при составлении программы проявить
фантазию, нетривиальную логику, специфику мышления и другие черты, свойственные творческим процессам. В то же время
программист ограничен конечным набором четких, однозначно
выполняемых команд компьютера, применение которых строго
оговорено и не допускает никаких других толкований. Поэтому,
располагая методом решения задачи и правильно применяя эти
команды, всегда можно составить какую-либо программу, что и
вносит рутину в процесс программирования.
В настоящее время программированию для компьютеров учат
в общеобразовательных и специализированных математических

Предисловие
школах, средних и высших учебных заведениях, на специальных
начальных курсах и курсах повышения квалификации специалистов. Объем материала по дисциплине напрямую зависит от объема выделенных часов, который в разных учебных заведениях
различен. Безусловно, профессиональные программисты после
изучения указанной дисциплины не могут быть подготовлены,
однако базис профессионализма, по нашему убеждению, должен
быть заложен.
С нашей точки зрения, для того чтобы стать прикладным
программистом, по крайней мере средней руки, начинающий
специалист должен уметь:
1) решать задачи из различных областей математики, физики, механики, статистики и др. и самое главное четко и ясно записывать ход их решения; иными словами — уметь составлять
алгоритмы решения задач;
2) знать устройство и принцип работы современного компьютера, четко представлять, что такое программа на языке компьютера, где она хранится и как им выполняется;
3) знать один или несколько алгоритмических языков программирования, т. е. языковых средств, которые используются
для составления программ, а также уметь пользоваться соответствующими системами программирования — инструментами,
которые непосредственно предназначены для составления и тестирования программ на компьютере с использованием того или
иного языка;
4) накопить достаточно большой опыт составления, отладки
и тестирования программ (не менее 150—300 задач) из различных областей науки, техники, экономики и других сфер человеческой деятельности.
Как приблизиться к выполнению перечисленных требований, с определенной степенью полноты изложено в настоящем
учебном пособии. Оно предназначено для учащихся средних
специальных заведений, выпускники которых обучаются по специальности 2202 «Автоматизированные системы обработки информации и управления», а также 2203 «Программное обеспечение вычислительной техники и автоматизированных систем».

Глава 1
АЛГОРИТМЫ И АЛГОРИТМИЗАЦИЯ
1.1. Определение и представление алгоритмов
Слово алгоритм происходит от имени узбекского математика
эпохи Возрождения аль-Хорезми, который в IX в. н. э. установил правила четырех арифметических действий над числами в
десятичной системе счисления. В Европе эти правила получили
название «алгоризм». Затем это слово постепенно преобразовалось в слово «алгоритм» и стало собирательным названием правил, которые применялись не только для выполнения арифметического счета.
В течение длительного времени термин «алгоритм» употребляли преимущественно математики, описывая правила решения
различных задач. При этом они пользовались так называемым
интуитивным понятием алгоритма как способа описания порядка решения той или иной задачи с помощью конечного набора
однозначных математических действий. На этом пути были получены ставшие теперь известными правила поиска корней
квадратных и кубических уравнений, решения систем линейных
и нелинейных уравнений, дифференцирования и интегрирования функций и многие другие правила вычислений. Более того,
известна попытка Г. Лейбница найти общий алгоритм решения
любых математических задач [1].
Вместе с тем, решая различные задачи, математики столкнулись с рядом неразрешимых проблем, т. е. задач, для которых
не удавалось построить решающий их алгоритм. Широко известной из них стала проблема П. Ферма. Существуют ли натуральные числа x, y, z, для которых при целом n 
 2 справедливо
равенство x
y
z
n
n
n


? Были известны и другие задачи, в частности из области геометрии: о квадратуре круга, удвоении куба
и др. [2]. Это побудило математиков более глубоко подойти к

Глава 1. Алгоритмы и алгоритмизация
обоснованию сущности алгоритмов и прежде всего формальным, т. е. математическим путем.
Основные результаты теории алгоритмов были получены
в 30—50-х годах ХХ в. Э. Черчем, А. Тьюрингом, А. Постом,
А. Колмогоровым, А. Марковым. Введенные в рассмотренные
модели алгоритмов (алгоритмические модели), машины А. Тьюринга, А. Поста дали возможность устанавливать алгоритмическую разрешимость проблемы путем построения соответствующих машин логического действия. Это дало возможность более
конструктивно подходить к поиску решения неразрешимых проблем, весьма часто акцентируя внимание на частных ее случаях.
Широкое употребление слова «алгоритм» обязано буму кибернетики — науки об управлении и связи в живом и машине,
который пришелся на 50-е годы ХХ в. Слово «алгоритм» стало
настолько популярным, что его начали применять в различных
случаях, весьма далеких от вычислений. Например, алгоритмами
стали называть рецепты приготовления и приема лекарств, перехода пешеходом улицы с интенсивным движением транспорта,
завязывания шнурков на ботинках и т. п. Дело дошло до абсурда. Появились дикие словосочетания типа «алгоритм изобретения», что означает ни что иное, как конец изобретательства
(творческой деятельности).
Оставляя в стороне подобного рода алгоритмы, сосредоточим внимание лишь на тех из них, которые описывают решение
задач обработки информации на ЭВМ. Построение таких алгоритмов должно удовлетворять ряду принципов. Первое, что следует отметить, — алгоритм применяется к исходным данным и
выдает результаты. Иными словами, он имеет информационный
вход и выход. Кроме того, в ходе выполнения алгоритма получаются промежуточные результаты, которые могут использоваться
в дальнейшем. Таким образом, каждый алгоритм выполняет операции с данными — входными, промежуточными и выходными.
Данные должны быть четко определены и отделены от «не
данных». Примерами данных, с которыми работают алгоритмы,
предназначенные для ЭВМ, являются числа, формулы, векторы,
матрицы смежности графов, чертежи, рисунки, фотографии. Не
данными являются, например, «хорошая книга» или «логическое
утверждение». С этими «не данными» алгоритм работать не будет до тех пор, пока они не будут представлены в форме подходящих данных.

1.1. Определение и представление алгоритмов
7
Для универсальности представления данных в алгоритмах
используются специальные алфавиты — конечные наборы символов, из которых конструируются слова и предложения. Поэтому считается, что вход алгоритмов — это слова разной длины,
определенные в конечном алфавите. Каждый символ алфавита
имеет стандартный код определенной длины, занимающий не
более восьми двоичных разрядов. В современных ЭВМ символы
кодируются при вводе их в ЭВМ с клавиатуры или со сканера.
Введенные в компьютер данные размещаются в памяти. Память является дискретной, состоящей из отдельных ячеек. Каждая ячейка может вмещать один символ. Так, что, например,
слово ALFA для своего размещения потребует четыре ячейки.
Таким образом, физической единицей памяти является ячейка.
На логическом уровне единица памяти называется байт.
Алгоритм состоит из отдельных элементарных шагов. Причем количество этих шагов должно быть конечно. Это значит,
что после выполнения этих шагов алгоритм должен прекратить
выполнять действия, т. е. остановиться. Если действия повторяются бесконечно, говорят, что алгоритм зацикливается.
Последовательность шагов алгоритма должна быть детерминированной (определенной). Это означает, что после каждого
шага либо указывается, какой шаг выполнять дальше, либо дается команда остановки, после этого действия алгоритма считаются законченными.
Алгоритм должен удовлетворять условию результативности,
т. е. после выполнения конечного количества шагов он должен
выдавать правильный результат решения той или иной информационной задачи.
Суммируя все перечисленные требования, которым должны
удовлетворять алгоритмы обработки информации на ЭВМ, введем следующие определения.
Определение 1.1. Алгоритм — это конечная последовательность детерминированных арифметических и логических действий над исходными и промежуточными данными задачи обработки информации, выполнение которых приводит к правильному ее решению, т. е. получению требуемых выходных данных.
При этом под исходными данными понимаются только те наборы данных, для которых имеет смысл решаемая задача. По существу алгоритм, определенный на этих данных, преобразует их

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

1.1. Определение и представление алгоритмов
9
При всей наглядности блок-схем алгоритмов они представляют собой достаточно грубое описание действий и отображают
лишь связи по управлению, а не по информации. Они не содержат сведений ни о данных, ни о требуемой памяти и, что весьма
часто, не содержат последовательности элементарных шагов. По
существу, блок-схемы — это средства описания детерминизма
алгоритма.
Как сообщалось раньше, текстовое представление алгоритмов средствами естественного языка подразумевает пошаговое
описание действий. При этом после каждого шага указывается,
какой шаг выполнять дальше. Вместе с тем существует соглашение: если шаги алгоритма выполняются в естественном порядке
(без пропуска и возвращения назад), переход к очередному шагу
может не указываться.
Текстовое описание алгоритма так же, как и его блок-схема,
не содержит сведений о данных, памяти и может быть представлено весьма укрупненно. Оно лишь требует меньше места для
записи алгоритмов.
Представление алгоритмов в виде укрупненной программы —
индивидуальный продукт каждого автора, который описывает алгоритм. Как правило, для этих целей используются фрагменты
каких-либо алгоритмических языков. В описании обычно указываются начальные шаги (инициализация переменных), основные
шаги, переходы и циклы, а также обозначаются результаты решения задачи. Полное представление алгоритма в виде программы,
возможно, лишь для весьма элементарных и коротких программ.
Для иллюстрации описанных методов представления алгоритмов рассмотрим следующую задачу. Необходимо составить
алгоритм приближенного вычисления квадратного корня x
a

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


	
ному соотношению x
x
a
x
x
n
n
n
n










1
1
1
1
2
, n  1, 2, ... при условии, что задано начальное значение корня x0. Тогда первое



	


,
второе
—
значение
корня
будет
равно
x
x
a
x
x
1
0
0
0
1
2







	


 и т. д. Корень будем считать вычисленным
x2  x1  1
2
1
1
a
x
x



Глава 1. Алгоритмы и алгоритмизация
с заданной точностью , если модуль очередного уточнения корня 1
2
1
x
x



	


  . Блок-схема алгоритма решения этой задачи
n
n


приведена на рис. 1.1.
Рис. 1.1. Блок-схема алгоритма вычисления квадратного корня методом Ньютона