Если у вас возникли сложности с курсовой, контрольной, дипломной, рефератом, отчетом по практике, научно-исследовательской и любой другой работой - мы готовы помочь.
Предоплата всего
Подписываем
Тема 7. Алгоритмизация
1. В основе решения любой задачи лежит понятие алгоритма. Под алгоритмом принято понимать «точное предписание, определяющее вычислительный процесс ведущий от варьируемых начальных данных к искомому результату». Таким образом, алгоритм должен содержать конечную последовательность шагов или операций переработки исходных данных в искомый результат. Сам термин алгоритм – это европеизированное произношение словосочетания «аль Хорезми», которое входило в название трудов известного математика древности из Хорезма, дававшем описание и ход выполнения четырех арифметических действий.
Алгоритм должен обладать следующими свойствами:
Способы описания алгоритмов. К изобразительным средствам описания алгоритмов относятся следующие основные способы их представления: словесный (записи на естественном языке), структурно-стилизованный (записи на алгоритмическом языке псевдокода), графический (изображения схем из графических символов), программный (тексты на языках программирования).
Словесный способ записи алгоритмов представляет собой описание последовательных этапов обработки данных и задается в произвольном изложении на естественном языке.
Пример. Записать алгоритм нахождения наибольшего общего делителя двух натуральных чисел (т и п) на естественном языке. При таком словесном способе содержание алгоритма может быть следующим:
Описанный алгоритм применим к любым натуральным числам и должен приводить к решению поставленной задачи.
Способ основан на использовании общепринятых средств общения между людьми и сточки зрения написания трудностей для авторов алгоритмов не представляет. Однако для «исполнителей» такие описания алгоритмов часто неприемлимы. Они строго не формализуемы, страдают многословностью записей, допускают неоднозначность толкования отдельных предписаний. Поэтому такой способ описания алгоритмов не имеет широкого распространения.
Структурно–стилизованный способ записи алгоритмов основан на формализованном представлении предписаний, задаваемых путем использования ограниченного набора типовых синтаксических конструкций, представленных в понятном для разработчика алгоритма виде. Такие средства описания алгоритмов часто называют псевдокодами. Разновидностью структурно-стилизованного способа описания алгоритма является известный школьникам алгоритмический язык в русской нотации (АЯРН), содержащий систему обозначений для единообразной и точной записи алгоритмов и задания правил их использования. Важной особенностью алгоритмических языков типа псевдокодов является их близость к языкам программирования.
Для изображения структур алгоритмов используется совокупность блочных символов (блоков), соединяемых линиями передач управления. Такое изображение называется методом б л о к – с х е м.
Поскольку алгоритмы воспринимается визуально, их следует изображать таким образом, чтобы их структура выглядела чётко и выразительно. Краткость, выразительность и планомерность при проектировании позволяют создавать схемы алгоритмов высокого качества.
В схеме алгоритма каждому типу действий (вводу исходных данных, вычислению значений выражений, проверке условий, управлению повторением действий, окончанию обработки и т.п.) соответствует геометрическая фигура, представленная в виде блочного символа (блока), называемого символом действия. Символы действия соединяются линиями переходов, определяющими очередность выполнения действий.
Блоки ввода - вывода используются для обозначения
операций ввода / вывода информации.
Блок обработки (процесс) применяется для обозначения
одного или последовательности действий, изменяющих
значение, форму представления или размещение данных.
Для улучшения наглядности схемы несколько отдельных
блоков обработки можно объединить в один блок.
Линии переходов используется для обозначения порядка
выполнения действий, Для улучшения наглядности следует
придерживаться стандартных правил изображения
лини передач управления - сверху вниз и слева направо.
Блоки решения (условия) используются для обозначения переходов
управления по условию. В каждом блоке решения должен быть
указан вопрос, решение, условие или сравнение, которые он
определяет. Стрелки, выходящие из блока решения, должны быть
помечены соответствующими ответами (например, ДА, НЕТ),
так чтобы были учтены все возможные ответы.
Блок модификаций (цикла) используются для организаций
циклических конструкций. Внутри блока записывается
параметр цикла для которого указываются его начальное
значения, граничное условие и правило изменения
значения параметра для каждого повторения.
Блок начала и конца алгоритма.
Наглядность и обозримость блок-схем, целостность восприятия, однозначность в отображении вычислительного процесса облегчают работу с алгоритмом, проверку его правильности и внесение изменений.
Однако блок-схемы страдают серьезным недостатком, заключающимся в том, что фактически отсутствуют правила задания и определения характеристик объектов, над которыми предписывается выполнение операций. Это вносит существенную неопределенность в организацию обработки данных, задаваемую с помощью графических схем, и потенциально является причиной многих ошибок и неточностей, которые появляются в программах.
2. К основным базовым управляющим конструкциям относятся следование,ветвление и повторение.
Рассмотрим каждую из них:
Алгоритм линейной структуры (следование). Блочные символы в этой структуре располагаются на схеме в том же порядке, в каком должны быть выполнены предписываемые действия. Такой порядок исполнения действий называется естественным.
В качестве примера можно рассмотреть схему алгоритма вычисления площади треугольника, зная значения трёх его сторон а, Ь, с , по формуле Герона. На рис.1 показана схема алгоритма вычисления площади по известным трем сторонам.
Алгоритм разветвленной структуры (ветвление). Это такая схема, в которой предусмотрено разветвление указанной последовательности действий на два направления и зависимости от итога проверке заданного условия.
В качестве, примера можно рассмотреть схему алгоритма нахождения максимума из двух чисел а и Ь. На рис.2 показан этот алгоритм.
Алгоритм циклической структуры (повторение). Алгоритм, в котором предусмотрено неоднократное выполнение одной и той же последовательности действий и называется циклом. Циклическая структура позволяет существенно сократить размер записи алгоритма, представить его компактно путем соответствующей организации повторения предписываемых действий. Естественно, что повторять какие-либо действия имеет смысл при различных значениях параметров, изменяемых при каждом новом выходе на повторение. Такие изменяемые параметры называют параметрами цикла.
начало
а, в, с
р:=
S:=
конец
Рис.1
Для организации циклической структуры можно использовать либо блочный символ «решение» в совокупности с символами «процесс» (рис. 4), либо специальный блочный символ «модификация» (рис.3). И в том, и в другом варианте схема организации алгоритма циклической структуры должна содержать действия, задающие начальное значение параметра цикла, правило его значения для перехода к новому повторению, а также условие выхода из цикла (или нахождения в нём).
Разновидности циклических алгоритмов. На рисунках 3 и 4 показаны циклы, в которых заранее известно количество повторений – такие алгоритмы называются циклами по счетчику. Алгоритмы, в которых число повторений цикла заранее не определено, называются итерационными.
начало
начало
vн,, vк, vш
а, в
a>b
нет да v:=vн, vк, vш
Повторяемый
участок цикла
max:=b
max:=a
max
конец
конец
Рис.2 Рис.3
Для их организации, в отличие от циклов по счетчику (где можно применить блок цикла), применяется комбинация блока условия и действия, но никак не блок цикла, который подразумевает знание наперед количества повторений цикла.
Структура итерационного цикла состоит из блока условия и функционального блока (блока действия), называемого телом цикла. Тело цикла – это группа действий, идущих подряд, которая повторяется несколько раз.
Данная структура может быть двух видов (рис.5,6).
В случае «цикл – ПОКА» блок тела цикла размещен после проверки
условия, поэтому может оказаться, что тело цикла не выполнится ни разу.
Однако, если условие выполняется – выполняется весь цикл. Проще говоря, «цикл – ПОКА» выполняется, п о к а выполняется условие. Условие здесь является условием продолжения цикла, т.к. в случае выполнения условия цикл продолжает работать.
В «цикле – ДО» блок тела цикла размещен до проверки выполнения условия, так что в этом варианте тело цикла в любом случае будет выполнено по крайней мере один раз. Условие в данном случае является условием выхода из цикла. Проще говоря, «цикл – ДО» выполняется д о наступления условия.
Алгоритм со структурой вложенных циклов. Внутри одного цикла могут находиться один или несколько других циклов. В этом случае охватывающий цикл называется внешним, а вложенные в него циклы - внутренними. Правила организации как внешнего. Так и внутренних циклов аналогичны правилам организации простого цикла. Параметры внешнего и внутреннего циклов изменяются не одновременно, т.е. при одном значении параметра внешнего цикла параметр внутреннего последовательно принимает все возможные значения. При организации вложенных циклов
начало
v:=vн
vн, vк, vш
v≤ vк
нет
да
Повторяемый участок цикла
v:=v+vш
конец
Рис. 4
необходимо следить за тем, чтобы область действия внутреннего цикла не выходила за область действия внешнего цикла.
цикл – ПОКА цикл - ДО
Тело цикла
Условие продолжения цикла
нет
Условие окончания цикла
нет
да
Тело цикла
да
Рис.5 Рис.6
Вопросы для самоконтроля:
Рекомендуемая литература: ОЛ 6.