Вверх вниз влево вправо.При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: Сверху свободно снизу свободно слева свободно справа свободно
Цикл ПОКА < условие >; Последовательность команд КОНЕЦ ПОКА выполняется, пока условие истинно. В конструкции ЕСЛИ < условие >; ТО команда1 ИНАЧЕ команда2 КОНЕЦ ЕСЛИ выполняется команда1 (если условие истинно) или команда2 (если условие ложно). Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся. Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)? 1) 8 2) 15 3) 24 4) 27
НАЧАЛО ПОКА < справа свободно ИЛИ снизу свободно >; ПОКА < справа свободно >; Вправо КОНЕЦ ПОКА ПОКА < снизу свободно >; Вниз КОНЕЦ ПОКА КОНЕЦ ПОКА КОНЕЦ Решение: 1) обратим внимание, что в программе три цикла, причем два внутренних цикла вложены в один внешний 2) цикл ПОКА < справа свободно >; Вправо КОНЕЦ ПОКА означает «двигаться вправо до упора», а цикл ПОКА < снизу свободно >; Вниз КОНЕЦ ПОКА означает «двигаться вниз до упора» 3) тогда программу можно записать в свободном стиле так: ПОКА не пришли в угол Двигаться вправо до упора Двигаться вниз до упора КОНЕЦ ПОКА где угол – это клетка, в которой есть стенки снизу и справа 4) за каждый шаг внешнего цикла Робот проходит путь в виде «сапога», двигаясь сначала вправо до упора, а затем – вниз до упора:
клетка, выделенная красным фоном особая – в ней заканчивается один шаг внешнего цикла и начинается следующий: а) Робот может попасть в эту клетку, двигаясь вниз из клетки, где справа – стенка б) снизу есть стенка; в) снизу стенка есть, справа – нет, поэтому будет выполнен еще один шаг внешнего цикла. 5) в клетку F6 (это угол, где Робот остановился), Робот мог придти за один шаг внешнего цикла (за один «сапог») только из отмеченных клеток:
6) теперь отметим красным фоном особые клетки, которые удовлетворяют условиям а-в пункта 4 (см. выше), их всего 2:
7) отметим все пути в форме «сапога», которые приводят в особые клетки:
8) больше особых клеток (см. пункт 4) нет; всего отмечено 24 клетки (считая конечную клетку F6) 9) таким образом, правильный ответ – 3.
Еще пример задания:
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости: Вверх вниз влево вправо. При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх ↑, вниз ↓, влево ←, вправо →. Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ: Сверху свободно снизу свободно слева свободно справа свободно Цикл ПОКА <условие> команда выполняется, пока условие истинно, иначе происходит переход на следующую строку. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ остановится в той же клетке, с которой он начал движение? 1) 1 2) 2 3) 3 4) 0 НАЧАЛО ПОКА <снизу свободно> вниз ПОКА <слева свободно> влево ПОКА <сверху свободно> вверх ПОКА <справа свободно> вправо КОНЕЦ Решение: 1) легко понять, что для того, чтобы исполнитель вернулся обратно в ту клетку, откуда он начал движения, четыре стенки должны быть расставлены так, чтобы он упирался в них сначала при движении вниз, затем – влево, вверх и, наконец, вправо: на рисунке красная точка обозначает клетку, начав с которой РОБОТ вернется обратно; 2) кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке справа зеленым фоном, был свободен для прохода 3) обратим внимание, что возможны еще «вырожденные» варианты, вроде таких: 4) итак, мы выяснили, что нужно рассматривать лишь те клетки, где есть стенка справа; отметим на исходной карте клетки-кандидаты:
5) этих «подозрительных» клеток не так много, но можно еще сократить количество рассматриваемых вариантов: если РОБОТ начинает движение с любой клетки на вертикали F, он все равно приходит в клетку F4, которая удовлетворяет заданному условию, таким образом, одну клетку мы нашли, а остальные клетки вертикали F условию не удовлетворяют:
6) проверяем оставшиеся четыре клетки-кандидаты, но для каждой из них после выполнения алгоритма РОБОТ не приходит в ту клетку, откуда он стартовал:
7) итак, условию удовлетворяет только одна клетка – F4 8) таким образом, правильный ответ – 1.
Еще пример задания:
Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет (не врежется в стену) и остановится в той же клетке, с которой он начал движение? 1) 1 2) 2 3) 3 4) 0 НАЧАЛО ПОКА <слева свободно> вверх ПОКА <сверху свободно> вправо ПОКА <справа свободно> вниз ПОКА <снизу свободно> влево КОНЕЦ Решение: 1) особенность этой задач в том, что РОБОТ проверяет стенку в одном направлении, а движется в другом 2) рассмотрим первый цикл: ПОКА <слева свободно> вверх понятно, что при движении вверх РОБОТ остановится в первой же клетке, где слева будет стена 3) рассуждая аналогично, находим, что во втором цикле при движении вправо РОБОТ останавливается в клетке, где есть стена сверху; в третьем цикле (движение вниз) РОБОТ останавливается в клетке, где есть стена справа; 4) наконец, в четвертом цикле РОБОТ останавливается в клетке, где есть стена снизу; при этом он должен попасть обратно в исходную клетку, обозначенную на рисунке красной точкой; 5) кроме этих четырех стенок, необходимо, чтобы коридор, выделенный на рисунке зеленым фоном, был свободен для прохода, иначе РОБОТ врежется в стенку
6) теперь отметим на карте все клетки-кандидаты, где снизу есть стена:
7) при движении из клеток B5, D1, E1, E6, F1 и F3 РОБОТ врежется в стенку, потому что слева стены нет и условие «слева свободно» всегда истинно:
8) начав движение с клетки A1, C1 или C2, РОБОТ также врезается в стенку и разрушается:
9) и только путь, начатый в клетке B1, приводит РОБОТА обратно в точку старта:
10) таким образом, только клетка B1 удовлетворяет условию задачи, поэтому правильный ответ – 1. Еще пример задания: В приведенном ниже фрагменте алгоритма, записанном на алгоритмическом языке, переменные 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) ‘АДЗОТ’ B1 (базовый уровень, время – 1 мин) Тема: Кодирование текстовой информации. Кодировка ASCII. Основные кодировки кириллицы. Что нужно знать: · все символы кодируются одинаковым числом бит[††] (алфавитный подход) · чаще всего используют кодировки, в которых на символ отводится 8 бит (8-битные) или 16 бит (16-битные) · при измерении количества информации принимается, что в одном байте 8 бит, а в одном килобайте (1 Кбайт) – 1024 байта, в мегабайте (1 Мбайт) – 1024 Кбайта · после знака препинания внутри (не в конце!) текста ставится пробел · чтобы найти информационный объем текста I, нужно умножить количество символов N на число бит на символ K: · две строчки текста не могут занимать 100 Кбайт в памяти · при кодировании текста каждому символу ставится в соответствие свой код · символы-цифры в кодовой таблице идут подряд в порядке возрастания, от «0» до «9» (символ «0» имеет код 48, символ «9» – код 57) · большие (прописные) латинские буквы в кодовой таблице идут подряд в алфавитном порядке от «A» до «Z» · маленькие (строчные) латинские буквы в таблице кодировки идут подряд в алфавитном порядке, от «a» до «z» · в большинстве кодовых таблиц (но не во всех!) русские буквы, как заглавные, так и строчные, также расположены по алфавиту (за исключением буквы «Ё») Ещё пример задания: Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке длиной в 20 символов, первоначально записанного в 2-байтном коде Unicode, в 8-битную кодировку КОИ-8. На сколько бит уменьшилась длина сообщения? В ответе запишите только число. Решение: 1) при 16-битной кодировке объем сообщения – 16*20 бит 2) когда его перекодировали в 8-битный код, его объем стал равен– 8*20 бит 3) таким образом, сообщение уменьшилось на 16*20 – 8*20 = 8*20 = 160 бит 4) Ответ: 160 бит.
Ещё пример задания: Автоматическое устройство осуществило перекодировку информационного сообщения на русском языке, первоначально записанного в 16-битном коде Unicode, в 8-битную кодировку КОИ-8. При этом информационное сообщение уменьшилось на 480 бит. Какова длина сообщения в символах? Решение: 1) обозначим количество символов через N 2) при 16-битной кодировке объем сообщения – 16*N бит 3) когда его перекодировали в 8-битный код, его объем стал равен– 8*N бит 4) таким образом, сообщение уменьшилось на 16*N – 8*N = 8*N = 480 бит 5) отсюда находим N = 480/8 = 60 символов. Ещё пример задания: Определите информационный объем текста в битах Бамбарбия! Кергуду! Решение: 1) в этом тексте 19 символов (обязательно считать пробелы и знаки препинания) 2) если не дополнительной информации, считаем, что используется 8-битная кодировка (чаще всего явно указано, что кодировка 8- или 16-битная) 3) поэтому в сообщении 19*8 = 152 бита информации. B2 (базовый уровень, время – 4 мин) Тема: Поиск алгоритма минимальной длины для исполнителя. Пример задания: У исполнителя Калькулятор две команды, которым присвоены номера:
|
