Выполнение алгоритмов для исполнителя (А18)

Слайд #1

Тема: Выполнение алгоритмов для исполнителя. (A18) Выполнила: Н.Н.Севрюкова, учитель информатики с.Богучаны, Красноярского края

Слайд #2

Задача 1: Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: вверх вниз влево вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно снизу свободно слева свободно справа свободно Цикл ПОКА команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение? 1) 1 2) 2 3) 3 4) 0 НАЧАЛО ПОКА вниз ПОКА влево ПОКА вверх ПОКА вправо КОНЕЦ

Слайд #3

НАЧАЛО КОНЕЦ ПОКА вниз ПОКА вправо ПОКА влево ПОКА вверх

Слайд #4

НАЧАЛО КОНЕЦ ПОКА вверх ПОКА вниз ПОКА влево ПОКА вправо

Слайд #5

Слайд #6

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

Слайд #7

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

Слайд #8

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

Слайд #9

Задача 2 Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: вверх вниз влево вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: сверху свободно снизу свободно слева свободно справа свободно 654321ABCDEF Цикл ПОКА команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет (не врежется в стену) и остановится в той же клетке, с которой он начал движение? 1) 1 2) 2 3) 3 4) 0 НАЧАЛО ПОКА вверх ПОКА вправо ПОКА вниз ПОКА влево КОНЕЦ

Слайд #10

НАЧАЛО КОНЕЦ ПОКА вверх ПОКА влева ПОКА вправо ПОКА вниз

Слайд #11

Слайд #12

Тема: Поиск алгоритма минимальной длины для исполнителя.

Слайд #13

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

Слайд #14

из числа 3 числа 57 «обратный ход»: 1. прибавь 3 2. умножь на 4 22111 Ответ: 22111 Ответ:

Слайд #15

Задача Исполнитель Робот действует на клетчатой доске, между соседними клетками которой могут стоять стены. Робот передвигается по клеткам доски и может выполнять команды 1 (вверх), 2 (вниз), 3 (вправо) и 4 (влево), переходя на соседнюю клетку в направлении, указанном в скобках. Если в этом направлении между клетками стоит стена, то Робот разрушается. Робот успешно выполнил программу 3233241 Какую последовательность из трех команд должен выполнить Робот, чтобы вернуться в ту клетку, где он был перед началом выполнения программы, и не разрушиться вне зависимости от того, какие стены стоят на поле?

Слайд #16

Нарисуем 3233241 1 (вверх), 2 (вниз), 3 (вправо), 4 (влево) 144 Ответ: 414 441

Слайд #17

Задача У исполнителя, который работает с положительными однобайтовыми двоичными числами, две команды, которым присвоены номера: 1. сдвинь влево 2. вычти 1 Выполняя первую из них, исполнитель сдвигает число на один двоичный разряд влево, а выполняя вторую, вычитает из него 1. Исполнитель начал вычисления с числа 104 и выполнил цепочку команд 11221. Запишите результат в десятичной системе.

Слайд #18

«сдвиг влево» бит переноса 0 0 1 0 1 1 0 1 0 =90 «* 2» «сдвиг влево» «* 2» «сдвиг вправо» «/ 2»

Слайд #19

число 104 выполнил цепочку команд 11221 1. сдвинь влево 2. вычти 1 умножь на 2 208 1 1 Умножить на 2 mod 208*2 на 256 160 Вычти 1 2 159 2 Вычти 1 2 159 Вычти 1 2 158 Вычти 1 2 1 Умножить на 2 mod 158*2 на 256 60

Слайд #20

Слайд #21

Задача В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные a, b, c имеют тип «строка», а переменные i, k – тип «целое». Используются следующие функции: Длина(a) – возвращает количество символов в строке a. (Тип «целое») Извлечь(a,i) – возвращает i-тый (слева) символ в строке a. (Тип «строка») Склеить(a,b) – возвращает строку, в которой записаны сначала все символы строки a, а затем все символы строки b. (Тип «строка») Значения строк записываются в одинарных кавычках (Например, a:='дом'). Фрагмент алгоритма: i := Длина(a) k := 2 b := 'А' пока i > 0 нц c := Извлечь(a,i) b := Склеить(b,c) i := i – k кц b := Склеить(b,'Т') Какое значение будет у переменной b после выполнения вышеприведенного фрагмента алгоритма, если значение переменной a было ‘ПОЕЗД’? 1) ‘АДЕПТ’ 2) ‘АДЗЕОП’ 3) ‘АДТЕТПТ’ 4) ‘АДЗОТ’

Слайд #22

‘ПОЕЗД’ i := Длина(a) k := 2 b := «А» пока i > 0 нц c := Извлечь(a,i) b := Склеить(b,c) i := i – k кц b := Склеить(b,'Т')

Слайд #23

i:=Длина(a) 5 k:=2 2 b:=«А» «А» i > 0? ДА c:=Извлечь(a,i) i:=Длина(a) 5 b:=Cклеить(b,c) «АД» i > 0? ДА i:=i–k 3 c:=Извлечь(a,i) «Е» b:=Cклеить(b,c) «АД» b:=Cклеить(b,c) «АДЕ» 1) ‘АДЕПТ’ 2) ‘АДЗЕОП’ 3) ‘АДТЕТПТ’ 4) ‘АДЗОТ’ 1) ‘АДЕПТ’ 2) ‘АДЗЕОП’ 3) ‘АДТЕТПТ’ 1) ‘АДЕПТ’ 2) ‘АДЗЕОП’ 3) ‘АДТЕТПТ’ 1) ‘АДЕПТ’ 2) ‘АДЗЕОП’ 4) ‘АДЗОТ’ 3) ‘АДТЕТПТ’ 1) ‘АДЕПТ’ 2) ‘АДЗЕОП’

Слайд #24

Материалы: http://kpolyakov.narod.ru/school/ege.htm