Алгоритмизация и типовые алгоритмические структуры

Тема 1.  Алгоритмизация  и  типовые  алгоритмические  структуры.

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

            Основу  любой  программы  составляет  алгоритм,  т.е.  точное  предписание  о  последовательности  действий,  которые  необходимо  произвести  для  достижения  необходимого  результата.  Известно  высказывание  австрийского  профессора  Николауса  Вирта  (“отца”  одного  из  популярнейших  языков  программирования  Паскаля)  -  “Программа  -  это  алгоритм   +  структура  данных.   Таким  образом,   алгоритм  -  это  основа  программы,  а  программа  -  это  запись  алгоритма  в  виде,  пригодном  для  реализации  на  конкретной  ЭВМ  (точнее  в  ее  программной  среде).

            Для  составления  алгоритма  важно  соблюдение  следующих  основных  требований  алгоритмизации:

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

2. Понятность.  Алгоритм  составляется  с  ориентацией  на  конкретного  исполнителя.  Для  этого  необходимо  четко  знать,  какие  предписания  (команды,  инструкции  и  др.)  он  может  понять  и  выполнить,  а  какие  нет.  У  каждого  исполнителя  такой  набор  предписаний  может  быть  отличным  от  такого  набора  у  других  исполнителей.

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

3. Детерминированность  (или  определенность).  Будучи  понятными,  предписания  не  должны  содержать  требований,  которые  можно  воспринять  неоднозначно.  Алгоритм  должен  быть  насколько  четким,  продуманным  в  деталях,  чтобы  у  исполнителя  не  возникала  потребность  в  принятии  каких-то  самостоятельных  решений,  не  предусмотренных  составителем  алгоритма.  Кроме  того  -  исполнителю  всегда  должно  быть  четко  понятно  какое  действие  он  должен  выполнять  после  окончания  выполнения  данного  действия.

4. Массовость.  Предпочтительными  являются  алгоритмы,  обеспечивающие  решение  некоторого  набора  сходных  задач.        

Рекомендуемые материалы

Например,  если  необходимо  найти  корни  квадратного  урав-нения  2x² + 5x + 7 = 0,  то  предпочтительнее  составить  алгоритм  (и  по  нему  программу)  нахождения  корней  уравнения  ax² + bx + c = 0,   а  значения  коэффициентов  a,  b  и  c  ввести  перед  счетом.

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

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

-  значения  двух  корней  уравнения

-  значение  единственного  корня  уравнения  и  сообщение  о  том,  что  уравнение  имеет  только  один  корень

-  сообщение  о  том,  что  данное  уравнение  действительніх  корней  не  имеет.

            Существует  много  способов  записи  алгоритмов.  Это  может  быть  :

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

- блок-схема алгоритма  (или  ее  многочисленные  разновидности,  например  схема  Несси-Шнердейман);

- запись  алгоритма  на  одном  из  алгоритмических  языков.

Наиболее  наглядным  и  удобным  для  восприятия  и  анализа  алгоритма  является  запись  его  в  виде  блок-схемы.

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

            Существуют  два  основных  типа  предписаний  :

- предписание  действия  (другое  название  -  блок  действия)

-   логическое  предписание  (или  логический  блок,  блок  ветвления  или  блок  принятия  решения).

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

         Логическое  предписание  (или  блок  принятия  решения)  используется  для  организации  ветвлений  в  алгоритме.  На  блок-схемах  его  изображают  в  двух  видах :

- если  предполагается  ветвление  в  двух  направлениях,  то  блок  изображается  в  виде  ромба  с  одним  входом  и  двумя  выходами.  Внутри  ромба  пишется  условие,  на  его  выходах  -  слова  «да»  и  «нет»,  которые  указывают  переходы  по  истинности  и  ложности  условия.

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

      Допускается  изображать  гребенку  в  повернутом  на  90⁰  против  направления  хода  часовой  стрелки  виде.

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

К  типовым  алгоритмическим  структурам  относятся  структуры  трех типов :

-  структура  следования,  в  которой  блоки  действия  следуют  друг  за  другом.

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

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

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

       цикл  с  предусловием                                       цикл  с  постусловием

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

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

Алгоритм  должен  начинаться  с  блока

и  заканчиваться  блоком

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

Для   улучшения  восприятия  алгоритма  -  он  должен  состоять  из  20 – 25   (в  исключительных  случаях  -  до  30)  блоков  или  макроблоков  и  располагаться  на  одном  листе  (формата  А3  или  А4).   Конкретизация  (разрисовка)   отдельных  макроблоков  может  бать  произведена  на  отдельных  листах,  являющихся  дополнением  к  основной  части  алгоритма.  На  этих  разрисовках  макроблоков  овалы  с  надписями  “Начало”  и  ”Конец”  изображать  не  надо.  Началом  и  концом  макроблока  должны  быть  вертикальные  черточки,  изображающие  вход  в  него  и  выход.   Под  ним  необходима  подпись  с  названием  макроблока  (такая  же  как  и  на  основной  блок-схеме).

Пример.  Составить блок-схему  алгоритма,  принадлежащего  древнему  мудрецу  Эвклиду,  нахождения  наибольшего  общего  делителя  (сокращенно  -  НОД)  двух  целых  положительных  чисел  a  и  b.

"5.15 Национальные революции в Османской империи" - тут тоже много полезного для Вас.

Суть  алгоритма  состоит  в  том,  что :

-  если   a = b,  то  НОД  равен  любому  из  этих  чисел,

-   в  противном  случае  -  из  большего  числа  вычитают  меньшее  и  результатом  вычитания  заменяют  большее  число  и  снова  производят  их  сравнение  (возвращаются  к  предыдущему  пункту  нашего  алгоритма). 

Доказано,  что  алгоритм  всегда  дает  результат  за  конечное  число  шагов.

Следует  отметить,  что  в  этом  алгоритме  соблюдены  все  требования  составления  алгоритмов  из  типовых  алгоритмических  структур,  включая  расширение  блоков  “вширь”  и  ”вглубь” .