Методические указания по выполнению работы

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

1. Линейные;

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

3. Циклические.

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

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

Структура такого алгоритма показана на рисунке 8.1.

 

 

Рисунок 8.1. Линейный алгоритм

 

Рассмотрим составление схем линейных алгоритмов на конкретных примерах.

Пример 1.Даны переменные А и В. Требуется обменять их значения, т.е. переменная А должна получить значение В, а В - значение А.

Решение.

1. Исходные данные: А, В. Вспомогательная переменная DOP. Результат: А, В.

2. Метод решения задачи: В ЭВМ каждая величина хранится в отдельном участке памяти (переменной). Поэтому задача заключается в том, чтобы поменять местами содержимое двух ячеек.

Решение задачи распадается на три этапа. Соответствующие им блоки и порядок их выполнения изображены на схеме алгоритма (рисунок 8.2).

 

 

Рисунок 8.2. Алгоритм решения примера 1

 

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

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

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

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

Пусть, например, В - проверяемое условие, а s1, s2 - некоторые выполняемые инструкции (действия). Тогда:

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

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

иначе

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

Блок-схема данного алгоритма представлена на рисунке 8.3.

 

 

Рисунок 8.3. Блок-схема ветвящегося алгоритма

 

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

Пример 2. Найти максимальное из двух чисел X,Z: Y = max{X,Z}.

Решение.

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

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

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

 

 

Рисунок 8.4. Алгоритм решения примера 2

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

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

Примеры циклических алгоритмов может служить алгоритм покраски забора.

Действительно, рассмотрим этот алгоритм в словесно-формульном виде:

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

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

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

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

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

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

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

Обозначим:

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

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

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

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

Общий вид структуры цикла с параметром будет:

 

 

2. Инструкция "цикл с предусловием" (цикл-"пока"):

Обозначим:

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

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

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

 

 

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

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

 

Пример 3. Дан массив А, состоящий из 20 - ти чисел. Найти сумму элементов меньше Б.

Решение:

Решение.

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

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

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

 

 

 

 

S = 0

 

 

S = S +A(I)     Задание 1

 

 

 

 

 

 

Рисунок 8.5. Алгоритм решения примера 3