Вербальное представление алгоритма
«Чтобы найти НОД двух целых положительных чисел составим таблицу из двух столбцов и назовем их m и n. Запишем первое из заданных чисел в столбец m, а второе — в столбец n. Если данные числа не равны, заменим большее из них результатом вычитания из большего меньшего числа. Повторяем такие замены до тех пор, пока числа не окажутся равными, после чего число из столбца m считаем искомым результатом».
Очевидно, такая форма представления алгоритма может тяжело восприниматься читателем и применяется в основном при решении простых задач.
Построчная запись алгоритма.
3. Если m¹n, перейти к пункту 4, иначе — к пункту 7.
4. Если m>n, перейти к пункту 5, иначе — к пункту 6.
5. m=m-n; перейти к пункту 3.
6. n=n-m; перейти к пункту 3.
8. Вывод результата.
Представление алгоритма в виде блок-схемы отличается высокой степенью наглядности. Блок-схема состоит из соединенных между собой стрелками (линиями потока информации) блоков различного вида, начертание которых регламентируется ГОСТом. Применительно к рассматриваемой задаче блок-схема алгоритма выглядит:
Представление алгоритма с помощью структурограммы позволяет изображать схему передач управления не с помощью явного указания линий потоков информации, а посредством представления вложенности структур:
 |
Запись алгоритма на конкретном языке программирования:
Источник
Вербальное представление алгоритма
Тема 10. Основы алгоритмизации.
Алгоритм — это детально описанная последовательность действий (операций), однозначно приводящая к решению поставленной задачи.
Понятие алгоритма в информатике и вычислительной технике является фундаментальным, поэтому для него не существует абсолютно строгого определения. Всякий алгоритм обработки информации обладает следующими свойствами:
1. Дискретность. Это означает, что выполнение алгоритма осуществляется поэтапно, по шагам. Каждое действие должно быть завершено исполнителем (человеком, компьютером, роботом), прежде, чем он перейдет к выполнению следующего.
2. Определенность. Это означает, что каждое правило алгоритма строго однозначно и исполнитель должен быть в состоянии выполнить каждую команду алгоритма в строгом соответствии с ее назначением.
3. Результативность алгоритма предполагает, что его исполнение сводится к выполнению конечного числа действий и всегда приводит к некоторому результату.
4. Массовость (практическая ценность). Под этим понимается, что алгоритм решения задачи разрабатывается в общем виде так, чтобы его можно было применить для целого класса задач, различающихся лишь набором исходных данных.
Существуют различные формы (способы) представления алгоритмов. Основными среди них являются:
1. Словесное описание алгоритма на естественном языке (вербальная форма).
2. Построчная запись алгоритма (более строгое описание на естественном языке).
3. Представление алгоритма в виде блок-схемы.
4. Способ изображения алгоритма с помощью структурограммы (схема Насси-Шнейдермана).
5. Запись алгоритма на каком-либо языке программирования.
Рассмотрим особенности каждой из этих форм на примере алгоритмизации задачи нахождения наибольшего общего делителя (НОД) двух целых положительных чисел методом последовательного вычитания (алгоритм Евклида).
«Чтобы найти НОД двух целых положительных чисел составим таблицу из двух столбцов и назовем их m и n. Запишем первое из заданных чисел в столбец m, а второе — в столбец n. Если данные числа не равны, заменим большее из них результатом вычитания из большего меньшего числа. Повторяем такие замены до тех пор, пока числа не окажутся равными, после чего число из столбца m считаем искомым результатом».
Очевидно, такая форма представления алгоритма может тяжело восприниматься читателем и применяется в основном при решении простых задач.
Построчная запись алгоритма.
3. Если m¹n, перейти к пункту 4, иначе — к пункту 7.
4. Если m>n, перейти к пункту 5, иначе — к пункту 6.
5. m=m-n; перейти к пункту 3.
6. n=n-m; перейти к пункту 3.
8. Вывод результата.
Представление алгоритма в виде блок-схемы отличается высокой степенью наглядности. Блок-схема состоит из соединенных между собой стрелками (линиями потока информации) блоков различного вида, начертание которых регламентируется ГОСТом. Применительно к рассматриваемой задаче блок-схема алгоритма выглядит:
 |
Представление алгоритма с помощью структурограммы позволяет изображать схему передач управления не с помощью явного указания линий потоков информации, а посредством представления вложенности структур:
 |
 |
Нам важно ваше мнение! Был ли полезен опубликованный материал? Да | Нет
Источник
Способы записи алгоритмов
Алгоритм и его свойства
Алгоритмом называется точная инструкция исполнителю в понятной для него форме, определяющая процесс достижения поставленной цели на основе имеющихся исходных данных за конечное число шагов.
Основными свойствами алгоритмов являются:
1. Универсальность (массовость) — применимость алгоритма к различным наборам исходных данных.
2. Дискретность — процесс решения задачи по алгоритму разбит на отдельные действия.
3. Однозначность — правила и порядок выполнения действий алгоритма имеют единственное толкование.
4. Конечность — каждое из действий и весь алгоритм в целом обязательно завершаются.
5. Результативность— по завершении выполнения алгоритма обязательно получается конечный результат.
6. Выполнимость — результата алгоритма достигается за конечное число шагов.
Алгоритм считается правильным, если его выполнение дает правильный результат. Соответственно алгоритм содержит ошибки, если можно указать такие допустимые исходные данные или условия, при которых выполнение алгоритма либо не завершится вообще, либо не будет получено никаких результатов, либо полученные результаты окажутся неправильными.
Выделяют три крупных класса алгоритмов:
— вычислительныеалгоритмы, работающие со сравнительно простыми видами данных, такими как числа и матрицы, хотя сам процесс вычисления может быть долгим и сложным;
— информационные алгоритмы, представляющие собой набор сравнительно простых процедур, работающих с большими объемами информации (алгоритмы баз данных);
— управляющие алгоритмы, генерирующие различные управляющие воздействия на основе данных, полученных от внешних процессов, которыми алгоритмы управляют.
Для записи алгоритмов используют самые разнообразные средства. Выбор средства определяется типом исполняемого алгоритма. Выделяют следующие основные способы записи алгоритмов:
— вербальный, когда алгоритм описывается на человеческом языке;
— символьный, когда алгоритм описывается с помощью набора символов;
— графический, когда алгоритм описывается с помощью набора графических изображений.
Общепринятыми способами записи являются графическая запись с помощью блок-схем и символьная запись с помощью какого-либо алгоритмического языка.
Описание алгоритма с помощью блок схем осуществляется рисованием последовательности геометрических фигур, каждая из которых подразумевает выполнение определенного действия алгоритма. Порядок выполнения действий указывается стрелками. Написание алгоритмов с помощью блок-схем регламентируется ГОСТом. Внешний вид основных блоков, применяемых при написании блок схем, приведен на рисунке:
В зависимости от последовательности выполнения действий в алгоритме выделяют алгоритмы линейной, разветвленной и циклической структуры.
В алгоритмах линейной структуры действия выполняются последовательно одно за другим:
В алгоритмах разветвленной структуры в зависимости от выполнения или невыполнения какого-либо условия производятся различные последовательности действий. Каждая такая последовательность действий называется ветвью алгоритма.
В алгоритмах циклической структуры в зависимости от выполнения или невыполнения какого-либо условия выполняется повторяющаяся последовательность действий, называющаяся телом цикла. Вложенным называется цикл, находящийся внутри тела другого цикла. Различают циклы с предусловием и постусловием:
Итерационным называется цикл, число повторений которого не задается, а определяется в ходе выполнения цикла. В этом случае одно повторение цикла называется итерацией.
Источник
Формы представления алгоритмов
Для записи алгоритма могут использоваться различные формы его представления.
Вербальная форма представления алгоритма предполагает запись алгоритма на русском языке (или любом другом естественном языке) в виде последовательности пронумерованных инструкций. Как правило, эта форма записи алгоритма громоздка, неудобна и недостаточно наглядна.
Например, в ней описание алгоритма нахождения НОД (наибольшего общего делителя) двух целых положительных чисел m и n может быть представлено в виде последовательности следующих четырех шагов:
Шаг 1: Сравнить m и n.
Шаг 2: Если m равно n, то m и есть исходный НОД, расчет окончен. Иначе перейти к шагу 3.
Шаг 3: Если m больше n, то уменьшить значение m на величину n и вернуться к шагу 1. Иначе перейти к шагу 4.
Шаг 4: Уменьшить значение n на величину m и вернуться к шагу 1.
Эта современная запись алгоритма нахождения НОД — весьма упрощенная. Запись, данная первоначально Евклидом, заполняет целую страницу текста, причем последовательность элементарных действий там значительно сложней.
Представление алгоритма в форме блок-схемы реализуется в виде набора геометрических элементов (блоков), соединенных стрелками. Каждый блок – это «шаг» алгоритма, его отдельное действие. Направление стрелок между блоками задает последовательность действий. В табл.1 представлены основные стандартные элементы блок-схем.
Начало или конец вычислений. Внутри фигуры пишут: «начало» или «конец» соответственно
Операция ввода-вывода данных
Вычислительное действие или последовательность действий
Проверка условия, указанного внутри фигуры
Заголовок цикла с параметром
Вычисления по подпрограмме
Вывод данных на печать
Соединяет между собой блоки, указывая очередность их выполнения
Элементы блок-схемы различаются по своему внешнему виду и назначению. Так, элементы, содержащие инструкции по каким-либо преобразованиям величин, обозначаются прямоугольниками, а элементы, содержащие проверку условий – ромбами. Операции ввода-вывода данных обозначаются параллелограммами. Начало и конец алгоритма обозначаются прямоугольниками с двумя скругленными противоположными сторонами, внутри которых пишут: «начало» или «конец» соответственно.
Из прямоугольника выходит единственная стрелка, входить в него может несколько стрелок. Из обеих острых вершин ромба выходят стрелки: одна из них помечается словом «да», другая – словом «нет», они задают дальнейшее направление вычислений в случае, соответственно, выполнения или невыполнения записанного внутри ромба условия.
Назначение и правила использования всех типов блоков приведены в табл.1 в графах Название элемента и Пояснение.
С использованием приведенных в табл.1 стандартных элементов вышеуказанный алгоритм нахождения НОД двух положительных целых чисел m и n примет вид блок-схемы на рис.1. Внутри блоков в ней знаком := обозначена операция присваивания переменной величине, указанной слева от знака, ее значения, вычисляемого по формуле, стоящей справа от знака.
Блок-схемы наиболее удобно использовать для отображения уже разработанных, готовых алгоритмов, а также на начальных стадиях изучения программирования, так как они позволяют подключить к восприятию алгоритма наглядные зрительные образы производимых операций. Кроме того, на стадии проектирования сложных программ эта форма представления алгоритмов используется при формировании верхних уровней в иерархической структуре программ, а также — на нижних уровнях, если не полностью определены средства описания программ.
На стадиях детальной разработки сложных алгоритмов использование блок-схем оказывается неэффективным, так как запутанное переплетение многочисленных соединительных стрелок затрудняет понимание разрабатываемого алгоритма.
Представление алгоритма в форме псевдокода основано на описании этапов решения задачи с помощью ограниченного набора стандартных синтаксических конструкций. В псевдокоде, в частности, могут использоваться отдельные инструкции формальных алгоритмических языков программирования. Например, возведение X в степень A обозначается как X**A, извлечение квадратного корня из X обозначается как Sqrt (X).
Так же, как в формальных языках программирования, в псевдокоде присутствуют ключевые слова, смысл которых заранее оговорен и фиксирован. В табл.2 приведен базовый перечень ключевых слов.
В качестве ключевых могут использоваться также соответствующие английские слова-аналоги: else вместо иначе, then вместо то, и т.д.
В самом общем виде запись алгоритма в форме псевдокода выглядит следующим образом:
алг название алгоритма (аргументы — входные параметры и параметры — результаты работы алгоритма)
дано | условия применимости алгоритма
надо | цель выполнения алгоритма
нач описание промежуточных (внутренних) величин алгоритма
Здесь часть записи от слова алг до слова нач называется заголовком алгоритма, а часть, заключенная между словами нач и кон — его телом. Внутри тела также могут встречаться слова нач и кон, группа команд между ними образует свой отдельный блок команд. Команды отделяются друг от друга символом «;».
Сразу после названия алгоритма в круглых скобках указываются характеристики (арг или рез) и тип значения (цел, вещ, сим, лог или таб) всех входных (арг) и выходных (рез) величин. При описании массивов служебное слово таб дополняется граничными парами значений по каждому индексу элементов массива.
Начало описания алгоритма
Входные данные (аргументы) алгоритма
Вещественный тип данных
Конец команды ветвления вычислений
Логическая константа «TRUE»
Описание условий применимости алгортима
Конечное значение параметра цикла
Логическая связка «И»
Логическая связка «ИЛИ»
Часть конструкции если … то … иначе …
Конец всего алгоритма или блока команд
Символьный (литерный) тип данных
Логический (булевский) тип данных
Описание цели алгоритма
Начало тела алгоритма или блока команд
Логическая константа «FALSE»
Начальное значение параметра цикла
Выходные данные (результаты) алгоритма
Табличный тип данных (массив данных)
Часть конструкции если … то … иначе
Целый тип данных
Шаг изменения параметра цикла
В конце любой строки в текст псевдокода после знака «|» можно вставлять комментарий, облегчающий понимание алгоритма.
Разделы дано и надо в записи алгоритма не являются обязательными.
К числу основных действий, составляющих тело алгоритма, относятся команды ввода-вывода, присваивания, перехода, ветвления и циклов. Для обозначения этих команд используются соответствующие ключевые слова.
Команда ввода: ключевое слово ввод, за которым указываются имена переменных, для которых вводятся значения. Например, команда ввод a,b,c означает ввод значений соответственно для переменных a,b,c.
Команда вывода: ключевое слово вывод, за которым следуют имена выводимых переменных, выводимые выражения и тексты (тексты помещаются в кавычки). Например, команда вывод «S = «, S означает вывод имени переменной S, за которым после знака равенства = следует вывод текущего значения этой переменной.
Команды присваивания используются для вычисления выражений и присваивания их значений переменным. Общий вид команды: «переменная» := «выражение», где знак «:=» означает команду замены прежнего значения переменной, стоящей в левой части, на вычисленное значение выражения, стоящего в правой части. Например, команда x := y + z означает присваивание переменной x значения суммы величин y и z, а команда k := k+1 означает увеличение текущего значения переменной k на единицу.
Команда перехода: ключевые слова идти к, после которых указывается номер той строки, команда которой должна выполняться следующей. Таким образом, команда перехода изменяет естественную последовательность выполнения команд по возрастанию номеров строк. Например, записанная в 5-й строке команда идти к 10 означает, что далее должна выполняться команда, записанная в 10-й строке, а не команда, записанная в следующей 6-й строке.
Для организации ветвлений вычислительного процесса применяются команды, начинающиеся с ключевых слов если и выбор, циклические вычисления организуются с помощью команд, начинающихся с ключевых слов пока и для. Подробно эти команды рассмотрены далее при описании базовых структур алгоритмов.
С использованием псевдокода вышеуказанный алгоритм нахождения НОД двух положительных целых чисел m и n примет следующий вид:
алг Наибольший Общий Делитель (арг цел m, n, рез цел nod)
дано | положительные целые числа m, n
надо | nod – наибольший общий делитель чисел m, n
Источник
