Средства представления алгоритмов
Процесс составления алгоритмов называют алгоритмизацией. Алгоритм можно представить различными способами: с помощью графического или текстового описания, в виде таблицы значений.
Графический способ представления алгоритмов имеет ряд преимуществ благодаря визуальности процесса решения задачи. Алгоритмы, представленные графическими средствами, получили название визуальные алгоритмы или блок – схемы .
Текстовое описание алгоритма является достаточно компактным и может быть реализовано на абстрактном или реальном языке программирования в виде программы для ЭВМ. Таблицы значений представляют алгоритм неявно, как некоторое преобразование конкретных исходных данных в выходные.
Табличный способ описания алгоритмов. Применяют для проверки правильности функционирования алгоритма на конкретных тестовых наборах входных данных, которые вместе с результатами выполнения алгоритма фиксируются в «таблицах трассировки».
Все три способа представления алгоритмов являются взаимодополняющими. На этапе проектирования наилучшим является графическое представление, на этапе проверки алгоритма — табличное описание, на этапе применения — текстовая запись в виде программы.
Визуальное представление алгоритмов
При проектировании визуальных алгоритмов используют специальные графические элементы, называемые графическими блоками, которые представ-лены в таблице. Существует Государственный стандарт (ГОСТ 19.002-80 и ГОСТ 19.003-80), определяющий правила выполнения схем и обозначения для отдельных операций.
Правила проектирования визуальных алгоритмов:
• В начале алгоритма должны быть блоки ввода значений входных данных.
• После ввода значений входных данных следуют блоки обработки и блоки условия.
• В конце алгоритма должны располагаться блоки вывода значений выходных данных.
• В алгоритме должен быть только один блок начала и один блок окончания.
• Связи между блоками указываются направленными или ненаправленными линиями.
• Данные, вычислительные формулы, логические выражения располагают внутри соответствующих блоков.
• Блоки могут сопровождаться комментариями в виде выносок.
Графическое представление алгоритмов имеет практическое значение не только для программистов. Те же информационные схемы (инфографика) используются журналистами для визуализации данных. Структурные схемы последовательности монтажа полезны для сборщиков мебели, например. Та же визуализация алгоритма трассировки (алгоритм Ли) может быть полезна для конструирования печатных плат, особенно когда требуется срочное изготовление таких плат по требованиям заказчика.
Источник
Способы представления алгоритмов
1. Словесный. Такое описание алгоритма состоит из словесного перечня действий в виде предложений.
Например, вычислить C=
Исходные данные А и В ввести в память ЭВМ, проверить выполнение неравенства АB. Если оно выполняется, то вычислить А-В. Результат обозначить как С и вывести его; в противном случае вычислить А+В, результат обозначить С и вывести его.
Недостаток такого представления — отсутствие четкой формализации и наглядности выполнения процесса.
Достоинством является то, что таким способом можно описывать алгоритмы с любою степенью детализации.
2. Формульно-словесный способ основан на задании инструкций о выполнении конкретных действий в четкой последовательности в сочетании со словесными пояснениями.
Для рассмотренного задания алгоритм, представленный формульно-словесным способом, будет следующим:
Этап 1. Ввести А, В.
Этап 2. Если АB, то перейти к этапу 4, иначе — к этапу 3.
Этап 3. С=А-В, перейти к этапу 5.
Этап 5. Принять значение С за результат.
Этап 6. Вывести С.
Этот способ более компактен, но не является строго формальным.
3. Табличный. Алгоритм задается в виде таблиц и расчетных форм. Этот способ наиболее часто используется в экономических расчетах. Исходные данные и результаты вносятся в заголовки столбцов таблицы.
4. Операторный (язык операторных схем). При использовании этого способа вычислительный процесс изображается в виде последовательности символов (операторов). Они обозначают группы стандартных или нестандартных операций, реализующих законченную процедуру с указанием связи между отдельными операторами. Этот способ значительно упрощает составление программы для компьютера, при этом вместо операторов подставляются соответствующие команды. Недостатком данного способа является его малая наглядность.
5. Графический (способ блок-схем). При таком представлении алгоритма каждый этап отображается в виде геометрических фигур — “блоков”, форма которых зависит от выполняемой операции. Блок может иметь имя (метку). Линия соединения блоков показывает направление процесса обработки данных. Каждое направление называется ветвью. Перечень блоков, их наименование, функции, формы, размеры определяются ГОСТ 19.003- 80.
Указанный ГОСТ регламентирует изображение и размеры отдельных блоков в блок-схеме, а также их взаимное расположение. Блоки, в которых не предусматривается разветвление алгоритма по условию, имеют вид прямоугольника с размерами сторон, отношение которых равно 3:2. Блоки, предусматривающие проверку условия с последующим разветвлением, — форму ромба, соотношение диагоналей которого также равно 3:2. Каждая блок-схема обязательно должна включать в себя блок-начало и блок-конец. Форма этих блоков — прямоугольник со скругленными углами, размеры — 3:1. Отдельно определяются блоки, в которых осуществляется ввод и вывод информации. В зависимости от того, откуда и куда осуществляется ввод/вывод, используются разные виды блоков ввода/вывода. Однако можно использовать блок ввода/вывода общего назначения в виде параллелограмма с соотношением длины основания к высоте как 3:2. Блоки соединяются стрелками, показывающими последовательность исполнения. Сам значок “стрелка” в направлении “вниз” и “вправо” можно не ставить, “вверх” и “влево ” — ставить обязательно. Блоки должны быть расположены так, чтобы расстояние между блоками и стрелками составляло не меньше 5 мм.
Алгоритм линейной структуры состоит из последовательности действий, формирующих одну ветвь вычислений. Примером линейного алгоритма может быть алгоритм расчета У по формуле У=Х 2 .
Решение задач не всегда можно представить в виде линейного алгоритма. Существуют задачи, в которых требуется организовать выбор выполнения последовательности действий в зависимости от каких-либо условий. Такие алгоритмы называются алгоритмами разветвляющейся структуры. В них должен присутствовать один или несколько логических операторов (проверки условия) и несколько ветвей решения. Примером разветвляющегося алгоритма может быть выбор наибольшего из двух введенных произвольных чисел.
Алгоритмы, отдельные действия в которых многократно повторяются, называются алгоритмами циклической структуры. Совокупность повторяющихся действий алгоритма принято называть циклом. При разработке циклического алгоритма вводят следующие понятия: параметр цикла — величина, с изменением значения которой связано многократное выполнение цикла; начальное и конечное значение параметров цикла; шаг цикла — значение, на которое изменяется параметр цикла при каждом повторении.
Цикл организуют по определенным правилам. Циклический алгоритм состоит из подготовки цикла; тела цикла; условия продолжения цикла.
В подготовку цикла входят действия, связанные с заданием исходных данных для параметров цикла и других величин, использующихся в цикле.
В тело цикла входят многократно повторяющиеся действия для вычисления искомых величин; подготовка следующего значения параметра цикла, подготовка других значений, необходимых для повторного выполнения действий в теле цикла.
В условии продолжения цикла определяется необходимость дальнейшего выполнения повторяющихся действий (тела цикла). Если параметр цикла превысил конечное значение, то выполнение цикла должно быть прекращено.
Примером циклического алгоритма выступает алгоритм определения суммы десяти произвольных чисел, вводимых пользователем.
Статьи к прочтению:
ОАиП. Лекция 1 \
Похожие статьи:
Для того чтобы ЭВМ <без участия человека>выполнила некоторые действия необходимо задать последовательность инструкций (команд) на понятном компьютеру…
Существуют несколько способов описания алгоритма: словесное, псевдокод, блок-схема, программа. Словесное описание представляет структуру алгоритма на…
Источник
Способы записи алгоритмов
На практике применяются алгоритмы следующих типов:
Линейные алгоритмы
Это алгоритмы, у которых последовательность операций при исполнении совпадает с порядком их следования в записи алгоритма и не зависит от конкретных значений исходных данных. С помощью таких алгоритмов реализуются задачи типа:
Y = А*Х+В
разветвляющиеся, ветвящиеся алгоритмы. Такие алгоритмы
используются для решения задач, в которых заложена операция выбора одной из формул, в зависимости от заданного
значения переменной. Такие алгоритмы используются при
решение задач, типа:
Y=Ln x, при x>=1
Y=1-x, при x n
Для записи алгоритмов обычно используют табличный, словесный и схематичный способы записи.
Табличный способ записи алгоритмов
Табличный способ записи алгоритмов применяется, когда требуется вычислить не одно, а несколько значений одного и того же выражения для различных значений входных величин.
Например, требуется вычислить площадь поверхности цилиндрического тела по формуле:
S=3.14*(D*H+D 2 /2)
где D — диаметр, Н — высота.
Табличный алгоритм вычисления площади поверхности тела по указанной формуле представлен в таблице:
| D | H | 3.14*D | 3.14*D 2 | 3.14*D 2 /2 | 3.14*D*H | S |
|---|---|---|---|---|---|---|
| 6 | 4 | 18,84 | 113,04 | 56,52 | 75,36 | 131,88 |
| 5 | 10 | 15,7 | 78,5 | 39,25 | 157 | 196,25 |
| 10 | 12 | 31,4 | 314 | 157 | 376,8 | 533,8 |
Словесный способ записи алгоритмов
Одна из самых распространенных форм представлении алгоритмов — словесная форма. Особенностью словесной представления алгоритма является то, что таким cnocoбом могут быть описаны любые алгоритмы, в том числе и вычислительные.
Опишем последовательность действий для вычислений по формуле:
Y=(6*x+25)/2.
1) Прочитаем заданное значение X;
2) Умножим X на 6;
3) К результату второго действия прибавим 25;
4) Результат третьего действия разделим на 2;
5) Запишем значение результата Y;
В результате получили словесную запись линейного вычислительного алгоритма.
В приведенном вычислительном алгоритме X является входной величиной (исходным значением, аргументом), а Y выходной величиной (результатом).
В словесной записи алгоритма, если при исполнении текущего предписания не указывается явно номер очередного предписания, происходит автоматический переход к предписанию, следующему за данным в порядке возрастания номеров.
После исполнения предписания с наибольшим номером, процесс выполнения алгоритма заканчивается.
Для удобства рекомендуется заканчивать запись словес о алгоритма специальным предписанием «конец».
При записи вычислительных алгоритмов удобно использовать специальный знак присваивания :=. Этот знак используется для записи специальной операции операции присваивания. Смысл операции присваивания состоит в том, что некоторой переменной, имя которой указывается слева, присваивается значение некоторого выражения, указанного справа.
Например, предписание, вида Y:=X читается так: «переменной Y присвоить значение X». Если X — является формулой, тогда нужно выполнить все действия, предусмотренные формулой и полученный результат (число) присвоить переменной Y.
Операция присваивания может быть обозначена и обычным знаком равенства или стрелками: A:=D*B, A=D*B, A->D*B.
Используя знак операции присваивания и вспомогательные переменные, в которых будут запоминаться промежуточные значения, можно сделать запись приведенного выше словесного алгоритма значительно компактнее:
После составления словесного алгоритма необходимо провести контроль правильности составления алгоритма. Проверка алгоритма в таблице состоит в том, что выбираются конкретные исходные данные и составленный алгоритм выполняется в строгом соответствии с записанными предписаниями.
Таблица контроля правильности алгоритма вычисления Y=(6*X+25)/2
| Шаги алгоритма | Аргумент X | Промежуточная величина А | Промежуточная величина B | Результат Y | Пояснения |
| 1 | 2 | чтение X | |||
| 2 | 12 | ||||
| 3 | 37 | ||||
| 4 | 18.5 | ||||
| 5 | запись 18.5 | ||||
| 6 | остановка |
Важное свойство операции присваивания состоит в том, что одна и та же переменная может находиться и слева и справа от знака присваивания, т.е. можно записать
А := А+В.
Такая запись означает, что к значению переменной А, которое она имела до начала выполнения операции присваивания, прибавляется значение переменной В и полученное в результате значение присваивается переменной А (становится новым значением переменной А). Прежнее значение переменной А при этом пропадает.
Используя это свойство операции присваивания, можно отказаться от использования избыточных промежуточных переменных.
Тогда запись алгоритма вычисления Y будет иметь следующий вид:
В приведенном примере можно не использовать ни одной вспомогательной переменной, т.к. для хранения промежуточных результатов достаточно использовать одну переменную Y.
Таблица проверки правильности алгоритма наглядно показывает механизм проведенных присваиваний.
Таблица контроля правильности алгоритма вычисления Y=(6*x+25)/2 без избыточных вспомогательных переменных
Источник
Средства представления алгоритмов
АЛГОРИТМЫ
Основные понятия
Понятие «алгоритм» появилось в девятом веке и связано с именем
математика Аль-Хорезми, который сформулировал правила выполнения
четырех арифметических действий над многозначными числами.
В настоящее время понятие алгоритма – одно из фундаментальных
понятий науки информатики. С одной стороны, алгоритм является
предметом изучения такой отрасли математики как теория алгоритмов, с
другой стороны, в информатике существует неформальное определение
алгоритма, и алгоритмизация выступает в качестве общего
Алгоритм– это точно определенная последовательность действий
для некоторого исполнителя, выполняемых по строго определенным
правилам и приводящих через некоторое количество шагов
к решению задачи.
Исполнитель алгоритмовопределяет элементарные действия, из
которых формируется алгоритм. Отдельные действия, составляющие
алгоритм, называются операциями. При этом под операцией понимается
как какое-то единичное действие, например, сложение, так и группа
Основными особенностями любого алгоритма являются решение
задачи в обобщенном виде и возможность выполнять действия по
решению задачи для конкретных значений (не только человеку, но и
различным техническим устройствам (исполнителям)). Основным
исполнителем несложных алгоритмов является человек. Достаточно
вспомнить последовательность действий для решения систем линейных
уравнений, вычисления корней уравнений.
При решении сложных задач исполнителем является программное
обеспечение ЭВМ, и составление алгоритма решения задачи является
необходимым этапом, детализирующим метод решения для
определенность – выполнив очередное действие, исполнитель
должен точно знать, что ему делать дальше;
дискретность – прежде, чем выполнить определенное действие,
надо выполнить предыдущее;
массовость – по одному и тому же алгоритму решаются
однотипные задачи и неоднократно;
понятность – алгоритм строится человеком для конкретного
исполнителя и должен быть ему понятен. Это облегчает его проверку и
модификацию при необходимости;
результативность – алгоритм всегда должен приводить
Мы видим, что в процессе формального решения задачи ее решение
сначала описывается на языке математики в виде системы формул, а затем
на языке алгоритмов в виде некоторого процесса, в котором используются
ранее определенные математические формулы и условия их выполнения.
Таким образом, алгоритм рассматривается как средство описания
процесса решения задачи, как связующее, промежуточное звено в цепочке
«метод решения – реализующая программа».
Средства представления алгоритмов
Построение алгоритмов подчиняется отдельным законам, использует
специальный язык для обозначений основных понятий и терминов,
активно используется для описания методов решения задач.
Алгоритм, реализующий решение задачи, можно задать различными
способами на основе различных языковых средств: графических,
Графические средствапредставления алгоритмов имеют ряд
преимуществ благодаря визуальности и явному отображению процесса
решения задачи. Алгоритмы, представленные на языке графических
объектов, получили название визуальные алгоритмы.
Текстовое описаниеалгоритма является достаточно компактным и
может быть реализовано на абстрактном или реальном языках
программирования в виде программы для ЭВМ. Таблицы значений
представляют алгоритм неявно, как некоторое преобразование конкретных
исходных данных в выходные.
Табличный способописания алгоритмов может быть с успехом
применен для проверки правильности функционирования разработанного
алгоритма на конкретных тестовых наборах входных данных, которые
вместе с результатами выполнения алгоритма фиксируются в «таблицах
Таким образом, все три способа представления алгоритмов можно
считать взаимодополняющими друг друга. На этапе проектирования
алгоритмов наилучшим способом является графическое представление, на
этапе проверки алгоритма – табличное описание, на этапе применения –
текстовая запись в виде программы.
Визуальные алгоритмы
При проектировании визуальных алгоритмов используют следующие
графические блоки, представленные на рис. 2.
Рассмотрим общие правила при проектировании визуальных
в начале алгоритма должны быть блоки ввода значений
после ввода значений входных данных могут следовать
блоки обработки и блоки условия;
в конце алгоритма должны располагаться блоки вывода
значений выходных данных;
в алгоритме должен быть только один блок начала и один
связи между блоками указываются направленными или
Этап проектирования алгоритма следует за этапом выбора
формальной модели и методов решения задачи, на котором определены
входные и выходные данные, а также зависимости между ними.
При построении алгоритмов для сложной задачи используют
системный подход с использованием последовательной декомпозиции
решаемой задачи на ряд подзадач до тех пор, пока не будут определены
задачи, для которых алгоритмическое решение известно или оно может
быть оперативно найдено.
Одним из системных методов разработки алгоритмов является метод
структурной алгоритмизации. Этот метод основан на визуальном
представлении алгоритма в виде последовательности управляющих
структурных фрагментов. Выделяют три базовые управляющие процессом
обработки информации структуры: композицию, альтернативу и итерацию.
С помощью этих структур можно описать решение большого класса задач
Композиция (следование)– это линейная управляющая
конструкция, не содержащая альтернативу и итерацию. Она предназначена
для описания единственного процесса обработки информации.
Альтернатива– это нелинейная управляющая конструкция, не
содержащая итерацию. Она предназначена для описания процессов
решения различных задач обработки информации, выбор которых зависит
от значений входных данных.
Итерация– это циклическая управляющая конструкция, которая
содержит композицию и ветвление. Она предназначена для организации
повторяющихся процессов обработки последовательности
Линейные алгоритмы не содержат блока условия. Они
предназначены для представления линейных процессов. Такие алгоритмы
применяют для описания обобщенного решения задачи в виде
Пример линейного алгоритма приведен на рис. 3.
В соответствии с наличием в алгоритмах управляющих структур
композиции, альтернативы и итерации алгоритмы классифицируют на
линейные, разветвленные и циклические алгоритмы.
Разветвленные алгоритмы
Разветвленные алгоритмыв своем составе содержат блок условия
и различные конструкции ветвления. Ветвление– это структура,
обеспечивающая выбор между альтернативами.
Каждая управляющая структура ветвления имеет один вход и один
выход. Ветвления содержат блок условия, в котором записывают
логические условия, такие как А > С, X С принимает значение «истина» или «ложь» и процесс вычислений
включает блок действия Z = A или Z = C. Аналогично происходит и в
управляющей структуре неполного ветвления (рис. 4, б). Только в этом
случае, если условие X 2 = X 2 +Y 2 .
Пример 4. Составить алгоритм определения корней уравнения X 2 +B*X+C=0.
Решение. При составлении этого алгоритма надо рассмотреть случаи, когда
уравнение не имеет корней и когда имеется только один корень. Обозначим корни
уравнения через переменные Х1, Х2.
D – промежуточная переменная для вычисления дискриминанта.
Алгоритм вычисления корней уравнения заданного вида приведен на рис. 9.
Задания для самостоятельного выполнения
Цель заданий. Приобрести умения в синтезе формальной и
алгоритмической моделей решения задач. Сформировать компетенции
анализа и синтеза алгоритмических моделей при решении простых задач.
Порядок выполнения.Составить формальные и алгоритмические
модели решения следующих задач:
1. В книжном магазине вы желаете купить три книги. У вас имеется
небольшая сумма наличных денег и пластиковая карта, на счету которой
большая сумма денег. Вам бы не хотелось сегодня пользоваться
пластиковой картой, так как Вы в дальнейшем запланировали крупную
покупку. Определите способ покупки.
2. Определите вариант пути от дома до места учебы, в зависимости от
времени выхода из дома и времени начала учебных занятий.
3. В избирательной компании в органы власти участвуют две партии:
зеленых и прозрачных. Какая информация будет опубликована в СМИ по
4. Для двух чисел Х, Y определить, являются ли они корнями уравнения
5. Определить, является ли точка с координатами X, Y точкой пересечения
диагоналей квадрата со стороной R, одна вершина которого расположена в
6. Определить значения функции в зависимости от значения аргумента
1. Что называют алгоритмом?
2. Определите понятие «исполнитель алгоритмов».
3. Каковы особенности алгоритмов?
4. Перечислите свойства алгоритмов.
5. Каким образом используются алгоритмы при решении задач?
6. Для чего применяют алгоритмы?
7. Укажите способы задания алгоритмов и их соотношения.
8. Каковы средства и основные блоки визуального представления алгоритмов?
9. Сформулируйте общие правила при проектировании визуальных
10. Как используется системный подход к построению алгоритмов?
11. В чем заключается метод структурной алгоритмизации?
12. Какие существуют базовые алгоритмические структуры? Приведите
13. Чем отличаются алгоритмические структуры композиция и альтернатива?
14. Чем отличаются алгоритмические структуры альтернатива и итерация?
15. Как классифицируются алгоритмы по структурному признаку?
16. Приведите примеры линейных и разветвленных алгоритмов.
Источник
