Урок на тему "Линейные и разветвленные алгоритмы" (СПО, 090203 "Программирование в компьютерных системах", дисциплина "Основы алгоритмизации и программирования"

Урок «Линейные и разветвленные алгоритмы»

Для студентов СПО специальности 09.02.03 «Программирование в компьютерных системах», изучающих дисциплину «Основы алгоритмизации и программирования».

Рассмотрим основные виды алгоритмов.

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

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

На рис.1 показан шаблон блок-схемы линейного алгоритма. Блок-схема линейного алгоритма содержит только блоки «Процесс»  и не использует блоки «Решение» или блоки цикла.

Рис.1 Блок-схема линейного алгоритма.                                                                                                                                                                                                                                         Разветвленный алгоритм:                                                                                                                                                          Циклический алгоритм:

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

Пример 1.

Даны два значения х и у. Требуется обменять  их местами, т.е. новое значение х должно стать равно старому значению у,  и наоборот.

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

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

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

Решение задачи распадается на три шага:

1)      Ввод исходных данных;

2)      Обмен местами:

-        Создание копии значения х в переменной copy;

-        Замена х на значение у;

-        Замена у на значение х, взятое из копии;

3)      Вывод результатов.

Алгоритм решения является линейным, так как не содержит условий и повторений.

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

1)     

Рис.2 Блок-схема алгоритма обмена местами двух значений.                                                                                                                                                                                                      Разветвленный алгоритм:                                                                                                                                                          Циклический алгоритм:

   Пример 2.

Дано значение радиуса круга R. Требуется вычислить площадь круга, используя формулу S=πR².

Решение.

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

Решение задачи распадается на три шага:

1)      Ввод исходных данных;

2)      Вычисление площади;

3)      Вывод результатов.

В таблице 1 для сравнения представлены два способа описания алгоритма: блок-схема и псевдокод.

Таблица 1. Алгоритм вычисления площади круга

Псевдокод	Блок-схема
алг ПлощадьКруга( ) нач Ввод R; Pi=3.14; S= Pi*R*R; Вывод S; кон

Разветвленным называется алгоритм, который имеет  несколько вариантов выполнения. Вариант выполнения называется ветвью алгоритма.

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

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

Различают три варианта разветвленной алгоритмической  структуры:

1)      Полное Ветвление;

2)      Неполное Ветвление;

3)      Выбор-Иначе.

Порядок выполнения Полного и Неполного Ветвления:

1)      Проверка условия, результат проверки значения true или false;

2)      Если true, то выполняется ветвь Да; 

3)      Если false, то выполняется ветвь Нет;

4)       В случае, когда Неполное ветвление, ветвь Нет не содержит никаких действий.

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

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

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

Таблица 2. Варианты разветвленной структуры

Название конструкции	Псевдокод	Блок-схема
Полное ветвление	Если условие То  действие 1; Иначе действие 2; Все;
Неполное ветвление	Если условие То  действие 1; Все;
Выбор - иначе	Выбор При выражение= значение_1: действие 1; При выражение= значение_2: действие 2; ….. При выражение= значение_n: действие n; Иначе действие n+1; все

Пример 3.

Даны два действительных числа х и у. Найти максимальное из этих чисел.

Решение.

Алгоритм решения задачи состоит в сравнении х и у. Если больше х, то х будет максимальным, если больше у, то максимум будет равен у. То есть, решение будет зависеть от условия, что больше, х или у. Наличие условия и отсутствие повторений каких-либо действий  определяет  в данном случае тип алгоритма – разветвленный.

Решение задачи распадается на следующие шаги:

1)      Ввод исходных данных;

2)      Проверка условия (х>у);

3)      Если условие истинно, то в переменную max записывается х, иначе у;

4)      Вывод результата max.

В таблице 3 для сравнения представлены два способа описания алгоритма: блок-схема и псевдокод.

Таблица 3. Алгоритм нахождения максимального их двух чисел

Псевдокод	Блок-схема
алг Максимум( ) нач Ввод х, у; Если (х>y) То  max=x; Иначе max=y; Все; Вывод max; кон

Пример 4.

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

Решение.

Алгоритм решения задачи состоит в вычислении у по разным формулам,  в зависимости от аргумента х. Если аргумент больше нуля, то у=cos(x). В противном случае, возможны два варианта: либо x<0, либо x=0. Поэтому, необходимо проверить хотя бы одно из этих условий, например  x<0. Таким образом, в данном случае тип алгоритма – разветвленный с проверкой двух условий. Чтобы алгоритм был более компактным, удобнее сначала проверить вырожденный случай (х=0) и вывести сообщение об ошибке, затем проверить одно из заданных условий. Такая конструкция называется вложенные условия, так как  в ветвь Иначе первого условия вложено другое условие.

Решение задачи распадается на следующие шаги:

1)      Ввод аргумента функции x;

2)      Проверка первого условия (х=0);

3)      Если условие истинно, то выводим сообщение об ошибке;

4)      Иначе Проверка второго условия (х>0);

5)      Если второе условие истинно, то вычисляем у по формуле y=cos(x);

6)      Если второе условие ложно, то вычисляем у по формуле y=sin(x);

7)      Вывод результата y.

В таблице 4 для сравнения представлены два способа описания алгоритма: блок-схема и псевдокод.

Таблица 4. Алгоритм вычисления значения функции

Псевдокод	Блок-схема
алг Функция( ) нач Ввод х; Если (х=0) То  Вывод «х не определено»; Иначе   Если (х>0) То y= cos(x); Иначе y=sin(x); Все; Вывод y; Все; кон

Пример 5.

Дано действительное число х и натуральное у (целое, большее нуля). Также пользователь задает одну из арифметических операций в виде знака: ‘+’, ’-‘, ’*’, ’/’. Вычислить результат заданной арифметической операции над числами х и у. 

Решение.

Алгоритм решения задачи состоит в проверке того, какая  арифметическая операция задана. Для этого надо сравнить заданный пользователем знак операции поочередно со всеми известными знаками: ‘+’, ’-‘, ’*’, ’/’.  Это проверка нескольких альтернативных условий, так как истинным может быть только одно. Проверка альтернативных условий реализуется с помощью алгоритмической конструкции Выбор – иначе, при этом, ветвь Иначе может и отсутствовать. После попадания на одну из ветвей Выбора, другие условия уже не проверяются, мы как бы «проваливаемся» на оператор, следующий за Выбором. Таким образом, в данном случае тип алгоритма – разветвленный, с проверкой нескольких условий.

Решение задачи распадается на следующие шаги:

1)      Ввод  чисел x и у;

2)      Ввод знака операции с;

3)      Вычисляем выражение с;

4)      При равенстве с=‘+’, вычисляем сумму rez=x+y; выводим результат;

5)      При равенстве с=‘-’, вычисляем разность rez=x-y; выводим результат;

6)      При равенстве с=‘*’, вычисляем произведение rez=x*y; выводим результат;

7)      При равенстве с=‘/’, вычисляем частное rez=x/y; выводим результат;

8)      Иначе выводим сообщение об ошибке ввода;

В таблице 5 для сравнения представлены два способа описания алгоритма: блок-схема и псевдокод.

Таблица 5. Алгоритм вычисления результата арифметической операции

Псевдокод	Блок-схема
алг Арифметическая_операция( ) нач Ввод х,у; Ввод с; Выбор При с=‘+’: rez=x+y; Вывод rez ; При с=‘-’: rez=x-y; Вывод rez ; При с=‘*’: rez=x*y; Вывод rez ; При с=‘/’: rez=x/y; Вывод rez ; Иначе Вывод «Ошибка»; все кон

Контрольные вопросы для самоанализа материала.

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

-        Линейный алгоритм

-        Разветвленный алгоритм

-        Блок-схема

-        Блок «Процесс»

-        Ветвь алгоритма

-        Блок «Решение»

-        Алгоритмическая конструкция «Полное ветвление»

-        Алгоритмическая конструкция «Неполное ветвление»

-        Алгоритмическая конструкция «Выбор - Иначе»

2.              Сравните линейный и разветвленный алгоритмы. Основания для сравнения выберите сами, например: используемые алгоритмические конструкции, количество ветвей обработки, область применения и другие. Наиболее принципиальные позиции зафиксируйте в таблице.

Основания для сравнения	Виды алгоритмов

3.              Проанализируйте блок-схему предложенного алгоритма (рис. 3). Перечислите используемые алгоритмические конструкции и укажите их назначение. Определите результат выполнения алгоритма при различных исходных данных.  Составьте краткую аннотацию к алгоритму (по пунктам):

-        Назначение алгоритма;

-        Краткая характеристика (основная идея);

-        Названия алгоритмических конструкций и цель их использования;

-        Вид алгоритма;

-        Диапазон входных данных;

-        Результат выполнения алгоритма при N=6, N=55, N=56;

-        Область применения.

                                         Рис. 3 Блок-схема алгоритма