1. Основы алгоритмизации

Подготовка задачи к решению на ЭВМ требует последовательного поэтапного её рассмотрения с целью:

1.      постановки и математической формализации;

3.      разработки алгоритма и определения структуры данных;

4.      реализации алгоритма на языке программирования (составление программы);

5.      подготовки задания для ПЭВМ, ввода программы и данных контрольного примера;

6.      отладки и испытания программы. Для решения задачи следует запустить программу на исполнение, ввести исходные данные, произвести вычисления, проанализировать и оформить результат вычислений.

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

1.1. Понятие, свойства и способы описания алгоритма

Под алгоритмом понимается «точное предписание, определяющее вычислительный процесс, ведущий от варьируемых начальных данных к искомому результату» (ГОСТ 19.781-74). Алгоритм включает систему правил, определяющих содержание и конечную последовательность действий (шагов и операций), выполняемых над некоторыми объектами с целью переработки исходных и промежуточных данных в искомый результат. Это пред­писание конкретному исполнителю о том, какие действия, над какими объектами и в каком порядке следует выполнять для решения поставленной задачи.

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

Понятие алгоритма, относящееся к фундаментальным концепциям информатики, возникло задолго до появления ПЭВМ.

Алгоритмы с IX века и до настоящего времени используются в математике для обозначения правил выполнения четырех арифметических действий: сложения, вычитания, умножения и деления. На протяжении многих веков люди интуитивно 'пользовались алгоритмами нахождения корней квадратного уравнения, расчета площади квадрата или круга, определения объема куба, цилиндра, конуса. В настоящее время сфера применения этого понятия существенно расширена. Об алгоритмах говорят при обсуждении процессов управления производством, проблем принятия решений или выполнения некоторых технологических операций.

Классическим примером словесного описания алгоритма является предложенный древнегреческим математиком Евклидом способ вычисления наибольшего общего делителя (НОД) двух натуральных чисел (А и В), включающий описанную ниже последовательность элементарных шагов, каждый из которых предписывает выполнение некоторых действий:

1.Обозначить первое число буквой А, второе - буквой В. Сравнить

А и В.

2.Если А = В, то принять D = А и перейти к п. 6 алгоритма,

иначе перейти к п. 3.

З.Если А<В, то принять О = А и М = В, иначе D = В и М = А. Перейти к п. 4.

4. Разделить М на D, остаток обозначить R, перейти к п. 5.

5. Если R = 0, то перейти к п. 6, иначе присвоить М = D, D = R и перейти к п. 4.

6. D есть искомое число. Закончить вычисления. Здесь алгоритм словесно описан предложениями естественного языка. Объектами его обработки являются числа, обозначенные буквами. Подставив конкретные числовые значения, например 80 и 28, можно проверить его «работу»:

1.Полагаем А = 80 и В = 28.

2.Так как А> В, то перейдем к п. 3 алгоритма.

3.Проверяем условие А < В. Так как ответ «нет», то

присваиваем D = 28 и М = 80.

4.Делим 80 на 28. Частное равно 2, остаток R = 24.

5.Проверяем условие R = 0. Ответ «нет», присваиваем М = 28,

D = 24 и переходим к п. 4 алгоритма.

6.28 делим на 24. Частное = 1, остаток R = 4.

7.Проверяем условие R = 0. Ответ «нет», присваиваем М = 24,

D = 4 и переходим к п. 4 алгоритма.

8.24 делим на 4. Частное = 6, остаток R = 0.

9.Проверяем условие R = 0. Ответ «да», переходим к п. 6 алгоритма.

10.НОД чисел 80 и 28 равен 4. Закончить вычисления.

Заметим, что описание алгоритма содержит всего шесть пунк­тов, а его выполнение требует большего числа шагов (в нашем примере 10). Это обусловлено тем, что некоторые действия (пункты 4 и 5), как и было предписано алгоритмом, повторялись несколько раз.

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

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

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

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

Для иллюстрации этих свойств алгоритма рассмотрим вычисление значения функции Sin(x) методом разложения ее в ряд по степеням аргумента по известной формуле:

Очевидно, что при расчете по подобной формуле окончательного ответа мы не получим, поскольку в условии задачи ничего не говорится о количестве членов ряда, которые необходимо учитывать при вычислениях. Без подобных указаний вычислительный процесс может продолжаться сколь угодно долго, то есть «бесконечно». Чтобы этого не произошло, следует ввести некоторые ограничения, обеспечивающие свойство конечности алгоритма, в частности задать некоторое допустимое число шагов выполнения алгоритма. Например, суммирование продолжать до тех пор, пока значение очередного, учитываемого в сумме члена ряда не станет меньше некоторого S, равного 10"^J. В этом случае за некоторое конечное число шагов будет получен результат и алгоритм вычисления функции приобретет свойство результативности.

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

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

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

Словесный способ записи алгоритмов представляет собой описание последовательности действий по обработке данных на естественном языке человеческого общения. Очевидные преимущества: доступность и простота использования. Недостатки: алгоритмы плохо формализуемы, громоздки и ненаглядны.

Структурно-стилизованный способ записи основан на применении естественного языка в формализованном представлении предписаний, конструкции которого близки к конструкциям структурных языков программирования. Примером такого способа является предложенный академиком А. П. Ершовым алгоритмический язык в русской нотации (АЯРН), известный многим из школьной дисциплины «Информатика».

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

Наиболее распространенным способом представления алгоритма является графический. В графическом представлении алгоритмы изображаются в виде блок-схемы, дополненной элементами словесной или математической записи. Схема алгоритма включает геометрические фигуры (блочные символы), соединенные между собой стрелками (линиями), указывающими порядок выполнения операций. Блочные символы стандартизированы и различаются по типу выполняемых действий ( ГОСТ 19.002-80 и 19.003-80, международные стандарты ИСО 2636-73 или ИСО 1028-73).

В схеме начало и завершение алгоритма, а также вход и выход из вспомогательных алгоритмов, отмечаются соответственно блочными символами «начало» и «конец» (рис. 1.1аи 1.16, блоки 1 и 2). Эти блоки, в отличие от большинства других, имеют один вход или один выход, отмечающие как бы начало и конец пути обработки информации. Каждая схема обязательно должна начинаться и заканчиваться этими символами.

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

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

Логический блочный символ «решение» (рис. 1.1ж-и, блоки 6, 7, 8 соответственно) используют для обозначения выбора направления выполнения алгоритма в зависимости от некоторого условия (условий). В блоке указывают условие, вопрос или решение, определяющие дальнейшее направление выполнения алгоритма. Условия могут быть простыми (рис. 1.1ж, блок 6) и составными (рис. 1.1и, блок 8). В них должны быть учтены абсолютно все возможные варианты следования процесса при решении задачи.

            Рис. 1.1. Наиболее употребляемые в схемах алгоритмов блок - символы

Из блока проверки условия может выходить два или три информационных потока, что отличает его от других блочных символов, имеющих не более одного выхода. Выходящие из блока линии должны снабжаться пояснениями о направлениях исполнения алгоритма при выполнении или невыполнении приведенное условия (например, «да», «нет», <«0», «=0», «>0», «+», «-», или др. Блочный символ модификации (рис. 1.1к и 1.1л, блоки 9 и 10) символизирует начало циклических вычислений (заголовок цикла), для управления которыми он используется. Внутри блока указывается переменная цикла и параметры, характеризующие закон ее изменения, например, i =А_нач, А_кон, ∆А, где i - переменная цикла, а_нач и А_кон, ~ начальное и конечное значения переменной цикла, ∆А - шаг ее изменения (переменная цикла изменяется от А_нач до А_кон с шагом ∆А). Если шаг равен 1, то ∆А можно не указывать.

Кроме входящей линии блок модификации имеет одну выходящую (на рис. 1.1л обозначенную «Вых»), а также линии, отмечающие передачу вычислительного процесса на обработку для циклических вычислений «Цикл» и возврат в начало для изменения переменной цикла «Изм. пер.».

Для обращения к вычислению по подпрограмме (стандартной или разработанной пользователем) в схеме используют блок-символ «предопределенный процесс», изображенный на рис. 1. 1м (блок 11). Он как бы заменяет алгоритм подпрограммы (вспомогательный алгоритм) и указывает, что информационный поток передается подпрограмме. По завершении вычислительного процесса в подпрограмме результаты расчета возвращаются в основной алгоритм, в котором процесс вычислений возобновляется с блока, следующего за блоком обращения к подпрограмме. Блок «предопределенный процесс» используют при организации вспомогательных алгоритмов, оформленных автономно в виде от­дельного модуля, или при обращении к библиотечным подпрограммам.

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

Если же линии соединяют блоки, расположенные на разных страницах, то используется символ межстраничного соединителя, в который вписывают не только номера блоков, но и номера страниц. В изображенном на рис. 1.1 и межстраничном соединителе указано, что вычислительный процесс передается на вход блока 23, 23 будет стоять приведенный на рис. l.lп межстраничный соединитель (информация передана с выхода блока 12, расположенного на странице 6).

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

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

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

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

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

•        В схеме алгоритма все линии от блока «начало» до блока

«конец» не должны иметь разрывов, не помеченных соединителями.

Все линии, указывающие последовательность выполнения

действий, должны быть замкнутыми.

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

• Не допускается передача управления в никуда. «Источник» передачи управления и «получатель» должны быть четко обозначены.