Способы записи алгоритма
На практике наиболее распространенными являются следующие формы записи алгоритмов: 1) графическая запись (блок-схемы); 2) словесная запись (псевдокоды); 3) язык программирования. Словесная форма записи алгоритма представляет собой описание на естественном языке последовательных этапов обработки данных. Словесный способ не имеет широкого распространения, так как такие описания строго не формализуемы, допускают неоднозначность толкования отдельных предписаний. Алгоритм, записанный с помощью псевдокода, представляет собой полуформализованное описание на условном алгоритмическом языке, включающее как основные элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и другие. Графическая форма записи, называемая также схемой алгоритма, представляет собой изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Графическая запись является более компактной и наглядной по сравнению со словесной. В схеме алгоритма каждому типу действий соответствует геометрическая фигура. Фигуры соединяются линиями переходов, определяющими очередность выполнения действий. Графическая форма записи, называемая также структурной схемой или блок-схемой алгоритма, представляет собой изображение алгоритма в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. В дальнейшем мы будем использовать блок-схемы алгоритмов. Они позволяют представить алгоритмы в более наглядном виде, это дает возможность анализировать их работу, искать ошибки в их реализации и т.д. В блок-схемах всегда есть начало и конец, обозначаемые эллипсами, между ними — последовательность шагов алгоритма, соединенных стрелками. 
Шаги бывают безусловными (изображаются прямоугольниками, параллелограммами) и условными (изображаются ромбами). Из ромба всегда выходят две стрелки — одна означает дальнейший путь, в случае выполнения условия (обозначается обычно словом «да» или «+»), другая — невыполнение (словом «нет» или «-«). Ввод с клавиатуры или вывод на экран значения выражения изображается параллелограммом. Команда, выполняющая обработку действий (команда присваивания), изображается в прямоугольнике. 
Если решение задачи сложное и достаточно длинное, то алгоритм может получиться очень большим. Избежать этого можно, заменив некоторую законченную последовательность шагов алгоритма блоками, которые будут являться вспомогательными алгоритмами. Блок обычно не элементарен, его размеры выбираются в зависимости от необходимости, однако если он правильно составлен, то обладает всеми необходимыми признаками алгоритмического шага: имеет точку входа (четко выделенное начало) и может быть условным или безусловным. Разные блоки алгоритма связаны друг с другом только через точки входа и выхода, поэтому если блок верно решает свою задачу, то его внутренняя структура несущественна для остальной части алгоритма. Такое блочное представление особенно удобно на первых этапах решения сложных задач, когда детализация блоков производится позднее и, возможно, другими разработчиками. Язык программирования — язык, используемый для формальной записи алгоритмов. Большинство языков программирования относятся к алгоритмическим языкам. Запись алгоритма на алгоритмическом языке называют программой. Язык, используемый для формальной записи алгоритмов, называется алгоритмическим языком. При описании любого языка (в том числе естественного, например, русского, английского и т.д.) используются следующие понятия: алфавит, синтаксис и семантика. Алфавит языка — это множество простейших знаков, которые могут быть использованы в текстах этого языка. Последовательность символов алфавита называют словом. Правила, согласно которым образуются слова из алфавита, называются грамматикой. Сам же язык — это множество всех слов, записываемых в данном алфавите согласно данной грамматике. Синтаксис — это набор правил, определяющих возможные сочетания (конструкции) из букв алфавита. Для описания синтаксиса языка, как правило, используют другой язык (метаязык) или синтаксические диаграммы. Семантика — это набор правил, определяющих значение (смысл) отдельных конструкций языка.
8.2. Формы записи алгоритмов
Существуют множество различных форм записи алгоритмов. Это связано с тем, что каждый исполнитель алгоритмов «понимает» лишь такой алгоритм, который записан на его «языке» и по его правилам. Условно выделяют четыре формы записи алгоритмов:
1. Словесно-пошаговая (текстовая).
3. Графическая форма записи (блок-схема).
4. Запись на алгоритмическом языке.
Словесная форма записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задается в произвольном изложении на естественном языке.
При использовании словесно-пошаговой (текстовой) формы записи алгоритм часто записывается в виде пронумерованных этапов его выполнения.
Например: Алгоритм сложения двух чисел ( a и b ).
1. Спросить, чему равно число a .
2. Спросить, чему равно число b .
3. Сложить a и b, результат присвоить с.
4. Сообщить результат с.
Словесный способ не имеет широкого распространения, так как такие описания: строго не формализуемы, страдают многословностью записей, допускают неоднозначность толкования отдельных предписаний.
Табличная форма записи – это запись алгоритма в виде таблицы. Используемые таблицы могут быть различными. Для примера будем использовать упрощенную форму. Порядок составления табличных алгоритмов:
1. Переписать выражение так, как допустимо в информатике.
2. Определить порядок действий.
3. Ввести обозначения промежуточных результатов.
4. Занести полученные действия в таблицу.
Пример: Алгоритм вычисления R=2a +3b .
При использовании графической формы записи (блок-схемы) алгоритм записывается в виде схемы, состоящей из блоков (геометрических фигур) с размещенными в них действиями. Блоки соединяются стрелочками и показывают структуру всего алгоритма. Алгоритм в виде блок-схемы начинается блоком «начало» и заканчивается блоком «конец».
Таблица Основные блоки
При составлении блок-схемы алгоритма сначала выделяют исходные данные (все переменные величины после знака равенства и в условии) и результат (величины которые необходимо найти). Если в задании подразумеваются, но не указываются имена величин, то они обозначаются самостоятельно.
При отсутствии исходных данных блок ввода не пишется. В один блок можно поместить одно действие.
Например: Алгоритм вычисления значения выражения (ВЗВ) K=3b+6а.
Результат: K
K=3*b+6*a
Существуют еще формы записи, которые можно отнести к графическим. Одной из таких форм является построение структурограмм.
Действия в структурограмме располагаются друг под другом. Это позволяет наглядно отслеживать обработку данных в алгоритмах. Все структуры имеют прямоугольную форму. Заполнение их сходно с аналогичными блоками в блок-схемах, но имеются и отличия. Рассмотрите блок-схему и структурограмму алгоритма.
Форма записи на алгоритмическом языке это запись алгоритма на специальном языке (в том числе и на том или языке программирования). Она осуществляется, строго следуя правилам выбранного языка.
Для единообразной записи алгоритмов в форме близкой к языковой, но не учитывающей особенностей конкретного языка программирования была придумана особая система обозначений и правил, получившая название псевдокод.
Псевдокод занимает промежуточное место между естественным и формальным языками. С одной стороны, он близок к обычному естественному языку, поэтому алгоритмы могут на нем записываться и читаться как обычный текст. С другой стороны, в псевдокоде используются некоторые формальные конструкции и математическая символика, что приближает запись алгоритма к общепринятой математической записи.
В псевдокоде не приняты строгие синтаксические правила для записи команд, присущие формальным языкам, что облегчает запись алгоритма на стадии его проектирования и дает возможность использовать более широкий набор команд, рассчитанный на абстрактного исполнителя.
Однако в псевдокоде обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В частности, в псевдокоде, так же, как и в формальных языках, есть служебные слова, смысл которых определен раз и навсегда. Они выделяются в печатном тексте жирным шрифтом, а в рукописном тексте подчеркиваются.
Стандарта псевдокода нет, т.е. нет единого или формального его определения, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.
Примером псевдокода является школьный алгоритмический язык в русской нотации (школьный АЯ), описанный в учебнике А.Г. Кушниренко и др. «Основы информатики и вычислительной техники», 1991. Этот язык в дальнейшем мы будем называть просто «алгоритмический язык».
Т а б л и ц а Основные служебные слова
4. Виды алгоритмов. Свойства и способы задания алгоритмов.
Выделяют следующие виды алгоритмов : линейный, разветвляющийся, циклический, комбинированный.
Алгоритм, который содержит сразу несколько структур называется КОМБИНИРОВАННЫМ.
Различные определения алгоритма в явной или неявной форме содержат следующий ряд общих требований:
Дискретность — алгоритм должен представлять процесс решения задачи как последовательное выполнение некоторых простых шагов. При этом для выполнения каждого шага алгоритма требуется конечный отрезок времени, то есть преобразование исходных данных в результат осуществляется во времени дискретно.
Детерминированность (определённость). В каждый момент времени следующий шаг работы однозначно определяется состоянием системы. Таким образом, алгоритм выдаёт один и тот же результат (ответ) для одних и тех же исходных данных. В современной трактовке у разных реализаций одного и того же алгоритма должен быть изоморфный граф. С другой стороны, существуют вероятностные алгоритмы, в которых следующий шаг работы зависит от текущего состояния системы и генерируемого случайного числа. Однако при включении метода генерации случайных чисел в список «исходных данных», вероятностный алгоритм становится подвидом обычного.
Понятность — алгоритм должен включать только те команды, которые доступны исполнителю и входят в его систему команд.
Завершаемость (конечность) — при корректно заданных исходных данных алгоритм должен завершать работу и выдавать результат за конечное число шагов. [ источник не указан 518 дней ] С другой стороны, вероятностный алгоритм может и никогда не выдать результат, но вероятность этого равна 0.
Массовость (универсальность). Алгоритм должен быть применим к разным наборам исходных данных.
Результативность — завершение алгоритма определёнными результатами.
Алгоритм содержит ошибки, если приводит к получению неправильных результатов либо не даёт результатов вовсе.
Алгоритм не содержит ошибок, если он даёт правильные результаты для любых допустимых исходных данных.
Способы задания алгоритма.
На практике наиболее распространены следующие способы задания алгоритмов:
— словесная (запись на естественном языке);
— графическая (изображения из графических символов);
— псевдокоды (полуформализованные описания алгоритмов на условном алгоритмическом языке, включающие в себя как элементы языка программирования, так и фразы естественного языка, общепринятые математические обозначения и др.);
— программная (тексты на языках программирования). Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных.
Словесный способ
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных. Алгоритм задаётся в произвольном изложении на естественном языке.
Пример. Записать алгоритм нахождения наибольшего общего делителя (НОД) двух натуральных чисел (алгоритм Евклида).
Алгоритм может быть следующим:
1) Задать два числа.
2) Если числа равны, то взять любое из них в качестве ответа и остановиться, в противном случае продолжить выполнение алгоритма.
3) Определить большее из чисел.
4) Заменить большее из чисел разностью большего и меньшего из чисел.
5) Повторить алгоритм с шага 2.
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи.
Графический способ
При графическом представлении алгоритм изображается в виде последовательности связанных между собой функциональных блоков, каждый из которых соответствует выполнению одного или нескольких действий. Такое графическое представление называется схемой алгоритма, или блок-схемой. В блок-схеме каждому типу действий соответствует геометрическая фигура, представленная в виде блочного символа. В таблице приведены наиболее часто употребляемые символы.
Урок 15
§ 2.2. Способы записи алгоритмов
Существуют различные способы записи алгоритмов. Основными среди них являются:
• словесные;
• графические;
• на алгоритмических языках.
Теоретические исследования нашего соотечественника Андрея Андреевича Маркова (младшего) (1903-1979), выполненные в середине прошлого века, показали, что в общем случае алгоритмы должны содержать предписания двух видов:
1) предписания, направленные на непосредственное преобразование информации (функциональные операторы);
2) предписания, определяющие дальнейшее направление действий (логические операторы).
Именно эти операторы положены в основу большинства способов записи алгоритмов.
2.2.1. Словесные способы записи алгоритма
Словесное описание. Самой простой является запись алгоритма в виде набора высказываний на обычном разговорном языке. Словесное описание имеет минимум ограничений и является наименее формализованным. Однако все разговорные языки обладают неоднозначностью, поэтому могут возникнуть различные толкования текста алгоритма, заданного таким образом. Алгоритм в словесной форме может оказаться очень объёмным и трудным для восприятия.
Пример 1. Словесное описание алгоритма нахождения наибольшего общего делителя (НОД) пары натуральных чисел (алгоритм Евклида).
Чтобы найти НОД двух чисел, составьте таблицу из двух столбцов и назовите столбцы X и У. Запишите первое из заданных чисел в столбец X, а второе — в столбец У. Если данные числа не равны, замените большее из них на результат вычитания из большего числа меньшего. Повторяйте такие замены до тех пор, пока числа не окажутся равными, после чего число из столбца X считайте искомым результатом.
Построчная запись. Это запись на естественном языке, но с соблюдением некоторых дополнительных правил:
• каждое предписание записывается с новой строки;
• предписания (шаги) алгоритма нумеруются;
• исполнение алгоритма происходит в порядке возрастания номеров шагов, начиная с первого (если не встречается никаких специальных указаний).
Кроме слов естественного языка предписания могут содержать математические выражения и формулы.
Пример 2. Построчная запись алгоритма Евклида.
1. Обозначить первое из заданных чисел X, второе обозначить Y.
2. Если X = Y, то перейти к п. 8.
3. Если X > Y, то перейти к п. 4, иначе перейти к п. 6.
4. Заменить X на X — Y.
5. Перейти к п. 2.
6. Заменить Y на Y — X.
7. Перейти к п. 2.
8. Считать X искомым результатом.
Построчная запись алгоритма позволяет избежать ряда неопределённостей; её восприятие не требует дополнительных знаний.
Вместе с тем использование построчной записи требует от человека большого внимания.
2.2.2. Блок-схемы
Наилучшей наглядностью обладают графические способы записи алгоритмов; самый распространённый среди них — блок-схема.
Блок-схема представляет собой графический документ, дающий представление о порядке работы алгоритма. Здесь предписания изображаются с помощью различных геометрических фигур, а последовательность выполнения шагов указывается с помощью линий, соединяющих эти фигуры. Направления линий связи слева направо и сверху вниз считаются стандартными, соответствующие им линии связи можно изображать без стрелок. Линии связи справа налево и снизу вверх изображаются со стрелками.
Рассмотрим некоторые условные обозначения, применяемые в блок-схемах.
Выполнение алгоритма всегда начинается с блока начала и оканчивается при переходе на блок конца (рис. 2.2, а). Из начального блока выходит одна линия связи; в конечный блок входит одна линия связи.
Внутри блока данных (рис. 2.2, б) перечисляются величины, значения которых должны быть введены (исходные данные) или выведены (результаты) в данном месте схемы. В блок данных входит одна линия связи, и из блока исходит одна линия связи.
В блоке обработки данных (рис. 2.2, в) содержится описание тех действий, которые должны быть выполнены при переходе на этот блок (выполнение определённой операции или группы операций, приводящее к изменению значения, формы или размещения информации). В блок обработки данных входит одна линия связи, и из блока исходит одна линия связи.
Проверка условия изображается с помощью блока принятия решения, внутри которого записывается это условие (рис. 2.2, г). В блок принятия решения входит одна линия, а выходят две линии, около которых записываются результаты проверки условия.
Комментарии (рис. 2.2, д) используются для добавления пояснительных записей, делающих блок-схему более понятной.
Рис. 2.2. Обозначения на блок-схемах
Пример 3. Запись алгоритма Евклида с помощью блок-схемы (рис. 2.3).
Рис. 2.3. Запись алгоритма Евклида с помощью блок-схемы
Создание детальной блок-схемы сложного алгоритма — трудоёмкая задача. Кроме того, блок-схема, не умещающаяся на одном стандартном листе, теряет своё основное преимущество — наглядность. При разработке сложных алгоритмов блок-схемы удобно использовать в качестве средства для наглядного представления решения задачи в общем виде.
2.2.3. Алгоритмические языки
Алгоритмические языки — формальные языки, предназначенные для записи алгоритмов. Каждый из них характеризуется:
• алфавитом — набором используемых символов;
• синтаксисом — системой правил, по которым из символов алфавита образуются правильные конструкции языка;
• семантикой — системой правил, строго определяющей смысл и способ употребления конструкций языка.
Класс алгоритмических языков очень широк. При изучении курса информатики в школах используются различные версии школьного (учебного) алгоритмического языка.
Школьный алгоритмический язык. Для записи алгоритмов на школьном алгоритмическом языке используется некоторое ограниченное множество слов, смысл и способ употребления которых заданы раз и навсегда. Это так называемые служебные слова: алг (алгоритм), дано, надо, нач (начало), кон (конец), арг (аргумент), рез (результат) и др. При записи алгоритмов в книгах служебные слова выделяются жирным шрифтом, в тетради и на доске — подчёркиванием.
В общем виде программу на школьном алгоритмическом языке можно представить так:
алг
нач
кон
Пример 4. Алгоритм, позволяющий из полного сосуда ёмкостью 12 л отлить половину, пользуясь двумя пустыми сосудами ёмкостью 8 и 5 л.
алг переливания
нач
наполнить сосуд ёмкостью 8 л из сосуда ёмкостью 12 л
наполнить сосуд ёмкостью 5 л из сосуда ёмкостью 8 л
вылить всё из сосуда ёмкостью 5 л в сосуд ёмкостью 12 л
вылить всё из сосуда ёмкостью 8 л в сосуд ёмкостью 5 л
наполнить сосуд ёмкостью 8 л из сосуда ёмкостью 12 л
долить из сосуда ёмкостью 8 л в сосуд ёмкостью 5 л
вылить всё из сосуда ёмкостью 5 л в сосуд ёмкостью 12 л
кон
По ссылке http://www.niisi.ru/kumir/ вы можете скачать систему КуМир (Комплект учебных Миров) или скачать архив программы с сайта, в которой используется школьный алгоритмический язык, со встроенными исполнителями Робот, Чертёжник, Водолей и др. Кумир работает в операционных системах Windows и Linux.
Далее, говоря об алгоритмическом языке, мы будем иметь в виду именно школьный алгоритмический язык.
САМОЕ ГЛАВНОЕ
Существуют различные способы записи алгоритмов: словесное описание, построчная запись, блок-схемы, школьный алгоритмический язык и др. Каждый из этих способов обладает своими достоинствами и недостатками.
Вопросы и задания
1. Ознакомьтесь с материалами презентации к параграфу, содержащейся в электронном приложении к учебнику. Что вы можете сказать о формах представления информации в презентации и в учебнике? Какими слайдами вы могли бы дополнить презентацию?
2. Каковы основные способы записи алгоритмов?
3. Чем вызвано существование многих способов записи алгоритмов?
4. Дайте словесное описание алгоритма сложения двух обыкновенных дробей а/b и c/d.
5. Представьте в виде построчной записи алгоритм решения следующей задачи: «Имеются четыре арбуза различной массы. Как, пользуясь чашечными весами без гирь, путём не более пяти взвешиваний расположить их по возрастанию веса?».
6. Представьте с помощью блок-схемы алгоритм решения следующей задачи: «Из трёх монет одинакового достоинства одна фальшивая (более лёгкая). Как её найти с помощью одного взвешивания на чашечных весах без гирь?».
7. Запишите на алгоритмическом языке алгоритм построения окружности заданного радиуса r, проходящей через заданные точки А и В.
8. В среде КуМир запишите и выполните алгоритм переливаний (пример 4) для исполнителя Водолей.
9. Подготовьте краткую биографическую справку о Маркове А. А. (младшем).
Электронное приложение к уроку
| Файлы | Материалы урока | Ресурсы ЭОР |
Cкачать материалы урока