аддитивные технологии. Вариант ЕГЭ. Задание Для хранения целого числа со знаком используется один байт. Сколько единиц содержит внутреннее представление числа (78) Задание 2

• Название: Задание Для хранения целого числа со знаком используется один байт. Сколько единиц содержит внутреннее представление числа (78) Задание 2
• Анкор: аддитивные технологии
• Дата: 01.11.2020
• Размер: 149.43 Kb.
• Имя файла: Вариант ЕГЭ.docx
• Тип: Документы; #147154
• страница: 3 из 4

Задание 8.

1. 
   из программы видно, что начальные значения переменных k и s равны нулю
   
2. 
   цикл заканчивается, когда нарушается условие s < 1024, то есть количество шагов цикла определяется изменением переменной s
   
3. 
   после окончания цикла выводится значение переменной k
   
4. 
   таким образом, задача сводится к тому, чтобы определить число шагов цикла, необходимое для того, чтобы значение s стало не меньше 1024
   
5. 
   с каждым шагом цикла значение s увеличивается на 10, а значение k – на единицу, так что фактически k – это счётчик шагов цикла
   
6. 
   поскольку s увеличивается на 10, конечное значение s должно быть кратно 10, то есть это 1030 > 1024
   
7. 
   для достижения этого значения переменную s нужно 103 раза увеличить на 10, поэтому цикл выполнится 103 раза
   
8. 
   так как k – это счётчик шагов цикла, конечное значение k будет равно 103
   

Ответ: 103.
Задание 9.

1. 
   вспомним, что 1 Мбайт = 2¹⁰ Кбайт = 2²⁰ байт = 2²³ бит
   
2. 
   время передачи несжатого файла (по варианту Б): 40  2²³ / 2²³ = 40 с
   
3. 
   время передачи файла по варианту А: 16 + 0,9  40 + 2 = 18 + 36 = 54 с
   
4. 
   таким образом, быстрее вариант Б на 54 – 40 = 14 с
   

Ответ: Б14.
Задание 10.

1. 
   в последовательности из 5 символов нужно использовать ровно две буквы А и три символа, не совпадающих с А, которые обозначим звездочкой
   
2. 
   сначала найдём количество перестановок из двух букв А и трёх звёздочек
   
3. 
   используем формулу для вычисления числа перестановок с повторениями:
   

Здесь – количество букв А, – количество звёздочек и восклицательный знак обозначает факториал натурального числа, то есть произведение всех натуральных чисел от 1 до :

4. 
   в нашем случае и , так что получаем
   

5. 
   теперь разберёмся со звёздочками: вместо каждой из них может стоять любой из трёх символов (кроме А), то есть на каждую из 10 перестановок мы имеем 3³ = 27 вариантов распределения остальных символов на месте звёздочек
   
6. 
   таким образом, получаем всего 10 · 27 = 270 вариантов.
   

Ответ: 270.
Задание 11.

1. 
   можно обойтись и без дерева, учитывая, что при каждом вызове с n < 5 происходит два рекурсивных вызова; сумму чисел, полученных при вызове , обозначим через :
   

2. 
   выполняем вычисления:
   

3. 
   теперь остаётся вычислить ответ «обратным ходом»:
   
4. 
   
   

Ответ: 49.
Задание 12.

1. 
   вспомним, что в маске сначала стоят все единицы (они выделяют часть IP-адреса, которая соответствует адресу подсети), а затем – все нули (они соответствуют части, в которой записан адрес компьютера)
   
2. 
   для того, чтобы получить адрес подсети, нужно выполнить поразрядную логическую операцию «И» между маской и IP-адресом (конечно, их нужно сначала перевести в двоичную систему счисления)
   

IP-адрес: 124.128.112.142 = 01111100.10000000.01110000.10001110

Маска: ???.???.???.??? = ????????.????????.????????.????????

Подсеть: 124.128. 64. 0 = 01111100.10000000.01000000.00000000

3. 
   Биты, которые выделены жёлтым фоном, изменились (обнулились!), для этого соответствующие биты маски должны быть равны нулю (помним, что X и 1 = X, а X и 0 = 0)
   
4. 
   С другой стороны, слева от самого крайнего выделенного бита стоит 1, поэтому этот бит в маске должен быть равен 1
   
5. 
   Поскольку в маске сначала идет все единицы, а потом все нули, маска готова, остаётся перевести все числа из двоичной системы в десятичную:
   

Подсеть: 124.128. 64. 0 = 01111100.10000000.01000000.00000000

Маска: 255.255.192.000 = 11111111.11111111.11000000.00000000

6. 
   Нам нужно только третье число, оно равно 192 (кстати, первое и второе всегда равны 255).
   

Ответ: 192.
Задание 13.

1. 
   если бы мы знали точно, сколько цифр и сколько специальных символов содержит пароль и где точно они расположены, можно было бы использовать «раздельное» кодирование: на кодирование цифр использовать по 4 бита (2⁴ > 10), на кодирование спецсимволов – по 3 бита (2³ > 6), а на кодирование остальных символов (латинских букв) – по 6 бит (2⁶ > 26·2=52)
   
2. 
   поскольку количество и месторасположение цифр и спецсимволов а пароле неизвестно, нужно рассматривать полный набор символов: 10 + 6 + 26·2 = 68
   
3. 
   при этом на каждый символ нужно выделить 7 бит (2⁷ > 68)
   
4. 
   на 11 символов пароля выделяется 77 бит, округляя вверх до целого числа байт получаем 10 байт (80 бит) на пароль
   
5. 
   на одного пользователя выделяется 900 : 30 = 30 байт
   
6. 
   на дополнительную информацию остается 30 – 10 = 20 байт
   

Ответ: 20.
Задание 14.

1. 
   запишем общее изменение координат Чертёжника в результате выполнения этого алгоритма:
   

2. 
   поскольку Чертёжник должен вернуться в исходную точку, эти величины должны быть равны нулю; следовательно, нужно найти набольшее натуральное n, при котором система уравнений
   

разрешима в целых числах относительно a и b

3. 
   несложно заметить, что для этого число n должно быть одновременно делителем чисел 14 и 25
   
4. 
   наибольший общий делитель чисел 14 и 25 равен 1
   

Ответ: 1.

Задание 15.

1. 
   нарисуем граф, в котором множественные дороги из одного города в другой будем обозначать одной дугой и подписывать около неё количество дорог:
   

2. 
   выпишем все маршруты, по которым можно ехать из A в D так, чтобы дважды не проезжать один и тот же город:
   

   1 1	1 2	1 2 2	1 2 1
   A  B  D	A  С  D	A  B  С  D	A  C  B  D

3. 
   теперь рассмотрим маршрут A  B  D; на всех участках только одна дорога, поэтому есть только один такой маршрут
   
4. 
   для маршрута A  С  D: на первом участке только одна дорога, на втором – две, общее число маршрутов равно произведению этих чисел: 1*2 = 2
   
5. 
   аналогично находит количество различных путей по другим маршрутам
   

A  B  С  D: 1*2*2 = 4

A  C  B  D: 1*2*1 = 2

6. 
   всего получается 1 + 2 + 4 + 2 = 9.
   

Ответ: 9.
Задание 16.

1. 
   общий вид чисел, которые дают остаток 5 при делении на 16:
   

где – целое неотрицательное число (0, 1, 2, …)

2. 
   среди всех таких чисел нужно выбрать те, что меньше или равны 25 («не превосходят 25»); их всего два: 5 (при ) и 21 (при )
   

Ответ: 5, 21.
Задание 17.

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

(США & Япония) | (США & Китай)  США & (Япония | Китай)

2. 
   тогда вводя обозначение для областей
   

A = США, B = Япония | Китай,

получаем стандартную задачу с двумя переменными:

Запрос	Количество страниц (тыс.)
А | B	450
B	260
А & B	50
А	?

3. 
   имеем по формуле
   

N_A = N_A|B - N_B + N_A&B = 450 – 260 + 50 = 240

Ответ: 240.

Задание 18.

1. 
   заметим, что здесь два условия объединяются с помощью логической операции «И»:
   

(x  A)  (x²  64)

(x²  25)  (x  A)

2. 
   рассмотрим первое условие; чтобы импликация была истинна, при истинной левой части (посылке) вторая часть (следствие) тоже должна быть истинна
   
3. 
   это значит, что если x принадлежит отрезку A, должно выполняться условие x²  64, то есть
   

| x |  8, поэтому отрезок A должен целиком содержаться внутри отрезка [–8; 8]

4. 
   теперь рассмотрим второе условие: если x²  25, то есть если | x |  5, то такой x должен принадлежать отрезку A
   
5. 
   это значит, что весь отрезок [–5; 5] должен находиться внутри A, длина этого отрезка – 10.
   

Ответ: 10.
Задание 19.

1. 
   в программе есть вложенный цикл, в котором переменная i обозначает строку, а k – столбец матрицы
   
2. 
   элементы, для которых i=k – это главная диагональ матрицы, поэтому элементы, для которых i > k (только они будут равны 1), находятся под главной диагональю
   
3. 
   в первой строке единичных элементов нет, во второй есть один такой элемент, в третьей – 2, в последней (10-ой) их 9, поэтому сумма элементов массива равна
   

1 + 2 + 3 + 4 + 5 + 6 + 7 + 8 + 9 = 45

4. 
   таким образом, правильный ответ – 45.
   
5. 
   при большом размере массива (например, 100 на 100) суммирование может оказаться трудоемким, поэтому лучше вспомнить формулу для вычисления суммы элементов арифметической прогрессии (именно такая прогрессия у нас, с шагом 1):
   

,

где - количество элементов, а и – соответственно первый и последний элементы последовательности; в данном случае имеем

.

Ответ: 45.

Задание 20.

1. 
   видим, что в последней строке выводится на экран переменная M
   
2. 
   ключевой момент решения: нужно узнать в строках программы, отмеченных знаком * в комментариях, АЛГОРИТМ ЕВКЛИДА для вычисления наибольшего общего делителя (НОД) чисел, записанный в переменные M и L
   
3. 
   введённое значение x записывается в переменную L и участвует в поиске НОД
   
4. 
   в переменную M до начала цикла записывается 65, но если было введено чётное
   (L mod 2 = 0) значение x (оно же L), значение M заменяется на 52
   
5. 
   сначала предположим, что замены не было, и в M осталось значение 65; поскольку по условию алгоритм печатает 26, тогда получается, что НОД(x,65)=26; этого явно не может быть, потому что 65 не делится на 26
   
6. 
   делаем вывод, что введено чётное значение x и произошла замена M на 52
   
7. 
   итак, нужно найти чётное число x, большее 100, такое, что НОД(x,52)=26
   
8. 
   первое число, большее 100, которое делится на 26 – это 104, но оно не подходит, потому что делится ещё и на 52, так что НОД(x,52)=52
   
9. 
   поэтому берём следующее число, которое делится на 26: 104 + 26 = 130
   

Ответ: 130.
Задание 21.

1. 
   Рассмотрим, как работает функция, приведенная в программе. Заметим, что (x mod 2) – младшая цифра двоичного представления числа х в двоичной системе счисления, (x div 2) – число х без младшей своей цифры в двоичном представлении.
   
2. 
   Таким образом, функция находит произведение цифр числа в двоичном представлении. Программа в целом находит количество чисел, произведение цифр в двоичной записи которых равно 1, то есть таких чисел, двоичная запись которых не содержит нулей.
   
3. 
   В общем виде такие числа можно представить, как 2ⁿ-1, где n – натуральное число. В диапазоне от 1 до 20 таких чисел 4: 1, 3, 7, 15. А в диапазоне от 1 до 100 – 6: 1, 3, 7, 15, 31, 63.
   
4. 
   Таким образом, искомые числа – это числа от 15 до 30.
   

Ответ: 16.
Задание 22.

1. 
   заметим, что при выполнении любой из команд число увеличивается (не может уменьшаться)
   
2. 
   для начального числа 2 количество программ равно 1: существует только одна пустая программа, не содержащая ни одной команды; если через обозначить количество разных программ для получения числа N из начального числа 2, то .
   
3. 
   теперь рассмотрим общий случай, чтобы построить рекуррентную формулу, связывающую с предыдущими элементами последовательности , то есть с решениями таких же задач для меньших N
   
4. 
   число N могло быть получено одной из трёх операций сложения:
   

• 
  увеличением на 1 числа N-1;
  
• 
  увеличением на 2 числа N-2;
  
• 
  из некоторого числа X увеличением на X+1 (следующее число), так что N = X + X + 1, откуда X = (N – 1) / 2; так могут быть получены только нечетные числа;
  

поэтому

для чётных чисел

для нечётных чисел

5. 
   остается по этой формуле заполнить таблицу для всех значений от 2 до 10:
   

N	2	3	4	5	6	7	8	9	10
	1	1	2	4	6	11	17	30	47

Ответ: 47.

Задание 23.

1. 
   упростим первые три уравнения, подставив y₂ = 0, откуда следует, что x₂  y₂ = 0:
   

x₁  y₁ = 0

1 + (x₃  y₃) = 1

((x₃  y₃))  (x₄  y₄) = 1

2. 
   очевидно, что первое уравнение имеет 3 решения: (x₁, y₁) = (0, 0), (1, 0) и (0, 1)
   
3. 
   поскольку x₂ входит в уравнение только в составе выражения x₂  y₂ = 0, существует 2 варианта выбора x₂ (0 и 1)
   
4. 
   из второго уравнения видим, что произведение x₃  y₃ может быть равно как 0, так и 1
   
5. 
   для случая x₃  y₃ = 1 (что дает только одна пара (x₃ , y₃) = (1, 1)) третье уравнение сводится к
   

(x₄  y₄) = 1

которое имеет одно решение (x₄ , y₄) = (1, 1)

6. 
   для случая x₃  y₃ = 0 (что дает три пары (x₃ , y₃) = (0, 0), (0, 1) и (1, 0)) третье уравнение сводится к
   

1 + (x₄  y₄) = 1

которое имеет четыре решения решение (x₄ , y₄) – любые комбинации переменных

7. 
   Общее количество решения по правилам комбинаторики: 3*2*(1*1+3*4) = 78
   

Ответ: 78.