1.Между населёнными пунктами А, В, С, D, Е, F построены дороги, протяжённость которых приведена в таблице. (Отсутствие числа в таблице означает, что прямой дороги между пунктами нет.)
A
B
C
D
E
F
A
B
C
D
E
F
Определите длину кратчайшего пути между пунктами А и F (при условии, что передвигаться можно только по построенным дорогам).
2.Логическая функция F задаётся выражением x ∧ y ∧ (z ∨ w). На рисунке приведён фрагмент таблицы истинности функции F, содержащий все наборы аргументов, при которых функция F истинна. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.
Перем. 1
Перем. 2
Перем. 3
Перем. 4
Функция
???
???
???
???
F
В ответе напишите буквы w, x, y, z в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.) Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Если бы функция была задана выражением x ∨ y, зависящим от двух переменных: x и y, и был приведён фрагмент её таблицы истинности, содержащий все наборы аргументов, при которых функция F истинна.
Перем. 1
Перем. 2
Функция
???
???
F
Тогда первому столбцу соответствовала бы переменная y, а второму столбцу — переменная x. В ответе следовало бы написать: yx.
3.Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID дяди Степаненко Т. Л.
Пояснение: дядей считается родной брат отца или матери.
Таб. 1
ID
Фамилия_И.О.
Пол
Леоненко М.Д.
Ж
Грант А.Б
М
Грант Б.А.
М
Грант Б.Б.
М
Степаненко З.А.
Ж
Степаненко Т.Л.
Ж
Степаненко Л.Л.
М
Кривец Д.Н.
Ж
Кривец Р.Д.
М
Колос Е.Л.
Ж
Колос А.Е.
М
Кроха М.Б.
Ж
Волченко Т.Д.
Ж
Таблица 2
ID_Родителя
ID_Ребенка
4.Для кодирования букв И, Д, Т, О, X решили использовать двоичное представление чисел 0, 1, 2, 3 и 4 соответственно (с сохранением одного незначащего нуля в случае одноразрядного представления). Закодируйте последовательность букв ТИХОХОД таким способом и результат запишите шестнадцатеричным кодом.
5.Автомат обрабатывает натуральное число N по следующему алгоритму:
1. Строится двоичная запись числа N.
2. В конец записи (справа) добавляется (дублируется) последняя цифра.
3. Складываются все цифры полученной двоичной записи. В конец записи (справа) дописывается остаток от деления суммы на 2.
4. Результат переводится в десятичную систему и выводится на экран.
Пример. Дано число N = 13. Алгоритм работает следующим образом:
1. Двоичная запись числа N: 1101.
2. Дублируется последняя цифра, новая запись 11011.
3. Сумма цифр полученной записи 4, остаток от деления на 2 равен 0, новая запись 110110.
4. На экран выводится число 54.
Какое наименьшее число, большее 105, может появиться на экране в результате работы автомата?
6.Определите, что будет напечатано в результате выполнения программы (записанной ниже на разных языках программирования).
Паскаль
var n, s: integer;
begin
n := 0;
s := 1;
while s <= 1000 do
begin
s := s * 3;
n := n + 3;
end;
write(n)
end.
7.Автоматическая камера производит растровые изображения размером 600 на 1000 пикселей. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Объём файла с изображением не может превышать 250 Кбайт без учёта размера заголовка файла. Какое максимальное количество цветов можно использовать в палитре?
8.Некоторый алфавит содержит пять различных букв. Сколько трёхбуквенных слов можно составить из букв данного алфавита (буквы в слове могут повторяться)?
9.Откройте файл электронной таблицы, содержащей вещественные числа — результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев.
Задание 9
Найдите количество значений, которые выше округленного до десятых среднего значения всех чисел таблицы, но меньше 30 °С.
10.С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «она» или «Она» в тексте романа в стихах А. С. Пушкина «Евгений Онегин». Другие формы слова «она» учитывать не следует. В ответе укажите только число.
Задание 10
11.При регистрации на сервере каждый пользователь получает уникальный персональный код, состоящий из 17 символов, каждый из которых может быть одной из 26 заглавных латинских букв или одной из 10 цифр. При этом в базе данных сервера формируется запись, содержащая этот код и дополнительную информацию о пользователе. Для представления кода используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством битов, а для кода в целом выделяется минимально возможное целое количество байтов. Для хранения данных о 30 пользователях потребовалось 2400 байт.
Сколько байтов выделено для хранения дополнительной информации об одном пользователе? В ответе запишите только целое число — количество байтов.
12.Исполнитель Редактор получает на вход строку цифр и преобразует её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 101 единиц?
НАЧАЛО
ПОКА нашлось (1111)
заменить (1111, 22)
заменить (222, 1)
КОНЕЦ ПОКА
КОНЕЦ
13.На рисунке – схема дорог, связывающих пункты А, Б, В, Г, Д, Е, Ж, И, К, Л, М, Н, П.
Сколько существует различных путей из пункта А в пункт П, не проходящих через пункт Е?
14.Значение арифметического выражения 97 + 321 – 9 записали в системе счисления с основанием 3. Сколько цифр «2» содержится в этой записи?
15.Элементами множеств А, P, Q являются натуральные числа, причём P = {1, 3, 5, 7, 9, 11, 13, 15, 17, 19, 21}, Q = {3, 6, 9, 12, 15, 18, 21, 24, 27, 30}. Известно, что выражение
((x ∈ P) → (x ∈ A)) ∨ ((x ∈ A) → (x ∈ Q))
истинно (т. е. принимает значение 1) при любом значении переменной х. Определите наименьшее возможное значение суммы элементов множества A.
17.Рассматривается множество целых чисел, принадлежащих числовому отрезку [1721; 4322], которые делятся на 3 и 11 и не делятся на 5, 9, 13, 22. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа без пробелов и других дополнительных символов: сначала количество, затем максимальное число.
Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц.
18.Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вверх. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вверх — в соседнюю верхнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Задание 18
Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой нижней клетки в правую верхнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
Для указанных входных данных ответом должна быть пара чисел 35 и 15.
22.Ниже на пяти языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 13, а потом 5.
Паскаль
var x, a, b, c: integer;
begin
readln(x);
a := 0; b := 10;
while x>0 do
begin
с := x mod 10;
a := a+c;
if c < b then b := c;
x := x div 10;
end;
writeln(a); write(b);
end.
24.Текстовый файл состоит не более чем из 106 символов L, D и R. Определите длину самой длинной последовательности, состоящей из символов R. Хотя бы один символ R находится в последовательности.
Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.
Задание 24
25.Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [110203; 110245], числа, имеющие ровно четыре различных чётных натуральных делителя. Для каждого найденного числа запишите эти четыре делителя в четыре соседних столбца на экране с новой строки. Делители в строке должны следовать в порядке возрастания.
Например, в диапазоне [2; 16] ровно четыре чётных различных натуральных делителя имеют числа 12 и 16, поэтому для этого диапазона вывод на экране должна содержать следующие значения:
2 4 6 12
2 4 8 16
26.Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные.
Задание 26
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 4000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера:
