Тема 14. Алгоритмы для исполнителей

Тип 1. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

нашлось (v)

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (18) ИЛИ нашлось (288) ИЛИ нашлось (3888)

ЕСЛИ нашлось (18)

ТО заменить (18, 2)

ИНАЧЕ

ЕСЛИ нашлось (288)

ТО заменить (288, 3)

ИНАЧЕ заменить (3888, 1)

КОНЕЦ ЕСЛИ

КОНЕЦ ЕСЛИ

КОНЕЦ ПОКА

КОНЕЦ

Какая строка получится в результате применения этой программы к строке, состоящей из цифры 1, за которой следуют 80 идущих подряд цифр 8? В ответе запишите полученную строку.

Тип 2. Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.

заменить (v, w)

нашлось (v)

Дана программа для исполнителя Редактор:

НАЧАЛО

ПОКА нашлось (444) ИЛИ нашлось (888)

ЕСЛИ нашлось (444)

ТО заменить (444, 8)

КОНЕЦ ЕСЛИ

ПОКА нашлось (555)

заменить (555, 8)

КОНЕЦ ПОКА

ПОКА нашлось (888)

заменить (888, 3)

КОНЕЦ ПОКА

КОНЕЦ ПОКА

КОНЕЦ

Дана строка, состоящая из 21 цифры, причем первые девять цифр – четверки, а остальные – пятерки. Какая строка получится в результате применения программы к данной строке?

Тип 3. Исполнитель Чертёжник перемещается на координатной плоскости, оставляя след в виде линии. Чертёжник может выполнять команду Сместиться на (a, b) (где a, b – целые числа), перемещающую Чертёжника из точки с координатами (x, y) в точку с координатами (x + a, y + b). Чертёжнику был дан для исполнения следующий алгоритм.

Сместиться на (1, -3)

Повтори... раз

Сместиться на (..., …)

Сместиться на (-1, -2)

конец

Сместиться на (-25, -33)

После выполнения этого алгоритма Чертёжник возвращается в исходную точку. Какое наибольшее число повторений могло быть указано в конструкции «Повтори … раз»?

Тип 4. Роботу был дан для исполнения алгоритм, в котором N > 1; А и В – целые числа.

НАЧАЛО

ВПРАВО 24

ПОВТОРИ N РАЗ

ВНИЗ 13

ВПРАВО А

ВНИЗ В

ВВЕРХ 28

ВНИЗ 15

КОНЕЦ ПОВТОРИ

ВНИЗ 13

КОНЕЦ

Укажите наименьшее возможное N, для которого найдутся такие А и В, что Робот после выполнения алгоритма окажется на 5 клеток ниже исходной.

Тип 5. Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F1)?

A	B	C	D	E	F

ПОКА снизу свободно ИЛИ справа свободно

ПОКА снизу свободно

Вниз

КОНЕЦ ПОКА

Вправо

КОНЕЦ ПОКА

Тип 6. Сколько клеток приведенного лабиринта соответствуют требованию, что, выполнив предложенную ниже программу, РОБОТ уцелеет и остановится в той же клетке, с которой он начал движение?

A	B	C	D	E	F

НАЧАЛО

ПОКА <сверху свободно> вправо

ПОКА <справа свободно> вниз

ПОКА <снизу свободно> влево

ПОКА <слева свободно> вверх

КОНЕЦ

Тема 15. Поиск путей.

Тип 1. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей, ведущих из города А в город М и проходящих через город В?

Тип 2. На рисунке – схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город К?

Тема 16. Системы счисления

Тип 1. Укажите через запятую в порядке возрастания все основания систем счисления, в которых запись числа 40 оканчивается на 4.

Тип 2. Укажите, сколько всего раз встречается цифра 3 в записи чисел 19, 20, 21, …, 33 в системе счисления с основанием 6

Тип 3. Укажите наименьшее основание системы счисления, в которой запись числа 70 трехзначна.

Тип 4. В системе счисления с некоторым основанием десятичное число 144 записывается в виде 264. Укажите это основание.

Тип 5. Запись числа 256 в системе счисления с основанием N содержит 3 цифры и оканчивается на 4. Чему равно минимально возможное основание системы счисления?

Тип 6. Решите уравнение . Ответ запишите в шестеричной системе счисления. Основание системы счисления указывать не нужно.

Тип 7. Значение арифметического выражения: 9⁸ + 3⁵ – 9 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?

Тип 8. Сколько значащих нулей в двоичной записи числа 4⁵¹² + 8⁵¹² – 2¹²⁸ – 250

Тема 17. Теория множества

Тип 1. В таблице приведены запросы к поисковому серверу. Расположите обозначения запросов в порядке возрастания количества страниц, которые найдет поисковый сервер по каждому запросу.

А) реферат | математика | Гаусс

Б) реферат | математика | Гаусс | метод

В) реферат | математика

Г) реферат & математика & Гаусс

Тип 2. Некоторый сегмент сети Интернет состоит из 1000 сайтов. Поисковый сервер в автоматическом режиме составил таблицу ключевых слов для сайтов этого сегмента. Вот ее фрагмент

Ключевое слово	Количество сайтов, для которых данное слово является ключевым
сомики	250
меченосцы	200
гуппи	500

Сколько сайтов будет найдено по запросу

сомики | меченосцы | гуппи

если по запросу сомики & гуппи было найдено 0 сайтов, по запросу
сомики & меченосцы – 20, а по запросу меченосцы & гуппи – 10.

 

Тип 3. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета:

Запрос	Количество страниц (тыс.)
декабрь & январь & февраль	113
декабрь & январь	225
декабрь & (январь | февраль)	645

Сколько страниц (в тысячах) будет найдено по запросу декабрь & февраль

Тип 4. В таблице приведены запросы и количество страниц, которые нашел поисковый сервер по этим запросам в некотором сегменте Интернета

Запрос	Количество страниц (тыс.)
(галера | бриг & фрегат) & корвет	620
галера & корвет	560
фрегат & галера & корвет & бриг	70

Сколько страниц (в тысячах) будет найдено по запросу

корвет & бриг & фрегат