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

Исполнители алгоритмов Учитель информатики МБОУ «СОШ № 36» г. Курска Плотникова Наталья Сергеевна

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

Благодаря этой рекламе сайт может продолжать свое существование, спасибо за просмотр.

Исполнитель 1.Исполнитель - это человек или коллектив людей, вооруженных набором инструментов и обученный выполнению некоторой совокупности операций в заданной последовательности.и обученный выполнению некоторой совокупности операций в заданной последовательности

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

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

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

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

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

Задачи с остановкой в заданной клетке Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)? НА­ЧА­ЛО ПОКА<,спра­ва сво­бод­но ИЛИ снизу сво­бод­но >, ПОКА <, снизу сво­бод­но >, вниз КОНЕЦ ПОКА ПОКА <, спра­ва сво­бод­но >, впра­во КОНЕЦ ПОКА КОНЕЦ ПОКА КОНЕЦ 1) 14 2) 17 3) 19 4) 21             1             2             3             4             5             6 A B C D E F

Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)? НАЧАЛО ПОКА <, справа свободно ИЛИ снизу свободно >, ПОКА <, справа свободно >, вправо КОНЕЦ ПОКА ПОКА <, снизу свободно >, вниз КОНЕЦ ПОКА КОНЕЦ ПОКА КОНЕЦ 1) 8 2) 15 3) 24 4) 27             1             2             3             4             5             6 A B C D E F

За каждый шаг внешнего цикла Робот проходит путь в виде «сапога», двигаясь вначале вправо до упора, затем вниз до упора: Красная клетка – особая, в ней заканчивается один внешний цикл и начинается другой. а) Робот может попасть в нее, двигаясь вниз из клетки, когда справа – стенка, б) снизу есть стенка, в) снизу стенка есть, справа – нет, тогда выполнится еще один шаг внешнего цикла. Таких клеток 24, следовательно верный ответ - 3             1             2             3             4             5             6 A B C D E F               1             2             3             4             5             6 A B C D E F               1             2             3             4             5             6 A B C D E F

Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, начав дви­же­ние в ней и вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ уце­ле­ет и оста­но­вит­ся в за­кра­шен­ной клет­ке (клет­ка F6)? НА­ЧА­ЛО ПОКА <,снизу сво­бод­но ИЛИ спра­ва сво­бод­но>, ПОКА <,спра­ва сво­бод­но>, ТО <,впра­во>, КОНЕЦ ПОКА ЕСЛИ <,снизу сво­боднo>, ТО <,вниз>, КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ 1) 18 2) 19 3) 20 4) 21              1             2             3             4             5             6 A B C D E F

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

Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение? НА­ЧА­ЛО ПОКА <, снизу сво­бод­но >, вниз ПОКА <, слева сво­бод­но >, влево ПОКА <, свер­ху сво­бод­но >, вверх ПОКА <, спра­ва сво­бод­но >, впра­во КОНЕЦ   1) 1 2) 2 3) 3 4) 4             6             5             4             3             2             1 A B C D E F

      6           5            4            3           2           1 A B C D E F              6            5            4            3            2            1 A B C D E F               6             5           4             3            2             1 A B C D E F            6             5             4             3             2             1 A B C D E F               6          5             4             3             2             1 A B C D E F               6           5             4             3             2            1 A B C D E F

Сколь­ко кле­ток ла­би­рин­та со­от­вет­ству­ют тре­бо­ва­нию, что, вы­пол­нив пред­ло­жен­ную про­грам­му, РОБОТ оста­но­вит­ся в той же клет­ке, с ко­то­рой он начал дви­же­ние?   НА­ЧА­ЛО ПОКА <, снизу сво­бод­но >, вниз ПОКА <, слева сво­бод­но >, влево ПОКА <, свер­ху сво­бод­но >, вверх ПОКА <, спра­ва сво­бод­но >, впра­во КОНЕЦ   1) 1 2) 2 3) 3 4) 4

Исполнитель Вычислитель У исполнителя Вычислитель три команды, которым присвоены номера: вычти 1 умножь на 3 прибавь 3 Первая из них уменьшает число на экране на 1, вторая — утраивает его, а третья увеличивает на 3. Запишите порядок команд в алгоритме получения из числа 5 числа 23 за наименьшее число команд. Например, 211 — это алгоритм: 2. умножь на 3 1. вычти 1 1. вычти 1,— который преобразует число 7 в 19.

Исполнитель Вычислитель вычти 1 умножь на 3 прибавь 3 Запишите порядок команд в алгоритме получения из числа 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 Для решения данной задачи полезно построить дерево.

Исполнитель Вычислитель Есть 2 команды, которым присвоены номера: Прибавь 1 Умножь на 2 Запишите порядок команд в программе преобразования числа 3 в число 63, содержащей не более 8 команд, указывая лишь номера команд. Если таких программ более одной, то запишите любую из них. 1 2 1 2 1 2 1 2 63 62 31 30 15 14 7 6 3 Такую задачу удобнее решать «с конца». Тогда дерево будет не таким большим, но необходимо заменить команды на противоположные: Вычти 1 Раздели на 2 Очевидно, что делить на 2 можно только четные числа, тогда:

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

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

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

Чертёжнику был дан для исполнения следующий алгоритм: Повтори 3 раз Сместиться на (–3, –2) Сместиться на (2, 1) Сместиться на (3, 0) конец Какую команду надо выполнить Чертёжнику, чтобы вернуться в исходную точку, из которой он начал движение? 1) Сместиться на (–3, –6) 2) Сместиться на (–6, 3) 3) Сместиться на (6, –3) 4) Сместиться на (3, 6) Задачи с возвращением в начальную точку, координаты и число повторений цикла известны

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

Возвращение Чертёжника  в исходную точку A из точки B соответствует варианту ответов 2) Сместиться на (-6,3), что наглядно видно из графика: Ответ: 2

Пусть Чертежник находится в точке (х,у), по команде сместиться на (а,b) он перемещается в точку (x+a, y+b). В начальном положении перо Чертежника находится в точке (0,0). Второй способ. После выполнения алгоритма Чертежник окажется в точке (6,-3), чтобы попасть в начальную точку (0,0) надо сместиться на (-6,3). Ответ: 2 ЕГЭ 2015 Сместиться на (–3, –2) (0+(-3),0+(-2)) (-3,-2) Сместиться на (2, 1) (-3+2,-2+1) (-1,-1) Сместиться на (3, 0) (-1+3,1+0) (2,-1) Сместиться на (–3, –2) (-1,-3) Сместиться на (2, 1) (1,-2) Сместиться на (3, 0) (4,-2) Сместиться на (–3, –2) (1,-4) Сместиться на (2, 1) (3,-3) Сместиться на (3, 0) (6,-3)

Третий способ - универсальный

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

Используем универсальный способ

Чертёжнику был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм: По­вто­ри 7 paз Сме­стить­ся на (−1, 2) Сме­стить­ся на (−2, 2) Сме­стить­ся на (4, −4) Конец Ка­ко­вы ко­ор­ди­на­ты точки, с ко­то­рой Чертёжник на­чи­нал дви­же­ние, если в конце он ока­зал­ся в точке с ко­ор­ди­на­та­ми (0, 0)? 1) Сме­стить­ся на (7, 0) 2) Сме­стить­ся на (−7, 0) 3) Сме­стить­ся на (0, −7) 4) Сме­стить­ся на (0, 7) Ответ - 2

Чертёжнику был дан для ис­пол­не­ния сле­ду­ю­щий ал­го­ритм: Сме­стить­ся на (−1,1) По­вто­ри 4 раз Сме­стить­ся на (3,1) Сме­стить­ся на (0, 2) Сме­стить­ся на (−1, 4) конец   На какую ко­ман­ду можно за­ме­нить этот ал­го­ритм?   1) Сме­стить­ся на (8, 28) 2) Сме­стить­ся на (7, 29) 3) Сме­стить­ся на (−8, −28) 4) Сме­стить­ся на (−7, −29) Ответ-2

Чертёжнику был дан для исполнения следующий алгоритм: Сместиться на (3,-3) Повтори N раз Сместиться на (27, 17) Сместиться на (a, b) конец Сместиться на (–27, –17) Чему должно равняться N, чтобы Чертежник смог вернуться в исходную точку, из которой он начал движение? 4 2) 5 3) 6 4) 7 Общий делитель 24 и 20 будет 2 и 4. Из предложенных вариантов ответа подходит 1

Источники для подготовки к ЕГЭ Образовательный портал для подготовки к экзаменам «Решу ЕГЭ» http://inf.reshuege.ru/ Сайт Константина Полякова http://kpolyakov.spb.ru/ ФИПИ – открытый банк заданий http://www.fipi.ru/ http://cdosh46.ru/video-uroki.html

Спасибо за внимание! Удачи на экзаменах!