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

Существуют несколько способов описания алгоритма: словесное, псевдокод, блок-схема, программа.

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

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

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

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

Основные конструкции, использующиеся для построения блок – схем.

- начало/конец алгоритма

 

<Действие>

- процесс, предназначенный для описания отдельных

действий

 

 

ввод/вывод с неопределенного носителя

 

 

Нет Да - проверка условия

 

 

 

 

- - предопределенный процесс, предназначенный для

- обращения к подпрограмме.

Лекция 5.2. Блок-схемы алгоритма

Алгоритмы решения задач

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

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

 

Выполнить B

Выполнить А

Вход Выход

 

 

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

Пример 5.2.1.

Опишем алгоритм сложения двух чисел на псевдокоде и в виде блок-схемы (рис. 5.2.2.).

1. Псевдокод:

2. Ввод двух чисел a, b

3. Вычисляем сумму S = a + b

4. Вывод S

5. Конец.

S= a + b

 

 

 

Рис. 5.2.2. Блок - схема к примеру 5.2.1.

 

Ветвление (развилка) – это структура, обеспечивающая выбор между двумя альтернативами. Выполняется проверка условия, а затем выбирается один из путей (рис. 5.2.3). Если условие имеет значение «Истина», то выполняется «Действие А». Если условие имеет значение «Ложь», выполняется «Действие В». Эта структура называется, также «Если – ТО – ИНАЧЕ» или «развилка». Каждый путь (ТО или ИНАЧЕ) ведет к общей точке слияния, так что выполнение алгоритма продолжается независимо от того, какой путь был выбран. Может оказаться, что для одного из результатов проверки ничего выполнять не надо. В этом случае можно применить только один обрабатывающий блок (рис. 5.2.4).

 

 

Вход

Ложь (НЕТ) Истина (ДА)

 

Выход

Рис. 5.2.3. Полное ветвление

 

Вход

 

ДА НЕТ

 

	Действие А

Рис. 5.2.4. Структура «непол-

ное ветвление»

Выход

 

 

Такая структура называется «неполным ветвлением» или «неполной развилкой».

Пример 5.2.2.

Вывести значение наибольшего числа из двух чисел (рис. 5.2.5).

Псевдокод:

1. Ввод двух чисел a, b

2. ЕСЛИ a>b, ТО «выводим a»,

ИНАЧЕ «выводим b»

3.

Max= b

Max= a

Конец.

 

НЕТ ДА

 

Рис. 5.2.5. Блок – схема к примеру 5.2.2.

 

 

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

Цикл с предусловием («Пока») (рис. 5.2.6).

 

Тело цикла

Истина Выход

 

Ложь

 

Рис. 5.2.6. Структура цикла «Пока».

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

Пример 5.2.3.

Вычислить сумму 100 чисел (рис. 5.2.7).

Псевдокод:

1. НАЧ

2. I =1; S = 0

3. ПОКА i<=100 делать

НЦ

4. Ввести a_i

5. S = S + a_i

6. i = i + 1

КЦ

7. Вывод S

8.

i=1; S=0

Конец.

НЕТ

 

 

ДА

 

 

 

 

 

Рис. 5.2.7. Блок – схема к примеру 5.2.3 с циклом «Пока»

Цикл с постусловием («До»).

Тело цикла

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

 

 

Вход Истина

 

Ложь Выход

 

 

Рис. 5.2.8. Структура «цикла с постусловием».

 

Пример 5.2.4.

Вывести максимальное значение из 100 натуральных чисел (рис. 5.2.9).

Псевдокод:

1. Начало

_2.

Max=a1; i=2

max = ai

i = i + 1

Ввести a₁

3. max = a₁; i = 2

4. НЦ

a. Ввести a_i

b. ЕСЛИ max < a_i ТО max = a_i

c. i = i + 1

5. ДО I>100;

6. КЦ

7. Вывести max.

8. Конец.

 

Истина

 

 

 

 

 

Ложь Истина

 

 

 

Рис. 5.2.9. Блок – схема к примеру 5.2.4. с циклом «До»

Базовые алгоритмические структуры можно комбинировать одну с другой – как путем организации их следования, так и путем создания суперпозиций (вложений одной структуры в другую). Используя описанные структуры, можно полностью исключить использование каких-либо еще операторов условного и безусловного перехода, что является важным признаком структурного программирования. Приведем несколько примеров (рис. 5.2.10, 5.2.11, 5.2.12, 5.2.13).

 

 

 

 

-

+

- +

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

- +

-

+

Рис. 5.2.11. Алгоритм типа «цикл, с предусловием, вложенный в неполную развилку»

- +

Рис. 5.2.12. Алгоритм типа «неполная развилка, вложенная в пол-

- + ную развилку».

Вопросы для самоконтроля

1. Дайте определение алгоритма и поясните его.

2. Какие формы представления алгоритма вы знаете?

3. В чем особенности графического представления алгоритма?

4. Назовите основные (базовые) алгоритмические структуры?

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