Свойства, характерные для интуитивного понятия алгоритма

Понятие алгоритма

Решение задачи при помощи ЭВМ начинается с составления алгоритма. Что же такое алгоритм?

Происхождение термина «алгоритм» связывают с именем великого математика Мухаммеда аль-Хорезми (763–850 гг.), который разработал правила выполнения четырех арифметических действий.

Согласно ГОСТ 19781-74:

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

То есть алгоритм – это четкое указание исполнителю алгоритма выполнить определенную последовательность действий для решения поставленной задачи и получения результата.

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

Основные особенности алгоритмов:

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

Способы записи алгоритмов

Разработанный алгоритм может быть представлен несколькими способами:

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

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

Графическая форма. Алгоритмы представляются в виде блок-схем. Существуют специальные стандарты для построения блок-схем, где определяются графические изображения блоков. Команды алгоритмов записываются внутри блоков на обычном языке или с использованием математических формул. Блоки соединяются по определенным правилам линиями связи, которые показывают порядок выполнения команд.

На языке программирования. Если алгоритм разработан для решения задачи на ЭВМ, то для того, чтобы он мог выполниться исполнителем – ЭВМ, его необходимо записать на языке, понятном этому исполнителю. Для этого разработано множество языков программирования для решения задач разных классов. Запись алгоритма на языке программирования называется программой.

Представление алгоритмов в виде блок-схем

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

Существует Государственный стандарт, определяющий правила создания блок-схем. Конфигурация блоков, а также порядок графического оформления блок-схем регламентированы ГОСТ 19.701-90 "Схемы алгоритмов и программ". В табл. 2.1 приведены обозначения некоторых элементов, которых будет вполне достаточно для изображения алгоритмов при выполнении студенческих работ.

Правила составления блок-схем:

Каждая блок-схема должна иметь блок «Начало» и один блок «Конец».
«Начало» должно быть соединено с блоком «Конец» линиями потока по каждой из имеющихся на блок-схеме ветвей.
В блок-схеме не должно быть блоков, кроме блока «Конец», из которых не выходит линия потока, равно как и блоков, из которых управление передается «в никуда».
Блоки должны быть пронумерованы. Нумерация блоков осуществляется сверху вниз и слева направо, номер блока ставится вверху слева, в разрыве его начертания.
Блоки связываются между собой линиями потока, определяющими последовательность выполнения блоков. Линии потоков должны идти параллельно границам листа. Если линии идут справа налево или снизу вверх, то стрелки в конце линии обязательны, в противном случае их можно не ставить.
По отношению к блокам линии могут быть входящими и выходящими. Одна и та же линия потока является выходящей для одного блока и входящей для другого.
От блока «Начало» в отличие от всех остальных блоков линия потока только выходит, так как этот блок – первый в блок-схеме.
Блок «Конец» имеет только вход, так как это последний блок в блок-схеме.
Для простоты чтения желательно, чтобы линия потока входила в блок «Процесс» сверху, а выходила снизу.
Чтобы не загромождать блок-схему сложными пересекающимися линиями, линии потока можно разрывать. При этом в месте разрыва ставятся соединители, внутри которых указываются номера соединяемых блоков. В блок-схеме не должно быть разрывов, не помеченных соединителями.
Чтобы не загромождать блок, можно информацию о данных, об обозначениях переменных и т.п. размещать в комментарияхк блоку.

Название блока

Обозначение блока

Назначение блока

Терминатор

Начало/Конец программы или подпрограммы

Процесс

Обработка данных (вычислительное действие или последовательность вычислительных действий)

Решение

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

Подготовка

Заголовок счетного цикла

Предопределенный процесс

Обращение к процедуре

Данные

Ввод/Вывод данных

Соединитель		Маркировка разрыва линии потока
Комментарий		Используется для размещения пояснений к действиям
Горизонтальные и вертикальные потоки		Линии связей между блоками, направление потоков

Типы алгоритмов

Тип алгоритма определяется характером решаемой в соответствии с его командами задачи. Различают три типа алгоритмов: линейные, разветвляющиеся, циклические.

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

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

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

Каждое из возможных направлений дальнейших действийназывается ветвью.

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

Различают несколько видов разветвляющихся алгоритмов.

1. «Обход» – такое разветвление, когда одна из ветвей не содержит ни одного оператора, т.е. как бы обходит несколько действий другой ветви.

2. «Разветвление» – такой тип разветвления, когда в каждой из ветвей содержится некоторый набор действий.

3. «Множественный выбор» – особый тип разветвления, когда каждая из нескольких ветвей содержит некоторый набор действий. Выбор направления зависит от значения некоторого выражения.

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

Различают:

циклы с известным числом повторений (или со счетчиком);
циклы с неизвестным числом повторений (циклы с предусловием и циклы с постусловием).

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

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

Циклы со счетчиком

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

Блок-схема циклического алгоритма в этом случае выглядит так:

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

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

При использовании цикла со счетчиком необходимо соблюдать некоторые требования:

в теле цикла нельзя принудительно изменять значение счетчика цикла;
не разрешается передавать управление оператору тела цикла извне, т.е. вход в цикл допускается только через начало цикла.

Циклы с предусловием

Циклы с предусловием чаще всего используют тогда, когда неизвестно число повторений цикла. Циклы с предусловием – это такие циклы, в которых до начала выполнения тела цикла проверяется условие выполнения следующего шага цикла. Если значение этого условия истинно (т.е. условие выполняется), то выполняется тело цикла. В теле цикла должно изменяться значение по крайней мере одной переменной, которая влияет на значение условия (иначе произойдет «зацикливание»). Далее опять проверяется условие выполнения цикла, и если значение условия ложно, то осуществляется выход из цикла.

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

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

На блок-схеме такой цикл реализуется следующей конструкцией:

Циклы с постусловием

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

На блок-схеме этот тип цикла изображается следующим образом:

Сложные циклы

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

При этом циклы, охватывающие другие циклы, называются внешними, а циклы, входящие во внешние, – внутренними циклами.

На каждом шаге внешнего цикла внутренний цикл «прокручивается» полностью.

Контрольные вопросы

1. Перечислите этапы создания программного продукта.

2. Для чего выполняется структуризация программ?

3. Что такое модуль, какие виды модулей вы знаете?

4. Назовите и охарактеризуйте методы структурного проектирования.

5. На чем основывается объектно-ориентированный подход?

6. Что такое алгоритм?

7. Перечислите основные особенности алгоритмов.

8. Назовите способы представления алгоритмов.

9. Что такое блок-схема, каковы правила составления блок-схем?

10. Какой алгоритм называется линейным?

11. Перечислите виды разветвляющихся алгоритмов.

12. Какие виды циклов вы знаете?

13. Объясните работу циклов со счетчиком.

14. В чем отличие циклов с предусловием от циклов с постусловием?

15. Что такое сложные циклы?

Свойства, характерные для интуитивного понятия алгоритма

1. Дискретность. Это свойство заключается в следующем: в начальный момент задается исходная система величин, а в каждый следующий момент система величин получается из предыдущей системы величин по определенному закону (программе).

2. Детерминированность. Система величин, получаемых в любой, отличный от начального, момент времени, однозначно определяется системой величин в предшествующие моменты времени.

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

4. Эффективность (результативность). Каждый шаг работы алгоритма должен заканчиваться результатом.

5. Массовость алгоритма. Начальная система величин может выбираться из некоторого бесконечного счетного множества Х.

6. Конструктивность. Объекты из Х, над которым работает алгоритм, должны быть конструктивными.

Конструктивный объект– тот, который может быть набран весь целиком и представлен для рассмотрения.

Примерами конструктивных объектов являются булевы функции, формулы алгебры логики, натуральные и рациональные числа, матрицы с натуральными или рациональными элементами, многочлены от неизвестных с рациональными коэффициентами.

Неконструктивными объектами являются, например, любые действительные числа, представления которых в десятичной записи a₀ a₁…a_n… ни для какого n из натуральных чисел не может быть целиком представлено для рассмотрения. Числа не являются конструктивными объектами.

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

Часто алгоритмическим процессам приписывают ряд свойств с их меньшим количеством и с другим акцентом требований:

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

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

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

Дата добавления: 2018-11-24; просмотров: 389; Мы поможем в написании вашей работы!

Поделиться с друзьями:

12 Следующая ⇒

Мы поможем в написании ваших работ!