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

Наименование	Обозначение	Функция
Блок начало-конец  (пуск-остановка)		Элемент отображает вход из внешней среды или выход из неё (наиболее частое применение −  начало и конец программы). Внутри фигуры записывается соответствующее  действие.
Блок вычислений (вычислительный блок)		Выполнение одной или  нескольких операций, обработка данных любого вида (изменение значения данных, формы представления, расположения). Внутри фигуры записывают непосредственно  сами операции, например, операции присваивания: a = 10*b + c.
Логический блок (блок условия)		Отображает решение или  функцию переключательного типа с одним входом и двумя или  более альтернативными выходами, из которых только один может быть выбран после вычисления условий, определенных внутри этого элемента. Вход в элемент  обозначается линией, входящей обычно в верхнюю вершину элемента. Если выходов два или три, то обычно каждый выход обозначается линией, выходящей из оставшихся вершин (боковых  и нижней). Если выходов больше трех, то их следует показывать одной линией, выходящей из вершины (чаще нижней) элемента, которая затем разветвляется. Соответствующие результаты вычислений могут записываться рядом с линиями, отображающими эти пути. Примеры  решения: в общем случае − сравнение (три выхода: >, <, =); в программировании − условные операторы if (два выхода: true, false) и case (множество выходов).
Предопределённый  процесс		Символ отображает выполнение процесса, состоящего из одной или  нескольких операций, который определен  в другом месте программы (в подпрограмме, модуле). Внутри символа записывается название процесса и передаваемые в  него данные. Например, в программировании − вызов процедуры или функции.
Данные  (ввод-вывод)		Преобразование данных в  форму, пригодную для обработки (ввод) или отображения результатов  обработки (вывод). Данный символ не определяет носителя данных (для указания типа носителя данных используются специфические  символы).
Граница цикла		Символ состоит из двух частей − соответственно, начало и  конец цикла − операции, выполняемые  внутри цикла, размещаются между  ними. Условия цикла и приращения записываются внутри символа начала или конца цикла − в зависимости  от типа организации цикла. Часто  для изображения на блок-схеме  цикла вместо данного символа  используют символ условия, указывая в  нём решение, а одну из линий выхода замыкают выше в блок-схеме (перед  операциями цикла).
Соединитель		Символ отображает вход в  часть схемы и выход из другой части этой схемы. Используется для  обрыва линии и продолжения её в другом месте (для избежания  излишних пересечений или слишком  длинных линий, а также, если схема  состоит из нескольких страниц). Соответствующие  соединительные символы должны иметь  одинаковое (при том уникальное) обозначение.
Комментарий		Используется для более  подробного описания шага, процесса или  группы процессов. Описание помещается со стороны квадратной скобки и охватывается ей по всей высоте. Пунктирная линия  идет к описываемому элементу, либо группе элементов (при этом группа выделяется замкнутой пунктирной линией). Также  символ комментария следует использовать в тех случаях, когда объём  текста, помещаемого внутри некоего  символа (например, символ процесса, символ данных и др.), превышает размер самого этого символа.

 

 

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

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

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

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

Рисунок 2. Пример блок-схемы алгоритма вычисления факториала числа N.

 

 

2.3 Порядок разработки иерархической схемы реализации алгоритмов

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

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

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

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

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

2. Условная конструкция. Этот  блок включает проверку некоторого  логического условия (P), в зависимости  от которого выполняется либо  один (S1), либо другой (S2) операторы:

P

 

S₁

 

S₂

 

P

 

S

 

3. Блок обобщенного цикла. Этот  блок обеспечивает многократное  повторение выполнения оператора  S пока выполнено логическое условие  P:

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

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

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

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

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

 

 

2.4 Циклический алгоритм

Алгоритмы содержащие команды  повторения, называют  циклическими.  Команды повторения составляют цикл.

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

Существуют три  вида  циклов.

  Это:  цикл  «До»,  цикл  «Пока»,  цикл  «Для...». 

Они все состоят из нескольких этапов. Это :

  1. Подготовка цикла,  в которую входят начальные  присвоения;

  2. Тело цикла - команды  повторения цикла;

  3. Условие - обязательная  часть циклов «До» и «Пока».

3.1 Цикл «До»

Цикл  «До»  это  такой  цикл,  где  тело  цикла  выполняется  перед условием. Его  лучше  использовать  в  той  циклической структуре, где заранее известно число повторений блока условия.

3.2 Цикл «Пока»

Цикл  «Пока»  это  такой  цикл,  где  тело  цикла  выполняется,   пока выполняются некоторые условия .  Его  лучше  использовать  там,  где  сразу

неизвестны начальные  значения цикла.

С помощью циклов «Пока» можно запрограммировать любые  повторяющиеся фрагменты алгоритмов. Но на практике цикл типа «Пока» чаще всего  используется в двух случаях:

1. Число повторений заранее  не известно (например, цикл до  достижения требуемой точности  результата, цикл до первого отрицательного  элемента массива и т.п.). Такой  цикл называется циклом типа  «Пока» с прерыванием.

2. Число повторений заранее  известно, но шаг параметра цикла  не равен 1 (в школьном АЯ) или  1, -1 (в Pascal). Такой цикл называется циклом типа «Пока» без прерывания.

Цикл типа «Пока» с прерыванием

Язык	Пример	Пояснения
Школьный  АЯ	i:=1; Flag:= «Нет» нц пока (i<=N) и (Flag= «Нет»)       если  A[i]<0           то Flag:= «Да»; k:=i           иначе i:=I + 1       все кц	Решается задача: определить номер первого отрицательного  элемента массива A(N). Здесь Flag – «управляющая» переменная литерного типа (можно использовать также логический или целый тип)
Pascal	i:=1; Flag:= False; While (i<=N) and not Flag do If A[i]<0        then begin               Flag:=True; k:=i         end         else i:=i+1;	Здесь Flag – переменная логического типа, принимающая значение True (истина) или False (ложь), and – операция «и» not – операция «не»
Basic	I:=1; FLAG:= 0 WHILE I<=N AND FLAG=0 IF A(I)<0 THEN FLAG=1 : K=I ELSE I=I+1 END IF WEND	Здесь FLAG – переменная целого типа (В некоторых версиях QBasic можно использовать и логический тип, что предпочтительнее)

 

 

 

Цикл типа «Пока» без прерывания

Язык	Пример	Пояснения
Школьный  АЯ	i:=1; S :=0 нц пока i < = N S:=S+A[i] I:=i+2 кц	Вычисляется сумма элементов  массива A(N) с нечетными индексами. Число таких элементов заранее известно. Шаг параметра цикла равен двум
Pascal	i:=1; S :=0; While i <=N do begin S:=S+A[i]; i:=i+2 end;
Basic	Лучше использовать цикл FOR: S=0 FOR I=1 TO N STEP 2     S=S+A(I) NEXT I

 

 

Для организации цикла  типа «Пока» можно также использовать:

• в языке Pascal оператор цикла с постусловием Repeat … until :

Repeat     Повторять тело цикла до

    тело цикла    тех пор, пока не выполнится

until <условие завершения>  условие завершения цикла

 

• в языке Basic операторы цикла DO WHILE … LOOP и DO UNTIL … LOOP (англ. LOOP – виток, петля) :

DO WHILE <условие продолжения> Пока выполняется условие

   тело цикла     продолжение цикла,

LOOP      повторять тело цикла

 

DO UNTIL <условие завершения>  Повторять тело цикла до

   тело цикла     тех пор, пока не выполнится

LOOP      условие завершения цикла

 

3.3 Цикл «Для»

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

Для  А от  Х  до  У  шаг  Z

      Х- начальное  значение

      У- конечное  значение

     Z- шаг или  приращение

А- переменная, которой присваивается  значения начиная с Х до У с  шагом

      Z.

Циклы типа «Для» применяются, когда число повторений цикла  известно к  началу его выполнения.

Язык	Пример	Величина шага
Школьный  АЯ	нц для I от 1 до N             тело цикла кц	Всегда 1
Pascal	For i:=1 to N do              тело цикла	1
	For i:=N downto 1 do              тело цикла	-1
Basic	FOR I=1 TO N STEP H              тело цикла NEXT I	Шаг Н произвольный (по умолчанию равен  1)

 

Глава III. Практическая часть

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Заключение

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