Информатика и программирование - Основы информатики (926517), страница 20

Просмтор этого файла доступен только зарегистрированным пользователям. Но у нас супер быстрая регистрация: достаточно только электронной почты!

Текст из файла (страница 20)

3. НОД := М.

4. Вывести НОД.

Конец.

Блок-схема алгоритма Евклида представлена на Рис. 9 .25, где блок 1 есть подготовка цикла, блок 2 – управление циклом, блоки 3, 4, 5 – тело цикла (разветвляющаяся структура), из них блоки 4, 5 являются блоками модификации значений переменных цикла M и N. □

Рис. 9.25. Алгоритм Евклида

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

Блок-схемы не накладывают никаких ограничений на степень детализации в изображении алгоритма. Это определяется программистом. Однако следует помнить, что схемы общего характера малоинформативны, а излишне подробные схемы проигрывают в наглядности. При разработке сложных алгоритмов, чтобы уяснить сущность выполняемых действий и выявить основные связи, сначала пытаются представить его общей схемой в виде достаточно крупных блоков. Затем эти крупные блоки разбивают на более мелкие, составляя более детальные схемы и проверяя их логическую правильность. Именно так мы поступили при разработке алгоритма Евклида, при этом использовали и словесную форму записи, и блок-схему.

9.4.3.Структурограммы

В практике структурного программирования для представления алгоритмов используются также структурограммы (схемы Насси-Шнейдермана). Этот способ позволяет изображать схему передач управления в алгоритме не с помощью явного указания линий потоков информации, а с помощью представления вложенности структур – функциональных блоков, которые используются для описания выполняемых действий. Некоторые из используемых в этом способе блоков соответствуют их изображению в схемах алгоритмов. Для изображения алгоритмов в структурограммах используются следующие блоки.

1. Блок обработки (вычислений). Каждый блок является блоком обработки. Каждый прямоугольник внутри любого блока представляет собой также блок обработки.
2. Блок следования. Этот блок объединяет ряд следующих друг за другом процессов обработки.
3. Блок решения. Этот блок применяется для обозначения структуры ветвления. Условие располагается в верхнем треугольнике, варианты решения – по сторонам треугольника, процессы обработки – в нижних прямоугольниках. Если блок решения является сокращенным (отсутствует одна из ветвей), то структурограмма видоизменяется соответствующим образом.
4. Блок варианта реализует структуру многоальтернативного выбора. Варианты, которые можно сформулировать точно, размещаются слева, остальные объединяются в один, называемый выходом по несоблюдению условий, располагаемый справа. Правую часть можно оставить незаполненной или опустить.
5. Блок цикла с предусловием реализует циклическую структуру с проверкой условия в начале цикла. Условие продолжения цикла размещается в верхней полосе, сливающейся с левой, указывающей границу цикла. Данный блок может быть использован и для обозначения цикла с параметром, тогда вверху указывают закон изменения параметра цикла.
6. Блок цикла с постусловие аналогичен блоку цикла с предусловием, но условие окончания цикла располагают внизу. Каждый блок имеет форму прямоугольника и может быть вписан в любой внутренний прямоугольник любого другого блока. Блоки дополняются элементами словесной записи с использованием математической символики. На Рис. 9 .26 приведен пример структурограммы алгоритма Евклида.
	Рис. 9.26. Структурограмма алгоритма Евклида

9.5.Технология разработки алгоритмов

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

Какими качествами должен обладать хороший алгоритм?

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

По своей сути структурный подход есть отказ от беспорядочного стиля в алгоритмизации и программировании (в частности, отказ от оператора go to) и определение ограниченного числа стандартных приемов построения легко читаемых алгоритмов и программ с ясно выраженной структурой. Теоретическим фундаментом этого подхода является теорема о структурировании, из которой следует, что алгоритм решения любой практически вычислимой задачи может быть представлен с использованием трех элементарных базисных управляющих структур: а) структуры следования или последовательности; б) структуры ветвления; в) структуры цикла с предусловием (Рис. 9 .27, соответственно а, б, в, где P – условие, S – оператор).

Рис. 9.27. Базисные управляющие структуры

Базисный набор управляющих структур является функционально полным, то есть с его помощью можно создать любой сколь угодно сложный алгоритм. Однако с целью создания более компактных и наглядных алгоритмов дополнительно используются следующие управляющие структуры: а) структура сокращенного ветвления; б) структура выбора; в) структура цикла с параметром; г) структура цикла с постусловием (Рис. 9 .28, соответственно а, б, в, г).

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

Рис. 9.28. Дополнительные управляющие структуры

Любой алгоритм может быть построен посредством композиции базисных и дополнительных структур:

- путем их последовательного соединения  образования последовательных конструкций;

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

Например, алгоритм Евклида, описанный ранее, представляет собой комбинацию из трех управляющих структур: последовательности, цикла и ветвления (Рис. 9 .29).

Рис. 9.29. Алгоритм Евклида как композиция базисных структур

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

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

В качестве примера рассмотрим задачу табулирования функции одной переменной, то есть вычисление значений функции у = f(x) для всех значений х, изменяющихся от х₀ до х_n с шагом h_x, сокращенно:
x = х₀(h_x) х_n.

Пусть

где

a, b, x₀, h_x, x_n – исходные данные.

Процесс проектирования алгоритма табулирования функции у = f(x) показан на Рис. 9 .30, а. На первом уровне детализации схема отражает процесс табулирования функции в общем виде (блоки 1.1-1.5). Далее осуществляется детализация блока 1.4 в виде последовательности блоков 2.1-2.3 второго уровня. Функция z = z(x), входящая в определение исходной функции, представлена разветвляющейся структурой третьего уровня детализации (блоки 3.1-3.5).

а

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

Характеристики

Список файлов книги