Алгоритмический язык (АЯ) – это специальный язык программирования, в котором алгоритм решения задачи (программа) записывается с помощью определенных правил построения конструкций для описания операций (синтаксиса языка). Предписание на выполнение определенной операции в АЯ называется оператором.
Специальная программа, предназначенная для преобразования текста программы на АЯ в двоичный код («машинный язык»), называется компилятором (интерпретатором). Каждый АЯ имеет свой компилятор или интерпретатор. Программа-компилятор (интерпретатор) содержит все правила, определяющие синтаксис данного АЯ, а также способы преобразования конструкций АЯ в язык машинных кодов.
Основное отличие компилятора от интерпретатора состоит в том, что в результате компиляции программы создается.exe-файл, который может выполняться самостоятельно, не требуя наличия среды, в которой разрабатывалась программа (Turbo Pascal, Delphi, C++), в то время как в результате работы интерпретатора.exe-файл не создается и программа будет работать только непосредственно в среде разработки (MatLab, Scilab).
Информатика 8 класс (Урок№7 — Исполнители и алгоритмы. Способы записи алгоритма.)
Одним из способов обеспечения высокого уровня технологичности разрабатываемого ПО является структурное программирование. (Можно сказать, что суть структурного программирования заключается в оформлении последовательности команд как замкнутых функций или процедур и в объединении данных, связанных по смыслу, в сложные структуры данных).
Различают три вида вычислительного процесса, реализуемого программами: линейный, разветвленный и циклический.
Линейная структура процесса вычислений предполагает, что для получения результата необходимо выполнить некоторые операции в определенной последовательности.
Разветвленная структура процесса вычислений предполагает, что конкретная последовательность операций зависит от значений одной или нескольких переменных.
Циклическая структура процесса вычислений предполагает, что для получения результата некоторые действия необходимо выполнить несколько раз.
Для реализации указанных вычислительных процессов в программах используют управляющие операторы. После того, как в 60-х годах ХХ в. было доказано, что любой сколь угодно сложный алгоритм можно представить с использованием трех основных управляющих конструкций, в языках программирования высокого уровня появились управляющие операторы для реализации соответствующих конструкций. Эти три конструкции принято считать базовыми (основными) (основными алгоритмическими структурами называют стандартные наборы блоков и способы их соединения для выполнения типичных последовательностей операций):
·?следование – обозначает последовательное выполнение действий;
·?ветвление – соответствует выбору одного из двух вариантов действий (if-then-else);
·?цикл-пока – определяет повторение действий, пока не будет нарушено некоторое условие, выполнение которого проверяется в начале цикла (while).
Способы записи алгоритмов
Кроме базовых процедурные языки программирования высокого уровня обычно используют еще три конструкции, которые можно составить из базовых:
· выбор – обозначает выбор одного варианта из нескольких в зависимости от значения некоторой величины (case);
· цикл-до – обозначает повторение некоторых действий до выполнения заданного условия, проверка которого осуществляется после выполнения действий в цикле (repeat-until);
· цикл с заданным числом повторений (счетный цикл) – обозначает повторение некоторых действий указанное количество раз (do).
Перечисленные шесть конструкций были положены в основу структурного программирования.
Примечание. Слово «структурное» в данном названии подчеркивает тот факт, что при программировании используются только перечисленные конструкции (структуры). Отсюда и понятие «программирование без goto».
Программы, написанные с использованием только структурных операторов передачи управления, называют структурными.
Представление алгоритма программы в виде блок-схемы с точки зрения структурного программирования имеет два недостатка:
· предполагает слишком низкий уровень детализации, что часто скрывает суть сложных алгоритмов;
· позволяет использовать неструктурные способы передачи управления, причем часто на блок-схеме они выглядят проще, чем структурные.
Кроме блок-схем для описания алгоритмов можно использовать псевдокоды, Flow-формы и диаграммы Насси-Шнейдермана. Все перечисленные нотации (системы обозначений) базируются на тех же основных структурах, что и структурное программирование, но допускают разные уровни детализации.
Псевдокод – формализованное текстовое описание алгоритма (текстовая нотация). Описать с помощью псевдокодов неструктурный алгоритм невозможно. Использование псевдокодов изначально ориентирует проектировщика только на структурные способы передачи управления, а потому требует более тщательного анализа разрабатываемого алгоритма. В отличие от блок-схем, псевдокоды не ограничивают степень детализации проектируемых операций. Они позволяют соизмерять степень детализации действия с уровнем абстракции, на котором это действие рассматривают, и хорошо согласуются с основным методом структурного программирования – методом пошаговой детализации.
Пример использования псевдокода для некоторых основных конструкций:
Flow-формы представляют собой графическую нотацию описания структурных алгоритмов, которая иллюстрирует вложенность структур. Каждый символ Flow-формы соответствует управляющей структуре и изображается в виде прямоугольника. Для демонстрации вложенности структур символ Flow-формы может быть вписан в соответствующую область прямоугольника любого другого символа. В прямоугольниках символов содержится текст на естественном языке или в математической нотации.
Диаграммы Насси-Шнейдермана. Диаграммы Насси-Шнейдермана являются развитием Flow-форм. Основное их отличие от Flow -форм заключается в том, что область обозначения условий и вариантов ветвления изображают в виде треугольников. Такое обозначение обеспечивает большую наглядность представления алгоритма.
Так же, как и при использовании псевдокодов, описать неструктурный алгоритм, применяя Flow -формы или диаграммы Насси-Шнейдермана, невозможно (для неструктурных передач управления в этих нотациях просто отсутствую условные обозначения.) В то же время, являясь графическими, эти нотации лучше отображают вложенность конструкций, чем псевдокоды.
Общим недостатком Flow- форм и диаграмм Насси-Шнейдермана является сложность построения изображений символов, что усложняет практическое применение этих нотаций для применения описания больших алгоритмов.
Источник: megalektsii.ru
Требования, предъявляемые к алгоритму
Первое правило – при построении алгоритма прежде всего необходимо задать множество объектов, с которыми будет работать алгоритм. Формализованное (закодированное) представление этих объектов носит название данных.
Алгоритм приступает к работе с некоторым набором данных, которые называются входными, и в результате своей работы выдает данные, которые называются выходными. Таким образом, алгоритм преобразует входные данные в выходные. Это правило позволяет сразу отделить алгоритмы от “методов” и “способов”. Пока мы не имеем формализованных входных данных, мы не можем построить алгоритм.
Второе правило – для работы алгоритма требуется память. В памяти размещаются входные данные, с которыми алгоритм начинает работать, промежуточные данные и выходные данные, которые являются результатом работы алгоритма. Память является дискретной, т.е. состоящей из отдельных ячеек. Поименованная ячейка памяти носит название переменной.
В теории алгоритмов размеры памяти не ограничиваются, т. е. считается, что мы можем предоставить алгоритму любой необходимый для работы объем памяти. В школьной “теории алгоритмов” эти два правила не рассматриваются. В то же время практическая работа с алгоритмами (программирование) начинается именно с реализации этих правил.
В языках программирования распределение памяти осуществляется декларативными операторами (операторами описания переменных). В языке Бейсик не все переменные описываются, обычно описываются только массивы. Но все равно при запуске программы транслятор языка анализирует все идентификаторы в тексте программы и отводит память под соответствующие переменные.
Третье правило – дискретность. Алгоритм строится из отдельных шагов (действий, операций, команд). Множество шагов, из которых составлен алгоритм, конечно.
Четвертое правило – детерменированность. После каждого шага необходимо указывать, какой шаг выполняется следующим, либо давать команду остановки. Пятое правило – сходимость (результативность). Алгоритм должен завершать работу после конечного числа шагов. При этом необходимо указать, что считать результатом работы алгоритма.
На практике наиболее распространены следующие формы представления алгоритмов:
словесная (запись на естественном языке);
графическая (изображения из графических символов);
псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
программная (тексты на языках программирования).
Что такое словесный способ записи алгоритмов? Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке. Например. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Эвклида). Алгоритм может быть следующим:
- задать два числа;
- если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма;
- определить большее из чисел;
- заменить большее из чисел разностью большего и меньшего из чисел;
- повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи. Убедитесь в этом самостоятельно, определив с помощью этого алгоритма наибольший общий делитель чисел 125 и 75.
Словесный способ не имеет широкого распространения, так как такие описания: строго не формализуемы; страдают многословностью записей; допускают неоднозначность толкования отдельных предписаний. Что такое графический способ записи алгоритмов?
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется блок-схемой. В блок-схеме каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура называемых блоками. Блоки соединяются линиями переходов (называемых ветвью алгоритма), определяющими очередность выполнения действий. В таблице приведены наиболее часто употребляемые блоки.
Название блока
Графическое изображение
Блок начало и конца алгоритма
Любой алгоритм начинается и заканчивается данным блокрм.
Источник: studfile.net
7.7. Что такое псевдокод? 7.8. Как записываются алгоритмы на школьном алгоритмическом языке?
Он занимает промежуточное место между естественным и формальным языками.
С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой строны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя. Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова , смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Примером псевдокода является школьный алгоритмический язык в русской нотации ( школьный АЯ ), описанный в учебнике А.Г. Кушниренко и др. «Основы информатики и вычислительной техники», 1991. Этот язык в дальнейшем мы будем называть просто «алгоритмический язык».
7.8. Как записываются алгоритмы на школьном алгоритмическом языке?
Основные служебные слова
| алг (алгоритм) | сим (символьный) | дано | для | да |
| арг (аргумент) | лит (литерный) | надо | от | нет |
| рез (результат) | лог (логический) | если | до | при |
| нач (начало) | таб(таблица) | то | знач | выбор |
| кон (конец) | нц (начало цикла) | иначе | и | ввод |
| цел (целый) | кц (конец цикла) | все | или | вывод |
| вещ (вещественный) | длин (длина) | пока | не | утв |
| Общий вид алгоритма: алг название алгоритма (аргументы и результаты) дано условия применимости алгоритма надо цель выполнения алгоритма нач описание промежуточных величин | последовательность команд (тело алгоритма) кон |
Часть алгоритма от слова алг до слова нач называется заголовком , а часть, заключенная между словами нач и кон — телом алгоритма.
В предложении алг после названия алгоритма в круглых скобках указываются характеристики (арг, рез) и тип значения (цел, вещ, сим, лит или лог) всех входных (аргументы) и выходных (результаты) переменных. При описании массивов (таблиц) используется служебное слово таб, дополненное граничными парами по каждому индексу элементов массива.
Примеры предложений алг :
Предложения дано и надо не обязательны. В них рекомендуется записывать утверждения, описывающие с остояние среды исполнителя алгоритма , например:
-
1. алг Замена (арг лит Str1, Str2, арг рез лит Text)
дано | длины подстрок Str1 и Str2 совпадают
надо | всюду в строке Text подстрока Str1 заменена на Str2
2. алг Число максимумов (арг цел N, арг вещ таб A[1:N], рез цел K)
дано | N>0
надо | К — число максимальных элементов в таблице А
Источник: www.examen.ru