Типы алгоритмов — Гипермаркет знаний. Виды алгоритмов

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

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

В информатике план действий называют алгоритмом .
Алгоритм состоит из отдельных шагов – команд . Ни одну из них нельзя пропустить, чаще всего никакие команды нельзя поменять местами.
Исполнитель – человек, животное или машина, способные понимать и выполнять некоторые команды.
Среда исполнителя – предметы, которые окружают исполнителя и с которыми он работает.
Список Команд Исполнителя (СКИ) – набор команд, понятных исполнителю. Исполнитель может выполнить только те команды, которые входят в его СКИ.

Для решения большинства задач недостаточно отдать одну команду исполнителю, надо составить для него алгоритм – план действий, состоящий из команд, которые ему понятны (входят в его СКИ).
Алгоритм – точно определенный план действий исполнителя, направленный на решение какой-то задачи. В алгоритм можно включать только те команды, которые есть в СКИ.

Какие бывают алгоритмы

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

Разветвляющийся алгоритм

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

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

Способы записи алгоритмов

Выделяют три наиболее распространенные на практике способа записи алгоритмов:

• словесный (запись на естественном языке);
• графический (запись с использованием графических символов);
• программный (тексты на языках программирования).

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

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

В качестве примера словесного способа записи алгоритма рассмотрим алгоритм нахождения площади прямоугольника

где S – площадь прямоугольника; а, b – длины его сторон.

Очевидно, что a, b должны быть заданы заранее, иначе задачу решить невозможно.

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

• Начало алгоритма.
• Задать численное значение стороны a.
• Задать численное значение стороны b.
• Вычислить площадь S прямоугольника по формуле S=a*b.
• Вывести результат вычислений.
• Конец алгоритма.

Графический способ описания алгоритмов

Для более наглядного представления алгоритма используется графический способ. Существует несколько способов графического описания алгоритмов. Наиболее широко используемым на практике графическим описанием алгоритмов является использование блок-схем. Несомненное достоинство блок схем – наглядность и простота записи алгоритма.

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

Так как в линейном алгоритме команды выполняются последовательно, то блок-схема будет иметь вид:

Так как в разветвляющемся алгоритме порядок следования команд может быть разный в зависимости от того, какова окружающая обстановка, то блок-схема примет вид:

В циклическом алгоритме некоторые действия повторяются несколько раз и для него блок-схема примет вид:

Программный способ записи алгоритмов

Для того, чтобы алгоритм был понятен роботу, компьютеру или другой машине, недостаточно только написать команды, надо еще и оформить алгоритм в таком виде, в котором его понимает машина (написать программу), т.е. записать его с использованием команд из СКИ, соблюдая правила оформления.

Правила оформления программы:

1. любой алгоритм имеет название;
2. алгоритм начинается с открывающей фигурной скобки “{“ и заканчивается закрывающей фигурной скобкой “}”; команды, расположенные между этими скобками, называются телом алгоритма;
3. в алгоритм могут входить только те команды, которые есть в СКИ исполнителя;
4. каждая команда заканчивается знаком “;”, который обозначает конец команды;
5. для того, чтобы нам было легче разбираться в программах, используют комментарии - текстовые пояснения, которые начинаются знаками “/*” и заканчиваются знаками “*/”; исполнитель не обращает внимания на комментарии в алгоритме.

Практические задания:

1. Составить блок-схему для нахождения периметра квадрата.
2. Составить блок схему для заваривания чая.
3. Составить блок-схему для перехода перекрестка со светофором.

Использован материал из книг:

1. "Современные информационные технологии", авторы преподаватели центра "Турбо"
2. "Алгоритмы и исполнители", автор Поляков К.

1. Линейный - алгоритм, в котором все предписания (шаги) выполняются так, как записаны, без изменения порядка следования, строго друг за другом.

2. Разветвляющийся - алгоритм, в котором выполнение того или иного действия (шага) зависит от выполнения или не выполнения какого-либо условия.

3. Циклический - алгоритм, в котором некоторая последовательность действий повторяется несколько раз.

Форма представления алгоритма зависит от его типа. Применяют не­сколько форм представления алгоритмов:

1) Табличную (применяется только для линейных вычислительных алгоритмов).

2) Словесно – формульное описание алгоритма, т.е описание с помощью слов и формул (применима для алгоритмов всех типов).

3) Графическое описание алгоритма (применима для алгоритмов всех типов), т.е описание с помощью специальных графических схем алгоритмов – блок-схем. Блок-схема алгоритма представляет собой систему связанных геометрических фигур. Каждая фигура обозначает один этап решения задачи и называется блоком. Порядок выполнения этапов указывается стрелками, соединяющими блоки. В схеме блоки стараются размещать сверху вниз в порядке их выполнения. Для наглядности операций разного вида изображаются в схеме различными геометрическими фигурами.

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

5) Запись алгоритма на одном из языков программирования .

Сроки: 2 5 .09.201 4 г. Класс: 9 Д Преподаватель: Мамедов А.

Тема урока : «ТИПЫ АЛГОРИТМОВ. »

Вид урока : смешанный.

Цели урока: дать понятие командам, структурам алгоритмов и научить этапам решения задач на паскале.

СТРУКТУРА АЛГОРИТМОВ

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

возьмем дневник откроем нужную страницу выполним домашнее задание поставим дневник на место

Команды линейного алгоритма состоят из команд (блоков), которые выполняются в указанной последовательности. Такое выполнение операций друг за другом назовем естественным поряд­ком.

Разветвляющиеся алгоритмы. В повседневной жизни алго­ритмы в основном делятся на группы, в которых в зависимости от выполнения или невыполнения некоторого условия последовательность команд разделяется на несколько ветвей.

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

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

если условие

то 1 -я серия иначе 2-я серия

Для выполнения алгоритмов в команде разветвления сначала проверяются условия. Если условия выполняются, то вьполняются команды 1 -й серии, заключенные между ключевыми словами если и иначе. Если условия не вьполняются, то вьполняются команды 2-й серии, заключенные между ключевыми словами иначе и все. В схему этого вида разветвляющегося алгоритма обязательно входит блок проверки условия. Он изображается в виде ромба и связывается с другими блоками с помощью одной линии входа и двух линий выхода.

В полном виде разветвляющегося алгоритма осуществляется выбор только одной серии из двух. Если высказывание истинно, тогда выполняется 1 -я серия, затем осуществляется переход к следующим операциям. Если высказывание ложно, то выполняется 2-я серия, только затем производятся следующие действия алгорит­ма. Итак, в зависимости от истинности или ложности высказывания выполняется 1 -я или 2-я серия.

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

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

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

вопросы для закрепления:

В чем сходство и отличия между программой и алгоритмом?

Перечислите свойства алгоритмов, выполняемых на компьютере.

Какие способы описания алгоритмов вы знаете?

Какими могут быть этапы решения задач на компьютере?

Перечислите виды блоков в схеме алгоритма, их изображения и связи.

Что вы знаете о линейных, разветвляющихся и циклических алгоритмах?

Назовите итерационные циклы и их особенности.

Известны три типа алгоритмов – линейные, разветвляющиеся, циклические.

Линейный тип алгоритмов

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

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

Пример

Постановка задачи : вычислить площадь круга, если известен радиус.

Дано: R– радиус круга.

Найти: S– площадь круга.

Решение: S=3,14R 2

Словесная форма записи алгоритма

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

Прочесть значение R.

Умножить значение Rна 3,14.

Умножить результат второго действия на значение R.

Записать полученный результат как значение S.

На языке блок-схем – рис. 8

Разветвляющийся тип алгоритмов

Решение задач не всегда можно представить в виде линейного алгоритма.

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

При графическом способе ветвление организуется с помощью логического элемента (ромб), имеющего один вход и два выхода. Назначение логического элемента – проверка заданного условия. В зависимости от выполнения (истинности) или невыполнения (ложности) проверяемого условия возможен выход соответственно на ветвь «Да» или «Нет».

Пример

Постановка задачи : вычислить
.

Дано : х – значение аргумента.

Найти : у – значение функции.

Решение:

y= x , если х  0

- x , если х<0

Блок-схема - см. рис. 9.

Словесное представление

На псевдокоде :

Прочесть значение х

Если х>0, то

Конец ветвления

Записать значение у

Выделяют полную и неполную условную конструкцию .

Циклический тип алгоритмов

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

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

Однако, «неоднократно» не значит «до бесконечности». Организация циклов, никогда не приводящая к остановке в выполнении алгоритма (так называемое зацикливание), является нарушением требования его результативности.

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

параметр цикла – величина, с изменением которой связано многократное выполнение цикла;

начальное и конечное значение параметра цикла ;

шаг цикла – это значение, на которое изменяется параметр цикла при каждом повторении.

Циклический алгоритм состоит из подготовки цикла, тела цикла, условия продолжения цикла .

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

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

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

Рассмотрим графическое представление циклического блока алгоритма (см. рис. 10).

Циклы могут быть с предусловием (когда условие проверяется перед началом тела цикла) и спостусловием (когда условие проверяется после первого прохождения тела цикла).

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