РЕШУ ЕГЭ — информатика

Вариант № 3746449

Сколько единиц в двоичной записи шестнадцатеричного числа 10FA₁₆?

Символом F обозначено одно из указанных ниже логических выражений от трёх аргументов: X, Y, Z. Дан фрагмент таблицы истинности выражения F:

X	Y	Z	F
1	0	0	0
0	1	1	1
1	0	1	1

Какое выражение соответствует F?

1)  X → Z ∧ Y

2)  ¬Z →(X → Y)

3)  ¬(X ∨ Y) ∧ Z

4)  ¬X ∨ ¬(Y ∧ Z)

Учитель работал в каталоге D:\Материалы к урокам\10 класс\Практические работы. Затем перешел в дереве каталогов на уровень выше, спустился в подкаталог Лекции и удалил из него файл Введение. Каково полное имя файла, который удалил преподаватель?

1)  D:\Материалы к урокам\10 класс\Введение

2)  D:\Материалы к урокам\10 класс\Лекции\Введение

3)  D:\Материалы к урокам\Лекции\Введение

4)  D:\Материалы к урокам\Введение\Лекции

По каналу связи передаются сообщения, содержащие только 4 буквы: П, А, Р, К. Для кодирования букв П, А, Р используются 6-битовые кодовые слова:

П  — 111111, А  — 110001, Р  — 001001.

Для этого набора кодовых слов выполнено такое свойство: любые два слова из набора отличаются не менее, чем в трёх позициях. Это свойство важно для расшифровки сообщений при наличии помех. Нужно подобрать кодовое слово для буквы К так, чтобы указанное свойство выполнялось для всех четырёх кодовых слов.

Можно ли использовать одно из таких слов: 000001, 111001, 000111?

1)  да, 000001

2)  да, 111001

3)  да, 000111

4)  нет, не подходит ни одно из указанных выше слов

У исполнителя Калькулятор две команды, которым присвоены номера:

1.  прибавь 2,

2.  умножь на 5.

Выполняя первую из них, Калькулятор прибавляет к числу на экране 2, а выполняя вторую, умножает его на 5. Запишите порядок команд в программе, которая преобразует число 2 в число 70 и содержит не более 4 команд. Указывайте лишь номера команд. (Например, программа 2121  — это программа умножь на 5, прибавь 2, умножь на 5, прибавь 2. Эта программа преобразует число 1 в число 37.)

Определите, что будет напечатано в результате выполнения программы (записанной ниже на разных языках программирования):

Бейсик	Паскаль
DIM N, S AS INTEGER N = 4 S = 0 WHILE N <= 8 S = S + 15 N = N + 1 WEND PRINT S	var n, s: integer; begin     n := 4;     s := 0;     while n <= 8 do     begin         s := s + 15;         n := n + 1     end;     write(s) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() {     int n, s;     n = 4;     s = 0;     while (n <= 8)     {         s = s + 15;         n = n + 1;     }     cout « s « endl; }	алг нач цел n, s n := 4 s := 0 нц пока n <= 8     s := s + 15     n := n + 1 кц вывод s кон
Python
n = 4 s = 0 while n <= 8:     s += 15     n += 1 print(s)

У Толи есть доступ к сети Интернет по высокоскоростному одностороннему радиоканалу, обеспечивающему скорость получения информации $2 в степени левая круглая скобка 19 правая круглая скобка$ бит в секунду. У Миши нет скоростного доступа в Интернет, но есть возможность получать информацию от Толи по низкоскоростному телефонному каналу со средней скоростью $2 в степени левая круглая скобка 15 правая круглая скобка$ бит в секунду. Миша договорился с Толей, что тот будет скачивать для него данные объемом 5 Мбайт по высокоскоростному каналу и ретранслировать их Мише по низкоскоростному каналу.

Компьютер Толи может начать ретрансляцию данных не раньше, чем им будут получены первые 512 Кбайт этих данных. Каков минимально возможный промежуток времени (в секундах) с момента начала скачивания Толей данных до полного их получения Мишей?

В ответе укажите только число, слово «секунд» или букву «с» добавлять не нужно.

Сколько существует шестизначных чисел, делящихся на 5, в которых каждая цифра может встречаться только один раз, при этом никакие две чётные и две нечётные цифры не стоят рядом.

Решение. Заметим, что чётных и нечётных цифр 5 и 5 соответственно. Чтобы число делилось на 5, необходимо, чтобы на конце числа стояла цифра 5 или 0. Найдём количество шестизначных чисел, делящихся на 5 и начинающихся с нечётной цифры: 5 · 4 · 4 · 3 · 3 · 1  =  720. Найдём количество шестизначных чисел, делящихся на 5 и начинающихся с чётной цифры (при этом число не должно начинаться с нуля): 4 · 4 · 4 · 3 · 3 · 1  =  576. Таким образом, получаем ответ: 720 + 576  =  1296.

Ответ: 1296.

Приведём другое решение на языке Python.

import itertools

alphabet = "0123456789"

ar = itertools.permutations(alphabet, 6) #Размещение

arl = []

for e in ar:

arl.append(list(e))

count = 0

for e in arl:

flag = True

for i in range(len(e)-1):

if (e[0] == "0") or (int(e[i]) % 2 == 0 and int(e[i+1]) % 2 == 0) or (int(e[i]) % 2 != 0 and int(e[i+1]) % 2 != 0) or (e[5] != "5" and e[5] != "0"):

flag = False

if flag:

count += 1

print(count)

Приведём решение Ильи Андрианова на языке Python.

from itertools import permutations

count = 0

for var in permutations('0123456789', 6):

num = ''.join(var)

if num[0] != '0' and num[-1] in '05':

num = num.replace('0', '2').replace('4', '2').replace('6', '2').replace('8', '2')

num = num.replace('3', '1').replace('5', '1').replace('7', '1').replace('9', '1')

if '22' not in num and '11' not in num:

count += 1

print(count)

Приведём решение Сергея Донец на PascalABC.NET:

begin

'0123456789'.Permutations(6) // 10-ричная 6-значных

.Where(s->(s[1] <> '0')and((s[6] = '0')or(s[6] = '5')) ) // Первой цифрой не может быть 0

.Where(s->not s.IsMatch('[02468][02468]')) //не две чётные цифры рядом

.Where(s->not s.IsMatch('[13579][13579]')) //не две нечётные цифры рядом

.Count.Print;//1296

end.

Ниже на пяти языках программирования записана рекурсивная функция (процедура) F.

Бейсик	Python
SUB F(n)     PRINT n,     IF n > 2 THEN       F(n − 1)       F(n − 2)       F(n − 3)     END IF END SUB	def F(n):     print (n)     if n > 2:         F(n − 1)         F(n − 2)         F(n − 3)
Паскаль	Алгоритмический язык
procedure F(n: integer); begin     write(n);     if n > 2 then     begin       F(n − 1);       F(n − 2);       F(n − 3)     end end;	алг F(цел n) нач     вывод n     если n > 2 то       F(n − 1)       F(n − 2)       F(n − 3)     все кон
Си
void F(int n ){     cout « n « endl;     if (n > 2) {         F(n − 1);         F(n − 2);         F(n − 3);     } }

Что выведет программа при вызове F(4)? В ответе запишите последовательность выведенных цифр слитно (без пробелов).

10.  

В терминологии сетей TCP/⁠IP маской сети называется двоичное число, определяющее, какая часть IP-⁠адреса узла сети относится к адресу сети, а какая  — к адресу самого узла в этой сети. Обычно маска записывается по тем же правилам, что и IP-⁠адрес. Адрес сети получается в результате применения поразрядной конъюнкции к заданному IP-⁠адресу узла и маске.

По заданным IP-⁠адресу узла и маске определите адрес сети.

IP-⁠адрес узла: 217.9.142.131

Маска: 255.255.224.0

При записи ответа выберите из приведенных в таблице чисел четыре элемента IP-⁠адреса и запишите в нужном порядке соответствующие им буквы без использования точек.

A	B	C	D	E	F	G	H
0	9	64	128	131	142	192	217

Пример.

Пусть искомый IP-⁠адрес 192.168.128.0 и дана таблица:

A	B	C	D	E	F	G	H
128	168	255	8	127	0	17	192

В этом случае правильный ответ будет записан в виде: HBAF.

11.  

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

12.  

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

Например, если Чертёжник находится в точке с координатами (4, 2), то команда Сместиться на (2, −3) переместит Чертёжника в точку (6, −1).

Запись

Повтори k раз

Команда1 Команда2 КомандаЗ

Конец

означает, что последовательность команд Команда1 Команда2 КомандаЗ повторится k раз.

Чертёжнику был дан для исполнения следующий алгоритм:

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

Повтори 4 раз

Сместиться на (3,1) Сместиться на (0, 2) Сместиться на (−1, 4) конец

На какую команду можно заменить этот алгоритм?

1)  Сместиться на (8, 28)

2)  Сместиться на (7, 29)

3)  Сместиться на (−8, −28)

4)  Сместиться на (−7, −29)

13.  

На рисунке – схема дорог, связывающих города A, B, C, D, E, F, G H. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой. Сколько существует различных путей из города A в город H?

14.  

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

15.  

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

Ключевое слово	Количество сайтов,для которых данное слово является ключевым
принтеры	400
сканеры	300
мониторы	500

Сколько сайтов будет найдено по запросу (принтеры | мониторы) & сканеры

если по запросу принтеры | сканеры было найдено 600 сайтов,

по запросу принтеры | мониторы – 900,

а по запросу сканеры | мониторы – 750.

16.  

Обозначим через m&n поразрядную конъюнкцию неотрицательных целых чисел m и n.

Так, например, 14&5  =  1110₂&0101₂ = 0100₂ = 4.

Для какого наименьшего неотрицательного целого числа А формула

$левая круглая скобка левая круглая скобка x\28 не равно 0 правая круглая скобка \vee левая круглая скобка x\45 не равно 0 правая круглая скобка правая круглая скобка arrow левая круглая скобка левая круглая скобка x\48=0 правая круглая скобка arrow левая круглая скобка x\A не равно 0 правая круглая скобка правая круглая скобка$

тождественно истинна (то есть принимает значение 1 при любом неотрицательном целом значении переменной x)?

Решение. Преобразуем выражение по законам алгебры логики:

(¬Х + ¬Y) → (W → ¬Z) = ¬(¬Х + ¬Y) + (¬W + ¬Z) = ХY + ¬(WZ) = WZ → XY.

Далее применяем обозначения и реализуем способ решения, изложенный К. Ю. Поляковым в теоретических материалах (см., например, раздел «Теория» на нашем сайте), без дополнительных пояснений.

Имеем импликацию Z₄₈Z_A → Z₂₈Z₄₅ или Z_{(48 or А)} → Z_{(28 or 45)}. Поскольку 28₁₀  =  11100₂, 45₁₀  =  101101₂, для побитовой дизъюнкции имеем: 28or45  =  111101. Тогда Z_{(48 or А)} = Z₆₁.

Импликация принимает вид Z_{(48 or A)} → Z₆₁. Единичные биты двоичной записи числа 61, должны являться единичными битами левой части. Поэтому в побитовой дизъюнкции 48orA единицы должны стоять на нулевой, второй, третьей, четвертой и пятой позициях (как обычно, считая справа налево, начиная с нуля). Запишем числа 48, А и 61 в двоичной системе счисления, и выясним, что наименьшее число, дающее при поразрядной дизъюнкции единицы на указанных позициях:

48: 110000

 A:  ??1101

61: 111101

В записи наименьшего числа, дающего при поразрядной дизъюнкции с числом 48 единицы в необходимых разрядах, на месте знаков ? должны стоять нули. Тем самым, искомым числом является А  =  1101₂  =  13₁₀.

Приведём другое решение.

Решим задание с помощью языка программирования PascalABC методом перебора:

var

A, x: integer;

B: boolean;

begin

for A := 0 to 63 do begin

B := True;

for x := 0 to 63 do

if not (((x and 28) = 0) and ((x and 45) = 0) or ((x and 48) <> 0) or ((x and A) <> 0)) then

B := False;

if B then begin

writeln(A);

break;

end;

end.

Приведём аналогичное решение на языке Python.

for A in range(64):
    B = True
    for x in range(64):
        if ((x&28==0) and (x&45==0) or (x&48!=0) or (x&A!=0))==0:
            B=False
    if B:
        print(A)
        break

Заметим, что можно не перебирать числа, большие 63, поскольку для записи чисел 28, 45 и 48 хватит шести разрядов. Программа выведет ответ 13.

Ответ: 13.

17.  

Ниже на пяти языках программирования записан алгоритм. Получив на вход число N, этот алгоритм печатает число q. Укажите наименьшее из таких чисел N, при вводе которого алгоритм напечатает 13.

Бейсик	Паскаль
DIM N, q, i AS INTEGER INPUT N FOR i = 1 TO N - 1 IF N MOD i = 0 THEN q = i NEXT i PRINT q	var N, q, i: integer; begin read(N); for i : = 1 to N - 1 do begin if N mod i = 0 then q : = i end; write(q) end.
Си++	Алгоритмический язык
#include <iostream> using namespace std; int main() { int N, q, i; cin >> N; for (i = 1; i <= N - 1; i++) { if (N%i == 0) q = i; } cout « q « endl; }	алг нач цел N, q, i ввод N нц для i от 1 до N - 1 если mod(N, i) = 0 то q : = i все кц вывод q кон
Python
n = int(input()) for i in range(1, n):     if n % i == 0:         q = i print(q)

18.  

Определите значение переменной с после выполнения следующего фрагмента программы {записанного ниже на разных языках программирования). Ответ запишите в виде целого числа.

Бэйсик	Паскаль
a = 20 b = 6 a = a - 3 * b IF a > b THEN     с = a + 2 * b ELSE     с = b + 2 * a ENDIF	a := 20; b := 6; a := a - 3 * b; if a > b then     c := a + 2 * b else     c := b + 2 * a;
Си++	Алгоритмический язык
a = 20; b = 6; a = a - 3 * b; if (a > b)     с = a + 2 * b; else     с = b + 2 * a;	a := 20 b := 6 a := a - 3 * b если a > b     то c := a + 2 * b     иначе с := b + 2 * a все
Python
a = 20 b = 6 a = a - 3 * b if a > b:     с = a + 2 * b else:     с = b + 2 * a

№ п/п	№ задания	Ответ
1	10464	7
2	3779	2
3	7241	2
4	6224	3
5	6418	2112
6	3563	75
7	2402	1288
8	26982	1296
9	10501	4321021
10	3532	HBDA
11	5514	140
12	7616	2
13	3520	14
14	2339	6, 8, 12, 24
15	3452	150
16	10419	13
17	5247	26
18	5966	10

Ключ