2020-05-25
208Задание 1
Укажите наименьшее четырёхзначное восьмеричное число, двоичная запись которого содержит 5 единиц. В ответе запишите только само восьмеричное число, основание системы счисления указывать не нужно.
Задание 2
Логическая функция F задаётся выражением ((x → y) ≡ (z → w)) ∨ (x ∧ w).
Дан частично заполненный фрагмент, содержащий неповторяющиеся строки таблицы истинности функции F.
Определите, какому столбцу таблицы истинности соответствует каждая из переменных x, y, z, w.
| Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
| ??? | ??? | ??? | ??? | F |
| 1 | 0 | |||
| 1 | 1 | 0 | ||
| 1 | 1 | 1 | 0 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
| Переменная 1 | Переменная 1 | Функция |
| ??? | ??? | F |
| 0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Задание 3
На рисунке справа схема дорог Н-ского района изображена в виде графа; в таблице слева содержатся сведения о протяжённости каждой из этих дорог (в километрах).
| П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
| П1 | 10 | ||||||
| П2 | 12 | ||||||
| П3 | 10 | 9 | 5 | ||||
| П4 | 10 | 5 | |||||
| П5 | 9 | 5 | 8 | 4 | |||
| П6 | 10 | 12 | 5 | 8 | |||
| П7 | 4 |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова длина дороги из пункта Г в пункт Е. В ответе запишите целое число — так, как оно указано в таблице.
Задание 4
Ниже представлены две таблицы из базы данных. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID племянника Петренко П. И.
Пояснение: племянником считается сын брата или сестры.
|
|
Задание 5
По каналу связи передаются сообщения, содержащие только семь букв: А, Б, В, Д, Е, И, Н. Для передачи используется двоичный код, удовлетворяющий условию Фано. Кодовые слова для некоторых букв известны: А — 110, Б — 01, И — 000. Какое наименьшее количество двоичных знаков потребуется для кодирования слова ВВЕДЕНИЕ?
Примечание. Условие Фано означает, что ни одно кодовое слово не является началом другого кодового слова.
Задание 6
Исполнитель КАЛЬКУЛЯТОР имеет только две команды, которым присвоены номера:
Вычти 1
Умножь на 2
Выполняя команду номер 1, КАЛЬКУЛЯТОР вычитает из числа на экране 1, а выполняя
команду номер 2, умножает число на экране на 2. Напишите программу, содержащую не
более 4 команд, которая из числа 2 получает число 14. Укажите лишь номера команд.
Например, программа 12211 – это программа:
Вычти 1
Умножь на 2
Умножь на 2
Вычти 1
Вычти 1,
которая преобразует число 7 в число 22.
Задание 7
Дан фрагмент электронной таблицы. Из ячейки C3 в ячейку D4 была скопирована формула. При копировании адреса ячеек в формуле автоматически изменились. Каким стало числовое значение формулы в ячейке D4?
| А | B | C | D | E | |
| 1 | 1 | 2 | 3 | 4 | 5 |
| 2 | 20 | 30 | 40 | 50 | 60 |
| 3 | 300 | 400 | =$B$3+D2 | 600 | 700 |
| 4 | 4000 | 5000 | 6000 | 8000 |
Примечание: знак $ обозначает абсолютную адресацию.
Задание 8
Запишите число, которое будет напечатано в результате выполнения следующей программы. Для Вашего удобства программа представлена на пяти языках программирования.
| Бейсик | Python |
| DIM S, N AS INTEGER S = 500 N = 200 WHILE S \ N >= 2 S = S + 5 N = N + 5 WEND PRINT S | s = 500 n = 200 while s // n >= 2: s = s + 5 n = n + 5 print(s) |
| Паскаль | Алгоритмический язык |
| var s, n: integer; begin s:= 500; n:= 200; while s div n >= 2 do begin s:= s + 5; n:= n + 5 end; writeln(s) end. | алг нач цел s, n s:= 500 n:= 200 нц пока div(s,n) >= 2 s:= s + 5 n:= n + 5 кц вывод s кон |
| Си++ | |
| #include <iostream> using namespace std; int main() { int s = 500, n = 200; while (s / n >= 2) { s = s + 5; n = n + 5; } cout << s; return 0; }
| |
Задание 9
Каково время (в минутах) передачи полного объема данных по каналу связи, если известно, что передано 1200 Мбайт данных, причем треть времени передача шла со скоростью 60 Мбит в секунду, а остальное время — со скоростью 90 Мбит в секунду?
Задание 10
Левий составляет 5-буквенные коды из букв Л, Е, В, И, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания ЕИ. Сколько различных кодов может составить Левий?
Задание 11
Ниже на пяти языках программирования записан рекурсивный алгоритм F.
| Бейсик | Python |
| SUB F(n) PRINT N IF n < 5 THEN F(2 * n) F(n + 3) END IF END SUB | def F(n): print(n) if n < 5: F(2 * n) F(n + 3) |
| Паскаль | Алгоритмический язык |
| procedure F(n: integer); begin write(n); if n < 5 then begin F(2 * n); F(n + 3) end end; | алг F(цел n) нач вывод n если n < 5 то F(2 * n) F(n + 3) все кон |
| С++ | |
| void F(int n) { std::cout << n; if (n < 5) { F(2 * n); F(n + 3); } }
| |
Запишите подряд без пробелов и разделителей все числа, которые будут показаны на экране при выполнении вызова F(1). Числа должны быть записаны в том же порядке, в котором они выводятся на экран.
Задание 12
В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске. По заданным IP-адресу узла и маске определите адрес сети.
IP-адрес узла: 64.32.128.224
Маска: 255.255.192.0
При записи ответа выберите из приведённых в таблице чисел четыре элемента IP-адреса сети и запишите в нужном порядке соответствующие им буквы без использования точек.
| A | B | C | D | E | F | G | H |
| 0 | 32 | 64 | 128 | 192 | 208 | 224 | 255 |
Пример. Пусть искомый IP-адрес: 192.168.128.0, и дана таблица:
| A | B | C | D | E | F | G | H |
| 128 | 168 | 255 | 8 | 127 | 0 | 17 | 192 |
В этом случае правильный ответ будет записан в виде: HBAF.
Задание 13
Каждый сотрудник предприятия получает электронный пропуск, на котором записаны личный код сотрудника, номер подразделения и некоторая дополнительная информация. Личный код состоит из 15 символов, каждый из которых может быть заглавной русской буквой (используется 25 различных букв) или одной из цифр от 0 до 5. Для записи кода на пропуске отведено минимально возможное целое число байт. При этом используют посимвольное кодирование, все символы кодируют одинаковым минимально возможным количеством бит. Номер подразделения — целое число от 1 до 1200, он записан на пропуске как двоичное число и занимает минимально возможное целое число байт. Всего на пропуске хранится 40 байт данных. Сколько байт выделено для хранения дополнительных сведений об одном сотруднике? В ответе запишите только целое число — количество байт байт.
Задание 14
Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости:
| вверх | вниз | влево | вправо |
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно (по отношению к наблюдателю): вверх ↑, вниз ↓, влево ←, вправо →.
Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ (также по отношению к наблюдателю):
| сверху свободно | снизу свободно | слева свободно | справа свободно |
Цикл
ПОКА < условие >
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ < условие >
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно)
Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.
Сколько клеток лабиринта соответствуют требованию, что, начав движение в ней и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?
НАЧАЛО
ПОКА снизу свободно ИЛИ справа свободно
ПОКА справа свободно
Вправо
КОНЕЦ ПОКА
Вниз
КОНЕЦ ПОКА
КОНЕЦ
Задание 15
На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Ж?
Задание 16 № 7992
Решите уравнение 224 x + 110 = 1018.
Задание 17
В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» – символ «&». В таблице приведены запросы и количество найденных по ним страниц некоторого сегмента сети Интернет.
| Запрос | Найдено страниц (в тысячах) |
| театр & комедия | 315 |
| театр & Москва | 225 |
| театр & Москва & комедия | 110 |
Компьютер печатает количество страниц (в тысячах), которое будет найдено по следующему запросу:
(Москва | комедия) & театр
Укажите целое число, которое напечатает компьютер. Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
Задание 18
Для какого наибольшего целого неотрицательного числа A выражение
(y + 2x ≠ 48) ∨ (A < x) ∨ (x < y)
тождественно истинно, то есть принимает значение 1 при любых целых неотрицательных x и y?
Задание 19
В программе описан одномерный целочисленный массив с индексами от 0 до 12. Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы, обрабатывающей данный массив:
| Бейсик | Паскаль |
| s = 0 n = 12 FOR i = 0 TO n IF A(n–i) – A(i) = A(i) THEN s = s+2*A(i) END IF NEXT i | s:= 0; n:= 12; for i:=0 to n do begin if A[n–i] – A[i] = A[i] then s:=s+2*A[i]; end; |
| Си++ | Алгоритмический язык |
| s = 0; n = 12; for (i = 0; i <= n; i++) { if (A[n–i] – A[i] == A[i]) s = s+2*A[i]; } | s:= 0 n:= 12 нц для i от 0 до n если A[n–i] – A[i] = A[i] то s:= s+2*A[i] все кц |
| Python | |
| s = 0 n = 12 for i in range(0, n+1): if A[n–i] – A[i] == A[i]: s = s+2*A[i] | |
В начале выполнения этого фрагмента в массиве находились числа 0, 10, 20, 30, 40, 50, 60, 70, 80, 90, 100, 110, 120, т. е. A[0] = 0, A[1] = 10 и т. д. Чему будет равно значение переменной s после выполнения данной программы?
Задание 20
Ниже на пяти языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа a и b. Укажите наибольшее из таких чисел x, при вводе которых алгоритм печатает сначала 2, а потом 10.
| Бейсик | Python |
| DIM X, A, B AS INTEGER INPUT X A = 0: B = 1 WHILE X > 0 IF X MOD 2 > 0 THEN A = A + X MOD 12 ELSE B = B * (X MOD 12) END IF X = X \ 12 WEND PRINT A PRINT B | x = int(input()) a=0; b=1 while x > 0: if x%2 > 0: a += x%12 else: b *= x%12 x = x // 12 print(a, b) |
| Паскаль | Алгоритмический язык |
| var x, a, b: longint; begin readln(x); a:= 0; b:= 1; while x > 0 do begin if x mod 2 > 0 then a:= a + x mod 12 else b:= b * (x mod 12); x:= x div 12; end; writeln(a); write(b); end. | алг нач цел x, a, b ввод x a:= 0; b:= 1 нц пока x > 0 если mod(x,2)>0 то a:= a + mod(x,12) иначе b:= b*mod(x,12) все x:= div(x,12) кц вывод a, нс, b кон |
| С++ | |
| #include <iostream> using namespace std; int main() { int x, a, b; cin >> x; a = 0; b = 1; while (x > 0) { if (x%2 > 0) a += x%12; else b *= x%12; x = x / 12; } cout << a << endl << b << endl; return 0; }
| |
Задание 21
Определите, какое число будет напечатано в результате выполнения следующего алгоритма:
| Бейсик | Паскаль |
| DIM A, B, T, M, R AS INTEGER A =-5: B = 5 M = A: R = F(А) FOR T = A TO B IF F(T) < R THEN M = T R = F(T) END IF NEXT T PRINT R FUNCTION F(x) F = (x+5)*(1-x) END FUNCTION | var a,b,t,M,R: integer; Function F(x:integer): integer; begin F:= (x+5)*(1-x) end; begin a:=-5; b:= 5; M:= a; R:= F(a); for t:= a to b do begin if (F(t) < R) then begin M:= t; R:= F(t) end end; write(R) end. |
| Си++ | Алгоритмический |
| #include <iostream> using namespace std; int F(int x) { return (x+5)*(1-x); } int main() { int a, b, t, M, R; a =-5; b = 5; M = a; R = F(a); for (t = a; t <= b; t++) { if (F(t) < R) { M = t; R = F(t); } } cout «R «endl; } | алг нач цел a, b, t, M, R a:=-5; b:= 5 M:= a; R:= F(a) нц для t от a до b если F(t) < R то M:= t; R:= F(t) все кц вывод R кон алг цел F(цел x) нач знач:= (x+5)*(1-x) кон |
| Python | |
| def f(x): return (x+5)*(1-x) a =-5 b = 5 M = a R = f(a) for t in range(a, b+1): if (f(t) < R): M = t R = f(t) print(R) | |
Задание 22
Исполнитель Тренер преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
Прибавить 1
Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя Тренер — это последовательность команд.
Сколько существует программ, которые преобразуют исходное число 1 в число 40 и при этом траектория вычислений содержит числа 12 и 25?
Траектория должна содержать оба указанных числа. Траектория вычислений – это последовательность результатов выполнения всех команд программы. Например, для программы 212 при исходном числе 7 траектория будет состоять из чисел 14, 15, 30.
Задание 23
Сколько существует различных наборов значений логических переменных x1, x2,... x10, которые удовлетворяют всем перечисленным ниже условиям?
(x1 ≡ x2) ∧ ((x1 ∧ x3) ∨ (x1 ∧ x3)) = 0
(x2 ≡ x3) ∧ ((x2 ∧ x4) ∨ (x2 ∧ x4)) = 0
...
(x8 ≡ x9) ∧ ((x8 ∧ x10) ∨ (x8 ∧ x10)) = 0
В ответе не нужно перечислять все различные наборы значений переменных x1, x2, … x10 при которых выполнена данная система равенств. В качестве ответа Вам нужно указать количество таких наборов.
Задание 24
Требовалось написать программу, которая решает неравенство «(ах) / (х + b) > 0» относительно х для любого ненулевого числа а и любого неотрицательного числа b и 
, введенных с клавиатуры. Все числа считаются действительными. Программист торопился и написал программу неправильно.
| Бейсик | Python |
| INPUT а, b, х IF b = 0 THEN PRINT "х > 0 или х <0" ELSE IF а>0 THEN PRINT "х >0 или х<",-b ELSE PRINT -b,"<х<0" ENDIF ENDIF END | a = int(input()) b = int(input()) x = int(input()) if b == 0: print("x > 0 или x < 0") else: if a > 0: print('x > 0 или x <',-b) else: print(-b,'< x <0 ') |
| Паскаль | Алгоритмический язык |
| var a,b,x: real; begin readln(a,b,x); if b = 0 then write('x > 0 или x < 0') else if a > 0 then write('x > 0 или x <',-b) else write(-b,'< x <0 '); end. | алг нач вещ a,b,x если b = 0 то вывод "x > 0 или x < 0" иначе если a > 0 то вывод "x > 0 или x <",-b иначе вывод -b,"< x <0" все все кон |
| Си++ | |
| #include <iostream> using namespace std; int main(void) { float a,b,x; cin >> a >> b >> x; if (b==0) cout << "x>0 или x<0" << endl; else if (a > 0) cout << "x > 0 или x <" << -b << endl; else cout << -b << "< x <0" << endl; } | |
Последовательно выполните три задания:
1) Приведите пример таких чисел a, b, x, при которых программа неверно решает поставленную задачу.
2) Укажите, какая часть программы является лишней.
3) Укажите, как нужно доработать программу, чтобы не было случаев ее неправильной работы. (Это можно сделать несколькими способами, поэтому можно указать любой способ доработки исходной программы).
Задание 25
Дан целочисленный массив из 30 элементов. Элементы массива могут принимать целые значения от 0 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести произведение двузначных элементов массива, с суммой цифр не кратной 6. Гарантируется, что в исходном массиве есть хотя бы один элемент, значение которого является двузначным числом, и при этом сумма его цифр не делится на 6. Исходные данные объявлены так, как показано ниже на примерах для некоторых языков программирования и естественного языка. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных. Исходные данные всегда подобраны так, что результат произведения не выходит за пределы объявленных типов данных.
| Бейсик | Паскаль |
| N = 30 DIM A(N) AS LONG DIM I, J, P AS LONG FOR I = 1 TO N INPUT A(I) NEXT I ... END | const N = 30; var a: array [1..N] of longint; i, j, p: longint; begin for i:= 1 to N do readln(a[i]); ... end. |
| Си++ | Алгоритмический язык |
| #include <iostream> using namespace std; #define N 30 int main() { long a[N]; long i, j, p; for (i = 0; i<N; i++) cin >> a[i]; ... } | алг нач цел N = 30 целтаб a[1:N] цел i, j, p нц для i от 1 до N ввод a[i] кц ... кон |
| Eстественный язык | |
| Объявляем массив A из 30 элементов. Объявляем целочисленные переменные I, J, P. В цикле от 1 до 30 вводим элементы массива A с 1-го по 30-й.… | |
| Python | |
| # допускается также # использовать две # целочисленные переменные j, p a = [] n = 30 for i in range(0, n): a.append(int(input())) ... | |
В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке программирования (укажите название и используемую версию языка программирования, например Free Pascal 2.4) или в виде блок-схемы. В этом случае Вы должны использовать те же самые исходные данные и переменные, какие были предложены в условии (например, в образце, записанном на естественном языке).
Задание 26
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в кучу один камень или увеличить количество камней в куче в три раза. Например, имея кучу из 15 камней, за один ход можно получить кучу из 16 или 45 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней.
Игра завершается в тот момент, когда количество камней в куче становится не менее 37. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 37 или больше камней. В начальный момент в куче было S камней, 1 ≤ S ≤ 36.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. У кого из игроков есть выигрышная стратегия при S = 12? Опишите эту стратегию.
2. Укажите два таких значения S, при которых у Пети есть выигрышная стратегия, причём Петя не может выиграть за один ход, но Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня. Для каждого из указанных значений S опишите выигрышную стратегию Пети.
3. Укажите значение S, при котором у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети, однако у Вани нет стратегии, которая позволит ему гарантированно выиграть 1-м ходом.
Для указанного значения S опишите выигрышную стратегию Вани. Постройте в виде рисунка или таблицы дерево всех партий, возможных при этой выигрышной стратегии Вани. На рёбрах дерева указывайте, кто делает ход, в узлах — количество камней в позиции.
Задание 27
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, находящихся на расстоянии не меньше 6 (разница в индексах элементов должна быть 6 или более). Необходимо определить количество пар, сумма чисел в которых чётна.
Описание входных и выходных данных.
В первой строке входных данных задаётся количество чисел N (6 ≤ N ≤ 1000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
8
1
3
5
4
6
7
9
8
Пример выходных данных для приведённого выше примера входных данных:
1
Пояснение. Из 8 чисел можно составить 3 пары, удовлетворяющие условию. Это будут элементы с индексами 1 и 7, 1 и 8, 2 и 8. Для заданного набора чисел получаем пары (1, 9), (1, 8), (3, 8). Суммы чисел в этих парах равны 10, 9, 11. Чётная сумма — одна.
Напишите эффективную по времени и по памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 килобайта и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и по памяти, — 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, — 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, — 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
