Лекция "структурные схемы алгоритмов"

способы представления алгоритмов. структурные схемы алгоритмов тема 2 вопрос 2     К изобразительным средствам описания алгоритмов относятся следующие основные  способы их представления:    а) словесный (записи на естественном языке);    б) структурно­стилизованный (записи на языке псевдокода);    в) программный (тексты на языках программирования);    г) графический (схемы графических символов).     Словесный способ записи алгоритмов представляет собой описание последовательных  этапов обработки данных и задается в произвольном изложении на естественном языке.  Способ основан на использовании общепринятых средств общения между людьми и, с  точки зрения написания, трудностей для авторов алгоритмов не представляет. Однако для  "исполнителей" такие описания алгоритмов часто неприемлемы. Они строго не  формализуемы, страдают многословностью записей, допускают неоднозначность  толкования отдельных предписаний. Поэтому такой способ описания алгоритмов не имеет  широкого распространения.     Пример. Записать алгоритм нахождения наибольшего общего делителя двух  натуральных чисел (m и n) на естественном языке.      При таком словесном способе содержание алгоритма может быть следующим:     1) если числа равны, то необходимо взять любое из них в качестве ответа, в противном  случае ­ продолжить выполнение алгоритма;     2) определить большее из чисел;     3) заменить большее число разностью большего и меньшего чисел;     4) повторить алгоритм с начала.     Структурно­стилизованный способ записи алгоритмов основан на формализованном  представлении предписаний, задаваемых путем использования ограниченного набора  типовых синтаксических конструкций. Такие средства описания алгоритмов часто  называются псевдокодами. Разновидностью структурно­стилизованного способа описания  алгоритмов является известный школьникам алгоритмический язык в русской нотации  (АЯРН).     Пример. Приведем описанный на АЯРН алгоритм решения задачи об определении  принадлежности точки D треугольнику АВС.     алг Определение принадлежности точки треугольнику (действ xA, yA, хB,  уB, хC, уC,  хD, уD целое z лит а);    арг хА, уА, хВ, уВ, хС, уС, хD, уD;    рез z,а;     нач     действ S1, S2, S3, S4     вычислить значение S1, равное площади тр­ка АВС;     вычислить значение S2, равное площади тр­ка АВD;     вычислить значение S3, равное площади тр­ка АСD;     вычислить значение S4, равное площади тр­ка СDВ;     если S1 = S2+S3+S4     то z := 1, а := "точка внутри треугольника",     иначе z := 0, а := "точка вне треугольника",     все     напечатать значение а:    кон     Программный способ записи алгоритмов ­ это алгоритм, записанный на языке  программирования, позволяющем на основе строго определенных правил формировать  последовательность предписаний, однозначно отражающих смысл и содержание частей  алгоритма с целью их последующего исполнения на ЭВМ. Пример. Программа на языке Бейсик перевода температуры из градусов Цельсия в  градусы Фаренгейта.    PRINT "Перевод температуры из град. Цельсия в град. Фаренгейта"    PRINT "Укажите температуру в град. Цельсия"    INPUT C    6 IF C = 9999 THEN 7    F = C*1.8 +32    PRINT C, F    GOTO 6                                              7 END     Для графического изображения алгоритмов используются графические символы.  Наиболее распространенными являются блочные символы (блоки), соединяемые линиями  передач управления. Существует государственный стандарт на выполнение графической  записи алгоритма. Графическая запись алгоритма является наиболее наглядной. Перечень  условных графических символов, их наименования, форма, размеры и отображаемые  функции устанавливаются ГОСТ 19.003­80. Основные графические символы, используемые для описания алгоритмов, приведены в литературе [1, 2].     Схемы могут быть представлены также в виде структограмм или по имени их авторов,  диаграммами Нэсси ­ Шнейдермана [7].      На рис. 3 приведена схема алгоритма перевода температуры из шкалы Цельсия в шкалу  Фаренгейта. Перевод осуществляется по формуле:     Температура по Фаренгейту = (температура по Цельсию) Ч 180/100 +32. СХЕМЫ АЛГОРИТМОВ     Использование схем позволяет представить алгоритм в наглядной форме, поэтому они  наиболее часто используются.     Вычислительный блок представляет собой прямоугольник, в котором записываются  расчетные формулы. Причем формула должна быть записана таким образом, что  вычисляемая переменная записывается слева, далее идет знак равенства (в данном случае  этот знак называется присваиванием), далее ­ расчетная формула.     Проверка условия изображается ромбом, внутри которого записывается это условие. В  результате проверки выбирается один из двух возможных путей вычислительного процесса.     Если условие выполняется, то есть имеет значение ДА, то следующим выполняется этап  по стрелке ДА. Если условие не выполняется, то осуществляется переход по стрелке НЕТ.      Начало и конец вычислительного процесса изображаются овалом, в котором  записываются слова "Начало" или "Останов".     При решении задач на ЭВМ исходные данные задаются при вводе в машину. Ввод данных может осуществляться разными способами, например, с клавиатуры, с перфоленты, с диска и т. д. Задание численных значений исходных данных мы будем называть вводом, а  фиксацию результатов расчета ­ выводом. Ввод исходных данных и вывод результатов  изображаются параллелограммом. Внутри него пишется слово "Ввод" или "Вывод" и  перечисляются переменные, подлежащие вводу или выводу.     Параллелограммом обозначается ввод ­ вывод, не привязанный к какому­либо  конкретному устройству. Если ввод или вывод осуществляется с использованием  конкретных устройств, то блоки ввода ­ вывода изображаются с помощью специальных  фигур [2].     Комментарий используется в тех случаях, когда пояснение не помещается внутри блока.     По стандарту высота блока равна а, ширина 2а, где размер а выбирается из ряда 10, 15,  20 мм. Блоки "начало" и "конец" имеют высоту 0.5а.     Линии потока проводят параллельно внешним краям рамки листа. Направление линий  потока сверху вниз и слева направо принимают за основное; если линии потока основного  направления не имеют изломов, то их направление стрелками можно не обозначать. В  остальных случаях направление линий потока обозначать стрелкой обязательно. Записи  внутри символа или рядом с ним должны выполняться машинописью или чертежным  шрифтом и должны быть краткими. В левом верхнем углу в разрыве линий ставится номер  блока. В настоящее время основная тенденция в использовании схем алгоритмов состоит не  столько в указании последовательности операций, сколько в группировании блочных  символов в виде базовых управляющих конструкций. К ним относятся следование,  ветвление и повторение. Основные структуры алгоритмов ­ это ограниченный набор блоков и стандартных способов их соединения для выполнения типичных последовательностей  действий. Такие структуры рекомендуются при использовании так называемого  структурного подхода к разработке алгоритмов и программ. Структурный подход  предполагает использование только нескольких основных структур, комбинация которых  дает все многообразие алгоритмов и программ. АЛГОРИТМЫ ЛИНЕЙНОЙ СТРУКТУРЫ     Алгоритм линейной структуры (следование) ­ алгоритм, в котором все действия  выполняются последовательно друг за другом. Такой порядок выполнения действий  называется естественным.     Рассмотрим несколько примеров.     Задача 1. Определить площадь треугольника по формуле Герона    где a, b, c ­ длины сторон;    p = (a + b + c)/2 ­ полупериметр треугольника.     Для того чтобы рассчитать S, необходимо иметь численные значения p, a, b, c. Мы можем рассчитать p по формуле, а вот значения a, b, c должны быть заданы заранее, иначе задачу  решить невозможно.     Запишем словесный алгоритм.     1. Задать численные значения a, b, c.     2. Вычислить p по формуле: p = (a + b + c)/2.     3. Вычислить S по формуле:     4. Зафиксировать результат.         Схема представляет собой последовательность блоков, соединенных линиями потоков.  Направление потока задается стрелкой, но стрелка не ставится, если направление потока  сверху вниз и слева направо. В левом верхнем углу в разрыве линий ставится номер блока.     Внутри блока ввода записывается слово "Ввод" и перечисляются исходные данные  (имена переменных), которые задаются извне. Внутри блока вывода записывается слово  "Вывод" и перечисляются переменные, которые являются результатом расчета.     Приведем еще один пример схемы алгоритма линейной структуры.     Задача 2. Вычислить значения функций Y и Z.     Разработка алгоритма (рис. 5).     Исходные данные: а, Ь, с. Y и Х должны быть определены раньше, чем Y и  Z так как  входят в расчетную формулу для Y и для Z. АЛГОРИТМЫ РАЗВЕТВЛЯЮЩЕЙСЯ СТРУКТУРЫ      На практике редко удается представить схему алгоритма решения задачи в виде  линейной структуры. Часто в зависимости от каких­либо значений промежуточных  результатов необходимо организовать вычисление либо по одним, либо по другим  формулам. Ветвление ­ такая схема, в которой предусмотрено разветвление указанной  последовательности действий на два направления в зависимости от итога проверки  заданного условия. В схемах такой структуры используется логический блок (рис. 6).     Задача 2.      Рассчитать Y.     Разработка алгоритма. В этой задаче должно быть задано X. Далее анализируется X.  Если X<0, то вычисления производятся по первой формуле, если это условие не  выполняется, то выполняется второе условие X і 0, так как условия X<0 и X і 0  взаимоисключающие, и Y вычисляется по второй формуле.     Словесный алгоритм решения этой задачи будет выглядеть следующим образом.     1. Задать численное значение для X.     2. Проверить условие X<0: если условие выполняется перейти к п. 5; если условие не выполняется перейти к п. 3. 3. Вычислить Y по формуле Y = X2.      4. Перейти к пункту 6.     5. Вычислить Y по формуле Y = ­X.      6. Зафиксировать вычисленное Y.     Схема данного алгоритма представлена на рис. 6.     Рекомендуется под словом "нет" записывать условие, противоположное проверяемому.     Задача 4. Вычислить значение функции Z = Х /Y, где Y = sin(nX) + 0.5.     Разработка алгоритма. Казалось бы решение этой задачи можно описать алгоритмом  линейной структуры. Однако, для удовлетворения свойств массовости и результативности  алгоритма необходимо, чтобы при любых исходных данных был получен результат или  сообщение о том, что задача не может быть решена при заданных исходных данных.  Действительно, если Y = 0, задача не может  быть решена. Поэтому в алгоритме  необходимо предусмотреть этот случай и выдать в качестве результата информацию о том, что Y = 0. Рассматриваемый вычислительный процесс должен иметь две ветви: в одной,  если Y № 0, необходимо вычислить значение переменной Z, а в другой ­ дать информацию  Y = О (рис. 7).     Если условие Y = О, выполняется, то работает блок 6, т.е. осуществляется вывод  сообщения о равенстве Y нулю. После блока 6 сразу же выполняется блок  8 ­ решение  заканчивается. Если условие Y = 0 не выполняется, это значит, что  выполняется условие Y № 0 и мы должны рассчитать Z и вывести его. АЛГОРИТМЫ ЦИКЛИЧЕСКОЙ СТРУКТУРЫ     Алгоритмы, отдельные действия в которых многократно повторяются, называются  алгоритмами циклической структуры (повторение). Совокупность действий алгоритма,  связанную с повторением, называют циклом. Алгоритмы циклической структуры Алгоритмы, отдельные действия в которых многократно  повторяются, называются алгоритмами циклической структуры  (повторение). Совокупность действий алгоритма, связанную с  повторением, называют циклом. На рис. 10 представлена схема  алгоритма циклической структуры. Блоки 3, 4, образующие тело цикла,  повторяются многократно. Сколько раз? Бесконечное количество. При  каждом расчете к предыдущему значению X прибавляется 2, далее  следует возврат к расчету Y, вывод Y и опять X изменяется на 2. По условию задачи  расчетом Y при X = 10 нужно ограничиться. Следовательно, необходимо включить условие окончания расчетов. До тех пор, пока X £ 10, расчеты производить; как только X станет  больше 10 – вычисления закончить. В схему включим логический блок. В блоке 2 осуществляется задание начального значения для X. В блоке 3  рассчитываются значения Y. В блоке 5 фиксируется текущее значение X с заданным шагом. В блоке 6 анализируется величина X. Если X еще не превысил своего конечного значения,  то необходимо вернуться к блоку 3 и повторить вычисления. Если X стал больше  предельного значения, расчеты нужно закончить. Еще раз обратите внимание на то, что блок 4 – модификация – включил в себя три блока предыдущей схемы – блоки 4, 7, 8. Нельзя точно сказать, какая из типов циклических структур (“До” или “Пока”) скрывается  в блоке “модификация”. Например, в языках программирования эта структура  организована по разному. АЛГОРИТМЫ СО СТРУКТУРОЙ ВЛОЖЕННЫХ ЦИКЛОВ     Любой цикл, содержащий внутри себя один или несколько других циклов, называется  вложенным. Цикл, охватывающий другие циклы, называется внешним а остальные циклы ­  внутренними. Правила организации как для внешнего, так и внутреннего циклов такие же,  как и для простого цикла. Параметры этих циклов изменяются одновременно, т. е. при  одном значении параметра внешнего цикла параметр внутреннего цикла принимает по  очереди все свои значения.      Матрицы ­ удобный пример для демонстрации алгоритмов со структурой вложенных  циклов. В матрице [A] М столбцов и N строк. Каждый элемент матрицы определен двумя  индексами, которые указывают положение этого элемента. На первом месте  записывается  номер строки, на втором ­ номер столбца. Например, а    ­ элемент матрицы [A ],  расположенный во второй строке третьего столбца.     Если необходимо задать значение матрицы, значит нужно задать значения всех ее  элементов. Назовем элемент матрицы аij. Для всей матрицы в целом i пробегает значения  от 1 до N, а j от 1 до М.     Каждую строку матрицы можно рассматривать как одномерный массив. С вводом  одномерного массива мы знакомы. Ввод первой строки матрицы определяет следующая  совокупность элементов схемы (рис. 24).         Такая же схема должна быть использована для второй строки матрицы, для третьей и  так далее до М ­ ой строки. То есть номер строки может быть задан циклом и этот цикл  будет внешним по отношению к циклу по столбцу. Cхема ввода матрицы [A]  без блока  модификации дана на рис. 25. Внешний цикл по i ­ блоки 3, 4, 5, 6, 7, 8, 9.  Блок 3 ­ подготовка цикла по i.  Блок 8 ­ изменение параметра цикла. Блок 9 ­ проверка условия окончания цикла. Блоки 4, 5, 6, 7, 8 ­ тело цикла. Внутренний цикл по j ­ блоки 4, 5, 6, 7. Блок 4 ­ подготовка цикла по j. Блок  6 ­ изменение параметра цикла. Блок 7 ­ проверка условия окончания цикла. Блоки 5, 6 ­ тело цикла.     При переходе к следующему значению i (к следующей строке) j ­ восстанавливает  первоначальное значение равное 1. ПОДЧИНЕННЫЕ АЛГОРИТМЫ     При записи алгоритмов могут использоваться алгоритмы, составленные раньше.  Алгоритмы, целиком используемые в составе других алгоритмов, называются  подчиненными алгоритмами или подалгоритмами. Не исключено, что алгоритм,  содержащий в своем описании подчиненные алгоритмы, сам может выступать в роли  подалгоритма. В схемах подалгоритм изображается символом     Задача 15. Составить алгоритм вычисления числа сочетаний. Число сочетаний  рассчитывается по формуле:      Вычисление факториала оформить в виде подалгоритма.     В блоках "начало" и "останов" в подчиненном алгоритме записываются слова "вход" и  "выход" (рис. 30 В).     В данной задаче необходимо трижды вычислить факториал: n!, m! и (n ­ m)!. Для расчета факториала разработан подалгоритм. Вместо полной записи последовательности блоков  подалгоритма, которая должна повторяться трижды в основной схеме, введены блоки  обращения к подалгоритму.      Использование подалгоритмов находит широкое применение в практике алгоритмизации  и является одним из наиболее значительных и интересных приемов.     Одним из приемов разработки алгоритма решения более сложных задач является метод  пошаговой детализации, когда первоначально продумывается и фиксируется общая  структура алгоритма без детальной проработки отдельных его частей, но при этом также  используются лишь основные структуры алгоритмов. Блоки, требующие дальнейшей  детализации, обозначаются пунктирной линией. Далее прорабатываются (детализируются)  отдельные блоки, не детализированные на предыдущем шаге. Полностью закончив  детализацию всех блоков, получим решение всей задачи в целом. пособы представления алгоритмов:     1. Формульно­словесный способ.     Основан на задании инструкций о выполнении конкретных действий в четкой  последовательности в сочетании со словесными пояснениями.     Пример. Вычислить: С =     Этап 1. Ввести А, В;     Этап 2. Если А В, то переходим к этапу 3; иначе переходим к этапу 4.     Этап 3. С=А­В, и переходим к этапу 5;     Этап 4. С=А+В;     Этап 5. Вывод С.     2. На алгоритмическом языке. Алгоритмический язык – совокупность правил и обозначений, использующиеся для записи  алгоритма.      Он включает:     а) математические выражения;     б) текст;  в) служебные слова (полные или сокращенные слова русского текста, стоящие в  определенном месте алгоритма, которые обязательно подчеркиваются) Пример. Вычислить значение А+ алг Проскурнин (нат А, вещ В, У, цел Х)         арг А, В, Х         рез У     нач         У:=А+     кон     3. Графический способ (метод блок­схемы).     При таком представлении алгоритма, каждый этап отображается в виде геометрических  фигур­блоков, форма которых зависит от выполняемой операции.     Линия соединения блоков, показывает направление процесса обработки данных. Каждое  направление называется ветвью.   Название блока Графическое представление блока Описание Линейный процесс Проверка условия, Логическое решение Ввод­вывод Начало­конец  алгоритма Предопределеный  процесс модуль Соединитель Пример. Выполнение операции или группы операций, в  результате которых изменяются значение,  фомы представления или расположение данных. Выбор направления выполнения алгоритма в  зависимости от некоторых переменных  условий. Преобразование данных в форму пригодную  для обработки (ввод) или отображения  результатов обработки (вывод). Начало, конец процесса обработки данных     Использование ранее созданных или отдельно  описанных алгоритмов (модулей).   Указание связи между линиями потока  обработки данных. Вычислить: С = 4. Табличный способ.   «Типы алгоритмов». 1) Линейный алгоритм:   2) Разветвляющийся алгоритм:   3) Циклический алгоритм:       Структурные схемы алгоритмов     Одним из свойств алгоритма является дискретность — возможность расчленения  процесса вычислений, предписанных алгоритмом, на отдельные этапы, возможность  выделения участков программы с определенной структурой. Можно выделить и наглядно  представить графически три простейшие структуры:   последовательность двух или более операций;  выбор направления;  повторение.     Любой вычислительный процесс может быть представлен как комбинация этих  элементарных алгоритмических структур. Соответственно, вычислительные процессы,  выполняемые на ЭВМ по заданной программе, можно разделить на три основных вида:    линейные;  ветвящиеся;  циклические.     Линейным принято называть вычислительный процесс, в котором операции  выполняются последовательно, в порядке их записи. Каждая операция является  самостоятельной, независимой от каких­либо условий. На схеме блоки, отображающие эти  операции, располагаются в линейной последовательности. Линейные вычислительные процессы имеют место, например, при вычислении  арифметических выражений, когда имеются конкретные числовые данные и над ними  выполняются соответствующие условию задачи действия. На рис. 11.1, а показан пример  линейного алгоритма, определяющего процесс вычисления арифметического выражения у=(b2­ас):(а+с).           а б Рис. 11.1. Примеры алгоритмов: а) линейный алгоритм; б) ветвящийся алгоритм     Вычислительный процесс называется ветвящимся, если для его реализации  предусмотрено несколько направлений (ветвей). Каждое отдельное направление процесса  обработки данных является отдельной ветвью вычислений. Ветвление в программе — это  выбор одной из нескольких последовательностей команд при выполнении программы.  Выбор направления зависит от заранее определенного признака, который может относиться к исходным данным, к промежуточным или конечным результатам. Признак характеризует  свойство данных и имеет два или более значений.     Ветвящийся процесс, включающий в себя две ветви, называется простым, более двух  ветвей — сложным. Сложный ветвящийся процесс можно представить с помощью простых  ветвящихся процессов.     Направление ветвления выбирается логической проверкой, в результате которой  возможны два ответа: «да» — условие выполнено и «нет» — условие не выполнено.  Следует иметь в виду, что, хотя на схеме алгоритма должны быть показаны все возможные  направления вычислений в зависимости от выполнения определенного условия (или  условий), при однократном прохождении программы процесс реализуется только по одной  ветви, а остальные исключаются. Любая ветвь, по которой осуществляются вычисления,  должна приводить к завершению вычислительного процесса. На рис. 11.1,б  показан пример алгоритма с разветвлением для вычисления следующего  выражения: Y = (а+b), если Х <0; с/b, если Х>0.     Циклическими называются программы, содержащие циклы. Цикл — это многократно  повторяемый участок программы. В организации цикла можно выделить следующие этапы:     Порядок выполнения этих этапов, например, Т и М, может изменяться. В зависимости  от расположения проверки условия окончания цикла различают циклы с нижним и верхним окончаниями (рис. 11.2). Для цикла с нижним окончанием (рис. 11.2, а) тело цикла  выполняется как минимум один раз, так как сначала производятся вычисления, а затем  проверяется условие выхода из цикла. В случае цикла с верхним окончанием (рис. 11.2, б)  тело цикла может не выполниться ни разу в случае, если сразу соблюдается условие  выхода.     • подготовка (инициализация) цикла (И);  • выполнение вычислений цикла (тело цикла) (Т);  • модификация параметров (М);  • проверка условия окончания цикла (У).              а б Рис. 11.2. Примеры циклических алгоритмов     Цикл называется детерминированным, если число повторений тела цикла заранее  известно или определено. Цикл называется итерационным, если число повторений тела  цикла заранее неизвестно, а зависит от значений параметров (некоторых переменных),  участвующих в вычислениях.     На рис. 11.3 показан пример циклического алгоритма вычисления суммы десяти чисел. Рис. 11.3. Алгоритм нахождения суммы 10­ти чисел