Информатика ЕГЭ - банк заданий - страница 139

Миша заполнял таблицу истинности функции (¬x /\ ¬y) \/ (x≡z) \/ w, но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

Определите, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.

В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала буква, соответствующая первому столбцу; затем буква, соответствующая второму столбцу, и т.д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.

На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).

Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова сумма протяжённостей дорог из пункта F в пункт E и из пункта B в пункт D.

В ответе запишите целое число.

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. Далее эта запись обрабатывается по следующему правилу:

а) если число N делится на 3, то к этой записи дописываются три последние двоичные цифры;

б) если число N на 3 не делится, то остаток от деления умножается на 3, переводится в двоичную запись и дописывается в конец числа.

Полученная таким образом запись является двоичной записью искомого числа R.

3. Результат переводится в десятичную систему и выводится на экран.

Например, для исходного числа 12 = 1100₂ результатом является число 1100100₂ = 100, а для исходного числа 4 = 100₂ это число 10011₂ = 19.

Укажите минимальное число R, большее 151, которое может быть получено с помощью описанного алгоритма. В ответе запишите это число в десятичной системе счисления.

Определите количество восьмеричных пятизначных чисел, которые не начинаются с нечётных цифр, не оканчиваются цифрами 2 или 6, а также содержат не более двух цифр 7.

На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.

1. Строится двоичная запись числа N.

2. К этой записи дописываются справа и слева ещё по одному или два разряда по следующему правилу: если N чётное, то в конец числа (справа) дописывается нуль, а в начало числа (слева) дописывается единица; если N нечётное, то в конец числа (справа) и в начало числа (слева) дописываются по две единицы.

Например, для числа 13 двоичная запись 1101 преобразуется в запись 11110111.

Полученная таким образом запись (в ней на два или четыре разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.

Укажите наименьшее число R, превышающее 225, которое может являться результатом работы данного алгоритма. В ответе это число запишите в десятичной системе счисления.

Какой минимальный объём памяти (в Кбайт) нужно зарезервировать, чтобы можно было сохранить любое растровое изображение размером 640×320 пикселей при условии, что в изображении могут использоваться 64 различных цвета? Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Искомый объём не учитывает размера заголовка файла. В ответе запишите только целое число, единицу измерения писать не нужно.

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделенной на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов А = {a0, a1, …, an-1}), включая специальный пустой символ а0. Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из состояний из множества допустимых состояний Q = {q0, q1, …, qn-1}. В начальный момент времени головка исполнителя находится в начальном состоянии q0.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остается в прежнем состоянии.

Программа работы исполнителя МТ задается в табличном виде.

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце

возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает

j-й символ, находясь в і-м состоянии. Если пара «символ - состояние» невозможна,

то клетка для команды остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент — записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент - один из четырёх символов «L», «R», «N», ‹S».

Символы «L» и «R› означают сдвиг в левую или правую ячейки соответственно, «N> - отсутствие сдвига, «S» - завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент - новое состояние головки после выполнения команды. Например, команда 0, L, qз выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние qз.

Приведём пример выполнения программы, заданной таблично.

На ленте записано неизвестное ненулевое количество расположенных подряд

в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «дельта». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «Z».

Программа заменяет на ленте все символы «Z› на «Х› и останавливает исполнителя в первой ячейке слева от последовательности символов «Х»

Возможное начальное состояние исполнителя: 

Конечное состояние исполнителя после завершения выполнения программы: 

Выполните задание.

На ленте в соседних ячейках записана последовательность из 520 символов,

включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «дельта». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 125 нулей. Определите максимально возможное число нулей в исходной последовательности

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделенной на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов А = {a0, a1, …, an-1}), включая специальный пустой символ а0. Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из состояний из множества допустимых состояний Q = {q0, q1, …, qn-1}. В начальный момент времени головка исполнителя находится в начальном состоянии q0.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остается в прежнем состоянии.

Программа работы исполнителя МТ задается в табличном виде.

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце

возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает

j-й символ, находясь в і-м состоянии. Если пара «символ - состояние» невозможна,

то клетка для команды остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент — записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент - один из четырёх символов «L», «R», «N», ‹S».

Символы «L» и «R› означают сдвиг в левую или правую ячейки соответственно, «N> - отсутствие сдвига, «S» - завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент - новое состояние головки после выполнения команды. Например, команда 0, L, qз выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние qз.

Приведём пример выполнения программы, заданной таблично.

На ленте записано неизвестное ненулевое количество расположенных подряд

в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «дельта». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «Z».

Программа заменяет на ленте все символы «Z› на «Х› и останавливает исполнителя в первой ячейке слева от последовательности символов «Х»

Возможное конечное состояние исполнителя

Выполните задание.

На ленте в соседних ячейках записана последовательность из 333 символов,

включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «дельта». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 125 нулей. Определите максимально возможное число нулей в исходной последовательности

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделенной на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов А = {a0, a1, …, an-1}), включая специальный пустой символ а0. Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из состояний из множества допустимых состояний Q = {q0, q1, …, qn-1}. В начальный момент времени головка исполнителя находится в начальном состоянии q0.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остается в прежнем состоянии.

Программа работы исполнителя МТ задается в табличном виде.

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце

возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает

j-й символ, находясь в і-м состоянии. Если пара «символ - состояние» невозможна,

то клетка для команды остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент — записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент - один из четырёх символов «L», «R», «N», ‹S».

Символы «L» и «R› означают сдвиг в левую или правую ячейки соответственно, «N> - отсутствие сдвига, «S» - завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент - новое состояние головки после выполнения команды. Например, команда 0, L, qз выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние qз.

Приведём пример выполнения программы, заданной таблично.

На ленте записано неизвестное ненулевое количество расположенных подряд

в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «дельта». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «Z».

Программа заменяет на ленте все символы «Z› на «Х› и останавливает исполнителя в первой ячейке слева от последовательности символов «Х»

Возможное конечное состояние исполнителя

Выполните задание.

На ленте в соседних ячейках записана последовательность из 520 символов, включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «дельта». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 125 нулей. Определите минимально возможное число нулей в исходной последовательности

Исполнитель МТ представляет собой читающую и записывающую головку, которая может передвигаться вдоль бесконечной горизонтальной ленты, разделенной на равные ячейки. В каждой ячейке находится ровно один символ из алфавита исполнителя (множество символов А = {a0, a1, …, an-1}), включая специальный пустой символ а0. Время работы исполнителя делится на дискретные такты (шаги). На каждом такте головка МТ находится в одном из состояний из множества допустимых состояний Q = {q0, q1, …, qn-1}. В начальный момент времени головка исполнителя находится в начальном состоянии q0.

На каждом такте головка обозревает одну ячейку ленты, называемую текущей ячейкой. За один такт головка исполнителя может переместиться в ячейку справа или слева от текущей, не меняя находящийся в ней символ, или заменить символ в текущей ячейке без сдвига в соседнюю ячейку. После каждого такта головка переходит в новое состояние или остается в прежнем состоянии.

Программа работы исполнителя МТ задается в табличном виде.

В первой строке перечислены все возможные символы в текущей ячейке ленты, в первом столбце

возможные состояния головки. На пересечении i-й строки и j-го столбца находится команда, которую выполняет МТ, когда головка обозревает

j-й символ, находясь в і-м состоянии. Если пара «символ - состояние» невозможна,

то клетка для команды остаётся пустой.

Каждая команда состоит из трёх элементов, разделённых запятыми: первый элемент — записываемый в текущую ячейку символ алфавита (может совпадать с тем, который там уже записан). Второй элемент - один из четырёх символов «L», «R», «N», ‹S».

Символы «L» и «R› означают сдвиг в левую или правую ячейки соответственно, «N> - отсутствие сдвига, «S» - завершение работы исполнителя МТ после выполнения текущей команды. Сдвиг происходит после записи символа в текущую ячейку. Третий элемент - новое состояние головки после выполнения команды. Например, команда 0, L, qз выполняется следующим образом: в текущую ячейку записывается символ «0», затем головка сдвигается в соседнюю слева ячейку и переходит в состояние qз.

Приведём пример выполнения программы, заданной таблично.

На ленте записано неизвестное ненулевое количество расположенных подряд

в соседних ячейках символов «Z», все остальные ячейки ленты заполнены пустым символом «дельта». В начальный момент времени головка находится на неизвестном ненулевом расстоянии справа от самого правого символа «Z».

Программа заменяет на ленте все символы «Z› на «Х› и останавливает исполнителя в первой ячейке слева от последовательности символов «Х»

Возможное конечное состояние исполнителя

Выполните задание.

На ленте в соседних ячейках записана последовательность из 333 символов,

включающая только нули и единицы. Ячейки справа и слева от последовательности заполнены пустыми символами «дельта». В начальный момент времени головка расположена в ближайшей ячейке справа от последовательности.

Программа работы исполнителя:

После выполнения программы на ленте осталось ровно 137 нулей. Определите минимально возможное число нулей в исходной последовательности