Основные алгоритмические структуры

1. Основные алгоритмические структуры.

2.

Алгоритм - это предназначенное для
конкретного
исполнителя
описание
последовательности действий, приводящих от
исходных данных к требуемому результату,
которое обладает свойствами:
• дискретности
• понятности
• определённости
• результативности
• массовости

3.

Исполнитель алгоритма
Исполнитель - это некоторый объект (человек, животное,
техническое
устройство),
способный
выполнять
определённый набор команд.
Исполнитель
Формальный
Неформальный
Круг решаемых задач
Среда исполнителя
СКИ
Режимы работы
Исполнители алгоритмов
Область, обстановка, условия
Непосредственное управление
Программное управление

4.

Свойства алгоритма
Свойства алгоритма
Дискретность
Путь решения задачи
разделён на отдельные шаги
Понятность
Алгоритм состоит из
команд, входящих в СКИ
Определённость
Команды понимаются
однозначно
Результативность
Обеспечивается получение
ожидаемого результата
Массовость
Обеспечивается решение
задач с различными исходными
данными

5.

Разработка алгоритма
Разработка алгоритма
Определение объектов,
указанных в задаче
Установление свойств
объектов, отношений
и действий с объектами
Определение исходных
данных и результата
Определение
последовательности
действий
Запись
последовательности
действий с помощью
команд СКИ
Алгоритм – модель деятельности исполнителя алгоритмов

6.

Основные способы записи
алгоритма
Графические
На
алгоритмических
языках
Словесное
описание
Последовательность рисунков
Школьный
алгоритмически
й
язык
Построчная
запись
Структурограмм
а
Словесные
Блок-схема
Язык
программирования

7.

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

8.

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

9.

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

10.

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

11.

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

12.

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

13.

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

14.

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

15.

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

16.

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

17.

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

18.

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

19.

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

20.

Цикл с заданным условием продолжения
работы
(цикл-ПОКА, цикл с предусловием)
нц пока <условие>
<тело цикла (последовательность действий)>
кц
нет
Условие
да
Тело цикла

21.

Цикл с заданным условием окончания работы
(цикл-ДО, цикл с постусловием)
Тело цикла
нет
Условие
да
Запись на алгоритмическом языке:
нц
<тело_цикла (последовательность действий)>
кц при <условие>

22.

Цикл с постусловием
Пример. Алгоритм по выучиванию наизусть четверостишия.
алг четверостишие
нач
нц
прочитать четверостишие по книге 1
раз
прочитать четверостишие наизусть
кц при не сделал ошибку
кон

23.

Вычисление значения переменной b
Начало
Список данных
a, b - цел
a := 1
b := 1
a := a *2
b := b +a
a=8
да
b
нет
Конец

24.

Таблица значений переменных
Шаг
алгоритма
Операция
Переменные
1
a := 1
1
2
b := 1
1
1
3
a := a * 2
2
1
4
b := b+a
2
3
5
a=8
6
a := a * 2
4
3
7
b := b+a
4
7
8
a=8
9
a := a * 2
8
7
10
b := b+a
8
15
11
a=8
a
Условие
b
a=8
2 = 8 (Нет)
4 = 8 (Нет)
8 = 8 (Да)

25.

Задача о тренировках
План тренировок:
В 1-й день пробежать 10 км.
Каждый
следующий
день
увеличивать расстояние на 10% от
результата предыдущего дня.
Как только дневной пробег
достигнет или превысит 25 км,
прекратить
увеличение
и
пробегать 25 км ежедневно.
Начиная с какого дня спортсмен
будет пробегать 25 км?
Пусть x — количество
километров, которое
спортсмен пробежит в
некоторый i-й день. Тогда в
следующий (i + 1)-й день он
пробежит x + 0,1x километров
(0,1x — это 10% от x).
Начало
Список данных
i – цел
x – вещ
i := 1
x := 10
i := i +1
x := x +0.1*x
x>= 25
да
i
нет
Конец

26.

Цикл с заданным числом повторений
(цикл-ДЛЯ, цикл с параметром)
i = i1, i2
Тело цикла
Запись на алгоритмическом языке:
нц для i от i1 до i2 шаг R
<тело_цикла (последовательность действий)>
кц

27.

Цикл с заданным числом повторений
алг переправа
нач
нц для i от 1 до 5
кц
кон
два мальчика переправляются на противоположный берег.
один мальчик высаживается на берег
другой мальчик плывёт обратно
солдат переправляется через реку
мальчик возвращается на исходную позицию

28. Вопросы: 1. Приведите пример линейного алгоритма. А) из литературного произведения; Б) из повседневной жизни; В) из любой

предметной области,
изучаемой в школе
Г)

29. Домашнее задание: §1.2.1, 1.2.2, .1.2.3, 1.2.4, 1.2.5 задание1.2, стр. 21, 1.3, стр. 23, 1.4, стр.25