Способы задания алгоритма — Алгоритмы — Краткий теоретический справочник
Алгоритм — заранее заданное возможному исполнителю точное предписание совершить определённую последовательность действий для получения решения задачи за конечное число шагов.
4.1. Способы задания алгоритма
На практике наиболее распространены следующие способы задания алгоритмов:
— словесный (запись на естественном языке);
— графический (изображения из графических символов);
— псевдокод (полуформализованное описание алгоритмов на условном алгоритмическом языке, включающее в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
— программный (тексты на языках программирования).
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задаётся в произвольном изложении на естественном языке.
Пример. Запишите алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Евклида).
Алгоритм может быть следующим:
1) Задать два числа.
2) Если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма.
3) Определить большее из чисел.
4) Заменить большее из чисел разностью большего и меньшего из чисел.
5) Повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи.
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется схемой алгоритма, или блок-схемой. В блок-схеме каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. В таблице приведены наиболее часто употребляемые символы.
Начало, конец алгоритма, входи выход в подпрограмму
Вычислительное действие или последовательность действий
Вычисления по подпрограмме
Ввод-вывод в общем виде
Блок «процесс» применяется для обозначения действия или последовательности действий, изменяющих значение, форму представления или размещения данных. Для улучшения наглядности схемы несколько отдельных блоков обработки можно объединять в один блок. Представление отдельных операций достаточно свободно.
Блок «решение» используется для обозначения переходов управления по условию. В каждом блоке «решение» должны быть указаны вопрос, условие или сравнение, которые он определяет.
Блок «модификация» используется для организации циклических конструкций. Внутри блока записывается параметр цикла, для которого указываются его начальное значение, граничное условие и шаг изменения значения параметра для каждого повторения.
Блок «предопределённый процесс» используется для указания обращений к вспомогательным алгоритмам, существующим автономно в виде некоторых самостоятельных модулей, и для обращений к библиотечным подпрограммам.
Псевдокод представляет собой систему обозначений и правил, предназначенную для единообразной записи алгоритмов.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам. В псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых однозначно определён. Например, алгоритмы на алгоритмическом языке записываются с помощью служебных слов, представленных в таблице 1.8.
Таблица 1.8. Служебные слова алгоритмического языка.
Источник
Способы задания алгоритмов
Любой алгоритм становится алгоритмом лишь тогда, когда он обретает какую-либо форму. Существует несколько способов представления алгоритмов, отличающихся наглядностью, компактностью, степенью формализации и другими показателями. Наибольшее распространение получили три способа: словесно-формульный, графический и в виде последовательности команд для ЭВМ. Рассмотрим эти способы.
Словесно-формульный способ записи алгоритмов.
Его особенностью является то, что здесь допустима некоторая произвольность в обозначениях и используемых словах.
Пусть даны числа А, В, С. Найти число Н, равное большему из них.
Решение задачи можно получить, действуя следующим образом:
1. Вначале найдем большее из двух чисел, например А и В.
2. Если А ≥В, то примем Н=А, иначе (т.е. если А
Этот же алгоритм можно представить более четко, если разбить все действия на отдельные пункты. Тогда алгоритм примет вид:
1. Если А≥В, то принять Н=А и перейти к пункту 3. Иначе перейти к пункту 2.
2. Принять Н=В и перейти к следующему пункту.
3. Если Н≥С, то перейти к пункту 5, иначе перейти к следующему пункту.
4. Принять Н=С и перейти к пункту 5.
Словесно-формульный способ записи алгоритмов ориентирован прежде всего на исполнителя-человека и допускает различную запись предписаний. Но при этом запись должна быть предельно точна, чтобы человек-исполнитель мог понять суть предписаний и формально их выполнить.
Графический способ записи алгоритмов.
Данный способ предполагает использование определенных графических символов — блоков. Для придания наглядности и единообразия схем алгоритмов все графические элементы стандартизированы (ГОСТ 19.003—80. Условные графические обозначения структурных схем алгоритмов и программ). Состав, наименование, обозначение основных обязательных графических символов и отображаемые ими функции в алгоритме должны соответствовать указанным в таблице. Размер а (ширина символа) должен выбираться из ряда 10, 15, 20 мм, b=1.5*а (высота символа). Линии потока рекомендуется выполнять в два раза тоньше линий обводки блоков.
Стандартные графические элементы.
| Наименование | Обозначение блока | Содержание |
 Процесс | Выполнение операции или группы операций, в результате которых изменяются значение, форма представления или расположения данных | |
 Решение | Выбор направления выполнения алгоритма или программы в зависимости от некоторых переменных условий |
 Модификация | Выполнение операций, меняющих команды или группы команд, изменяющих программу |
 Предопределенный процесс | Использование ранее созданных и отдельно описанных алгоритмов или программ |
 Ввод-вывод | Преобразование данных в форму, пригодную для обработки (ввод) или отображения результатов обработки (вывод) |
 Документ | Ввод-вывод данных, носителем которых служит бумага |
 Линии потока | Указание на последовательность связей между символами |
 Соединитель | Указание на связь между прерванными линиями потока, соединяющими символы |
 Пуск-остановка | Начало, конец, прерывание процесса обработки данных или выполнения программы |
  Комментарии | Связь между элементом схемы и пояснением |
Каждый блок предписывает выполнение определенных действий. Совокупность блоков образует так называемую схему алгоритма, или блок-схему. Графический способ записи алгоритмов отличается большой наглядностью и оказывается весьма полезным на начальных стадиях разработки алгоритмов.
В теории программирования доказано, что для записи сколько угодно сложного алгоритма достаточно следующих структур, называемых базовыми алгоритмическими структурами (БАС). К БАС относятся:
БАС следование предполагает последовательное выполнение действий 1 и 2.
Следует отметить, что эта структура может содержать любое конечное число выполняемых действий.
БАС логическое условие читается следующим образом: «если условие принимает значение истина, то выполняется действие 1, иначе действие 2».
В данной структуре действие 2 может отсутствовать, т.е. имеется неполное логическое условие. В этом случае, если условие принимает значение «ложь», то никакое действие не выполняется и управление передается следующему оператору.
Под циклом будем понимать многократное повторение одного или нескольких действий в соответствии с некоторым условием.
Совокупность действий, выполняемых циклом, называется телом цикла. Однократное выполнение тела цикла называется шагом или итерацией. Заметим, что условие цикла должно определяться таким образом, чтобы цикл завершал свою работу за конечное число итераций.
Циклы бывают трех видов:
· фиксированным числом шагов.
Блок-схема цикла с предусловием выглядит следующим образом:
До тех пор, пока условие принимается значение «истина» выполняются операторы тела цикла. Если условие изначально принимает значение «ложь», то действия, входящие в тело цикла, не выполняются ни разу и управление передается следующему действию.
Для цикла с постусловием условие следует за телом. При этом цикл выполняется, пока условие принимает значении «ложь». Как только оно выполняется, цикл заканчивает работу. В отличие от цикла с предусловием, цикл с постусловием всегда выполняется как минимум один раз.
Цикл с фиксированным числом шагов является частным случаем циклов с пред- и постусловием.
Он всегда содержит специальную целочисленную переменную – счетчик, которая отсчитывает количество выполненных итераций. Значение счетчика меняется в интервале [n1, n2]. После каждой итерации значение счетчика увеличивается или уменьшается на величину шага h. Цикл заканчивает свою работу, как только счетчик достигнет определенного значения.
Представление алгоритмов в виде последовательности команд для ЭВМ.
При этом способе используются языки программирования — системы кодирования предписаний и правила их использования. По степени детализации предписаний алгоритма различают языки программирования низкого и высокого уровня.
Языки низкого уровня называются машинными кодами, поскольку программы составляются в кодах конкретной машины. При этом системы команд различных ЭВМ отличаются количеством адресов в команде, количеством разрядов, отводимых под каждый адрес, набором операций, которые может выполнять машина, и обозначений этих операций.
Языки программирования высокого уровня ориентированы не на систему команд той или иной ЭВМ, а на систему операторов, характерных для записи определенного класса алгоритмов. Например: язык Фортран (формульный транслятор) ориентирован на удобное представление формул и широко используется для инженерных и научных расчетов. Язык Паскаль разработан специально для обучения программированию и призван помогать формировать мышление программиста, естественным образом отображать структуру алгоритма в программе. Си — типичная реализация практических потребностей системного программиста, направленная на разработку новых языков — изначально создавался как инструментальное средство для реализации операционной системы UNIX. Однако его популярность переросла рамки этой системы, и в настоящее время язык Си является одним из универсальных языков программирования. Бейсик широко используется для обучения программированию и употребляется для написания простых программ.
Источник
Выберите способ задания алгоритмов
Различают следующие виды алгоритмов :
линейный – список команд (указаний), выполняемых последовательно друг за другом;
разветвляющийся – алгоритм, содержащий хотя бы одну проверку условия, в результате которой обеспечивается переход на один из возможных вариантов решения;
циклический – алгоритм, предусматривающий многократное повторение одной и той же последовательности действий. Количество повторений обусловливается исходными данными или условием задачи.
Любая алгоритмическая конструкция может содержать в себе другую конструкцию того же или иного вида, т. е. алгоритмические конструкции могут быть вложенными. Рассмотрим следующие способы описания алгоритма: словесное описание, псевдокод, блок-схема, программа.
Словесное описание представляет структуру алгоритма на естественном языке. Например, любой прибор бытовой техники (утюг,электропила, дрель и т.п.) имеет инструкцию по эксплуатации, т.е.словесное описания алгоритма, в соответствии которому данный прибор должен использоваться. Никаких правил составления словесного описания не существует. Запись алгоритма осуществляется в произвольной форме на естественном, например, русском языке. Этот способ описания не имеет широкого распространения, так как строго не формализуем (под «формальным» понимается то, что описание абсолютно полное и учитывает все возможные ситуации, которые могут возникнуть в ходе решения); допускает неоднозначность толкования при описании некоторых действий; страдает многословностью.
1. определить температуру воздуха
2. если температура ниже 0, то надеть шубу, иначе надеть куртку
Псевдокод — описание структуры алгоритма на естественном, частично формализованном языке, позволяющее выявить основныеэтапы решения задачи, перед точной его записью на языке программирования. В псевдокоде используются некоторые формальные конструкции и общепринятая математическая символика. Строгих синтаксических правил для записи псевдокода не существует. Это облегчает запись алгоритма при проектировании и позволяет описать алгоритм, используя любой набор команд. Однако в псевдокоде обычно используются некоторые конструкции, присущие формальным языкам, что облегчает переход от псевдокода к записи алгоритма на языке программирования. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором используемых слов и конструкций.
Блок-схема — описание структуры алгоритма с помощью геометрических фигур с линиями-связями, показывающими порядок выполнения отдельных инструкций. Этот способ имеет ряд преимуществ. Благодаря наглядности, он обеспечивает «читаемость»алгоритма и явно отображает порядок выполнения отдельных команд. В блок-схеме каждой формальной конструкции соответствует определенная геометрическая фигура или связанная линиями совокупность фигур.
Описания алгоритма в словесной форме, на псевдокоде или в виде блок-схемы допускают некоторый произвол при изображении команд. Вместе с тем они настолько достаточны, что позволяет человеку понять суть дела и исполнить алгоритм. На практике исполнителями алгоритмов выступают компьютеры. Поэтому алгоритм, предназначенный для исполнения на компьютере, должен быть записан на «понятном» ему языке, такой формализованный язык называют языком программирования .
Источник
