Слайд 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,'Т')
Слайд 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) ‘АДЗЕОП’
