Эта информация поможет вам

АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

ОСНОВНЫЕ СВЕДЕНИЯ ОБ АЛГОРИТМАХ

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

• последовательная структура ветвящаяся структура циклическая структура рекурсия
• последовательная структура
• ветвящаяся структура
• циклическая структура
• рекурсия

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

Вне зависимости от выбранной формы записи элементарные шаги алгоритма объединяются в алгоритмические конструкции (структуры):

ПОСЛЕДОВАТЕЛЬНЫЕ

ВЕТВЯЩИЕСЯ

АЛГОРИТМИЧЕСКИЕ СТРУКТУРЫ

ЦИКЛИЧЕСКИЕ

РЕКУРСИВНЫЕ

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

Последовательная алгоритмическая конструкция

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

!

Начало

Пример 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