Алгоритмические структуры (типы алгоритмов). Типы алгоритмов и формы их представления
Программирование - это записывание чего-то с использованием чужого малознакомого языка. С развитием этой области знания разработчики пошли еще дальше и научились записывать "что-то", даже не понимая, как оно звучит на русском языке. Новички учатся писать код сразу на C++ или php, используя множество библиотек, и толком даже не понимают, как то, что они создают, звучит на их родном языке. Алгоритмизация занимается разъяснением и доведением до понятного этого "что-то".
Алгоритмизация
Большинство примеров алгоритмов по информатике даже в вузах изучается на посредственном уровне. Общепринятой практикой является бесконечное написание все более сложного кода. Попытки неопытных программистов приступать к написанию программ сразу на языке программирования можно сравнить с работой журналиста, который, едва овладев основами иностранного языка, пишет статью для журнала. Избежать подобную проблему можно, если начать записывать свое произведение сначала на родном языке, отредактировать его, проверить на ошибки и в конце перевести на необходимый язык.
Преимущество такого подхода заключается главным образом в том, что переводом разработчик будет заниматься только 25 % времени, в то время как при написании программы на новом языке он потратит на работу с малознакомым языком все 100 %. При этом он окажется в стесненных условиях и не сможет провести хорошую проверку на ошибки и доработку проекта.
Алгоритмизация помогает при реализации проекта на компьютере описать процесс решения на родном и понятном языке в виде схемы взаимосвязанных алгоритмов, провести анализ идей и получить наиболее качественный и продуманный код, который будет устойчивее к ошибкам и эффективнее работать.
Понятие алгоритма
Компьютер не умеет решать задачи, он способен только выполнять простые действия в указанном порядке. "Как же калькулятор?" - спросите вы. Он тоже является плодом трудов программистов, которые создали программу, использующую определенные алгоритмы для получения необходимых результатов. Рассмотрим абстрактную ситуацию. Что следует сделать, если попросить найти корни квадратного трехчлена человека, который не знаком с методами решения уравнений?
Очевидно, что его необходимо обучить решать квадратные уравнения. Происходит это по следующей схеме:
- Выбрать способ решения.
- Изучить все детали выбранного способа.
- Объяснить первые два пункта будущему исполнителю на понятном ему языке.
Затем можно будет давать исполнителю задания на решение квадратного уравнения. И если первые два шага просты и понятны - все способы решения описаны в соответствующей литературе, то третий шаг представляет сложность.
Как можно гарантировать, что идеи, используемые при решении задачи, будут восприняты исполнителем так же, как это понимаете вы? Здесь мы вплотную подходим к понятию алгоритма. Практика показывает, что для правильного объяснения чего-то кому-то необходимо соблюдать следующие шаги:
- определить исходные данные (переменная и коэффициенты квадратного уравнения);
- разбить процесс решения на однозначно известные компоненты для исполнителя (формулы дискриминанта и нахождения корней);
- указать порядок выполнения этапов (сначала вычислить дискриминант, затем корни);
- установить условие, при котором решение считается завершенным (проверить найденные корни, подставив их в уравнение на место переменных);
- обозначить, каким именно должен быть результат решения (корни принадлежат множеству действительных чисел).
Описанный набор шагов в общем смысле и являет собой алгоритм. Таким образом под алгоритмом можно понимать способ решения поставленной задачи, записанный при помощи определенных правил, позволяющих обеспечить однозначное понимание выполняемых действий и их порядка. Ниже будут подробнее рассмотрены алгоритмы и примеры задач.
Основные свойства алгоритма
Дискретность. Процесс решения задачи всегда состоит из строго отделенных друг от друга действий, называемых шагами, имеющими определенный порядок выполнения.
Определенность. Каждый шаг должен быть понятным и однозначным как по смыслу, так и в ключе действия, которое предстоит совершить.
Результативность. Алгоритм должен давать результат. При этом количество шагов может исчисляться тысячами или миллионами, но они всегда должны приводить к результату.
Массовость. Любой алгоритм, разработанный для решения какой-либо задачи, должен быть применим ко всем задачам этого типа для всех допустимых исходных данных.
Возможности компьютера
Для правильного создания алгоритмов под компьютеры важно понимать их возможности. Рассмотрим сначала величины, с которыми работает ЭВМ. В общем случае их можно разделить на числовые и текстовые, постоянные и переменные.
Под постоянными числами понимаются все числа: 3,15, 100, 105, их особенностью является неизменность в течение всей работы программы. Переменные величины меняют свое значение в ходе выполнения кода и обозначаются, как правило, буквами: x, y, max, min и т. д.
Текстовые переменные аналогично числовым бывают постоянными или переменными. В первом случае это просто текст: "хорошо", "a и b" и пр. Во втором - такое же символьное обозначение, как и числовых переменных: name, city и т. п. Отличие между ними заключается главным образом в выделяемой памяти компьютера под хранение такой переменной.
Операции, которые способен выполнять компьютер:
- Считывать данные с устройств ввода (клавиатура, мышь, файлы).
- Вычисление значений с использованием математические функции: сложение, вычитание, sin, cos, ln и т. д. - в каждом языке программирования свой набор встроенных функций.
- Вывод данных (на экран, на бумагу, в сетевой интерфейс).
- Переход между этапами выполнения программы.
- Сравнение двух величин (больше, меньше, равно).
Это основные операции, которые могут выполняться большинством языков программирования.
Способы описания алгоритмов
Словесный. Это самый простой способ. Его примером может служить кулинарный рецепт. Допускается использование простых математических формул.
Графический. Описание с помощью схем. Это особый способ записи алгоритмов с использованием своего рода общепринятого алгоритмического языка - фигур и блоков, имеющих определенное значение: прямоугольник - простой действие, наклонный параллелограмм - ввод/вывод, ромб - условие и т. д.
Использование алгоритмического языка. Аналогично графическому, это также особенный способ записи алгоритма. Существует множество алгоритмических языков. Их правила не являются строгими, иначе это был бы язык программирования. Рассмотрим пример алгоритма расчета заработной платы в зависимости от стажа, записанный при помощи алгоритмического языка.
Алг заработная плата (int ST, real ZP) арг ST рез ZP начало если ST
Алгоритмический язык можно назвать более строгой формой записи по сравнению со словесной. Используется ограниченный набор слов и их конструкций, а также оформление с отступами. Минусом словесной формы и алгоритмического языка является ухудшающаяся наглядность алгоритма при увеличении его размеров. Поэтому данные способы могут быть использованы только для передачи смысла небольших алгоритмов.
Виды алгоритмов
Существует огромное множество алгоритмов, созданных для решения самых разных задач. Например, любой учебник высшей математики содержит сотни алгоритмов: решение системы линейных уравнений, нахождение экстремумов функции, вычисление интеграла и т. д. Однако при детальном рассмотрении их структуры оказывается, что все алгоритмы можно разделить на несколько видов. Рассмотрим эти виды алгоритмов с примерами.
- линейный (вычисление результата сложения или умножения, обмен значениями нескольких переменных);
- разветвляющийся (определение наибольшего из нескольких чисел);
- циклический (сортировка массива, вычисление факториала).
Это базовые виды. Стоит также отметить, что в ряде литературы выделяется еще и четвертый вид - рекурсивный. Но особого обозначения в схематической записи он не имеет и реализуется через базовые.
Подробнее о каждом алгоритме вычисления с примерами будет рассказано ниже.
Принципы алгоритмизации
- Определить исходные данные.
- Выбрать способ решения.
- Разбить выбранные способ на шаги исходя из возможностей компьютера (языка программирования).
- Выполнить алгоритм в виде схемы, определив четкий порядок шагов.
- Вывод результатов вычислений.
- Обозначить переход к выходу схемы.
Отладка алгоритма
Человек допускает ошибки, и это факт. Главным параметром любого алгоритма должна быть правильность его работы. Отладка - это процесс выявления и исправления ошибок алгоритма. Для этого берется определенный набор исходных данных, называемых тестовыми. Они представляют собой, как правило, всевозможные типы исходных данных. Например, если на ввод подается число, то алгоритм следует проверить на корректную работу с учетом: положительных, отрицательных, целых и вещественных чисел, нулевые значения и т. п.
Главным инструментом для проверки точности алгоритма остается человеческий мозг. Конечно, допустимо использование других компьютерных инструментов для автоматизации проверки, но так или иначе подготовкой тестов и анализом результатов занимается человек. В таком случае возникает вопрос, а зачем нужен алгоритм, если человек выполняет все сам? Затем, что главная задача алгоритма - многократное решение определенного типа задач.
Линейные алгоритмы
Линейным является алгоритм, в котором шаги идут последовательно друг за другом. Любой алгоритм, не содержащий ветвлений и циклов, является линейным. Рассмотрим пример алгоритма, решающего следующую задачу: в двух клетках сидят волк и заяц, нужно поменять их местами.
Ключом к решению данной задачи является дополнительная клетка temp, которую следует использовать, чтобы поменять местами животных.
Разветвляющиеся алгоритмы
Как и следует из названия, алгоритм имеет несколько ветвей. Суть работы заключается в выборе одного из возможных вариантов вычислительного процесса в зависимости от каких-либо условий. Схематическое ветвление изображается ромбовидным блоком, внутри которого указывается условие, а по сторонам от него располагаются ветви выбора в зависимости от того, истинно условие или ложно. Разветвляющийся алгоритм и примеры его применения можно найти повсеместно. В программировании это типичная конструкция if-else, которая есть почти в любом языке.
Приведем пример алгоритма для решения задачи о нахождении наибольшего среди трех чисел.
Циклический алгоритм
Циклическим является алгоритм, в котором происходит многократное повторение одних и тех же шагов, в которых меняться может только значение конкретной переменной, над которой производятся расчеты. Виды циклического алгоритма и пример будут рассмотрены ниже, а пока перечислим основные шаги для построения цикла.
- Присваивание начального значения переменных. Без выполнения этого условия цикл, скорее всего, не сможет работать или будет совершать ошибки.
- Блок вычисления результатов. Это основное тело цикла.
- Проверка условия окончания циклического процесса. Если забыть указать условие, при котором следует завершить цикл, алгоритм будет выполняться бесконечно.
- Изменение переменных. Этот блок вступает в силу после проверки условия окончания, если оно было ложным. Если забыть про этот блок, то цикл будет вечно выполнять одно действие и никогда не завершится. Поэтому важно, чтобы переменные претерпевали какие-либо изменения на каждой итерации цикла.
Существует несколько видов циклических алгоритмов: с постусловием, предусловием и параметром.
Построим циклический алгоритм на примере нахождения факториала числа N.
Другие типы алгоритмов
Существует еще ряд алгоритмов, которые отличаются по классификации или происхождению.
- Механические алгоритмы. Например, работа двигателя внутреннего сгорания или сборочного конвейера.
- Вероятностные алгоритмы. Их работа основана на теории вероятности и математической статистике.
- Эвристические алгоритмы. Используют практические соображения в своей работе, без строгого математического обоснования.
- Генетические алгоритмы. Применяют биологические идеи в своей работе.
В информатике план действий называют алгоритмом
.
Алгоритм состоит из отдельных шагов – команд
. Ни одну из них нельзя пропустить, чаще всего никакие команды нельзя поменять местами.
Исполнитель
– человек, животное или машина, способные понимать и выполнять некоторые команды.
Среда исполнителя
– предметы, которые окружают исполнителя и с которыми он работает.
Список Команд Исполнителя (СКИ)
– набор команд, понятных исполнителю. Исполнитель может выполнить только те команды, которые входят в его СКИ.
Для решения большинства задач недостаточно отдать одну команду исполнителю, надо составить для него алгоритм – план действий, состоящий из команд, которые ему понятны (входят в его СКИ).
Алгоритм
– точно определенный план действий исполнителя, направленный на решение какой-то задачи. В алгоритм можно включать только те команды, которые есть в СКИ.
Какие бывают алгоритмы
Линейный алгоритм
В линейном алгоритме команды выполняются последовательно, одна за другой. Примером линейного алгоритма может служить алгоритм заварки чая.
Разветвляющийся алгоритм
В разветвляющемся алгоритме порядок следования команд может быть разный в зависимости от того, какова окружающая обстановка. Примером разветвляющегося алгоритма может служить алгоритм перехода улицы.
Циклический алгоритм
В циклическом алгоритме некоторые действия повторяются несколько раз (в информатике говорят, что выполняется цикл). Существуют два вида циклических алгоритмов. В одном из них мы знаем заранее, сколько раз надо сделать эти действия, в другом мы должны остановиться лишь тогда, когда выполним работу, то есть наши действия прекращаются при выполнении какого-то условия.
Примером цикла первого типа является наша жизнь в рабочие дни (от понедельника до субботы) – мы выполняем 6 раз почти одни и те же действия.
Пример цикла второго типа – алгоритм распилки бревна: мы не можем заранее сказать, сколько раз нам надо провести пилой от себя и на себя - это зависит от плотности дерева, качества пилы и наших усилий. Однако мы точно знаем, что надо закончить работу, когда очередное отпиленное полено упадет на землю.
Способы записи алгоритмов
Выделяют три наиболее распространенные на практике способа записи алгоритмов:
- словесный (запись на естественном языке);
- графический (запись с использованием графических символов);
- программный (тексты на языках программирования).
Словесный способ записи алгоритмов
Словесный способ – способ записи алгоритма на естественном языке . Данный способ очень удобен, если нужно приближенно описать суть алгоритма. Однако при словесном описании не всегда удается ясно и точно выразить логику действий.
В качестве примера словесного способа записи алгоритма рассмотрим алгоритм нахождения площади прямоугольника
где S – площадь прямоугольника; а, b – длины его сторон.
Очевидно, что a, b должны быть заданы заранее, иначе задачу решить невозможно.
Словестный способ записи алгоритма выглядит так:
- Начало алгоритма.
- Задать численное значение стороны a.
- Задать численное значение стороны b.
- Вычислить площадь S прямоугольника по формуле S=a*b.
- Вывести результат вычислений.
- Конец алгоритма.
Графический способ описания алгоритмов
Для более наглядного представления алгоритма используется графический способ. Существует несколько способов графического описания алгоритмов. Наиболее широко используемым на практике графическим описанием алгоритмов является использование блок-схем. Несомненное достоинство блок схем – наглядность и простота записи алгоритма.
Каждому действию алгоритма соответствует геометрическая фигура (блочный символ). Перечень наиболее часто употребляемых символов приведен в таблице ниже.
Так как в линейном алгоритме команды выполняются последовательно, то блок-схема будет иметь вид:
Так как в разветвляющемся алгоритме порядок следования команд может быть разный в зависимости от того, какова окружающая обстановка, то блок-схема примет вид:
В циклическом алгоритме некоторые действия повторяются несколько раз и для него блок-схема примет вид:
Программный способ записи алгоритмов
Для того, чтобы алгоритм был понятен роботу, компьютеру или другой машине, недостаточно только написать команды, надо еще и оформить алгоритм в таком виде, в котором его понимает машина (написать программу), т.е. записать его с использованием команд из СКИ, соблюдая правила оформления.
Правила оформления программы:
- любой алгоритм имеет название;
- алгоритм начинается с открывающей фигурной скобки “{“ и заканчивается закрывающей фигурной скобкой “}”; команды, расположенные между этими скобками, называются телом алгоритма;
- в алгоритм могут входить только те команды, которые есть в СКИ исполнителя;
- каждая команда заканчивается знаком “;”, который обозначает конец команды;
- для того, чтобы нам было легче разбираться в программах, используют комментарии - текстовые пояснения, которые начинаются знаками “/*” и заканчиваются знаками “*/”; исполнитель не обращает внимания на комментарии в алгоритме.
Практические задания:
- Составить блок-схему для нахождения периметра квадрата.
- Составить блок схему для заваривания чая.
- Составить блок-схему для перехода перекрестка со светофором.
Использован материал из книг:
- "Современные информационные технологии", авторы преподаватели центра "Турбо"
- "Алгоритмы и исполнители", автор Поляков К.
Цель: Ознакомить студентов с основами алгоритмизации.
Учебные вопросы:
1. Алгоритм и его свойства. Способы записи алгоритмов.
2. Основные типы алгоритмов. Блок-схемы типовых алгоритмов.
Изучив данную тему, студент должен:
Знать:
· свойства алгоритма;
· блоки для построения схем;
· основные типы алгоритмов;
Уметь :
· строить алгоритмы по условию задачи;
Понятие алгоритма
Понятие алгоритма – одно из фундаментальных понятий информатики, которое исторически оформилось в самостоятельную дисциплину «теория алгоритмов», близкую к другой дисциплине «математическая логика». С другой стороны, дисциплину «теория алгоритмов» можно рассматривать промежуточной между двумя дисциплинами: математикой и информатикой, связанной с разделом программирования.
Алгоритмизация относится к общим методам информатики, имеет большое значение при решении сложных задач. Прежде, чем написать программу решения задачи на ЭВМ, необходимо просмотреть последовательность действий, которые должны быть выполнены для правильного решения рассматриваемой задачи.
Алгоритм это последовательность арифметических, логических и прочих операций, необходимых для выполнения на ЭВМ.
Для получения правильного результата алгоритм должен быть составлен так, чтобы при его исполнении все команды трактовались однозначно. Поэтому появились обязательные требования, которые должны учитываться при составлении алгоритмов. Требования формулируются в виде свойств.
Алгоритм должен быть всегда результативным, иметь свойство повторяемости и должен быть рассчитан на конкретного исполнителя. В технике таким исполнителем является ЭВМ. Для обеспечения возможности реализации на ЭВМ алгоритм должен быть описан на языке понятном ЭВМ, то есть на машинном языке. Однако прежде, чем представить алгоритм на языке понятном для ЭВМ (машинном языке), необходимо написать программу с помощью алгоритмического языка программирования.
Алгоритм может быть представлен различными способами, в частности:
1) словесно (вербальное описание);
2) таблично;
3) в виде блок-схемы;
4) на алгоритмическом языке.
Достаточно распространенным способом представления алгоритма является его запись на алгоритмическом языке, представляющем в общем случае систему обозначений и правил для единообразной и точной записи алгоритмов и их исполнения. Этот способ представления алгоритма предусматривает запись его в виде программы.
Программа – это запись алгоритма на языке программирования, приводящая к конечному результату за конечное число шагов.
Предпочтительнее до записи на алгоритмическом языке представить алгоритм в виде блок-схемы. Для построения алгоритма в виде блок-схемы необходимо знать назначении каждого из блоков. В таблице 13. приводятся типы блоков и их назначение.
Таблица 13
Назначение блока | Комментарий {блоку соответствует оператор} |
||
Начало или конец блок-схемы | |||
Ввод или вывод данных | ввода / вывода |
||
Процесс (в частности вычислительный) | присваивания |
||
| |||
| Модификатор цикла |
5.2. Основные типы алгоритмов
Алгоритмизация выступает как набор определенных практических приёмов, особых специфических навыков рационального мышления в рамках заданных языковых средств. Алгоритмизация вычислений предполагает решение задачи в виде последовательности действий, т. е. решение, представленное в виде блок-схемы. Можно выделить типичные алгоритмы. К ним относятся: линейные алгоритмы, разветвляющиеся алгоритмы, циклические алгоритмы.
Линейные алгоритмы
Линейный алгоритм является наиболее простым. В нём предполагается последовательное выполнение операций. В этом алгоритме не предусмотрены проверки условий или повторений.
Пример: Вычислить функцию z= (х-у)/x +y2 .
Составить блок-схему вычисления функции по линейному алгоритму. Значения переменных х , у могут быть любые, кроме нуля, вводить их с клавиатуры.
Решение: Линейный алгоритм вычисления функции задан в виде блок-схемы на рис.8. При выполнении линейного алгоритма значения переменных вводятся с клавиатуры, подставляются в заданную функцию, вычисляется результат, а затем выводится результат.
Рис.8. Линейный алгоритм
Назначение блоков в схеме на рис.8:
· Блок 1 в схеме служит в качестве логического начала.
· Блок 3 представляет арифметическое действие.
· Блок 4 выводит результат.
· Блок 5 в схеме служит в качестве логического завершения схемы.
Алгоритмы ветвлений
Разветвляющийся алгоритм предполагает проверку условий для выбора решения. Соответственно в алгоритме появятся две ветви для каждого условия.
В примере рассматривается разветвляющийся алгоритм, где в зависимости от условия выбирается один из возможных вариантов решений. Алгоритм представляется в виде блок-схемы.
Пример: При выполнении условия x >0 вычисляется функция: z = ln x + y , иначе, а именно, когда х=0 или x <0 , вычисляется функция: z = x + y 2 .
Составить блок-схему вычисления функции по алгоритму ветвления. Значения переменных х, у могут быть любые, вводить их с клавиатуры.
Решение: На рис.9 представлен разветвляющийся алгоритм, где в зависимости от условия выполнится одна из веток. В блок-схеме появился новый блок 3, который проверяет условие задачи. Остальные блоки знакомы из линейного алгоритма.
https://pandia.ru/text/78/136/images/image008_57.gif" width="300" height="360 src=">
Рис.9. Алгоритм ветвления
Пример: Найти максимальное значение из трёх различных целых чисел, введенных с клавиатуры. Составить блок-схему решения задачи.
Решение: Данный алгоритм предполагает проверку условия. Для этого выбирается любая из трёх переменных и сравнивается с другими двумя. Если она больше, то поиск максимального числа окончен. Если условие не выполняется, то сравниваются две оставшиеся переменные. Одна из них будет максимальной. Блок-схема к этой задаче представлена на рис 10.
https://pandia.ru/text/78/136/images/image010_48.gif" width="492" height="456 src=">
Рис. 10. Блок-схема поиска максимума
Циклические алгоритмы
Циклический алгоритм предусматривает повторение одной операции или нескольких операций в зависимости от условия задачи.
Из циклических алгоритмов выделяют два типа:
1) с заданным количеством циклов или со счётчиком циклов;
2) количество циклов неизвестно.
Пример: В цикле вычислить значение функции z=x*y при условии, что одна из переменных x меняется в каждом цикле на единицу, а другая переменная у не меняется и может быть любым целым числом. В результате выполнения цикла при начальном значении переменной х=1 можно получить таблицу умножения. Количество циклов может быть любым. Составить блок-схему решения задачи.
Решение: В примере количество циклов задаётся. Соответственно выбирается алгоритм циклов первого типа. Алгоритм этой задачи приводится на рис. 11.
Во втором блоке вводятся количество циклов n и любые целые числа х , y .
В блок-схеме появился новый блок 3, в котором переменная i считает количество циклов, после каждого цикла увеличиваясь на единицу, пока счётчик не будет равен i=n . При i=n будет выполнен последний цикл.
В третьем блоке указывается диапазон изменения счётчика цикла (от i =1 до i=n ).
В четвёртом блоке изменяются значения переменных: z , x .
В пятом блоке выводится результат. Четвёртый и пятый блоки повторяются в каждом цикле.
Рис.11 . Циклический алгоритм со счётчиком циклов
Этот тип циклических алгоритмов предпочтителен, если дано количеством циклов.
Если количество циклов неизвестно, то блок-схемы циклических алгоритмов могут быть представлены в виде рисунков 12, 13.
Пример: Вычислить у=у- x пока y > x , если y =30 , x =4. Подсчитать количество выполненных циклов, конечное значение переменной у . В цикле вывести значение переменной у , количество выполненных циклов. Составить блок-схему решения задачи.
Решение: В примере количество циклов неизвестно. Соответственно выбирается алгоритм циклов второго типа. Алгоритм этой задачи приводится на рис. 12.
Условие проверяется на входе в цикл. В теле цикла выполняется два блока:
1) у=у-х; i = i +1 ;
2) вывод значений переменных i , y .
Цикл выполняется до тех пор, пока выполняется условие y>x
. При условии равенства этих переменных у=х
или y
Алгоритм, представленный на рис.12, называется циклический алгоритм с предусловием , так как условие проверяется в начале цикла или на входе в цикл.> x на входе в цикл. Если условие выполняется, то переход к блоку 4, иначе на блок 6.
В четвёртом блоке вычисляется значение переменной у i = i +1 .
В пятом блоке выводится результат:
· значение переменной у ,
i .
Пример: Составить блок-схему примера (рисунок 12), проверяя условие выхода из цикла. В этом примере условие задачи не меняется, и результат выведется тот же, но блок-схема будет другой.
Решение: В этом случае проверяется условие на выход из цикла: y<=x . При этом условии цикл не выполняется. Условие в блок-схеме следует перенести в конец цикла, после вывода на печать. Цикл выполняется до тех пор, пока выполняется условие y>x .
Алгоритм, если условие перенести в конец цикла, называется алгоритмом цикла с постусловием . Алгоритм этой задачи приводится на рис. 13.
Во втором блоке вводятся y =30 , x =4 .
В третьем блоке вычисляется значение переменной у , подсчитывается количество выполненных циклов i = i +1 .
В четвёртом блоке выводится результат:
· значение переменной у ,
· количество выполненных циклов i .
В пятом блоке проверяется условие y <= x на выход из цикла. Если условие выполняется, то переход к блоку 6, иначе на блок 3 и цикл повторяется.
Рис.13 . Алгоритм цикла с постусловием
Контрольные вопросы
1. Понятие алгоритма.
2. Виды алгоритмов.
3. Основные алгоритмические структуры.
4. Основные блоки графического алгоритма.
5. Линейная алгоритмическая структура. Пример.
6. Ветвление. Пример.
7. Циклические алгоритмические структуры. Пример.
Аннотация: Алгоритм является базовым понятием для тех, кто хочет начать программировать на любом языке программирования. Любая задача может быть формализована алгоритмически. Чтобы понять, с чего начать, рассмотрим основные виды алгоритмов. Цель данной лекции – ознакомить студентов с понятием алгоритма; показать, что такая абстрактная вещь как алгоритм окружает нас в повседневной жизни.
Пример псевдокода:
алг Нахождение частного двух чисел начало вывод ("задайте делимое и делитель") ввод (делимое, делитель) если делитель ≠ 0 то частное = делимое / делитель вывод(частное) иначе вывод("нет решения") кон алг Нахождение частного двух чисел
В данном примере используется три переменные: делимое, делитель и частное. Делимое и делитель задаются исполнителем произвольными числами. Частное считается лишь в том случае, если делитель не равен нулю.
Графическая реализация алгоритма представляет собой блок-схему. Блок-схема состоит из блоков определенной формы, соединенных стрелками. Ответ при этом получает человек, который выполняет команды согласно блок-схеме. Более подробно о блок-схемах будет рассказано в Лекции 2.
Программная реализация алгоритма – это компьютерная программа, написанная на каком-либо алгоритмическом языке программирования, например: С++, Pascal, Basic и т.д. Программа состоит из команд определенного языка программирования. Отметим, что одна и та же блок-схема может быть реализована на разных языках программирования. Ответ при этом получает ЭВМ, а не человек. Более подробно о составлении программ на языке программирования С++ смотреть Лекцию 3.
Различают три основных вида алгоритмов:
- линейный алгоритм,
- разветвляющийся алгоритм,
- циклический алгоритм.
Линейный алгоритм – это алгоритм, в котором действия выполняются однократно и строго последовательно.
Самый простой пример реализации линейного алгоритма – путь из университета домой.
Словесный способ записи данного алгоритма:
- выйти из университета на остановку;
- подождать нужный автобус;
- сесть на нужный автобус;
- оплатить проезд;
- выйти на требуемой остановке;
- дойти до дома.
Очевидно, что данный пример относится к линейному алгоритму, т.к. все действия следуют одно за другим, без условий и повторений.
Разветвляющийся алгоритм – это алгоритм, в котором в зависимости от условия выполняется либо одна, либо другая последовательность действий.
Самый простой пример реализации разветвляющегося алгоритма – если на улице идет дождь, то необходимо взять зонт, иначе не брать зонт с собой.
Приведенный выше пример псевдокода по нахождению частного двух чисел также относится к разветвляющемуся алгоритму.
Циклический алгоритм – это алгоритм, команды которого повторяются некое количество раз подряд.
Самый простой пример реализации циклического алгоритма – при чтении книги будут повторяться одни и те же действия: прочитать страницу, перелистнуть и т.д.
Более подробно о линейном, разветвляющемся и циклическом алгоритмах смотреть Лекцию 2.
ПОНЯТИЕ АЛГОРИТМА. СВОЙСТВА АЛГОРИТМА. ВИДЫ АЛГОРИТМОВ. СПОСОБЫ ОПИСАНИЯ АЛГОРИТМОВ
Алгоритмом называется точное и понятное предписаниe исполнителю совершить последовательность действий, направленных на решение поставленной задачи. Слово «алгоритм» происходит от имени математика Аль Хорезми, который сформулировал правила выполнения арифметических действий. Первоначально под алгоритмом понимали только правила выполнения четырех арифметических действий над числами. В дальнейшем это понятие стали использовать вообще для обозначения последовательности действий, приводящих к решению любой поставленной задачи. Говоря об алгоритме вычислительного процесса, необходимо понимать, что объектами, к которым применялся алгоритм, являются данные. Алгоритм решения вычислительной задачи представляет собой совокупность правил преобразования исходных данных в результатные.
Основными свойствами алгоритма являются:
- детерминированность (определенность). Предполагает получение однозначного результата вычислительного процecca при заданных исходных данных. Благодаря этому свойству процесс выполнения алгоритма носит механический характер;
- результативность. Указывает на наличие таких исходных данных, для которых реализуемый по заданному алгоритму вычислительный процесс должен через конечное число шагов остановиться и выдать искомый результат;
- массовость. Это свойство предполагает, что алгоритм должен быть пригоден для решения всех задач данного типа;
- дискретность. Означает расчлененность определяемого алгоритмом вычислительного процесса на отдельные этапы, возможность выполнения которых исполнителем (компьютером) не вызывает сомнений.
Алгоритм должен быть формализован по некоторым правилам посредством конкретных изобразительных средств. К ним относятся следующие способы записи алгоритмов: словесный, формульно-словесный, графический, язык операторных схем, алгоритмический язык.
Наибольшее распространение благодаря своей наглядности получил графический (блок-схемный) способ записи алгоритмов.
Блок-схемой называется графическое изображение логической структуры алгоритма, в котором каждый этап процесса обработки информации представляется в виде геометрических символов (блоков), имеющих определенную конфигурацию в зависимости от характера выполняемых операций. Перечень символов, их наименование, отображаемые ими функции, форма и размеры определяются ГОСТами.
При всем многообразии алгоритмов решения задач в них можно выделить три основных вида вычислительных процессов:
- линейный;
- ветвящийся;
- циклический.
Линейным называется такой вычислительный процесс, при котором все этапы решения задачи выполняются в естественном порядке следования записи этих этапов.
Ветвящимся называется такой вычислительный процесс, в котором выбор направления обработки информации зависит от исходных или промежуточных данных (от результатов проверки выполнения какого-либо логического условия).
Циклом называется многократно повторяемый участок вычислений. Вычислительный процесс, содержащий один или несколько циклов, называется циклическим . По количеству выполнения циклы делятся на циклы с определенным (заранее заданным) числом повторений и циклы с неопределенным числом повторений. Количество повторений последних зависит от соблюдения некоторого условия, задающего необходимость выполнения цикла. При этом условие может проверяться в начале цикла - тогда речь идет о цикле с предусловием, или в конце - тогда это цикл с постусловием.