В одном из буддийских монастырей монахи уже тысячу лет занимаются перекладыванием колец. Они располагают тремя пирамидами, на которых надеты кольца разных размеров. В начальном состоянии 64 кольца были надеты на первую пирамиду и упорядочены по размеру. Монахи должны переложить все кольца с первой пирамиды на третью, выполняя единственное условие кольцо нельзя положить на кольцо меньшего размера. При перекладывании можно использовать все три пирамиды. Монахи перекладывают одно кольцо за одну секунду. Как только они закончат свою работу, наступит конец света. 1

Количество перекладываний в зависимости от количества колец вычисляется по формуле 2 n 1. Для 64-х колец это перекладываний, и, если принять скорость "одно перекладывание в секунду", получится около лет, то есть, апокалипсис наступит нескоро. 2

Учитель информатики Курочкина А. З. Сорокинская СОШ 1 Тюменская область 3

А5 (базовый уровень, время – 2 мин) 1).Определите значение переменной c после выполнения следующего фрагмента программы. a := 5; a := a + 6; b := –a; c := a – 2*b; 1) c = –112) c = 153) c = 274) c = 33 Решение. 4 a := 5; a := a + 6; 5 11 b := –a; -11 c := a – 2*b;33 abc Правильный ответ: 4) c=33

5 А5 (базовый уровень, время – 2 мин) 2).Определите значение целочисленных переменных a и b после выполнения фрагмента программы: a := 1819; b := (a \100)*10+9; a := (10*b–a) mod 100; 1)a = 81, b = 1992) a = 81, b = 189 3) a = 71, b = 199 4) a = 71, b = 189 Правильный ответ: 4)a =71,b=189

6 А5 (базовый уровень, время – 2 мин) 3).Определите значение целочисленных переменных a и b после выполнения фрагмента программы: a := 42; b := 14; a := a \b; b := a*b; a := b \ a; 1)a = 42, b = 142) a = 1, b = 42 3) a = 0, b = 5884) a = 14, b = 42 Правильный ответ: 4)a =14,b=42

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

Решение 8 1. легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движение, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо: на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно; 2. кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода; 3. итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки- кандидаты: ABCDEF

Решение 9 4. этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют: ABCDEF

Решение проверяем оставшиеся три клетки-кандидаты, но для них всех после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал: итак, условию удовлетворяет только одна клетка – F4 таким образом, правильный ответ – 1. итак, условию удовлетворяет только одна клетка – F4 таким образом, правильный ответ – 1.

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

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

13 B2 (базовый уровень, время – 1 мин) 1). Запишите значение переменной b после выполнения фрагмента алгоритма: a:=a*2; b:=b+a; a:=1; b:=1; a = 256? да нет a1 b … Правильный ответ: b= 511

14 2). Определите значения переменных m после выполнения фрагмента алгоритма. m:=54; n:=16; m = n? да нет m > n? да m:=m-n; нет n:=n-m; B2 (базовый уровень, время – 1 мин) Правильный ответ: m=2

15 3). Определите значения переменных x и y после выполнения фрагмента алгоритма. B2 (базовый уровень, время – 1 мин) x:=10; y:=15; y < 16? нет да x

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

прибавь 3 2. умножь на 4 Число команд не более 6. > Правильный ответ: … 24 2 … 15 1 … Решение (вариант 1, «прямой ход»): 3 57

18 Правильный ответ: Решение (вариант 2, «обратный ход»): 1)57:4=не делится нацело. Значит, 57-3=54. Команда 1. 2)54:4=не делится нацело. Значит, 54-3=51. Команда 1. 3)51:4=не делится нацело. Значит, 51-3=48. Команда 1. 4)48:4=12. Команда 2. 5)12:4=3. Команда 2. 6)Поскольку мы шли в обратном порядке, записываем результат с конца в начало. 1. прибавь 3 2. умножь на 4 Число команд не более 6.

19 B5 (повышенный уровень, время – 10 мин) 2) У исполнителя Утроитель две команды, которым присвоены номера: 1. вычти 2 2. умножь на три Первая из них уменьшает число на экране на 2, вторая – утраивает его. Запишите порядок команд в программе получения из 11 числа 13, содержащей не более 5 команд, указывая лишь номера команд. (Например, – это программа: умножь на три вычти 2 умножь на три вычти 2 вычти 2, которая преобразует число 2 в 8). (Если таких программ более одной, то запишите любую из них.) Правильный ответ: 11121

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

21

22

23 А5 (базовый уровень, время – 2 мин) 4).Определите значение целочисленных переменных х, y и t после выполнения фрагмента программы: x := 5; y := 7; t := x; x := y mod x; y := t; 1)x=2, y=5, t=52) x=7, y=5, t=5 3) x=2, y=2, t=24) x=5, y=5, t=5 Правильный ответ: 1)x =2,y=5,t=5

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

25 3). Определите значение переменной х после выполнения фрагмента алгоритма. B2 (базовый уровень, время – 1 мин) x:=55; y:=75; x y? нет да x > y? нет y:=y-x ; да x:=x-y; Правильный ответ: x=5

26 B5 (повышенный уровень, время – 10 мин) 3) У исполнителя Калькулятор две команды, которым присвоены номера: 1. прибавь 2 2. умножь на 3 Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, утраивает его. Запишите порядок команд в программе получения из 0 числа 28, содержащей не более 6 команд, указывая лишь номера команд. (Например, программа – это программа: умножь на 3 прибавь 2 умножь на 3 прибавь 2 прибавь 2, которая преобразует число 1 в 19). Правильный ответ:

27 Имеется исполнитель Кузнечик, который живет на числовой оси. Система команд Кузнечика: Вперед N (Кузнечик прыгает вперед на N единиц); Назад M (Кузнечик прыгает назад на M единиц). Переменные N и M могут принимать любые целые положительные значения. Известно, что Кузнечик выполнил программу из 50 команд, в которой команд Назад 2 на 12 больше, чем команд Вперед 3. Других команд в программе не было. На какую одну команду можно заменить эту программу, чтобы Кузнечик оказался в той же точке, что и после выполнения программы?