Курс лекций (стр. 11 из 24)

2. Определенность (детерминированность). Каждое правило алгоритма должно быть четким и однозначным. Отсюда выполнение алгоритма носит механический характер.

3. Результативность (конечность). Алгоритм должен приводить к решению задачи за конечное число шагов.

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

Понятия алгоритма и программы разграничены не очень четко. Обычно программой называют окончательный вариант алгоритма, ориентированный на конкретного исполнителя – вычислительную машину.

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

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

Обработка (вычисление). Основная операция, при помощи которой осуществляется обработка данных – это операция присваивания. При ее выполнении переменной присваиваивается значение. Переменная обозначается с помощью имени. Имя – обычно некоторая комбинация букв и цифр, выбираемая пользователем с соответствии с установленными правилами. Именами обозначаются также различные функции (sin, sqrt, sqr,…), которые имеют в языках программирования закрепленные за ними имена. Имя обозначает симвоический адрес той ячейки памяти, в которой записано числовое значение соответствующей переменной или функции после ее вычисления. Числа, используемые, например, в операциях присваивания для задания значения переменных, называются константами. Константы обозначают сами числа, а не ячейки памяти (хотя бывают поименнованные константы).

Примеры. К = 1 – в ячейку памяти с символическим адресом К помещается 1 (переменной К присваивается значение 1); L = K – в ячейку памяти с символическим адресом L пресылается содержимое ячейки с адресом К, при этом значение К не изменяется; К = К + 1 – к содержимому ячейки К прибавляется 1, результат помещается в туже ячейку К, при этом старое значение К пропадает (стирается); Y = sin(X) – вычисляется sin угла, величина которго находится в ячейке Х, и результат помещается в ячейку Y.

Замечания. 1. Перед выполнением присваивания старое значение стирается. 2. Переменным, которые располагаются в правой части оператора присваивания (в языках программирования оператор – конструкция, предписывающая выполнение какой-либо операции), должны быть присвоены определенные значения предшествующими операторами. 3. Если переменной не присвоено значение, то ее значение не определено.

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

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

Начало и конец вычислительного процесса.

Подпрограмма. Группа операторов, которая решает логически самостоятельную часть задачи, может объединяться в подпрограмму.

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

Точки связи или соединители. Ими пользуются в том случае, если соединительная линия не может быть доведена до следующего блока или до точки объединения. Тогда линия оканчивается соединителем, в котором записывается любой символ. Продолжением этой линии считается вторая точка связи, помеченная тем же символом.

Комментарии можно записывать около любого блока.

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

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

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

Доказано (Бойм и Якопини (Bohm, Jacopini, 1966), Милс (Mills, 1972)), что программу для любой логической задачи можно составить из структур следование, разветвление и повторение (цикл) (основные структуры). Главная идея этого доказательства сводится к тому, что необходимо преобразовать каждую часть программы в одну из трех основных структур или их комбинацию так, чтобы неструктурированная часть программы уменьшилась. После достаточного числа таких преобразований оставшаяся неструктурированной часть либо исчезнет, либо станет ненужной.

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

Рассмотрим основные конструкции, включающие следование, два разновидности цикла и три разновидности разветвления.

Следование (рис.6а) – это последовательное размещение блоков и групп блоков.

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

Цикл «До» (рис.6б) применяется при необходимости выполнить какие-либо вычисления несколько раз до выполнения условия (блок 3). Особенность в том, что он выполняется хотя бы один раз, т.к. первая проверка условия выхода из цикла происходит после того, как тело цикла выполнено. Тело цикла (блок 2) – та последовательность действия, которая выполняется многократно (в цикле). Начальные присвоения (блок 1) – задание начальных значений тем переменным, которые используются в теле цикла. Цикл «Пока» (рис.6в) отличается от цикла «До» тем, что проверка условия (блок 3) производится до выполнения тела цикла (блок 2). В этом случае, если при первой проверке условия оно выполняется, то тело цикла не выполняется ни разу. Иначе такой цикл называется циклом по условию.

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

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

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

Множественный выбор (рис.6е) является обобщением разветвления, когда в зависимости от значения переменной (I, в данном случае) выполняется одно из нескольких действий. Например, при I = 1 действие, обозначенное блоком S₁, и т.д.

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

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