Вариант № 7
1. Сколько единиц в двоичной записи шестнадцатеричного числа ВЕС216?
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. На рисунке схема дорог изображена в виде графа, в таблице содержатся сведения о длине этих дорог в километрах.
| 
|
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите длину кратчайшего пути из пункта Г в пункт Д, если передвигаться можно только по указанным дорогам. В ответе укажите целое число – длину дороги в километрах.
ВНИМАНИЕ. Длины отрезков на схеме не отражают длины дорог.
4. Сколько записей удовлетворяют условию «Пол = 'м' И Материаловедение < Охрана труда»?
| Фамилия | Пол | Родной язык | Охрана труда | Материаловедение | Химия | Высшая математика |
| Андрюшин | м | |||||
| Борискин | м | |||||
| Варенкова | ж | |||||
| Дегтеряев | м | |||||
| Евлашина | ж | |||||
| Закирина | ж |
5. Для кодирования букв А, Б, В, Г решили использовать двухразрядные последовательные двоичные числа (от 00 до 11 соответственно). Закодируйте таким образом последовательность символов ГБВА и запишите результат шестнадцатеричным кодом.
6. У исполнителя Калькулятор две команды, которым присвоены номера:
Возведи в квадрат,
Прибавь 1.
Первая из них возводит число на экране в квадрат, вторая увеличивает его на 1. Запишите порядок команд в программе, которая преобразует число 2 в число 100 и содержит не более 4 команд. Указывайте лишь номера команд. (Например, программа 2122 — это программа
Прибавь 1,
Возведи в квадрат,
Прибавь 1,
Прибавь 1.
Эта программа преобразует число 1 в число 6.)
7. В ячейке F10 электронной таблицы записана формула. Эту формулу скопировали в ячейку Е11. В соответствии с формулой, полученной в ячейке Е11, значение в этой ячейке равно сумме значений в ячейках В16 и А17.
Напишите, сколько из следующих четырёх утверждений не противоречат этим данным.
A)Значение в ячейке F10 равно х+у, где х — значение в ячейке В16, а у — значение в ячейке А17.
Б)Значение в ячейке F10 равно х+у, где х — значение в ячейке С15, а у — значение в ячейке А17.
В)Значение в ячейке F10 вычисляется по формуле х+у, где х — значение в ячейке С16, а у — значение в ячейке A16.
Г)Значение в ячейке F10 равно 2 · х, где х — значение в ячейке В16.
8. Определите, что будет напечатано в результате работы следующего фрагмента программы:
| Бейсик | Python |
| DIM K, S AS INTEGER S = 3 K = 1 WHILE K < 25 S = S + K K = K + 2 WEND PRINT S | s = 3 k = 1 while k < 25: s += k k += 2 print(s) |
| Паскаль | Алгоритмический язык |
| var k, s: integer; begin s:=3; k:=1; while k < 25 do begin s:=s+k; k:=k+2; end; write(s); end. | алг нач цел k, s s:= 3 k:= 1 нц пока k < 25 s:= s + k k:= k + 2 кц вывод s кон |
| Си++ | |
| #include <iostream> using namespace std; int main() { int s, k; s = 3, k = 1; while (k < 25) { s = s + k; k = k + 2; } cout << s << endl; return 0; } |
9. Документ объёмом 30 Мбайт можно передать с одного компьютера на другой двумя способами.
А. Сжать архиватором, передать архив по каналу связи, распаковать.
Б. Передать по каналу связи без использования архиватора.
Какой способ быстрее и насколько, если:
· средняя скорость передачи данных по каналу связи составляет 220 бит в секунду;
· объём сжатого архиватором документа равен 30% исходного;
· время, требуемое на сжатие документа, — 18 секунд, на распаковку — 2 секунды?
В ответе напишите букву А, если быстрее способ А, или Б, если быстрее способ Б. Сразу после буквы напишите число, обозначающее, на сколько секунд один способ быстрее другого. Так, например, если способ Б быстрее способа А на 23 секунды, в ответе нужно написать Б23. Единицы измерения «секунд», «сек.», «с.» к ответу добавлять не нужно.
10. Некоторый алфавит содержит три различные буквы. Сколько трёхбуквенных слов можно составить из букв данного алфавита (буквы в слове могут повторяться)?
11. Ниже на пяти языках программирования записаны две рекурсивные функции: F и G.
| Бейсик | Python |
| FUNCTION F(n) IF n > 2 THEN F = F(n - 1) + G(n - 2) ELSE F = n END IF END FUNCTION FUNCTION G(n) IF n > 2 THEN G = G(n - 1) + F(n - 2) ELSE G = n + 1 END IF END FUNCTION | def F(n): if n > 2: return F(n-1) + G(n-2) else: return n def G(n): if n > 2: return G(n-1) + F(n-2) else: return n+1 |
| Паскаль | Алгоритмический язык |
| function F(n: integer): integer; begin if n > 2 then F:= F(n - 1) + G(n - 2) else F:= n; end; function G(n: integer): integer; begin if n > 2 then G:= G(n - 1) + F(n - 2) else G:= n+1; end; | алг цел F(цел n) нач если n > 2 то знач:= F(n - 1)+G(n - 2) иначе знач:= n все кон алг цел G(цел n) нач если n > 2 то знач:= G(n - 1)+F(n - 2) иначе знач:= n+1 все кон |
| Си | |
| int F(int n) { if (n > 2) return F(n-1) + G(n-2); else return n; } int G(int n) { if (n > 2) return G(n-1) + F(n-2); else return n + 1; } |
Чему будет равно значение, вычисленное при выполнении вызова F (6)?
12. В терминологии сетей TCP/IP маской сети называется двоичное число, определяющее, какая часть IP-адреса узла сети относится к адресу сети, а какая — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-адрес, — в виде четырёх байтов, причём каждый байт записывается в виде десятичного числа. При этом в маске сначала (в старших разрядах) стоят единицы, а затем с некоторого разряда — нули. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-адресу узла и маске.
Например, если IP-адрес узла равен 231.32.255.131, а маска равна 255.255.240.0, то адрес сети равен 231.32.240.0. Для узла с IP-адресом 147.192.92.64 адрес сети равен 147.192.80.0. Чему равно значение третьего слева байта маски? Ответ запишите в виде десятичного числа.
13. При регистрации в компьютерной системе каждому пользователю выдаётся пароль, состоящий из 6 символов и содержащий только символы из 7 буквенного набора Н, О, Р, С, Т, У, X. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование паролей, все символы кодируются одинаковым и минимально возможным количеством бит. Кроме собственно пароля для каждого пользователя в системе хранятся дополнительные сведения, для чего отведено 10 байт.
Определите объём памяти, необходимый для хранения сведений о 100 пользователях. (Ответ дайте в байтах.)
14. Система команд исполнителя РОБОТ, «живущего» в прямоугольном лабиринте на клетчатой плоскости, состоит из 8 команд. Четыре команды - это команды-приказы:
| вверх | вниз | влево | вправо |
При выполнении любой из этих команд РОБОТ перемещается на одну клетку соответственно: вверх 
вниз 
влево 
вправо 
Четыре команды проверяют истинность условия отсутствия стены у каждой стороны той клетки, где находится РОБОТ:
| сверху свободно | снизу свободно | слева свободно | справа свободно |
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда 1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно)
В конструкциях ПОКА и ЕСЛИ условие может содержать команды проверки, а также слова И, ИЛИ, НЕ, обозначающие логические операции.
Если РОБОТ начнёт движение в сторону находящейся рядом с ним стены, то он разрушится и программа прервётся.
Сколько клеток лабиринта соответствуют требованию, что, начав движение в данной клетке и выполнив предложенную программу, РОБОТ уцелеет и остановится в закрашенной клетке (клетка F6)?
НАЧАЛО
ПОКА снизу свободно ИЛИ справа свободно
ПОКА снизу свободно
вниз
КОНЕЦ ПОКА
ЕСЛИ справа свободно
ТО
вправо
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦl
15. На рисунке — схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, И, К, Л. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города А в город Л?
16. Решите уравнение:
101N+1 = 101N + 158
Ответ запишите в десятичной системе счисления.
17. В языке запросов поискового сервера для обозначения логической операции «ИЛИ» используется символ «|», а для логической операции «И» - символ
| Запрос | Количество страниц (тыс.) |
| Сербия & Хорватия | |
| Сербия|Хорватия | |
| Сербия |
Какое количество страниц (в тысячах) будет найдено по запросу Хорватия? Считается, что все запросы выполнялись практически одновременно, так что набор страниц, содержащих все искомые слова, не изменялся за время выполнения запросов.
18. Обозначим через m & n поразрядную конъюнкцию неотрицательных целых чисел m и n.
Например, 14 & 5 = 11102 & 01012 = 01002 = 4.
Для какого наименьшего неотрицательного целого числа А формула
x&33 = 0 → (x&45≠0 → x&А ≠ 0)
тождественно истинна (т. е. принимает значение 1 при любом неотрицательном целом значении переменной х)?
19. В программе описан одномерный целочисленный массив с индексами от 0 до 10. Ниже представлен записанный на разных языках программирования фрагмент одной и той же программы, обрабатывающей данный массив:
| Бейсик | Паскаль |
| s = 0 n = 10 FOR i = 1 ТО n s = s + A(i) - A (i-1) NEXT i | s: = 0; n: = 10; for i: = 1 to n do begin s: = s + A[i] - A[i-1]; end |
| Си++ | Алгоритмический язык |
| s = 0; n = 10; for (i = 1; i <= n; i++) { s = s + A[i] - A[i - 1]; } | s: = 0 n: = 10 нц для i от 1 до n s:= s + A[i] - A[i - 1] кц |
| Python | |
| s = 0 n = 10 for i in range(1, n+1): s = s + A[i] - A[i - 1] |
В начале выполнения этого фрагмента в массиве находились числа 0, 2, 4, 6, 8, 10, 12, 14, 16, 18, 20, т.е. А[0]=0, А[1]=2 и т. д. Чему будет равно значение переменной s после выполнения данной программы?
20. Ниже на пяти языках записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: a и b. Укажите наименьшее из таких чисел x, при вводе которых алгоритм печатает сначала 12, а потом 5.
| Бейсик | Паскаль |
| DIM X, А, В, С AS INTEGER INPUT X А = 0: В = 10 WHILE X > 0 С = X MOD 10 А = А + С IF С < В THEN В = С X = X \ 10 WEND PRINT А PRINT В | 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. |
| Си++ | Алгоритмический |
| #include <iostream> using namespace std; int main() { int x, a, b, c; cin >> x; a = 0; b = 10; while (x>0) { с = x%10; a = a+c; if (c<b) b = c; x = x /10; } cout << a << endl << b endl; } | алг нач цел х, а, b, с ввод X а:= 0; b:= 10 нц пока х>0 с:= mod(х,10) а:= а+с если с<b то b:= с все х:= div(х,10) кц вывод а, не, b кон |
| Python | |
| x = int(input()) a = 0 b = 10 while x > 0: с = x % 10 a += c if c < b: b = c x //= 10 print(a) print(b) |
21. Напишите в ответе число, которое будет напечатано в результате выполнения следующего алгоритма (для Вашего удобства алгоритм представлен на четырёх языках).
| Бейсик | Паскаль |
| DIM A, B, T, M, R AS INTEGER A = 5: B = 35 M = A: R = F(A) FOR T = A TO B IF F(T) > R THEN M = T R = F(T) END IF NEXT T PRINT M FUNCTION F(x) F = 3*(x-1)*(x-1)+37 END FUNCTION | var a,b,t,M,R: integer; Function F(x:integer): integer; begin F:= 3*(x-1)*(x-1)+37 end; begin a:= 5; b:= 35; 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(M); end. |
| Си++ | Алгоритмический |
| #include <iostream> using namespace std; int F(int x) { return 3*(x-1)*(x-1)+37; } void main() { int a, b, t, M, R; a = 5; b = 35; M = a; R = F(a); for (t = a; t <= b; t++) { if (F(t) > R) { M = t; R = F(t); } } cout «M «endl; } | алг нач цел a, b, t, M, R a:= 5; b:= 35 M:= a; R:= F(a) нц для t от a до b если F(t) > R то M:= t; R:= F(t) все кц вывод M кон алг цел F(цел x) нач знач:= 3*(x-1)*(x-1)+37 кон |
| Python | |
| def f(x): return 3*(x-1)*(x-1)+37 a = 5 b = 35 M = a R = f(a) for t in range(a, b+1): if (f(t) > R): M = t R = f(t); print(M) |
22. У исполнителя Калькулятор две команды:
Умножь на 6,
Подели на 2.
Первая из них увеличивает число на экране в 6 раз, вторая – уменьшает его в 2 раза. Программа для Калькулятора – это последовательность команд. Сколько различных чисел можно получить из числа 512 с помощью программы, которая содержит ровно 6 команд?
23. Сколько различных решений имеет уравнение
((J → K) → (M ∧ N ∧ L)) ∧ ((J ∧ K) → (M ∧ N ∧ L)) ∧ (M → J) = 1
где J, K, L, M, N – логические переменные?
В ответе не нужно перечислять все различные наборы значений J, K, L, M и N, при которых выполнено данное равенство. В качестве ответа нужно указать количество таких наборов.
24. Для заданного положительного вещественного числа A необходимо найти максимальное целое число K, при котором выполняется неравенство
(при K = 0 сумма считается равной 0).
Для решения этой задачи ученик написал такую программу.
| Бейсик | Python |
| DIM A, S AS DOUBLE DIM K AS INTEGER INPUT A K = 0 S = 1 WHILE S < A K = K + 1 S = S + 1.0/K WEND PRINT K END | a = float(input()) k = 0 s = 1 while s < a: k = k + 1 s = s + 1.0/k print(k) |
| Алгоритмический язык | Паскаль |
| алг нач вещ a, s цел k ввод a k:= 0 s:= 1 нц пока s<a k:= k + 1 s:= s + 1.0/k кц вывод k кон | var a, s: real; k: integer; begin read(a); k:= 0; s:= 1; while s<a do begin k:= k + 1; s:= s + 1.0/k; end; write(k); end. |
| Си++ | |
| #include <iostream> using namespace std; int main(){ double a, s; int k; cin >> a; k = 0; s = 1; while (s<a) { k = k + 1; s = s + 1.0/k; } cout «k «endl; return 0; } |
Последовательно выполните следующее.
1. Напишите, что выведет эта программа при вводе числа 1.8.
2. Приведите пример числа, при вводе которого программа даст верный ответ.
3. Найдите в программе все ошибки (их может быть одна или несколько).
Для каждой ошибки выпишите строку, в которой она допущена, и приведите эту же строку в исправленном виде.
Обратите внимание: вам нужно исправить приведённую программу, а не написать свою. Вы можете только исправлять ошибочные строки; удалять строки или добавлять новые строки нельзя. Постарайтесь также не внести новые ошибки – за это оценка снижается.
25. Дан целочисленный массив из 30 элементов. Элементы массива могут принимать значения от 1 до 5 и содержат годовые оценки по информатике учащихся выпускного класса. Опишите на русском языке или на одном из языков программирования алгоритм, который позволяет подсчитать и вывести средний балл среди «хорошистов» и «отличников» (тех, кто получил итоговую отметку «4» или «5»). Гарантируется, что в классе есть хотя бы один «хорошист» или «отличник». Исходные данные объявлены так, как показано ниже. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать часть из них.
| Бейсик | Паскаль |
| N=30 DIM A(N) AS INTEGER DIM I, X, Y AS INTEGER DIM S AS SINGLE FOR I = 1 TO N INPUT A(I) NEXT I … END | const N=30; var a: array [1..N] of integer; i, x, y: integer; s: real; begin for i:=1 to N do read (a[i]); … end. |
| Си++ | Алгоритмический язык |
| #include <iostream> using namespace std; #define N 30 int main(void) {int a[N]; int i, x, y; float s; for (i=0; i < N; i++) cin >> a[i]; … } | алг нач цел N = 30 целтаб a[1:N] цел i, x, y вещ s нц для i от 1 до N ввод a[i] кц ... кон |
| Естественный язык | |
| Объявляем массив A из 30 элементов. Объявляем целочисленные переменные I, X, Y. Объявляем вещественную переменную S. В цикле от 1 до 30 вводим элементы массива A с 1-го по 30-й. | |
| Python | |
| # допускается также # использовать две # целочисленные переменные x, y # и вещественную переменную s a = [] n = 30 for i in range(0, n): a.append(int(input())) ... |
В качестве ответа Вам необходимо привести фрагмент программы (или описание алгоритма на естественном языке), который должен находиться на месте многоточия. Вы можете записать решение также на другом языке
программирования (укажите название и используемую версию языка программирования, например Borland Pascal 7.0) или в виде блок-схемы. В этом случае Вы должны использовать переменные, аналогичные переменным, используемым в алгоритме, записанном на естественном языке, с учётом синтаксиса и особенностей используемого Вами языка программирования.
26. Два игрока, Паша и Вова, играют в следующую игру. Перед игроками лежит куча камней. Игроки ходят по очереди, первый ход делает Паша. За один ход игрок может добавить в кучу 1 камень или 10 камней. Например, имея кучу из 7 камней, за один ход можно получить кучу из 8 или 17 камней. У каждого игрока, чтобы делать ходы, есть неограниченное количество камней. Игра завершается в тот момент, когда количество камней в куче становится не менее 41. Победителем считается игрок, сделавший последний ход, то есть первым получивший кучу, в которой будет 41 или больше камней.
В начальный момент в куче было S камней, 1 ≤ S ≤ 40.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника.
Выполните следующие задания. Во всех случаях обосновывайте свой ответ.
1. а) Укажите все такие значения числа S, при которых Паша может выиграть в один ход. Обоснуйте, что найдены все нужные значения S, и укажите выигрывающие ходы.
б) Укажите такое значение S. при котором Паша не может выиграть за один ход, но при любом ходе Паши Вова может выиграть своим первым ходом. Опишите выигрышную стратегию Вовы.
2. Укажите два значения S, при которых у Паши есть выигрышная стратегия, причём Паша не может выиграть за один ход, но может выиграть своим вторым ходом независимо от того, как будет ходить Вова. Для указанных значений S опишите выигрышную стратегию Паши.
3. Укажите значение S, при котором у Вовы есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Паши, однако у Вовы нет стратегии, которая позволит ему гарантированно выиграть первым ходом. Для указанного значения S опишите выигрышную стратегию Вовы. Постройте дерево всех партий, возможных при этой выигрышной стратегии Вовы (в виде рисунка или таблицы). На ребрах дерева указывайте, кто делает ход, в узлах — количество камней в куче.
27. Соревнования по игре «Тетрис-онлайн» проводятся по следующим правилам.
1. Каждый участник регистрируется на сайте игры под определённым игровым именем. Имена участников не повторяются.
2. Чемпионат проводится в течение определённого времени. В любой момент этого времени любой зарегистрированный участник может зайти на сайт чемпионата и начать зачётную игру. По окончании игры её результат
(количество набранных очков) фиксируется и заносится в протокол.
3. Участники имеют право играть несколько раз. Количество попыток одного участника не ограничивается.
4. Окончательный результат участника определяется по одной игре, лучшей для данного участника.
5. Более высокое место в соревнованиях занимает участник, показавший лучший результат.
6. При равенстве результатов более высокое место занимает участник, раньше показавший лучший результат.
В ходе соревнований заполняется протокол, каждая строка которого описывает одну игру и содержит результат участника и его игровое имя. Протокол формируется в реальном времени по ходу проведения чемпионата, поэтому строки в нём расположены в порядке проведения игр: чем раньше встречается строка в протоколе, тем раньше закончилась соответствующая этой строке игра. Напишите эффективную, в том числе по памяти, программу, которая по данным протокола определяет победителя и призёров. Гарантируется, что в чемпионате участвует не менее трёх игроков.
Перед текстом программы кратко опишите алгоритм решения задачи и укажите используемый язык программирования и его версию.
Описание входных данных
Первая строка содержит число N — общее количество строк протокола. Каждая из следующих N строк содержит записанные через пробел результат участника (целое неотрицательное число, не превышающее 100 миллионов) и игровое имя (имя не может содержать пробелов). Строки исходных данных соответствуют строкам протокола и расположены в том же порядке, что и в протоколе.
Гарантируется, что количество участников соревнований не меньше 3.
Описание выходных данных
Программа должна вывести имена и результаты трёх лучших игроков по форме,
приведённой ниже в примере.
Пример входных данных:
69485 Jack
95715 qwerty
95715 Alex
83647 M
197128 qwerty
95715 Jack
93289 Alex
95715 Alex
95715 M
Пример выходных данных для приведённого выше примера входных
данных:
1 место. qwerty (197128)
2 место. Alex (95715)
3 место. Jack (95715)