Ученики на Учителя.com


Конспект урока "Алгоритмические схемы: линейный алгоритм, алгоритм с ветвлением" 6 класс

Тема: Алгоритмические схемы: линейный алгоритм, алгоритм с
ветвлением
Теоретический материал
Вначале введем условные обозначения графического языка блок-схем
(Таблица 1).
Таблица 1. Условные обозначения блок-схем
Условное
графическое
обозначение
Название
Комментарий
Стрелка
Означает, к
исполнению какого
действия следует
перейти. С помощью
стрелки обозначают
последовательность
исполнения команд
Начало
Точка блок-схемы, с
которой начинается
исполнение алгоритма
Ввод
или
Вывод
Блок, означающий,
что в этом месте
алгоритма
необходимо
произвести ввод или
вывод данных
Простое
действие
(в данном
случае –
присваивание)
Один элементарный
шаг алгоритма.
Присваивание
значения выражения
переменной (в данном
случае переменной х
присвоено значение 1)
Условие
Исполнение
предполагает
вычисление условия –
логического
выражения. Если
условие истинно
(Истина, True), то
необходимо перейти к
Условное
графическое
обозначение
Название
Комментарий
действию по стрелке
помеченной T, если
условие ложно – то по
стрелке F (Ложь,False)
Модификация
(цикл со
счетчиком)
Повторение
исполнения тела
цикла для каждого из
последовательных
значений
целочисленного
счетчика i от 1 до n.
Конец
Точка блок-схемы,
дойдя до которой
прекращается процесс
исполнения
алгоритма.
Выделяют три вида алгоритмических схем, с помощью которых можно
представить (сконструировать) любой алгоритм.
a. Линейный алгоритм представляет собой последовательность шагов
(действий) без ветвлений и возвратов. Последовательность исполнения
шагов такого алгоритма полностью совпадает с его структурой.
b. Алгоритм с ветвлением. В таком алгоритме исполнение тех либо иных
действий зависит от истинности некоторого условия (логического
выражения).
c. Циклический алгоритм. Алгоритм, в котором некоторая
последовательность шагов (команд), исполняется многократно.
Исполняемые многократно шаги называются телом цикла. Количество
повторений может оказаться равным 0 (то есть тело цикла ни разу не
исполнилось), 1 (однократное исполнение) или быть больше (многократное
исполнение).
Указанные виды алгоритмических схем можно проиллюстрировать
следующими рисунками
[1]
(Таблица 2). Стрелки на рисунках обозначают
направление возможного движения по «коридору».
Таблица 2. Пояснение смысла алгоритмических схем
Линейный
Ветвление
Цикл
Подробнее о применении указанных алгоритмических схем будет
рассмотрено в следующих разделах.
Линейные алгоритмы
Линейный алгоритм представляет собой простую последовательность
шагов, которые исполняются в том порядке, в котором они перечислены в
алгоритме (Рисунок 1). В линейном алгоритме не может быть ветвлений и
возвратов.
Рассмотрим несколько примеров задач на составление линейных алгоритмов.
Пример 1. Составить блок-схему алгоритма, решающего следующую
задачу. Даны три вещественных положительных числа a, b и c. Найти
площадь треугольника, стороны которого равны a, b и c.
Для нахождения площади треугольника по трем его известным сторонам
воспользуемся формулой Герона:
,
где – полупериметр треугольника, равный
.
Зная последовательность вычислений из школьного курса математики,
легко составить алгоритм (Рисунок 2).
Задача решена. Сделаем два замечания. Первое: в отличие от математики,
где приводимые формулы декларируют некоторые факты, соотношения и
порядок указания которых не так важен (или важен только с точки зрения
логичности изложения), в алгоритмических схемах важна в первую очередь
правильная последовательность действий (формул), которая и определяет
порядок выполнения шагов. Например, если в приведенной блок-схеме
переставить местами шаги, вычисляющие S и p, то алгоритм не будет
правильным, так как до вычисления S
необходимо предварительно вычислить p.
Второе замечание. В решении этой задачи никак не рассматривается
вопрос существования треугольника, площадь которого вычисляется. То есть
мы предполагаем, что входные данные должны быть корректны. В данном
случае должны выполняться условия существования
треугольника: . Алгоритм не может быть успешно
исполненным, если эти неравенства не выполняются. Кстати, почему?
Пример 2. Составить блок-схему решения следующей задачи. Даны
значения двух действительных переменных a и b. Обменять местами их
значения, то есть добиться, чтобы a получила значение, которое
изначально имела переменная b, а b – получила бы значение a.
Если первым же присваиванием алгоритма мы переменной a присвоим b,
то сразу же потеряем исходное значение a. Поэтому воспользуемся для
временного хранения исходного значения переменной a дополнительной
переменной d. Блок-схема алгоритма приведена ниже (Рисунок 3).
Пример 3. Составить блок-схему решения следующей задачи. Даны
значения двух действительных переменных a и b. Обменять местами их
значения без использования дополнительных переменных.
В предыдущем примере решалась та же задача, но сейчас запрещается
использовать какие-либо переменные, кроме самих a и b. Казалось бы, это
невозможно, однако, можно найти и такое решение, причем не одно! Блок-
схема решения – на рисунке (Рисунок 4).
Упражнение 1. Составить блок-схему решения следующей задачи. Даны
значения двух действительных переменных a и b. Обменять местами их
значения, при этом нельзя использовать никаких дополнительных
переменных.
Упражнение 2. Составить блок-схему решения следующей задачи. Даны
значения трех действительных переменных a, b и c. Обменять местами их
значения так, чтобы a получила бы значение b, b получила значение c, а
переменная c получила исходное значение a.
Алгоритмы с ветвлением
При создании алгоритмов часто возникает необходимость исполнение тех
или иных действий поставить в зависимость от некоторого условия. Такая
возможность называется ветвлением. Блок-схема ветвления приведена на
рисунке 5.
Последовательность исполнения ветвления такова: вначале вычисляется
значение условия – логического выражения. Затем, если значение условия
истинно, то исполняются действия S1 (мы будем их всегда размещать на
левой ветви ветвления и помечать эту ветвь буквой T); если же значение
условия ложно, то исполняются действия S2 (такие действия будем
располагать на правой ветви и помечать её буквой F).
Заметим, что при исполнении ветвления будет исполнена либо
ветвь T (действия S1, слева), либо ветвь F (действия S2, справа).
Одновременно пройти по обеим ветвям или не пройти ни по одной нельзя.
Иногда одна из ветвей алгоритма с ветвлением отсутствует, то есть, нет
действий либо S1, либо S2. Этот случай называют неполным ветвлением.
Пример 4. Составить блок-схему решения следующей задачи. Даны
значения двух действительных переменных a и b. Найти наибольшее
значение из a и b.
Составим блок-схему алгоритма по следующим соображениям. Мы
должны сравнить значения переменных a и b, и если из них a имеет большее
значение, то присвоить это значение переменной max. Если же a не больше b,
но присвоить переменной max значение b. После этого в
переменной maxбудет храниться искомое наибольшее значение из a и b.
Получаем блок-схему (Рисунок 6).
Пример 5. Составить блок-схему решения следующей задачи. Даны
значения трех действительных переменных a, b и c. Найти наибольшее
значение из a, b и c.
Выбирать наибольшее значение из двух уже умеем (см. пример выше). В
этой задаче надо найти большее из трех. Можно ли свести эту задачу к
предыдущей? Можно, а именно – вначале найти наибольшее значение
из a и b, а потом сравнив его и c, снова найти наибольшее из двух. Это можно
представить такой блок-схемой (см. рис.)
Тесты для Примера 5
№
теста
Вход
Выход
a
b
c
1.
2
1
3
3
2.
0
-2
-1
0
3.
11
56
29
56
4.
4
2
4
4
5.
3
3
3
3
Пример 6. Составить блок-схему решения следующей задачи. Даны
значения действительных переменных b и c. Решить линейное
уравнениеbx+c=0.
Напомним, что решить уравнение – это найти множество всех его корней.
Решение «в лоб» «корень равен –c/b» неверно, так как не учитывает случай,
когда b=0, что вполне допустимо условием задачи. Действительно, если b≠0,
то существует единственный корень, равный –c/b. Если же b=0, то возможны
два случая. Первый: если c≠0, то корней уравнение не имеет, то есть
множество корней пусто . Второй: если же c=0, то уравнение не
определено, то есть любое действительное число является его корнем, иначе
говоря множество корней уравнения – все действительные числа .
Все вышесказанное можно представить в виде блок-схемы алгоритма
(см. рис.) и протестировать его на таблице тестов.
Тесты для Примера 6
№
теста
Вход
Выход
b
c
1.
1
-2
2
2.
2
1
-0,5
3.
10
0
0
4.
0
1
5.
0
0
Пример 7. Составить блок-схему решения следующей задачи. Даны
значения действительных переменных a, b и c, причем a≠0. Решить
уравнение ax
2
+bx+c=0.
Это квадратное уравнение, алгоритм его решения (через дискриминант)
известен любому школьнику. Приведем его блок-схему и таблицу тестов.
Обращаем внимание, что по условию этой задачи a не может равняться нулю.
Тесты для Примера 7
№
теста
Вход
Выход
a
b
c
1.
1
2
-3
-3; 1
2.
2
8
8
-2
3.
2
-1
4
Пример 8. Составить блок-схему решения следующей задачи. Даны
значения действительных переменных a, b и c. Решить
уравнениеax
2
+bx+c=0.
В отличие от предыдущего примера, здесь нет условия a≠0, то
есть a может равняться нулю. Поэтому надо отдельно рассмотреть два
случая. Первый случай, если a≠0; тогда мы получаем квадратное уравнение,
алгоритм решения которого изложен в примере 7. Второй случай, если a=0;
тогда мы имеем линейное уравнение, как в примере 6. Таким образом, блок-
схема решения этой задачи будет содержать алгоритмы решения квадратного
и линейного уравнений. Предлагается составить эту блок-схему
самостоятельно. Тесты даны.
Тесты для Примера 8
№
теста
Вход
Выход
a
b
c
1.
1
2
-3
-3; 1
2.
2
8
8
-2
3.
2
-1
4
4.
0
1
-2
2
5.
0
0
1
6.
0
0
0
Скачать материал

Информатика - еще материалы к урокам: