Презентация, доклад по информатике на тему Исполнители алгоритмов, подготовка к ЕГЭ

последовательность операций для решения конкретного множества задач и обладает пятью важными чертами: конечность, определённость, ввод, вывод, эффективность (Д. Э. Кнут).

Алгоритм — это всякая система вычислений, выполняемых по строго определённым правилам, которая после какого-либо числа шагов заведомо приводит к решению поставленной задачи (А. Н. Колмогоров).

Алгоритм — это последовательность действий, либо приводящяя к решению задачи, либо поясняющая, почему это решение получить нельзя.

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

обученный выполнению некоторой совокупности операций в заданной последовательности.и обученный выполнению некоторой совокупности операций в заданной последовательности

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

предписываемые алгоритмом. Обычно исполнитель ничего не знает о цели алгоритма. Он выполняет все полученные команды формально (не обдумывая). В информатике универсальным исполнителем алгоритмов является компьютер.

объектами

Определение исходных
данных и результата

Определение
последовательности
действий

Запись
последовательности
действий с помощью
команд СКИ

Алгоритм – модель деятельности исполнителя алгоритмов

Разработка алгоритма

Робота:
вверх вниз влево вправо
вверх ↑, вниз -↓, влево ←, вправо →.
сверху свободно снизу свободно
слева свободно справа свободно
Цикл ПОКА <условие> команда выполняется, пока
условие истинно, иначе происходит переход на следующую строку.
В кон­струк­ции
ЕСЛИ < усло­вие >
ТО ко­ман­да1
ИНАЧЕ ко­ман­да2
КОНЕЦ ЕСЛИ
вы­пол­ня­ет­ся ко­ман­да1 (если усло­вие ис­тин­но) или ко­ман­да2 (если усло­вие ложно)
Если РОБОТ начнёт дви­же­ние в сто­ро­ну на­хо­дя­щей­ся рядом с ним стены, то он раз­ру­шит­ся и про­грам­ма прервётся.

начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)?

НА­ЧА­ЛО
ПОКА<спра­ва сво­бод­но ИЛИ снизу сво­бод­но >
ПОКА < снизу сво­бод­но >
вниз
КОНЕЦ ПОКА
ПОКА < спра­ва сво­бод­но >
впра­во
КОНЕЦ ПОКА
КОНЕЦ ПОКА
КОНЕЦ
1) 14
2) 17
3) 19
4) 21

вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)?

НАЧАЛО
ПОКА < справа свободно ИЛИ снизу свободно >
ПОКА < справа свободно >
вправо
КОНЕЦ ПОКА
ПОКА < снизу свободно >
вниз
КОНЕЦ ПОКА
КОНЕЦ ПОКА
КОНЕЦ

1) 8 2) 15 3) 24 4) 27

двигаясь вначале вправо до упора, затем вниз до упора:
Красная клетка – особая, в ней заканчивается один
внешний цикл и начинается другой.
а) Робот может попасть в нее, двигаясь вниз из
клетки, когда справа – стенка;
б) снизу есть стенка;
в) снизу стенка есть, справа – нет, тогда выполнится еще один шаг внешнего цикла.







Таких клеток 24, следовательно верный ответ - 3

вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)?

НА­ЧА­ЛО
ПОКА <снизу сво­бод­но ИЛИ спра­ва сво­бод­но>
ПОКА <спра­ва сво­бод­но>
ТО
<впра­во>
КОНЕЦ ПОКА
ЕСЛИ <снизу сво­боднo>
ТО
<вниз>
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ

1) 18
2) 19
3) 20
4) 21 

их «особые») в лабиринте, к которым робот вернется пройдя четыре раза по прямой (пока выполняется условие цикла). При этом он, естественно, пройдет по сторонам прямоугольника.
1) необходимо, чтобы стенки были расставлены так, чтобы Робот упирался в них сначала при движении вниз, затем
влево, вверх и вправо;
2) необходимо, чтобы выделенный зеленый
коридор был свободен;
3) возможны еще «вырожденные» варианты:

Задачи с остановкой в клетке, из которой начато движение

РОБОТ остановится в той же клетке, с которой он начал движение?

НА­ЧА­ЛО
ПОКА < снизу сво­бод­но > вниз
ПОКА < слева сво­бод­но > влево
ПОКА < свер­ху сво­бод­но > вверх
ПОКА < спра­ва сво­бод­но > впра­во
КОНЕЦ
 
1) 1
2) 2
3) 3
4) 4

в той же клет­ке, с ко­то­рой он начал дви­же­ние?
 
НА­ЧА­ЛО
ПОКА < снизу сво­бод­но > вниз
ПОКА < слева сво­бод­но > влево
ПОКА < свер­ху сво­бод­но > вверх
ПОКА < спра­ва сво­бод­но > впра­во
КОНЕЦ
 
1) 1
2) 2
3) 3
4) 4

на 3
прибавь 3
Первая из них уменьшает число на экране на 1, вторая — утраивает его, а третья увеличивает на 3.
Запишите порядок команд в алгоритме получения из числа 5 числа 23 за наименьшее число команд.

Например, 211 — это алгоритм:
2. умножь на 3
1. вычти 1
1. вычти 1,— который преобразует число 7 в 19.

из числа 5 числа 23 за наименьшее число команд.

5

-1

*3

+3

4

15

8

-1

*3

+3

-1

*3

+3

-1

3

12

7

14

45

18

7

24

11

+3

*3

*3

+3

-1

23

I

II

III

Ответ: 321

Для решения данной задачи полезно построить дерево.

команд
в программе преобразования
числа 3 в число 63, содержащей
не более 8 команд, указывая
лишь номера команд. Если
таких программ более одной,
то запишите любую из них.
1 2 1 2 1 2 1 2
63 62 31 30 15 14 7 6 3

Такую задачу удобнее решать «с конца». Тогда дерево будет не таким большим, но необходимо заменить команды на противоположные:
Вычти 1
Раздели на 2
Очевидно, что делить на 2
можно только четные числа, тогда:

2. умножь на 4 Выполняя первую из них, Калькулятор прибавляет к числу на экране 3, а выполняя вторую, умножает его на 4. Запишите порядок команд в программе получения из числа 3 числа 57, содержащей не более 6 команд, указывая лишь номера команд.

направление своего движения относительно последнего (текущего) положения.
* Если обе координаты положительные, то Чертёжник переходит в I четверть координатной плоскости (движется вправо и вверх).
* Если первая координата отрицательная, а вторая положительная, то Чертёжник переходит во II четверть координатной плоскости (движется влево и вверх).
* Если обе координаты отрицательные, то Чертёжник переходит в III четверть координатной плоскости (движется влево и вниз).
* Если первая координата положительная, а вторая отрицательная, то Чертёжник переходит в IV четверть координатной плоскости (движется вправо и вниз). 

Что нужно знать

Чертежник

виде линии. Может выполнять команду сместиться на (a, b), где a, b – целые числа. Эта команда перемещает Чертежника из точки с координатами (x, y) в точку с координатами (x+a, y+b).
Например, если Чертежник находится в точке с координатами (4, 2), то команда сместиться на (2, -3) переместит Чертежник в точку (6, -1). Цикл
ПОВТОРИ число РАЗ
последовательность команд
КОНЕЦ ПОВТОРИ
Означает, что последовательность команд будет выполнена указанное число раз(число должно быть натуральным)

Исполнитель Чертежник

на (–3, –2) Сместиться на (2, 1) Сместиться на (3, 0)
конец

Какую команду надо выполнить Чертёжнику, чтобы вернуться в исходную точку, из которой он начал движение?

1) Сместиться на (–3, –6)
2) Сместиться на (–6, 3)
3) Сместиться на (6, –3)
4) Сместиться на (3, 6)

Задачи с возвращением
в начальную точку, координаты и число повторений цикла известны

Сместиться на (3,0)
                  конец
Чертёжник переместиться из точки A в точку B. Каждая из ломаных линий одного цвета соответствует однократному прохождению одного из трёх повторений цикла.

Первый способ.

Сместиться на (-6,3), что наглядно видно из графика:

Ответ: 2

он перемещается в точку (x+a, y+b). В начальном положении перо Чертежника находится в точке (0,0).

Второй способ.

После выполнения алгоритма Чертежник окажется в точке (6,-3),
чтобы попасть в начальную точку (0,0) надо сместиться на (-6,3).

Ответ: 2

неизвестны
Чертежнику был дан для исполнения алгоритм (буквами a, b, n обозначены неизвестные числа, n>1)
НАЧАЛО
сместиться на (-3, -3)
ПОВТОРИ n РАЗ
сместиться на (a, b)
сместиться на (27, 12)
КОНЕЦ ПОВТОРИ
сместиться на (-22, -7)
КОНЕЦ
Укажите наименьшее возможное значение числа n, для которого найдутся такие значения чисел a и b, что после выполнения программы Чертежник возвратиться в исходную точку.

2) Сме­стить­ся на (−2, 2) Сме­стить­ся на (4, −4) Конец

Ка­ко­вы ко­ор­ди­на­ты точки, с ко­то­рой Чертёжник на­чи­нал дви­же­ние, если в конце он ока­зал­ся в точке с ко­ор­ди­на­та­ми (0, 0)?

1) Сме­стить­ся на (7, 0)
2) Сме­стить­ся на (−7, 0)
3) Сме­стить­ся на (0, −7)
4) Сме­стить­ся на (0, 7)

раз
Сме­стить­ся на (3,1) Сме­стить­ся на (0, 2) Сме­стить­ся на (−1, 4) конец
 
На какую ко­ман­ду можно за­ме­нить этот ал­го­ритм?
 
1) Сме­стить­ся на (8, 28)
2) Сме­стить­ся на (7, 29)
3) Сме­стить­ся на (−8, −28)
4) Сме­стить­ся на (−7, −29)

Сместиться на (27, 17)
Сместиться на (a, b)
конец
Сместиться на (–27, –17)
Чему должно равняться N, чтобы Чертежник смог вернуться в исходную точку, из которой он начал движение?
4 2) 5 3) 6 4) 7

ЕГЭ»
http://inf.reshuege.ru/
Сайт Константина Полякова
http://kpolyakov.spb.ru/
ФИПИ – открытый банк заданий
http://www.fipi.ru/
http://cdosh46.ru/video-uroki.html