Классификация способов представления алгоритмов
Различают следующие виды алгоритмов :
линейный – список команд (указаний), выполняемых последовательно друг за другом;
разветвляющийся – алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один из возможных вариантов решения;
циклический – алгоритм, предусматривающий многократное повторение одной и той же последовательности действий. Количество повторений обусловливается исходными данными или условием задачи.
Любая алгоритмическая конструкция может содержать в себе другую конструкцию того же или иного вида, т. е. алгоритмические конструкции могут быть вложенными. Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг,электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е.словесное описания алгоритма, в соответствии которому данный прибор должен использоваться. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.
1. определить температуру воздуха
2. если температура ниже 0, то надеть шубу, иначе надеть куртку
Псевдокод — описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основныеэтапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Строгих синтаксических правил для записи псевдокода не существует. Это облегчает запись алгоритма при проектировании и позволяет описать алгоритм, используя любой набор команд. Однако в псевдокоде обычно используются некоторые конструкции, присущие формальным языкам, что облегчает переход от псевдокода к записи алгоритма на языке программирования. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций.
Блок-схема — описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость»алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.
Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем они настолько достаточны, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования .
Источник
Теория алгоритмов и программ — Практика
1. Основные понятия алгоритма. Правила построения и разбиения программ
Алгоритм – конечный набор правил или команд (указаний), позволяющий исполнителю решать любую конкретную задачу из некоторого класса однотипных задач.
Исполнителем может быть человек, группа людей, станок, компьютер и др. С учетом особенностей исполнителя составленный алгоритм может быть представлен различными способами: с помощью графического или словесного описания, в виде таблицы, последовательностью формул, записанных на алгоритмическом языке (языке программирования) и др.
Язык – знаковая система (множество символов и правил) любой физической природы, выполняющая познавательную и коммуникативную (общение) функции в процессе человеческой деятельности.
Язык может быть естественным и искусственным. Естественный язык – форма выражения мыслей и средство общения между людьми. Искусственный язык – вспомогательный, созданный на базе естественного языка людьми для каких-либо частных целей. Первоначально для записи алгоритмов пользовались средствами естественного языка.
Словесный алгоритм – описание последовательных этапов обработки данных на естественном языке.
Уточним понятие словесного алгоритма на примерах сложения n чисел , т.е. вычисления по формуле и нахождения минимального числа x в массиве из n чисел .
В первом случае процесс может быть записан в виде следующей системы последовательных указаний:
- Полагаем S равным нулю и переходим к следующему указанию.
- Полагаем i равным единице и переходим к следующему указанию.
- Полагаем S равным S+a1 и переходим к следующему указанию.
- Проверяем, равно ли i числу n. Если равно, то вычисления прекращаем. Если i
Процесс нахождения минимального числа x в массиве из n чисел , осуществляется следующим образом. Первоначально в качестве числа x принимается a1, т.е. полагаем x=a1 , после чего x сравниваем с последующими числами массива, начиная с a2. Если х
- Полагаем i=1 и переходим к следующему указанию.
- Полагаем х=ai и переходим к следующему указанию.
- Сравниваем i с n, если i
- Увеличиваем i на единицу и переходим к следующему указанию.
- Сравниваем ai с х. Если ai>x, то переходим к указанию 3, если ai
Алгоритмами в современной математике принято называть конструктивно задаваемые соответствия между словами в абстрактных алфавитах.
Под абстрактным алфавитом понимают любую конечную совокупность объектов, называемых буквами или символами данного алфавита. Символом абстрактных алфавитов можно считать, например, буквы алфавита какого-либо языка, цифры, любые знаки, рисунки и т.п.
Также понятие «алгоритм» можно уточнить, указав перечень основных свойств, характерных для алгоритмов. К ним относятся:
- Дискретность алгоритма означает, что алгоритм разделен на отдельные шаги (действия), причем, выполнение очередного шага возможно только после завершения всех операций на предыдущем шаге. При этом набор промежуточных данных конечен и он получается по определенным правилам из данных предыдущего шага.
- Детерминированность алгоритма состоит в том, что совокупность промежуточных величин на любом шаге однозначно определяется системой величин, имевшихся на предыдущем шаге. Данное свойство означает, что результат выполнения алгоритма не зависит от того, кто (или что) его выполняет (т.е. от исполнителя алгоритма), а определяется только входными данными и шагами (последовательностью действий) самого алгоритма.
- Элементарность шагов: закон получения последующей системы величин из предыдущей должен быть простым и локальным. Какой шаг (действие) можно считать элементарным, определяется особенностями исполнителя алгоритма.
- Направленность алгоритма: если способ получения последующих величин из каких-либо исходных не приводит к результату, то должно быть указано, что следует считать результатом алгоритма.
- Массовость алгоритма: начальная система величин может выбираться из некоторого множества.
Последнее свойство означает, что один алгоритм, т.е. одна и та же последовательность действий, в общем случае, может применяться для решения некоторого класса (т.е. многих) задач. Для практики и, в частности, решения задачи на компьютере, это свойство существенно, поскольку, как правило, пользовательская ценность программы оказывается тем выше, чем больший круг однотипных задач она позволяет решить. Однако для построения алгоритмической теории это свойство не является существенным и обязательным.
Как видно из рисунка 1 по уровню формализации представление алгоритмов можно разделить на две группы: естественное и формальное. В группу естественного представления входят некоторые виды строчной записи и графическая форма. Группа формального представления включает алгоритмические модели и формальные языковые конструкции.
В данном случае нас интересует графический способов представления алгоритмов, а именно, блок-схемы.
Классификация способов представления алгоритмов
Рис. 2.1. Классификация способов представления алгоритмов
Блок-схема представляет собой совокупность символов, соответствующих этапам работы алгоритма и соединяющих их линий.
В этой форме для представления отдельных блоков алгоритма используются обусловленный набор геометрических фигур (табл. 2.1).
Графическая форма предназначена, безусловно, только для исполнителя «человек» — в этом ее основной недостаток. Главное достоинство такой формы представления — наглядность; блок-схема позволяет охватить весь алгоритм сразу, отследить различные варианты его выполнения. На стадии разработки в блоках можно делать записи как на естественном, так и на формальном языке. Именно по этой причине блок-схема считается весьма полезной формой при обучении алгоритмизации, а также при разработке сложных алгоритмов. Однако в блок-схеме, как правило, отсутствует подробное описание конкретных действий — их существование лишь обозначено.
Обозначения основных символов блок-схемы
По блок-схеме гораздо проще осуществляется запись алгоритма на каком-либо формальном языке. Правда, следует заметить, что синтаксическое богатство языков программирования выше языка блок-схем — по этой причине не все языковые конструкции имеют простое графическое представление — примером может служить конструкция цикла с параметром FOR . DO (или FOR . NEXT), не имеющая собственного представления в языке блок-схем.
Пример простой линейной программы:
Пример использования оператора ветвления:
Пример задачи с циклом – пока a меньше 100, увеличивать а на 5:
Пример задачи с циклом (задано число итераций и шаг) – найти сумму 10 введенных чисел; i:=0,10,1 (начальное значение, конечное значение, шаг):
Пример задачи-вопроса – какое значение будет выведено, если а=35?:
Пример задачи-вопроса – какое значение будет выведено?:
В заключение хотелось бы подчеркнуть различие между блок-схемами и синтаксическими диаграммами. Синтаксические диаграммы являются средством описания и средством генерации конструкций формального языка. При этом каждая диаграмма позволяет генерировать множество однотипных конструкций. Другими словами синтаксическая диаграмма — это правило порождения некоторой конструкции языка. Блок-схема же является графической формой представления конкретного алгоритма, в который отдельные конструкции входят в качестве составных элементов.
Источник
Виды алгоритмов и типы их схем
В этой статье будут рассмотрены основные виды алгоритмов, а также схематические блоки, которые используются при их описании. Кроме получения информации о видах блоков алгоритмов, читатель узнает о наиболее популярных методах описания алгоритмических последовательностей. Будут приведены соответствующие примеры с пояснениями.
Блок-схема
Алгоритмы бывают разные, но прежде чем приступить к рассмотрению их видов, следует рассказать об основном способе визуализации алгоритмической последовательности — созданию блок-схемы. Такие схемы состоят из соответствующих функциональных блоков, которые связаны между собой. Каждый блок отвечает за выполнение какого-нибудь действия. Для каждого типа действия определён конкретный блок, представляющий собой геометрическую фигуру.
Существует и очередность выполнения действий — она определяется линиями, которые соединяют блоки. По умолчанию используемые в схеме блоки соединяются слева направо и сверху вниз. В случае другой последовательности выполнения, блоки соединяются направленными линиями (речь идёт о линиях, оснащённых стрелками).
Типы и назначение блоков алгоритма можно посмотреть в таблице ниже:
Теперь рассматривать виды алгоритмов будет гораздо понятнее.
Виды алгоритмов
Алгоритмы бывают: — линейные – подразумевается последовательное выполнения операций (команд, указаний), то есть выполнение действий происходит друг за другом. Вот, как это выглядит на схеме с блоками:
— разветвляющиеся – характеризуются выполнением хотя бы одной операции по проверке условия, в результате чего осуществляется переход действия на какой-нибудь другой из возможных вариантов решения. Смотрим схему:
— циклические – данным алгоритмом предусмотрено многократное повторение определенной последовательности действий (речь идёт об одинаковых операциях). Здесь число повторений будет обусловлено либо условием задачи, либо исходными данными.
Также стоит добавить, что любая алгоритмическая конструкция способна включать в себя какую-нибудь другую конструкцию того либо иного вида, то есть алгоритмы бывают вложенными.
Способы описания алгоритмов
О блок-схеме, как об основном способе представления алгоритмов, мы уже поговорили. Но кроме блоков, есть и другие методы:
- Словесное описание — это когда структура алгоритма описывается естественным языком. Лучше всего вспомнить любой бытовой прибор (утюг, телевизор, микроволновую печь, холодильник и т. п.). Все эти приборы имеют инструкцию по эксплуатации, то есть перед нами типичное описание алгоритма словами, с учётом которых прибором надо пользоваться. Такой способ не формализован и не учитывает все возможные ситуации, возникающие при эксплуатации. К недостаткам словесного описания относят и неоднозначность толкования некоторых терминов.
Представьте, что вы куда-то собрались, и вас интересует погода на улице. Словесное описание будет приблизительно таким: 1) смотрим на градусник, определяем температуру на улице; 2) если температура ниже 0, надеваем шубу, если выше — куртку. - Псевдокод — в этом случае можно говорить о естественном и частично формализованном языке, то есть это описание уже позволяет определить главные этапы решения задачи, что необходимо перед составлением программы — точной записи на языке программирования. Псевдокод характеризуется уже наличием формализованных конструкций и общепринятой математической символикой, однако строгих синтаксических правил по записи не существует.
- Блок-схема. Схему, состоящую из блоков и линий, включая значения наиболее часто используемых блоков, уже рассмотрели выше. Но вернёмся к нашему примеру с погодой:
- Программа — описание, созданное на языке алгоритмического программирования. Такой вариант характеризуется высокой степенью формализации, то есть появление программы позволяет решать прикладные задачи. В форме программы описываемый ранее пример будет выглядеть следующим образом:
Источник
