Алгоритмы ветвящейся структуры

⇐ ПредыдущаяСтр 3 из 3

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

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

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

В частном случае может отсутствовать один из блоков — «Действие 1» или «Действие 2».

Пусть, например, В — проверяемое условие, a s 1, s 2 — некоторые выполняемые инструкции (действия). Тогда:

если условие В выполняется (истинно), то

выбрать для исполнения s1, иначе

выбрать для исполнения s2.

Запишем ветвящийся алгоритм на псевдокоде и графически:

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

Пример 2

Вычислить значение У по одной из формул:

Решение

Исходные данные: х.

Результат: Y .

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

Алгоритм

Переменные х, у: вещественные;

Начало

Ввод (х);

Если х < 10, то у : = х + 2;

иначе у : = х - 2;

Вывод (у); Конец.

К задачам рассмотренного выше вида очень часто сводятся вполне реальные задачи, например расчет стипендии, если известно среднее арифметическое оценок студента за месяц. Стипендия отличника равна 100 руб., хорошиста (5 < SJR<4) — 80 руб., остальные стипендию не получают.

Математическая формула:

т. е. мы пришли к задаче вычисления функции по разветвляющемуся алгоритму.

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

Пример 3

Найти максимальное из двух чисел X , Z . Решение

Исходные данные: X , Z .

Результат: Мах.

Метод решения задачи: нужно сравнить два числа и сделать вывод. Блок-схема алгоритма решения этой задачи выглядит следующим образом:

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

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

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

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

Шаг I. Подготовить исходные данные (забор, краску, кисть).

Шаг II. Подойти к забору.

Шаг III. Обмакнуть кисть в краску.

Шаг IV. Нанести краску кистью на поверхность забора.

Шаг V. Если забор еще не весь окрашен, то повторить алгоритм, начиная с пункта (шаг III).

Существует несколько видов циклических инструкций, с помощью которых можно организовать циклы:

1. Инструкция «Цикл с параметром» (цикл с заданным количеством повторений).

Обозначим:

х — параметр цикла (является счетчиком количества повторений);

a , b — соответственно начальные и конечные значения параметра цикла;

h — шаг, с которым изменяется параметр цикла;

S — оператор (инструкция), повторяемый в цикле.

Общий вид структуры цикла с параметром будет для х : = а до b с шагом h повторять S

2. Инструкция «Цикл с предусловием» (цикл — «пока»).

Обозначим:

В — некоторое проверяемое логическое условие;

S — оператор (инструкция), повторяемый в цикле.

Тогда инструкция в псевдокоде примет вид

Блок-схема такого цикла имеет вид

3. Инструкция «Цикл с постусловием" (цикл — «до»):

Блок-схема такого цикла имеет вид:

Резюме

Все вышесказанное об основных типах алгоритмов можно обобщить в виде следующей схемы:

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

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

A. Линейные;

Б. Разветвляющиеся;

B. Структурные;
Г. Циклические.

Некоторые из этих понятий не относятся к основным группам алгоритмов. Укажите, какие именно.

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

Верно ли данное высказывание? - ДА/НЕТ

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

Верно ли данное высказывание? - ДА/НЕТ

4. Циклом называется...

A. - Этап решения задачи, выполняемый строго последовательно;

B. - Последовательность действий, выполняемых многократно, каждый раз при новых значениях параметров;