Файл: Основные структуры алгоритмов: сравнительный анализ и примеры их использования (Определение алгоритма).pdf

3.1 Словесное описание алгоритма

Запись действий на естественном языке. Такая форма записи часто приводит к избыточности представления и одновременно к неоднозначности выполнения алгоритма из-за плохой формализации средствами естественных языков. Для лучшей формализации действий используются ограниченный набор ключевых слов, фразы типовой структуры. Словесное описание алгоритма получил значительно меньшее распространение из-за его многословности и отсутствия наглядности.

Определим форматы переменных A, B, Ф, где A и B — значения для сравнения, Ф — переменная для хранения максимального значения;

получим два значения чисел A и B для сравнения;

сравним A и B.

если A меньше B, значит большее число B.

Поместим в переменную Ф значение B.

Если A не меньше (больше) B, значит большее число A.

Поместим в переменную Ф значение A.

Словесный способ не имеет широкого распространения по следующим причинам:

такие описания строго не формализуемы;

страдают многословностью записей;

допускают неоднозначность толкования отдельных предписаний.

3.2 Графический способ записи алгоритмов

Графический способ представления алгоритмов является более компактным и наглядным по сравнению со словесным.

При графическом способе алгоритм изображается в виде последовательности связанных между собой блоков, каждый из которых соответствует выполнению соответствующих действий. Внутри блока дается описание соответствующего действия.

Данное графическое изображение называется схемой алгоритма или блок-схемой.

Графическое изображение алгоритма часто используется до программирования задачи из-за его наглядности, ибо визуальное восприятие облегчает процесс создания программы, анализ дальнейшего развития проекта и варианты исправления ошибок в ходе тестирования .

Можно встретить даже такое утверждение: “Внешне алгоритм представляет собой схему – набор прямоугольников, других символов, внутри которых записывается, что вычисляется, что вводится в машину и что выдается на печать и другие средства отображения информации“. Здесь форма представления алгоритма смешивается с самим алгоритмом.

Принцип программирования “сверху вниз” требует, чтобы блок-схема поэтапно раскрывалась и каждый блок “расписывался” до элементарных операций. Данный подход можно применять при решении не самых сложных задач. При решении серьезной задачи блок-схема разрастается до такой степени, что ее невозможно будет просмотреть за один раз.

Блок-схемы удобно использовать для объяснения работы уже существующего алгоритма, при этом в качестве блоков берутся действительные блоки алгоритма, работа которых не нуждается в объяснении. Задача блок-схемы помочь упростить изображение алгоритма, а не усложнить.

Схема - это графическое представление алгоритма, дополненное разъясняющими комментариями. Каждый пункт алгоритма отображается на схеме геометрической фигурой - блоком, различным типам выполняемых действий соответствуют различные геометрические фигуры.

Графические элементы в схеме соединяются линиями, их можно назвать линиями «потока информации». Основное направление идет сверху вниз и слева на право. В других случаях применение стрелок обязательно. По отношению к блоку линии потока могут быть входящими или выходящими. Количество входящих линий для блока ограничений не имеет. Выходящая же линия, напротив, может быть только одна.

Исключение оставляют логические блоки, имеющие не менее двух

выходящих линий потока, каждая из которых соответствует одному из возможных исходов проверки логического условия, а также блоки модификации.

Например, для условия, на основе которого строится ветвление, изображается ромбом. Оператор, в котором происходит обработка информации, изображается прямоугольником.

У любой программы есть начало и конец. На блок-схемах начало и конец программ обозначаются прямоугольниками со скруглёнными углами. Внутри прямоугольников пишут: "Начало", "Конец".

 В одной схеме следует использовать блоки одинаковых размеров. Необходимо также нумеровать все блоки. Виды и назначение основных блоков приведены в Таблице 1.

 Линии, соединяющие блоки и указывающие последовательность  связей между ними, должны проводится параллельно линиям рамки. Стрелка в конце линии может не ставиться, если линия направлена слева направо или сверху вниз. В блок может входить несколько линий, то есть блок может являться преемником любого числа блоков. Из блока (кроме логического) может выходить только одна линия. Логический блок может иметь в качестве продолжения несколько вариантов и из него выходят две линии(п2 таблица1).

Если на схеме имеет слияние линий, то место их пересечения необходимо выделить точкой. Точку можно не ставить в случае, когда одна линия подходит к другой и слияние их очевидно .

Схему алгоритма нужно выполнять как единое целое, но в случае необходимости можно обрывать , соединяющие блоки линии.

Если при обрыве линии  схема находится на этом же листе, то на одном и другом конце линии изображается специальный символ соединитель — окружность диаметром 0,5 мм (п7 таблица1). Внутри парных окружностей указывается один и тот же номер идентификатор. В качестве идентификатора, используется порядковый номер блока, к которому направлен соединитель.

А если схема занимает более одного листа, то в случае разрыва линии используется межстраничный соединитель (п8 таблица1). Внутри каждого такого межстраничного соединителя указывается «адрес» — откуда и куда направлена линия. Адрес записывается в две строки: в первой указывается номер листа, во второй —порядковый номер блока.

 Блок-схема должна содержать все разветвления,

циклы и обращения к подпрограммам, содержащиеся в программе.

Таблица 1. Условные графические обозначения, применяемые при составлении схем алгоритмов.

Блок вычислений применяется для обозначения действия, изменяющих значение, размещения данных или форму представления. Для наглядности схемы нескольких блоков обработки можно объединять в один.

Логический блок используется для обозначения переходов управления по условию. В каждом блоке "решение" должны быть указаны вопрос, условие или сравнение, которые он определяет.

Блок предопределенный процесс используется для указания обращений к вспомогательным алгоритмам, существующим отдельно в виде самостоятельных модулей и для обращений к подпрограммам.

Блок модификация используется для организации циклических

элементов. Внутри блока записывается параметр цикла, для которого

указываются начальное значение, условия и шаг изменения значения параметра для каждого повторения.

3.3 Псевдокод

Псевдокод - это система обозначений, предназначенная для неформального представления в ходе разработки алгоритмов. Он занимает промежуточное место между естественным и формальным языками.

Один из способов создания псевдокода - ослабление правил того языка программирования, на котором будет создаваться программа. В подобной ситуации псевдокод может состоять из синтаксических и семантических структур, аналогичных структурам целевого языка программирования, но не столь формализованных.

Псевдокод схож с обычным языком, поэтому алгоритмы могут записываться и читаться как обычный текст. Также, в псевдокоде используются некоторые формальные элементы и математическая символика, что приближает запись алгоритма к общепринятой математической форме. В псевдокоде не приняты строгие синтаксические правила для записи команд, как формальных языках, что облегчает запись алгоритма на стадии его разработки и дает возможность использовать более широкий набор команд. В псевдокод обычно имеются некоторые конструкции, присущие формальным языкам, что облегчает переход от записи на псевдокоде к записи алгоритма на формальном языке. В псевдокоде есть служебные слова, смысл которых строго определен. В печатном тексте они выделяются жирным шрифтом и подчеркиваются в рукописном тексте. Единого или формального определения псевдокода не существует, поэтому возможны различные псевдокоды, отличающиеся набором служебных слов и основных (базовых) конструкций.

Например, алгоритмы на алгоритмическом языке записываются с помощью служебных слов, представленных в таб­лице 2

Таблица 2

Вид алгоритма записанный в псевдокоде:

алг название алгоритма (аргументы и результаты)

дано  применимость алгоритма

надо цель ,которую достигнуть выполняя алгоритм

нач описание промежуточных величин

тело алгоритма (последовательность программ)

кон.

Часть алгоритма от слова алг до слова нач называется заголовком, а часть заключённая между словами нач и кон — телом алгоритма. В предложении  алг после названия алгоритма в круглых скобках указываются  характеристики  (арг, рез) и тип значения (цел, вещ, сим, лит или лог)  всех  входных (аргументы) и выходных (результаты) переменных. При описании массивов (таблиц) используется служебное слово таб, дополненное граничными парами по каждому индексу элементов массива.

Для ветвления применяют команды если и выбор, для организации циклов - команды для и пока.

алг Сумма квадратов (арг цел n, рез цел S)

дано | n > 0

надо | S = 1*1 + 2*2 + 3*3 + ... + n*n

нач цел i  

ввод n; S:=0  

нц для i от 1 до n    

S:=S+i*i  

кц  

вывод "S = ", S

кон

алг Объем и площадь цилиндра (арг вещ R, H, рез вещ V, S)

алг Корни КвУр(арг вещ а, b, c, рез вещ x1, x2, рез лит t)

алг Исключить элемент(арг цел N, арг рез вещ таб А[1:N])

алг Диагональ(арг цел N, арг цел таб A[1:N,1:N], рез лит Otvet)

Предложения дано и надо не обязательны. В них рекомендуется записывать утверждения, описывающие состояние среды исполнителя алгоритма.

алг Замена (арг лит Str1, Str2, арг рез лит Text)

дано | длины подстрок Str1 и Str2 совпадают

надо | всюду в строке Text подстрока Str1 заменена на Str2

алг Сопротивление (арг вещ R1, R2, арг цел N, рез вещ R)

дано | N>5, R1>0, R2>0

надо | R – сопротивление схемы

В предложениях дано и надо после знака "|" записаны комментарии. Комментарии можно помещать в конце любой строки, они облегчают понимание алгоритма.

3.4 Программный способ записи алгоритма

Способ записи алгоритмов с помощью блок-схем нагляден и точен , но алгоритм предназначен для выполнения на компьютере, а блок-схемы компьютер не воспринимает. Вместе с тем такая запись точна настолько, что позволяет человеку понять суть дела и исполнить алгоритм. Поэтому алгоритм должен быть записан на языке, понятном компьютеру с точной записью команд.

Таким образом, алгоритм должен быть записан на каком-то промежуточном языке, с однозначными правилами и отличном от естественного и языка блок-схем и понятном компьютеру. Язык для записи алгоритмов должен быть формализован, не оставляющей места для произвольного толкования. Такой язык принято называть языком программирования, а запись алгоритма на этом языке — программой для компьютера

Программный способ записи алгоритма – это запись алгоритма на языке программирования, позволяющем на основе строго определенных правил формировать последовательность команд, точно описывающих смысл и содержание алгоритма, с целью исполнения его на машине (компьютере).