Слайд 1
Тема:
Выполнение алгоритмов для исполнителя.
(A18)
Выполнила:
Н.Н.Севрюкова, учитель информатики
с.Богучаны,
Красноярского края
Слайд 2Задача 1:
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на
клетчатой плоскости: вверх вниз влево вправо.
При выполнении любой из
этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху свободно снизу свободно
слева свободно справа свободно
Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение?
1) 1 2) 2 3) 3 4) 0
НАЧАЛО
ПОКА <снизу свободно> вниз
ПОКА <слева свободно> влево
ПОКА <сверху свободно> вверх
ПОКА <справа свободно> вправо
КОНЕЦ
Слайд 3НАЧАЛО
КОНЕЦ
ПОКА вниз
ПОКА вправо
ПОКА
влево
ПОКА вверх
Слайд 4НАЧАЛО
КОНЕЦ
ПОКА вверх
ПОКА вниз
ПОКА влево
ПОКА вправо
Слайд 9Задача 2
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на
клетчатой плоскости:
вверх вниз влево вправо.
При выполнении любой из
этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
сверху свободно снизу свободно
слева свободно справа свободно
654321ABCDEF Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет (не врежется в стену) и остановится в той же клетке, с которой он начал движение?
1) 1 2) 2 3) 3 4) 0
НАЧАЛО
ПОКА <слева свободно> вверх
ПОКА <сверху свободно> вправо
ПОКА <справа свободно> вниз
ПОКА <снизу свободно> влево
КОНЕЦ
Слайд 10
НАЧАЛО
КОНЕЦ
ПОКА вверх
ПОКА
влева
ПОКА вправо
ПОКА вниз
Слайд 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
Слайд 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,'Т')
Слайд 23i:=Длина(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