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

1.

АЛГОРИТМИЧЕСКАЯ
КОНСТРУКЦИЯ
«СЛЕДОВАНИЕ» и «ВЕТВЛЕНИЕ»

2.

Ключевые слова
• следование
• линейные алгоритмы

3.

Основные алгоритмические конструкции
Для записи любого алгоритма достаточно трёх основных
алгоритмических конструкций:
следования,
ветвления,
повторения.
(Э. Дейкстра)
Эдсгер Вибе Дейкстра (1930–2002).
Выдающийся нидерландский учёный,
идеи которого оказали огромное
влияние на развитие компьютерной
индустрии.

4.

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

5.

Линейный алгоритм
приготовления отвара шиповника
Начало
Столовую ложку сушёных плодов
шиповника измельчить в ступке
Залить стаканом кипячёной воды
Кипятить 10 минут на слабом огне
Охладить
Процедить
Конец

6.

Линейный алгоритм
для исполнителя Робот
СКИ исполнителя Робот: вверх, вниз, влево, вправо и закрасить.
алг узор
нач
закрасить
вправо
вправо
закрасить
вниз
влево
закрасить
вверх
влево
кон

7.

Вычисления по алгоритму
Алгоритм
Шаг
алгоритма
х:=2
у:=х*х
у:=у*у
х:=у*х
s:=x+y
Переменные
x
y
s
1
2
-
-
2
2
4
3
2
16
-
4
32
16
-
5
32
16
48
Ответ: s = 48

8.

Целочисленная арифметика
С помощью операции div вычисляется целое частное, с
помощью операции mod - остаток.
7 : 3 = 2 (ост.1)
7 div 3 = 2
7 mod 3 = 1
8 : 3 = 2 (ост.2)
8 div 3 = 2
8 mod 3 = 2
10 : 3 = 3 (ост.1)
10 div 3 = 3
10 mod 3 = 1
13 : 4 = 3 (ост.1)
13 div 4 = 3
13 mod 4 = 1
11 : 4 = 2 (ост.3)
11 div 4 = 2
11 mod 4 = 3
8 : 5 = 1 (ост.3)
8 div 5 = 1
8 mod 5 = 3

9.

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

10.

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

11.

Полная форма ветвления
если <условие>
то <действие 1>
иначе <действие 2>
все
Да
Действие 1
Пример
алг правописание частиц НЕ, НИ
нач
если частица под ударением
то писать НЕ
иначе писать НИ
все
кон
Условие
Нет
Действие 2

12.

Неполная форма ветвления
если <условие>
то <действие 1>
все
Да
Действие 1
Пример:
алг сборы на прогулку
нач
если на улице дождь
то взять зонтик
все
кон
Условие
Нет

13.

Операции сравнения
A<B
A <= B
А меньше В
А меньше или равно В
A=B
А равно В
A>B
А больше В
A >= B
А больше или равно В
A <> B
А не равно В

14.

Вычисление функции f(x)=|x|
Начало
Список данных
X, Y -вещ
Х
да
Х>0
Y:=X
нет
Y:=-X
Y
Конец

15.

Простые и составные условия
Простые условия состоят из одной операции сравнения.
Составные условия получаются из простых с помощью
логических связок and (и), or (или), not (не).
Пример. Алгоритм определения принадлежности точки Х
отрезку [A; B].
A, B, X
да
(X>=A) and (X<=B)
ДА
нет
НЕТ
Ответ:
Ответ:Не
Принадлежит
принадлежит
A=2
B=4
X=4
B=6
X=6

16.

Наибольшая из 3-х величин
Переменной Y присваивается значение большей из трёх
величин A, B и C.
YY
B==>Y
AB
C
Шаг
Y:=A
да
B>Y
нет
Y:=B
1
Константы
А
В
С
10
30
20
Переменная
Y
10
2
да
Y:=C
C>Y
30 > 10 (Да)
нет
3
Условие
30
4
20 > 30 (Нет)
Ответ: Y = 30

17.

Решение линейного уравнения ax + b = 0
Список данных
a, b, x - вещ
a, b
да
x:=-b/a
нет
a<>0
да
Корней нет
b<>0
нет
Любое число

18.

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

19.

Самое главное
Для записи любого алгоритма достаточно трёх
основных алгоритмических конструкций (структур):
следования, ветвления, повторения.
Ветвление - алгоритмическая конструкция, в которой
в зависимости от результата проверки условия (да или
нет)
предусмотрен
выбор
одной
из
двух
последовательностей действий (ветвей).
Алгоритмы, в основе которых лежит структура
«ветвление», называют разветвляющимися.

20.

Вопросы и задания
Известно,
31 января
2011 года9 приходится
Дополнитечто
алгоритм
из примера
так, чтобы сна
его
понедельник.
Какиебыло
значения
быть присвоены
помощью можно
найтидолжны
наибольшую
из четырёх
Определите,
Приведите
Запишите
Какие
Запишите
алгоритмы
алгоритм
пример
алгоритм
есть ли
называют
разветвляющегося
определения
среди
правописания
цифр
разветвляющимися?
заданного
принадлежности
приставок,
алгоритма
целого
из
Составьте
алгоритм,
с
помощью
которого
можно
литерной
переменной
y
в
алгоритме,
определяющем
Запишите
Составьте
алгоритм
алгоритм,
определения
с
помощью
количества
которого
можно
чётных
величин
A,
B,
C
и
D.
Составьте
Даны
алгоритм
две
точки
возведения
на плоскости.
чётного
числа в из
Какая
задача
решается
с
помощью
следующего
точки
Х
отрезку
[А;
В]
с
использованием
комбинации
начинающихся
трёхзначного
повседневной
числа
с
буквы
одинаковые
жизни.
«з»
(«с»).
определить,
существует
ли
треугольник
сзаданными
длинами
чисел
среди
целых
чисел
А,
В киначалу
С.2011
определить,
является
ли
треугольник
с
день
недели
длязаданных
любого
числа
(chislo)
января
Определите,
квадрат,
какая
из
а
них
нечётного
находится
в
куб.
ближе
алгоритма?
двух
ветвлений.
сторон
с.
года?
длинами сторон
a,
b,a,сb,равносторонним.
координат.
chislo:=Y:=A
chislo
mod 7
К:=0
если
chislo=3
тоНетнет
у:='…‘
да Да
А>=0
B>Y
если
chislo=4
то у:='…‘
K:=K+1
если chislo=5 то у:='…‘
Y:=B
Да
B>=0 тоНет
если chislo=6
у:='…‘
K:=K+1
если
chislo=0 то у:='…‘
да
нет
C>Y то у:='…‘
если chislo=1
K
если chislo=2 то у:='…'
Y:=C

21.

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

22.

Вопросы и задания
Известно,
Запишите
Приведите
Какие
По
что
линейный
алгоритму
алгоритмы
1данное
миля
пример
алгоритм,
=-целочисленных
восстановите
7целое
называются
вёрст,
линейного
исполняя
1суток
верста
алгоритма
линейными?
формулу.
=который
саженей,
из xРобот
Исходное
Для
заданного
количества
трёхзначное
(tfh
) 500
требуется
число
. xи
Определите
значение
переменных
Какое
значение
получит
переменная
у после
нарисует
1
сажень
на
=
клетчатом
повседневной
3
аршина,
поле
1
аршин
жизни.
следующий
=
28
дюймов,
узор
и (c).
a1:=1/x
определить
Выполните
количество
для
x
=
125
часов
следующий
(
h
),
минут
алгоритм.
(
m
)
и
секунд
y после
выполнения
фрагмента
алгоритма.
выполнения
фрагмента
алгоритма?
вернётся
1
дюйм
в
исходное
=
25,4
положение:
мм.
a2:=a1/x
a:=x div 100
х:=1 составьте линейный
Пользуясь этой информацией,
x:=336
b:=x mod 100 div 10 a3:=a2/x
у:=2*x Х миль в километры.
алгоритм
перевода
расстояния
* a4:=a3/x
y:=8
c:=x mod 10
у:=у+3
x:=x
div y
s:=a+b+с.
у:=у*х
y:=a1+a2
y:=у+4s этого алгоритма?
Чем
y:=х mod
у является результат
y:=y+a3
y:=y*х
y:=y+a4
y:=y+5
Восстановите формулу вычисления у для
произвольного значения х.

23.

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