АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ
ОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ
- алгоритм
- основные алгоритмические конструкции
- последовательная структура ветвящаяся структура циклическая структура рекурсия
- последовательная структура
- ветвящаяся структура
- циклическая структура
- рекурсия
Основные алгоритмические структуры
Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры):
ПОСЛЕДОВАТЕЛЬНЫЕ
ВЕТВЯЩИЕСЯ
АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ
ЦИКЛИЧЕСКИЕ
РЕКУРСИВНЫЕ
Для записи любого алгоритма достаточно трёх основных алгоритмических структур: последовательной, ветвящейся, циклической.
Последовательная алгоритмическая конструкция
Алгоритм реализован через последовательную алгоритмическую конструкцию , если все команды алгоритма выполняются один раз, причём в том порядке, в котором они записаны в тексте программы.
!
Начало
Пример 1. Алгоритм представлен блок-схемой.
Выясните, какую задачу решает этот алгоритм.
Чему равен результат работы алгоритма при х = 2 .
X
REZ := X * X
Решение:
REZ
№
REZ := REZ * REZ
Комментарии
Интерактивный элемент – кнопка Решение – появляется краткое решение с ответом
1
X 2
REZ := REZ * REZ
2
X 4
X 8
3
REZ := REZ * X
X 9
4
REZ
Решение
Ответ: 512
Конец
4
Ветвящаяся алгоритмическая конструкция
Алгоритм реализован через ветвящуюся алгоритмическую конструкцию , если от входных данных зависит, какие команды алгоритма будут выполняться.
!
Пример 2. Алгоритм представлен блок-схемой. Выясните, какую задачу решает этот алгоритм. Найдите значение переменной Y при:
Начало
X
1) х = –10;
2) х = 2;
3) х = 10.
Да
X
Y := –X
Нет
Да
X
Комментарии
Интерактивный элемент - кнопка Ответ
Y := X – 5
Y := –1
Y
Ответ
Ответ: 1) 10 ; 2)– 1 ; 3) 5
Конец
5
Циклическая алгоритмическая конструкция
Алгоритм реализован с использованием циклической алгоритмической конструкции , если некая группа подряд идущих шагов алгоритма может выполняться многократно в зависимости от входных данных.
!
Цикл с постусловием (цикл-до)
Цикл с параметром
Цикл с предусловием (цикл-пока)
Нет
Условие
Параметр = НЗ, КЗ
Тело цикла
Да
Тело цикла
Тело цикла
Нет
Условие
Да
Последовательность команд, повторяющуюся при выполнении цикла, называют телом цикла .
6
Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры): последовательные, ветвящиеся, циклические, вспомогательные и рекурсивные. Для записи любого алгоритма достаточно трёх основных алгоритмических структур: последовательной, ветвящейся, циклической.
Алгоритм реализован через последовательную алгоритмическую конструкцию , если все команды алгоритма выполняется один раз, причём в том порядке, в котором они записаны в тексте программы.
Алгоритм реализован через ветвящуюся алгоритмическую конструкцию , если от входных данных зависит, какие команды алгоритма будут выполняться.
Алгоритм реализован с использованием циклической алгоритмической конструкции , если некая группа подряд идущих шагов алгоритма может выполняться многократно в зависимости от входных данных.
Давайте обсудим. Игра в ассоциации
Какие ассоциации, связанные с основными алгоритмическими конструкциями, вызывают данные объекты. Объясните свой выбор.
6
Вопросы и задания
Задание 1-А. У исполнителя Вычислитель три команды:
- прибавь 1 – увеличивает число на экране на 1 ;
- умножь на 2 – удваивает число;
- умножь на 3 – утраивает число.
Сколько существует различных программ, которые число 1 преобразуют в число 12 ?
Решение (один из способов оформления):
7
11
10
9
8
4
6
5
3
2
12
1
10
9
7
8
11
4
3
2
1
5
6
12
+ 1
15
18
2
3
5
5
10
10
+ 1
23
23
1
Комментарии
ЕГЭ-2017. Задание 22. На уроках желательно рассмотреть актуальное задание данного типа
Кнопка Ответ – появляется заполненная таблица + ответ
Кнопка Решение – переход на скрытый слайд – пошаговое решение
× 2
2
10
5
5
3
1
× 2
× 3
× 3
3
5
2
1
Всего
38
23
Всего
23
18
15
10
10
5
5
3
2
1
Ответ : 38
Ответ
Решение
9
Вопросы и задания
Задание 1-А. У исполнителя Вычислитель три команды:
- прибавь 1 – увеличивает число на экране на 1 ;
- умножь на 2 – удваивает число;
- умножь на 3 – утраивает число.
Сколько существует различных программ, которые число 1 преобразуют в число 12 ?
Решение (один из способов оформления):
× 2
+1
× 2
+1
+1
× 3
+1
+1
× 3
× 2
11
12
9
8
7
6
5
4
3
2
1
10
+ 1
10
1
2
3
5
5
10
15
18
23
23
× 2
3
2
10
5
5
1
× 3
1
2
5
3
Всего
1
5
2
23
3
18
5
10
38
10
15
23
Ответ : 38
Вопросы и задания
Задание 1-Б. У исполнителя Вычислитель три команды:
- прибавь 1 – увеличивает число на экране на 1 ;
- умножь на 2 – удваивает число;
- умножь на 3 – утраивает число.
Сколько существует различных программ, которые число 1 преобразуют в число 12 и при этом траектория вычислений содержит число 6 ?
Решение (основа – решение задачи 1-А):
!
8
12
11
10
9
7
6
5
4
3
2
1
+ 1
10
1
2
3
5
5
10
10
10
10
10
Комментарии
Другой вариант того же задания
Таблица заполняется по столбцам (по щелчку мыши/пробелу)
× 2
1
–
2
3
10
–
× 3
1
–
–
2
Всего
10
5
5
3
1
10
2
20
10
10
10
10
Ответ : 20
11
Вопросы и задания
Задание 1-В. У исполнителя Вычислитель три команды:
- прибавь 1 – увеличивает число на экране на 1 ;
- умножь на 2 – удваивает число;
- умножь на 3 – утраивает число.
Сколько существует различных программ, которые число 1 преобразуют в число 12 и при этом траектория вычислений НЕ содержит число 4 ?
Решение (основа – решение задачи 1-А):
х
12
11
10
9
8
7
5
4
3
2
1
6
+ 1
8
8
1
2
0
0
5
5
5
8
Комментарии
Другой вариант того же задания
Таблица заполняется по столбцам (по щелчку мыши/пробелу)
× 2
0
0
3
1
5
× 3
1
0
3
2
Всего
2
1
8
13
8
8
5
5
5
0
3
0
Ответ : 13
12
Вопросы и задания
Задание 2. Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды:
- нашлось ( v ) – проверяет, встречается ли цепочка v в строке;
- заменить ( v , w ) – заменяет в строке первое слева вхождение цепочки v на цепочку w .
Дана программа для исполнителя:
НАЧАЛО
ПОКА нашлось (444) ИЛИ нашлось (22)
ЕСЛИ нашлось (444)
ТО заменить (444, 2)
ИНАЧЕ заменить (22, 4)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Какая строка получится в ре-зультате применения программы к строке, состоящей из:
А) 303 идущих подряд цифр 2 ;
Б) 303 идущих подряд цифр 4.
Комментарии
ЕГЭ-2017. Задание 14. На уроках желательно рассмотреть актуальное задание данного типа
Кнопки Решение – переход на скрытые слайды с решением
Решение
Решение
12
Вопросы и задания
Задание 2-А. 303 идущих подряд цифр 2 .
Программа:
НАЧАЛО ПОКА нашлось (444) ИЛИ нашлось (22) ЕСЛИ нашлось (444) ТО заменить (444, 2) ИНАЧЕ заменить (22, 4) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ
2
2
2
2
2
2
2
…
2
} 303
2
2
2
2
2
2
4
4
4
2
Выполним алгоритм для начала последовательности.
Шесть « 2 » заменяются на одну, т.е. пять из них вычеркивается.
Найдем, сколько « 2 » останется невычеркнутыми: вычислим остаток от деления 303 на 5 .
303 : 5 = 60 (3)
То есть остаются три « 2 »: 222 .
Применив программу к данной строке символов, получаем: 42.
Ответ: 42
14
Вопросы и задания
Задание 2-Б. 303 идущих подряд цифр 4 .
Программа:
НАЧАЛО ПОКА нашлось (444) ИЛИ нашлось (22) ЕСЛИ нашлось (444) ТО заменить (444, 2) ИНАЧЕ заменить (22, 4) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ
…
2
} 101
2
…
2
2
2
2
2
2
4
2
} 303
4
2
4
4
4
4
4
4
4
4
4
2
2
2
2
Выполним алгоритм.
Все последовательности из трех « 4 » заменяются на одну « 2 ».
Таких замен будет:
303 : 3 = 101 (0)
Т.е. в результате исходная после-довательность заменится на последовательность из 101 « 2 ».
Задача сводится к предыдущей. Решите ее самостоятельно.
Ответ: 2
15
Вопросы и задания
Задание 3. Автомат по продаже напитков имеет только две кнопки ( A и B ), но должен продавать 4 напитка: горячий кофе, горячий чай, яблочный сок и лимонад. Исследуйте работу автомата. Представьте в форме блок-схемы алгоритм его работы.
A
A
A
B
B
B
Начало
Нет
Да
А
Комментарии
Интерактивные элементы кнопки А и В. Нажатие кнопок приводит к появлению напитков: АА- лимонад, АВ – сок, ВА – чай, ВВ – кофе. Щелчок по появившемуся напитку удаляет его с экрана. Также он исчезает при начале новой серии команд.
По кнопке «Ответ» появляется один из вариантов решения.
Нет
Нет
Да
Да
А
А
Сок
Кофе
Чай
Лимонад
Ответ
Конец
16
Информационные источники
- https://cdn.pixabay.com/photo/2013/07/12/16/01/clock-150754_960_720.png
- http://1.bp.blogspot.com/-amDD3QME4B8/UXJGU5MIEwI/AAAAAAAAAHo/toyrXJ74Fhw/s1600/sneginka.JPG
- http://www.codenet.ru/np-includes/upload/2005/04/11/128343.gif
- http://connellyscuriousclassmates.weebly.com/uploads/4/0/6/3/40639717/5471196_orig.jpg
- http://vignette2.wikia.nocookie.net/roac/images/1/16/25eb370c.jpg/revision/latest?cb=20150715115114
- http://cliparts.co/cliparts/rcL/nn8/rcLnn8RGi.png
- http://www.iaim.ru/wp-content/uploads/2013/03/bibor_v_gizni.jpg
- https://pixabay.com/ru/песочные-часы-песок-часы-время-1046841/
- https://www.proza.ru/pics/2011/01/11/717.gif
- http://img0.liveinternet.ru/images/attach/c/7/98/66/98066074_p030413945.png
- https://www.kidsbrain.es/assets/images/blocks/df23e431e13dd224c12ac689c52251d4.png
- http://img1.reactor.cc/pics/comment/Клуб-аметистов-разное-буратино-1649251.jpeg
- https://lorirtaylor.com/wp-content/uploads/2013/09/Wake-Up-And-Smell-The-Coffee.jpg
- https://healthylivings.com/wp-content/uploads/2013/06/blacktea.jpeg
- http://imp72.ru/upload/resizer2/12_1d762f431ad445dd8bf72665cc7f23d7.png
- http://www.silesiatoastmasters.pl/wp-content/uploads/2016/09/kawa-herbata-2.jpg