1.
1 задание. Демо ЕГЭ 2021 информатика, ФИПИ:
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Г в пункт Ж. В ответе запишите целое число – так, как оно указано в таблице.
Ответ: 9
Видео
2.
2 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Миша заполнял таблицу истинности функции
(x ∨ y) ∧ ¬(y ≡ z) ∧ ¬w
но успел заполнить лишь фрагмент из трёх различных её строк, даже не указав, какому столбцу таблицы соответствует каждая из переменных w, x, y, z.
Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных w, x, y, z.
Перем.1 | Перем.2 | Перем.3 | Перем.4 | Функция |
??? | ??? | ??? | ??? | F |
1 | 1 | 1 | ||
0 | 1 | 0 | 1 | |
1 | 1 | 0 | 1 |
В ответе запишите буквы в том порядке, в котором идут соответствующие им столбцы.
3.
3 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID женщины, ставшей матерью в наиболее молодом возрасте. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц. Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID женщины, ставшей матерью в наиболее молодом возрасте. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.
Ответ: 64
4.
4 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв – П и Р – кодовые слова неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.
5.
5 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа).
Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия – справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R.
Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
Ответ: 19
Разбор
подобного
задания смотрите на видео:
Видео
✍ Решение:
- Заметим, что после второго пункта условия задачи получаются только четные числа (т.к. если число в двоичной системе заканчивается на 0, то оно четное). Таким образом, нас будут интересовать только четные числа.
- Наименьшим возможным числом, превышающим 77, является число 78. С ним и будем работать.
- Переведем 78 в двоичную систему счисления. Используя компьютер это можно сделать с помощью программистского режима калькулятора. Либо в консоли интерпретатора Python набрать bin(78). Получим:
1001110
N
. Значит, необходимое нам двоичное число — это 10011. После первого пункта задачи к данному числу должна была добавиться справа единица, так и есть: 100111. А затем добавляется 0: 1001110. Соответственно, оно подходит.int('10011',2)
Ответ: 19
6.
6 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Определите, при каком наименьшем введённом значении переменной s программа выведет число 64. Для Вашего удобства программа представлена на четырёх языках программирования.
Паскаль:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
var s, n: integer; begin readln(s); n := 1; while s < 51 do begin s := s + 5; n := n * 2 end; writeln(n) end. |
Алгоритмический язык:
алг нач цел n, s ввод s n := 1 нц пока s < 51 s := s + 5 n := n * 2 кц вывод n кон |
Python:
s = int(input()) n = 1 while s < 51: s = s + 5 n = n * 2 print(n) |
С++:
#include <iostream> using namespace std; int main() { int s, n; cin >> s; n = 1 ; while (s < 51) { s = s + 5; n = n * 2; } cout << n << endl; return 0; } |
✍ Решение:
-
✎ Способ 1 (программный):
- Поскольку в цикле
s
увеличивается, а по условию задания следует найти наименьшее значениеs
, то можно начать сs=1
, постоянно увеличивая значениеs
на единицу во внешнем цикле. - Важно для внешнего цикла использовать другую переменную, т.к. во внутреннем цикле переменная
s
меняется, а нам следует каждый шаг внешнего цикла сохранить предыдущее значение s, увеличив его всего на 1. Используем переменнуюS1
для этих целей.
Pascalabc.net:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
begin var s1 := 1; while true do // внешний цикл, бесконечный begin var s := s1; // --- код из условия задания --- // var n := 1; while s < 51 do begin s := s + 5; n := n * 2 end; if n = 64 then // если найдено, то выводим соответствующее s begin print(s1); break; // выход из бесконечного цикла end; s1 := s1 + 1; // end; end. |
Пояснение:
Бейсик: |
Python:
s1 = 1 while True: # внешний цикл, бесконечный s = s1 # --- код из условия задания --- n = 1 while s < 51: s = s + 5 n = n * 2 # --- конец кода из условия задания --- if n == 64: print(s1) break s1 += 1 |
С++: |
Ответ: 21
7.
7 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Для хранения произвольного растрового изображения размером 128×320 пикселей отведено 20 Кбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков.
Какое максимальное количество цветов можно использовать в изображении?
Ответ: 16
Разбор
подобного
задания смотрите на видео:
🎦 Видео
8.
8 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?
Ответ: 48
✍ Решение:
-
✎ Решение с использованием программирования:
PascalABC.net:
|
||
Python:
|
||
С++: |
Разбор подобного задания смотрите на видео:
🎦 Видео
9.
9 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Задание выполняется с использованием прилагаемых файлов
Откройте файл электронной таблицы, содержащей вещественные числа – результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев.
Найдите разность между максимальным значением температуры и её средним арифметическим значением.
В ответе запишите только целую часть получившегося числа.
10.
10 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Задание выполняется с использованием прилагаемых файлов
С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «долг» или «Долг» в тексте романа в стихах А.С. Пушкина «Евгений Онегин». Другие формы слова «долг», такие как «долги», «долгами» и т.д., учитывать не следует. В ответе укажите только число.
11.
11 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
При регистрации в компьютерной системе каждому объекту сопоставляется идентификатор, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом объекте отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно идентификатора, для каждого объекта в системе хранятся дополнительные сведения, для чего отведено 24 байта на один объект.
Определите объём памяти (в байтах), необходимый для хранения сведений о 20 объектах. В ответе запишите только целое число – количество байт.
Ответ: 600
Разбор
подобного
задания смотрите в видео:
🎦 Видео
12.
12 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды заменить (111, 27) преобразует строку 05111150 в строку 0527150.Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка исполнителя при этом не изменяется.
…
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.
НАЧАЛО ПОКА нашлось (2222) ИЛИ нашлось (8888) ЕСЛИ нашлось (2222) ТО заменить (2222, 88) ИНАЧЕ заменить (8888, 22) КОНЕЦ ЕСЛИ КОНЕЦ ПОКА КОНЕЦ
-
✎ Решение с использованием программирования:
PascalABC.NET:
Вариант 1:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 |
begin var s := '8'*70; var p2 := Pos('2222',s); var p8 := Pos('8888',s); while (p2 > 0) or (p8 > 0) do begin if p2 > 0 then begin Delete( s, p2, 4 ); Insert( '88', s, p2 ); end else begin Delete( s, p8, 4 ); Insert( '22', s, p8 ); end; p2 := Pos('2222',s); p8 := Pos('8888',s); end; write(s); end. |
Вариант 2:
1 2 3 4 5 6 7 8 9 10 11 |
begin var s: string := '8' * 70; while (s.contains('2222')) or (s.contains('8888')) do begin if (s.contains('2222')) then s := s.replace('2222', '88') else s := s.replace('8888', '22'); end; writeln(s); end. |
Питон:
1 2 3 4 5 6 7 |
s = 70 * '8' while "2222" in s or "8888" in s: if "2222" in s: s = s.replace( "2222", "88", 1 ) else: s = s.replace( "8888", "22", 1 ) print(s) |
Разбор подобного задания смотрите в видео:
🎦 Видео
13.
13 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город В?
Ответ: 24
Разбор
подобного
задания смотрите в видео:
🎦 Видео
14.
14 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Значение арифметического выражения: 497 + 721 – 7 – записали в системе счисления с основанием 7. Сколько цифр 6 содержится в этой записи?
Ответ: 13
✍ Решение:
✎ Решение с использованием программирования:
PascalABC.NET:
begin var k := 0; var x: Biginteger; x := Biginteger.Pow(49, 7) + Biginteger.Pow(7, 21) - 7; // в получившемся числе рассматриваем каждую цифру в 7-й системе сч. while x > 0 do begin if x mod 7 = 6 then k += 1; // если цифра = 6, то считаем ее x := x div 7; // убираем разряд числа в 7-й системе сч. end; println(k); end. |
Python:
x = 49**7 + 7**21 - 7 k = 0 # в получившемся числе рассматриваем каждую цифру в 7-й системе сч. while x: if x % 7 == 6: # если цифра = 6, то считаем ее k += 1 x //= 7 # убираем разряд числа в 7-й системе сч. print( k ) |
С++: |
Ответ: 13
Разбор подобного задания смотрите в видео:
🎦 Видео
15.
15 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Обозначим через ДЕЛ(n, m)
утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной х)?
Ответ: 18
✍ Решение:
✎ Решение с использованием программирования:
PascalABC.NET:
Питон:
1 2 3 4 5 6 |
for A in range(1,1000): OK = 1 for x in range(1,1000): OK *= (x % A != 0) <= ((x % 6 == 0) <= (x % 9 != 0)) if OK: print( A ) |
C++:
✎ Решение теоретическое:
- Введем обозначения и перепишем исходную формулу:
¬А → (6 → ¬9) = 1
А ∨ ¬6 ∨ ¬9 = 1
¬(¬6 ∨ ¬9) = 1
6 ∧ 9 = 1
А
, на которое делятся все натуральные х
, такое что эти х
делятся и на 6 и на 9 одновременно:x/A : x/6 AND x/9
х
, которые одновременно делятся и на 6 и на 9:х = 18, 36, 54, 72 ...
А
, начиная с наименьшего, до такого наибольшего А, которое будет делителем всех найденных х
:А = 1, 2, 3,4,5, ... 18
При попытке взять большее А
, x
равный 18 не будет делиться на такое А
.
Ответ: 18
16.
16 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Алгоритм вычисления значения функции F(n), где n – натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1; F(n) = n + F(n − 1), если n – чётно, F(n) = 2 × F(n − 2), если n > 1 и при этом n – нечётно
Чему равно значение функции F(26)?
Ответ: 4122
🎦 Видео
✍ Решение:
✎ Решение с использованием программирования:
PascalABC.NET:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
function F(n: integer): integer; begin if n <= 1 then F := 1; if n mod 2 = 0 then F := n + F(n - 1); if (n > 1) and (n mod 2 <> 0) then F := 2 * F(n - 2) end; begin print(F(26)) end. |
Питон:
1 2 3 4 5 6 7 8 |
def F( n ): if n <= 1: return 1 if (n % 2 == 0): return n + F(n-1) if (n>1 and n % 2 != 0): return 2 * F(n-2) print (F(26)) |
C++:
Ответ: 4122
17.
17 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Рассматривается множество целых чисел, принадлежащих числовому отрезку [1016; 7937], которые делятся на 3 и не делятся на 7, 17, 19, 27. Найдите количество таких чисел и максимальное из них.
В ответе запишите два целых числа: сначала количество, затем максимальное число.
! Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц
Ответ: 1568 | 7935
🎦 Видео
✍ Решение:
-
✎ Решение с использованием программирования:
- Первое значение диапазона введем в ячейку A1:
- Используем прогрессию для заполнения всего диапазона числами. Для это выберите вкладку Главная и щелкните по кнопке Прогрессия:
- Столбец B будем использовать для поиска чисел, которые делятся на 3. Для этого в ячейку B1 введите формулу с рисунка:
- Двойным щелчком по маркеру заполнения скопируйте формулу на весь столбец:
- Столбец С будем использовать для поиска чисел, которые НЕ делятся на 7. Для этого в ячейку С1 введите формулу с рисунка:
- Заполните весь столбец двойным щелчком по маркеру заполнения.
- Cтолбцы D, E, F таким же образом будем использовать для поиска чисел столбца А, которые не делятся на 17, 19 и 27
- Для поиска всех истинных значений используем столбец G. В ячейку G1 введите функцию
ЕСЛИ
: если все значения ячеек в столбцах B-F в этой строке истинны, выводим число из А1, иначе – пустую строку: - Ячейку H1 будем использовать для подсчета таких чисел, которые удовлетворяют всем условиям, т.е. для подсчета непустых ячеек столбца G:
- Ячейку H2 будем использовать для подсчета такого наибольшего числа:
Паскаль:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 |
var i, k, max: integer; begin k := 0; max := 0; for i := 1016 to 7937 do begin if (i mod 3 = 0) and (i mod 7 > 0) and (i mod 17 > 0) and (i mod 19 > 0) and (i mod 27 > 0) then begin max:= i; inc(k); end; end; writeln(k, ' ', max) end. |
PascalABC.NET:
1 2 3 4 |
begin var s := Range( 1017, 7937, 3).Where( i -> not i.DivsAny(7, 17, 19, 27) ); print( s.Count, s.Max ); end. |
Питон:
1 2 3 |
a = [n for n in range(1016,7937+1) if (n%3==0 and n%7!=0 and n%17!=0 and n%19!=0 and n%27!=0)] print(len(a),max(a)) |
Список a формируем, используя генератор списка: то есть в список попадут только не числа из диапазона [1016,7937], которые удовлетворяют всем перечисленным условиям: n%3==0
(число делится на 3), n%7!=0
(число не делится на 7) и т.п.
C++:
1 2 3 4 5 6 7 8 9 10 11 12 13 |
#include <iostream> int main() { int count = 0; int maxGood = 0; for(int n=1016; n<=7937; n++) if( (n % 3 == 0) and (n % 7 != 0) and (n % 17 != 0) and (n % 19 != 0) and (n % 27 != 0) ) { maxGood = n; count += 1; } std::cout << count << " " << maxGood; } |
✎ Решение с помощью Excel:
Заполните весь столбце, используя маркер автозаполнения.
🎦 Видео
18.
18 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Задание выполняется с использованием прилагаемых файлов
Квадрат разлинован на N×N клеток (1 < N < 17
). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз – в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю.
В ответе укажите два числа – сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
Для указанных входных данных ответом должна быть пара чисел:
Ответ: 1204 | 502
Видео
Решение подобного задания
19.
19 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза.
Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10).
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче – S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна.
Ответ: 18
✍ Решение 1:
- Нарисуем таблицу, в первом столбце которой будем откладывать количество камней в первой куче, а в первой строке — количество камней во второй куче. Получим матрицу. Поскольку в первой куче количество начинается с 7, то это и будет первым значением в таблице. Во второй куче начнем с наибольшего возможного числа — 69:
- Далее будем рассуждать так: Петя может выиграть первым ходом, выполнив команду *2 (увеличить количество камней в куче в два раза), если вместо
S
(кол-во камней во второй куче), мы будем изменять значение, начиная от 35, до последнего возможного по условию значения 69:
7 + 35*2 = 77 (>=77)
+
означает выигрышную позицию с первого хода.S
, из которого можно попасть в диапазон выигрышных позиций для соперника:17 * 2 = 34 (мало, необходимо 35 и более)
18 * 2 = 36 подходит!
Ответ: 18
✍ Решение 2 (Excel):
- В столбце
А
отложим значения — количество камней в первой куче. Начнем с ячейкиА2
, в которую внесем начальное количество камней, т.е. 7. Автозаполнением продлим значения вниз до 25 примерно: - В строке
1
таблицы (начиная с ячейкиB1
) отложим значения для второй кучи. Поскольку в задании говорится, что 0<=S<=69, то последним значением пусть будет 40. В дальнейшем часть таблицы можно будет удалить: - Из двух команд, которые могут выполнять игроки, выберем наиболее сильную, т.е. благодаря которой можно быстрее достичь выигрышного диапазона и попасть в значения S>=77. Это команда удваивания количества камней, т.е.
*2
. - Для каждой из ячеек полученной таблицы рассчитаем значение, полученное в результате удвоения той кучи камней, в которой большее количество камней (так как это даст бОльший результат). Например, для ячейки С5, в которой игрок имеет в первой куче 10 камней, а во второй куче 2 камня, мы бы выполнили действие 10*2+2. Т.е. удвоили бы первую кучу, т.к. в ней больше камней.
- Чтобы автоматизировать процесс необходимо использовать формулу, в которой найдем максимальное значение из двух вариантов: Максимальное из(1куча*2 + 2куча, 1куча + 2*2куча). Выразив это в формуле Excel, получим результат, который внесем в ячейку
B2
:
=МАКС($A2+2*B$1;2*$A2+B$1)
$
будем использовать для фиксации столбца А и строки 1 при копировании формулы.Ответ: 18
Решение задания смотрите на видео (2 способ, Excel):
Видео
Решение задания смотрите на видео (1 способ):
Видео
Решение подобного задания смотрите на видео:
🎦 Видео
20.
20 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Для игры, описанной в предыдущем задании, найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
Найденные значения запишите в ответе в порядке возрастания.
Ответ: 31 | 34
✍ Решение 1:
- Проанализируем таблицу, увеличивая количество камней в первой куче и выполняя поиск выигрышных позиций с одного хода. Знаком
+2
будет отмечать выигрышные позиции со второго хода, т.е. из которых можно перевести соперника в проигрышную позицию со знаком-
: - Последующая логика рассуждений: Петя может выиграть свои вторым ходом, если он не может выиграть первым ходом, и одновременно получив позицию, выигрышную со второго хода:
(7,34) -> (8,34) (7,31) -> (14,31)
Ответ: 31 34
✎ Решение 2 (Excel)
- Продолжаем работать с той же таблицей, что и в задании 19. Выделим все проигрышные позиции (из которых можно походить только в выигрышные позиции для соперника, т.е. в выделенные ячейки):
Ответ: 31 34
Решение задания смотрите на видео (1 способ):
🎦 Видео
21.
21 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Для игры, описанной в задании 19, найдите минимальное значение S, при котором одновременно выполняются два условия:
✍ Решение:
- Необходимо найти для Пети проигрышные позиции со второго хода. Это должна быть первая строка, т.к. это первый ход Пети. Первое подходящее значение — 33, из него Петя может либо сразу походить в выигрышную позицию с первого хода
(7, 66)
, либо в выигрышную позицию со второго хода:(7,34)
и(8,33)
. - Но есть значение меньше 33, это значение 30:
Ваня выиграет с первого хода, если: Петя (7,60) Ваня выиграет с последующих ходов, если: Петя (7,31), (8,30), (14,30)
Ответ: 30
Решение задания смотрите на видео:
🎦 Видео
22.
22 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Ниже на четырёх языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 4, а потом 5.
Паскаль:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 |
var x, L, M, Q: integer; begin readln(x); Q := 9; L := 0; while x >= Q do begin L := L + 1; x := x - Q; end; M := x; if M < L then begin M := L; L := x; end; writeln(L); writeln(M); end. |
Алгоритмический язык:
алг нач цел x, L, M, Q ввод x Q := 9 L := 0 нц пока x >= Q L := L + 1 x := x - Q кц M := x если M < L то M := L L := x все вывод L, нс, M кон |
Python:
x = int(input()) Q = 9 L = 0 while x >= Q: L = L + 1 x = x - Q M = x if M < L: M = L L = x print(L) print(M) |
С++:
#include <iostream> using namespace std; int main() { int x, L, M, Q; cin >> x; Q = 9; L = 0; while (x >= Q){ L = L + 1; x = x - Q; } M = x; if (M < L){ M = L; L = x; } cout <<L <<endl <<M <<endl; return 0; } |
Ответ: 49
23.
23 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2.
Программа для исполнителя – это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 20, и при этом траектория вычислений содержит число 10?
Траектория вычислений программы – это последовательность результатов выполнения всех команд программы.
Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Ответ: 28
24.
24 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Задание выполняется с использованием прилагаемых файлов
Текстовый файл состоит не более чем из 106 символов X, Y и Z.
Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.
Для выполнения этого задания следует написать программу.
Ответ: 35
🎦 Видео
✍ Решение:
-
Паскаль:
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 |
var f: text; i, k, max: integer; s: string; begin assign(f, 'D:24.txt'); reset(f); readln(f, s); max := 1; k := 1; // кол-во подряд идущих for i := 2 to length(s) do begin if s[i] <> s[i - 1] then begin inc(k); if k > max then max := k; end else k := 1; end; write(max) end. |
Python:
1 2 3 4 5 6 7 8 9 10 11 |
f=open('D:/24.txt') s=f.readline() m=1 k=1 for i in range(1,len(s)): if s[i]!=s[i-1]: k+=1 m=max(k,m) else: k=1 print(m) |
25.
25 задание. Демоверсия варианта ЕГЭ по информатике 2021, ФИПИ:
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.
Например, в диапазоне [5; 9] ровно два целых различных натуральных делителя имеют числа 6 и 8, поэтому для этого диапазона таблица на экране должна содержать следующие значения:
2 | 3 2 | 4
Ответ:
3 | 58153 7 | 24923 59 | 2957 13 | 13421 149 | 1171 5 | 34897 211 | 827 2 | 87251
Разбор подобного задания смотрите на видео:
🎦 Видео
✍ Решение:
- Поскольку требуется искать числа, у которых есть всего два делителя, то следует помнить, что:
- Будем использовать оптимизированный вариант программы, подходящий для «медленных» компьютеров. Для этого перебор делителей для числа
n
будем выполнять от2
до√n
, округлив его до ближайшего целого числа (не включая точный квадратный корень, если он существует):
PascalABC.net:
|
||
Python:
|
||
С++: |
✎ Решение (оптимизированный вариант 1):
если число имеет ровно два делителя, отличных от единицы и самого числа, то произведение этих делителей и есть само число
вместо диапазона делителей [2; число] использовать диапазон [2; округл(√n)]
n
), то в список делителей добавлять будем только сам делитель, если нет – то добавляем пару делителей (делитель
и n // делитель
):Пример: число 8 = 2 * 4 Достаточно рассмотреть цикл от 2 до округл(√8) (=2) если 8 делится на 2 и 8/2 не равно 2, то делители: 2 и 4 (8/2)
PascalABC.net:
|
||
Python:
|
||
С++: |
✎ Решение (оптимизированный вариант 2):
Python:
1 2 3 4 |
for n in range(174457, 174505+1): divs = [d for d in range(2, n) if n % d == 0] # range(2, n), т.к. два делителя, не считая 1 и самого числа if len(divs) == 2: print( *divs ) |
✎ Решение (оптимизированный вариант 3):
PascalABC.net:
|
||
Python:
|
||
С++: |
26.
27.
Сегодня на повестке дня 8 задание из ЕГЭ по информатике 2021. Данный тип заданий включает в себя нахождение количества вариантов, элементы комбинаторики и другие математические понятия.
Перейдём к практике решения задач задания 8 ЕГЭ по информатике 2021.
Задача (Классика)
Все 4-буквенные слова, составленные из букв А, Е, И, О записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. АААА
2. АААЕ
3. АААИ
4. АААО
5. ААЕА
…
Запишите слово, стоящее на 248-м месте от начала списка.
Решение:
Обозначим условно А — 0, Е — 1, И — 2, О — 3.
Важно: Нужно буквам присваивать цифры именно в том порядке, в котором они идут в самом правом столбце, потому что буквы могут дать в «перепутанном порядке» (например Е, А, И, О), и тогда ничего не получится.
Теперь запишем список с помощью цифр.
1. 0000
2. 0001
3. 0002
4. 0003
5. 0010
…
Получился обычный счёт в четверичной системе!! (всего используются 4 цифры: 0, 1, 2, 3). А слева нумерация показывает соответствие нашей десятичной системе. Но все числа десятичной системы в этой таблице соответствия сдвинуты на 1, ведь мы должны были начать с нуля.
Нас просят записать слово стоящее на 248, т.е. если была обычная таблица соответствия чисел десятичной системы и четверичной системы, слово стоящее на 248 месте, находилось бы на 247 (248 — 1) месте. Значит, наше искомое четверичное число соответствует 247 в десятичной системе.
Переведём число 247 в четверичную систему!
Получилось число 33134 в четверичной системе. Сделаем обратное декодирование в буквы. Таким образом, ответ будет ООЕО.
Ответы: ООЕО
Ещё одна похожая задача 8 задания из примерных вариантов ЕГЭ по информатике, но другой вариации.
Задача (Классика, Другая вариация)
Все 5-буквенные слова, составленные из букв А, Р, У, К записаны в алфавитном порядке. Вот начало списка:
1. ААААА
2. ААААК
3. ААААР
4. ААААУ
5. АААКА
……
Укажите номер слова УКАРА
Решение:
Закодируем буквы цифрами: А — 0, К — 1, Р — 2, У — 3. Здесь как раз буквы даны не в том порядке, как они идут в самом правом столбце. Но мы должны кодировать именно в том порядке, как буквы идут в самом правом столбце.
У нас получилось четыре цифры! Значит снова можно слова превратить в таблицу соответствия между десятичной системой и четверичной системой. Но десятичная система смещена на 1 позицию.
1. 00000
2. 00001
3. 00002
4. 00003
5. 00010
……
Выписываем данное нам слово и посмотрим, какое число в четверичной системе было бы, если бы у нас были в место слов числа в четверичной системе!
Получили число в четверичной системе 310204. Узнаем, какое число в десятичной системе соответствовало этому числу, если бы была обычная таблица соответствия. Для этого переведём число 310204 из четверичной системы в десятичную. Перевод делаем по аналогии перевода из двоичной системы в десятичную.
Но помним, что у нас нумерация идёт на 1 быстрее, нежели мы бы поставили десятичные числа, как в таблице соответствия, потому что нумерация начинается не с нуля, а с 1. Поэтому к числу 840 нужно прибавить 1, и в ответе будет 841
Ответ: 841
Задача (Демонстрационный вариант ЕГЭ по информатике, 2020)
Все 4-буквенные слова, в составе которых могут быть буквы Н, О, Т, К, И,
записаны в алфавитном порядке и пронумерованы, начиная с 1.
Ниже приведено начало списка.
1. ИИИИ
2. ИИИК
3. ИИИН
4. ИИИО
5. ИИИТ
6. ИИКИ
…
Под каким номером в списке идёт первое слово, которое начинается
с буквы О?
Решение:
Закодируем буквы цифрами.
Получилось 5 цифр ( 0, 1, 2, 3, 4 ), значит, будем работать в пятеричной системе.
Нужно найти номер первого слова, которое начинается с буквы О. Если говорить на языке пятеричных чисел, то нужно найти номер числа 30005. Мы «забиваем нулями», чтобы число было четырёхразрядное, т.к. слова 4-х буквенные. Именно нулями, потому что нужно именно первое слово найти.
Теперь, как в предыдущей задаче, переведём число 30005 из пятеричной системы в десятичную.
0 * 5 0 + 0 * 5 1 + 0 * 5 2 +
3 * 5 3 = 375 (в десят. системе)
Но опять же должны прибавить 1 к числу 375, т.к. нумерация отличается от десятичных чисел на 1 в большую сторону.
Ответ: 376
Задача (Досрочная волна 2020 ЕГЭ по информатике, вариант 1)
Вася составляет 5-буквенные слова, в которых есть только буквы В, О, Л, К,
причём буква В используется в каждом слове ровно 1 раз. Каждая из других
допустимых букв может встречаться в слове любое количество раз или
не встречаться совсем. Словом считается любая допустимая
последовательность букв, не обязательно осмысленная. Сколько существует
таких слов, которые может написать Вася?
Решение:
Для начала решим вводную подзадачу.
Пусть у нас есть те же буквы В, О, Л, К, каждая из букв может встречаться в слове любое количество раз или
не встречаться совсем. Сколько можно составить 5-буквенных слов ?
Т.е буквы могут повторяться!
Например
Такая конструкция сильно напоминает перебор чисел, где вместо цифр используются буквы.
Рассмотрим перебор трёхразрядных чисел. Вместо 5 букв теперь можно использовать 10 цифр ( 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ). Цифры так же могут повторяться. Сколько получится вариантов ?
Выведем общую формулу для количества вариантов, когда символы могут повторяться!
Для трёхразрядных чисел от 000 до 999:
N = 103 = 1000 вариантов.
Вернёмся к пятибуквенным словам и нашей подзадаче. Здесь количество букв (разрядов) в слове равно 5, количество допустимых символов равно 4 ( В, О, Л, К ).
N = 45 = 1024 вариантов.
Вернёмся к изначальной задаче. Сначала найдём количество вариантов, когда буква В находится в самой левой ячейке!
Применим формулу! Здесь слово сократилось до четырёхразрядного. А количество букв для использования 3 (О, Л, К).
N = 34 = 81 комбинация.
Но буква В так же может стоять во второй ячейке слева. Этот случай тоже даст 81 других комбинаций. Буква В может стоять в каждой из 5-ти ячеек, и везде будет получатся 81 комбинация.
Таким образом, окончательный ответ будет:
N = 81 * 5 = 405 различных вариантов.
Ответ: 405
Разобравшись с этой задачей, больше половины тренировочных задач десятого задания из различных книг и сайтов по подготовке к ЕГЭ по информатике будут решаться, как по маслу!
Задача(Закрепление формулы)
Рассматриваются символьные последовательности длины 5 в шестибуквенном алфавите {У, Ч, Е, Н, И, К}. Сколько существует таких последовательностей, которые начинаются с буквы У и заканчиваются буквой К?
Решение:
Применим главную формулу 8 задания из ЕГЭ по информатике
N = mi = 63 = 216
Здесь буквы могут изменяться на 3 ячейках! Значит, в формуле i=3. Количество допустимых символов, которые можно поставить в каждую ячейку равно 6. Значит, в формуле m=6.
В ответе будет 216.
Примечание: Здесь можно использовать все буквы в каждой ячейке, включая У и К. В некоторых задачах их уже использовать нельзя, т.е. сказано, что буквы У и К используются один раз в слове. Тогда в формуле m, будет на 2 единицы меньше. Нужно внимательно читать задачу!
Ответ: 216
Задача (Демонстрационный вариант ЕГЭ по информатике, 2019)
Вася составляет 5-буквенные слова, в которых есть только буквы З, И, М, А,
причём в каждом слове есть ровно одна гласная буква и она встречается
ровно 1 раз. Каждая из допустимых согласных букв может встречаться
в слове любое количество раз или не встречаться совсем. Словом считается
любая допустимая последовательность букв, не обязательно осмысленная.
Сколько существует таких слов, которые может написать Вася?
Решение:
Рассмотрим количество вариантов, когда гласная И стоит в первом месте!
Подсчитаем количество слов с помощью супер-формулы
N = mi = 24 = 16
Длина изменяющихся ячеек равна 4, а количество допустимых букв равно 2.
Но буква И может стоять не только на первом месте. Она так же может стоять и на 2, и на 3, и на 4, и на 5 месте. Каждый такое случай добавляет столько же новых слов.
Значит, при использовании только буквы И будет количество слов 16 * 5 = 80. Ещё столько же слов добавится, если в словах вместо буквы И будет использоваться буква А. Поэтому окончательный ответ будет 80 * 2 = 160
Ответ: 160
Отработаем главную формулу 8 задания из ЕГЭ по информатике.
Задача (Развиваем понимание формулы!)
Сколько слов длины 5, начинающихся с согласной буквы и заканчивающихся гласной буквой, можно составить из букв З, И, М, А? Каждая буква может входить в слово несколько раз. Слова не обязательно должны быть осмысленными словами русского языка.
Решение:
Рассмотрим, какие варианты могут быть, если у нас на первом месте стоит согласная, а на последнем месте гласная
Получилось 4 разных случая. Подсчитаем, сколько слов можно составить при одном случае.
N = mi = 43 = 64
Длина изменяющихся ячеек равна 3, а количество возможных букв 4.
Но т.к. таких случая у нас четыре, то ответ будет 4 * 64 = 256
Ответ: 256
Рассмотрим важнейший «метод умножения» при решении 8 задания из ЕГЭ по информатике.
Задача (Другой метод решения!!)
Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз , при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?
Решение:
Эта задача отличается от уже разобранных тем, что каждую букву можно использовать один раз. В этой задаче удобнее воспользоваться немного другим методом решения! «Методом умножения»!
Решим вводную подзадачу (без дополнительных ограничений).
Сколькими способами можно составить 6-x буквенное слово из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз .
Чтобы найти возможные варианты, перемножаем для каждой ячейки количество букв из которых у нас есть выбор!
N = 6 * 5 * 4 * 3 * 2 * 1 = 720
Вернёмся к изначальной задаче!
В начале подсчитаем «методом умножения» количество слов, не обращая внимание, на условие, в котором сказано, что слово не может содержать сочетание АЕ.
N = 5 * 5 * 4 * 3 * 2 * 1 = 600
В формуле стоят почти все те же самые числа, как и в вводном примере, только первый множитель не 6, а 5. Это произошло из-за того, что у нас в задаче слово не может начинаться на букву Й. Значит, выбор на первую позицию будет не из 6 букв, а из 5.
Но в 600 комбинаций входят и те случаи, когда в слове присутствует сочетание АЕ. Теперь найдём сколько таких слов, где присутствует сочетание АЕ
Узнаем количество вариантов в каждом таком случае.
N1 = 4 * 3 * 2 * 1 = 24
На первом месте мы не можем использовать букву Й, поэтому мы на первом месте выбираем из 3 букв.
N2 = 3 * 3 * 2 * 1 = 18
Аналогично предыдущему случаю.
N3 = 3 * 3 * 2 * 1 = 18
N4 = 3 * 3 * 2 * 1 = 18
N5 = 3 * 3 * 2 * 1 = 18
Всего слов с сочетанием АЕ будет
24 + 18 + 18 + 18 + 18 = 96
Значит, всего слов, которые удовлетворяют условию задаче будет
N = 600 — 96 = 504
Примечание: Метод умножения можно было использовать и в задачах, которые мы рассмотрели ранее. Например, в задаче «Закрепление формулы» в первой свободной ячейке выбираем из 6 букв, во второй свободной ячейке тоже из 6 букв, и в третий свободной ячейке тоже можно использовать 6 букв. Значит, по методу умножения получается N = 6 * 6 * 6 = 63 = 216
Ответ: 504
Задача (Закрепления «метода умножения»)
Полина составляет 6-буквенные коды из букв П, О, Л, И, Н, А. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Полина?
Решение:
Опять сказано, что каждая буква используется 1 раз, следовательно, нужно применять «метод умножения».
На первое место можно выбрать из 6 букв, предположим, мы выберем согласную. Тогда на второе место нужно выбирать из 3 гласных. Потом опять должна идти согласная, но их у нас осталось только 2. Далее, на следующее место выбираем из 2 гласных букв. И на предпоследнее место выбирается 1 согласная, а на последнее место остаётся 1 гласная.
Т.к. количество гласных букв и согласных одинаковое, и равно трём, то если мы бы начали делать «метод умножения» с гласной буквы, количество вариантов бы не поменялось.
N = 6 * 3 * 2 * 2 * 1 * 1 = 72
Ответ: 72
Задача (Азбука Морзе)
Азбука Морзе позволяет кодировать символы для сообщений по радиосвязи, задавая комбинацию точек и тире. Сколько различных символов (цифр, букв, знаков пунктуации и т.д.) можно закодировать, используя код Морзе длиной не менее трёх и не более четырёх сигналов (точек и тире) ?
Решение:
Зная формулу, без проблем решим данную примерную задачу из ЕГЭ по информатике.
У нас есть 2 символа, которые можно использовать: точка и тире. Фраза, что сообщение может иметь «не менее трёх и не более четырёх сигналов», означает, что сообщения могут быть длиною 3 символа и длиною 4 символа.
Подсчитаем общее количество вариантов.
N = 23 + 24 = 8 + 16 = 24 комбинаций.
Значит, для 24 различных символов (цифр, букв, знаков пунктуации и т.д.) мы найдём различные комбинации, чтобы их закодировать
Ответ: 24
Задача (Обратная предыдущей)
Световое табло состоит из цветных индикаторов. Каждый индикатор может окрашиваться в четыре цвета: белый, черный, желтый и красный. Какое наименьшее количество лампочек должно находиться на табло, чтобы с его помощью можно было передать 300 различных сигналов?
Решение:
Нам нужно закодировать 300 различных вариантов! Имеются 4 различных лампочки! (Они имеют смысл, как количество допустимых символов!) На этот раз нужно узнать количество лампочек (количество разрядов, «длину слова»). Применяем формулу.
N = 4x = 300
Не найдётся такое целое x, чтобы равенство стало верным. Поэтому берём целое минимальное x такое, чтобы 4x больше 300.
45 = 1024
Пять лампочек на табло хватит, чтобы закодировать 300 сигналов, но, к сожалению, много комбинаций просто не пригодится!
Ответ: 5
Задача (Важная!)
Нужно выбрать в подарок 3 книги из 5. Сколькими способами можно выбрать ?
Решение:
На рисунке показано две комбинации, как можно выбрать в подарок 3 книги из 5.
Данную задачку нужно решать используя формулу сочетаний из раздела комбинаторика.
n — количество книг, из которых мы выбираем подарок, m — количество книг, которое мы хотим выбрать, C — количество вариантов (способов).
Восклицательный знак — это факториал!
Факториалом числа «n» (условное обозначение n!- читается как «эн» — факториал) называется произведение чисел от 1 до «n»
Примечание: При использовании формулы сочетаний, не важен порядок, в котором мы выбираем одни и те же книги. Это будет один и тот же вариант.
Ответ: 10
Следующая задача часто встречается в книгах по подготовке к ЕГЭ по информатике.
Задача (Главная формула + сочетания)
Шифр кодового замка представляет собой последовательность из пяти символов, каждый из которых является цифрой от 1 до 5. Сколько различных вариантов шифра можно задать, если известно, что цифра 1 встречается ровно три раза, а каждая из других допустимых цифр может встречаться в шифре любое количество раз или не встречаться совсем?
Решение:
В начале нужно посчитать, сколькими способами на 5-ти ячейках можно расположить 3 единицы!
Обратите внимание, как будто мы выбираем 3 книги в подарок из 5 возможных! Значит, опять применяем формулу сочетаний из комбинаторики. Мы вычисляли уже её точно с такими же числами в прошлой задаче, количество вариантов равно 10.
Подсчитаем, сколько вариантов кодового замка можно составить при одном определённом расположении трёх единиц.
Применим формулу, есть две ячейки, в которых изменяются цифры, а в каждой ячейке может быть одна из 4 цифр.
N = mi = 42 = 16
Т.к. различных вариантов, как расположить единицы на 5 ячейках равно 10, то ответ будет 16 * 10 = 160
Ответ: 160
Ещё одна задача из примерных вариантов по подготовке к ЕГЭ по информатике.
Задача (Таблица соревнований)
Для записи результатов соревнований используется таблица, в которой для каждой из 20-ти команд по каждому из 10-ти видов состязаний записано 1, 2 или 3 (если команда заняла соответствующее место в этом состязании) или прочерк (если не заняла призовое место или не участвовала). Какое количество информации (бит) содержит таблица ?
Решение:
Есть таблица с 20 командами и для каждой команды есть результат по 10-ти видам состязаний.
1 команда | 2 команда | 3 команда | … | 20 команда | |
1 дисциплина | 1 | — | 1 | … | 3 |
2 дисциплина | — | 2 | 1 | … | 2 |
… | … | … | … | … | … |
10 дисциплина | 1 | 1 | 2 | … | — |
В каждой ячейке может быть 4 различных значения ( 1, 2, 3, — ). Нужно узнать, сколько бит занимает одна ячейка таблицы. Один бит может быть либо единицей, либо нулём.
Сделав рисунок, задача обрела привычные очертания.
Как будто мы решаем задачу с перебором слов. Но здесь длина слова неизвестна, а количество вариантов, которое должно получится уже дано и равно 4 (четырём). Применим главную формулу из 10 задания из ЕГЭ по информатике.
N = mi = 2i = 4
i=2 бита (длина равна «2 буквам», если воспринимать задачу, как со словами.)
Одна ячейка таблицы весит 2 бита. Найдём количество ячеек во всей таблице соревнований.
Всего ячеек = 20 * 10 = 200
Тогда вся таблица будет весит:
V = 2 бита * 200 = 400 бит.
Ответ: 400
Формула Шеннона
Задача (Формула Шеннона)
В корзине лежат 8 черных шаров и 24 белых. Сколько бит информации несет сообщение о том, что достали черный шар?
Решение:
Данную задачу нужно решать по формуле Шеннона
Найдём вероятность p того, что вытащили чёрный шарик.
p = (количество чёрных шаров) / (количество всех шаров) = 8 / (24 + = 8 / 32 = 1 /4
p = 1 / 4
Применим формулу Шеннона.
x = log2(4)
2x = 4
x = 2 бита
Ответ: 2
Доброго времени суток ! Помогите пожалуйста решить задачу .) Матвей составляет 6-буквенные коды из букв М, А, Т, В, Е, Й. Каждую букву нужно использовать ровно 1 раз, при этом код не может начинаться с буквы Й и не может содержать сочетания АЕ. Сколько различных кодов может составить Матвей?
В закрытом ящике находится 32 карандаша, некоторые из них синего цвета. Наугад вынимается один карандаш. Сообщение «этот карандаш – НЕ синий» несёт 4 бита информации. Сколько синих карандашей в ящике?
Был бы очень рад , если вы разберете и эту задачку
Добрый день. Полностью разобрал этот номер, но наткнулся на один интересный пример. Объясните доступным языком, пожалуйста. На решу егэ вообще не понял их решение:
Тимофей составляет 5-буквенные коды из букв Т, И, М, О, Ф, Е, Й. Буква Т должна входить в код не менее одного раза, а буква Й — не более одного раза. Сколько различных кодов может составить Тимофей? (ответ: 8006)
Добрый день! Подскажите пожалуйста, как решить следующую задачу: Сколько существует чисел, шестнадцатеричная запись которых содержит 3 цифры, причём все цифры различны и никакие две чётные и две нечётные цифры не стоят рядом.
Петя составляет семибуквенные слова перестановкой букв слова АССАСИН. Сколько всего различных слов может составить Петя? Мое решение: 21 вариант с буквой А, 35- с буквой С, и 4 на буквы И и Н. Всего 60 и умножаем на 7. Получается 420. Не уверена, что применила верный алгоритм. Прокомментируйте, пожалуйста, решение
Можете заказать решение задачи через раздел «связь».
В Задаче (Другой метод решения!!) допущена ошибка в решении, ведь 24 + 18 + 18 + 18 + 18 = 114,значит N = 600 — 114 = 486!
Добрый день! Помогите пожалуйста решить задачку
Сколько чисел длиной 6 можно составить, если известно, что цифры идут в порядке убывания, при этом четные и нечетные цифры чередуются?
У меня только один вопрос. Почему в школах на уроках информатики вместо действительно полезного изучения какого нибудь языка программирования, заставляют заниматься вот этой вот ересью и решать какое по счету слово напишет Вася? Я могу только составить в ответ на это только слова которые нельзя здесь писать. От таких знаний и занятий ни один ребенок не захочет стать программистом, потому что это непонятно, и неизвестно зачем уметь решать такие задачи. Я сам программист с 10 летним стажем не смог объяснить ребенку как решать некоторые задачи и самое главное, я не знаю зачем дети должны уметь это решать.
Дмитрий, согласен с Вами. Особенно 11 задание и формула Шеннона. Надо либо излагать задание корректно, либо исключить вообще: «В корзине лежат черные и белые шары. Среди них 18 черных шаров. Сообщение о том, что достали белый шар, несет 2 бита информации. Сколько всего шаров в корзине?» — для двух состояний достаточно одного бита.
marvell special for u
c = 0
from itertools import*
for i in permutations(‘МАТВЕЙ’, r=6):
i = ».join(i)
if i[0] != ‘Й’ and i.count(‘АЕ’) == 0:
print(i)
c += 1
print(c)
Демонстрационная версия ЕГЭ−2021 по информатике
При выполнении заданий с кратким ответом впишите в поле для ответа цифру, которая соответствует номеру правильного ответа, или число, слово, последовательность букв (слов) или цифр. Ответ следует записывать без пробелов и каких-либо дополнительных символов. Дробную часть отделяйте от целой десятичной запятой. Единицы измерений писать не нужно.
Если вариант задан учителем, вы можете вписать или загрузить в систему ответы к заданиям с развернутым ответом. Учитель увидит результаты выполнения заданий с кратким ответом и сможет оценить загруженные ответы к заданиям с развернутым ответом. Выставленные учителем баллы отобразятся в вашей статистике.
Версия для печати и копирования в MS Word
1
На рисунке схема дорог Н-ского района изображена в виде графа, в таблице содержатся сведения о протяжённости каждой из этих дорог (в километрах).
П1 | П2 | П3 | П4 | П5 | П6 | П7 | |
П1 | 9 | 7 | |||||
П2 | 5 | 11 | |||||
П3 | 12 | ||||||
П4 | 9 | 5 | 4 | 13 | 15 | ||
П5 | 4 | 10 | 8 | ||||
П6 | 11 | 12 | 13 | 10 | |||
П7 | 7 | 15 | 8 |
Так как таблицу и схему рисовали независимо друг от друга, то нумерация населённых пунктов в таблице никак не связана с буквенными обозначениями на графе. Определите, какова протяжённость дороги из пункта Д в пункт Е. В ответе запишите целое число — так, как оно указано в таблице.
Ответ:
2
Логическая функция F задаётся выражением (x ∨ y) ∧ ¬(y ≡ z) ∧ ¬w. На рисунке приведён частично заполненный фрагмент таблицы истинности функции F, содержащий неповторяющиеся строки. Определите, какому столбцу таблицы истинности функции F соответствует каждая из переменных x, y, z, w.
Переменная 1 | Переменная 2 | Переменная 3 | Переменная 4 | Функция |
---|---|---|---|---|
1 | 1 | 1 | ||
0 | 1 | 0 | 1 | |
1 | 1 | 0 | 1 |
В ответе напишите буквы x, y, z, w в том порядке, в котором идут соответствующие им столбцы (сначала — буква, соответствующая первому столбцу; затем — буква, соответствующая второму столбцу, и т. д.). Буквы в ответе пишите подряд, никаких разделителей между буквами ставить не нужно.
Пример. Пусть задано выражение x → y, зависящее от двух переменных x и y, и фрагмент таблицы истинности:
Переменная 1 | Переменная 2 | Функция |
---|---|---|
??? | ??? | F |
0 | 1 | 0 |
Тогда первому столбцу соответствует переменная y, а второму столбцу соответствует переменная x. В ответе нужно написать: yx.
Ответ:
3
Ниже представлены два фрагмента таблиц из базы данных о жителях микрорайона. Каждая строка таблицы 2 содержит информацию о ребёнке и об одном из его родителей. Информация представлена значением поля ID в соответствующей строке таблицы 1. Определите на основании приведённых данных ID женщины, ставшей матерью в наиболее молодом возрасте. При вычислении ответа учитывайте только информацию из приведённых фрагментов таблиц.
|
|
Ответ:
4
Для кодирования некоторой последовательности, состоящей из букв Л, М, Н, П, Р, решили использовать неравномерный двоичный код, удовлетворяющий условию, что никакое кодовое слово не является началом другого кодового слова. Это условие обеспечивает возможность однозначной расшифровки закодированных сообщений. Для букв Л, М, Н использовали соответственно кодовые слова 00, 01, 11. Для двух оставшихся букв П и Р — кодовые слова неизвестны.
Укажите кратчайшее возможное кодовое слово для буквы П, при котором код будет удовлетворять указанному условию. Если таких кодов несколько, укажите код с наименьшим числовым значением.
Ответ:
5
На вход алгоритма подаётся натуральное число N. Алгоритм строит по нему новое число R следующим образом.
1. Строится двоичная запись числа N.
2. К этой записи дописываются справа ещё два разряда по следующему правилу:
а) складываются все цифры двоичной записи числа N, и остаток от деления суммы на 2 дописывается в конец числа (справа). Например, запись 11100 преобразуется в запись 111001;
б) над этой записью производятся те же действия — справа дописывается остаток от деления суммы её цифр на 2.
Полученная таким образом запись (в ней на два разряда больше, чем в записи исходного числа N) является двоичной записью искомого числа R. Укажите такое наименьшее число N, для которого результат работы данного алгоритма больше числа 77. В ответе это число запишите в десятичной системе счисления.
Ответ:
6
Определите, при каком наибольшем введённом значении переменной s программа выведет число 64. Для Вашего удобства программа представлена на четырёх языках программирования.
Си++ | Python |
---|---|
#include <iostream> using namespace std; int main() { int s, n; cin >> s; s = s / 10; n = 1 ; while (s < 51) { s = s + 5; n = n * 2; } cout << n << endl; return 0; } |
s = int(input()) s = s // 10 n = 1 while s < 51: s = s + 5 n = n * 2 print(n) |
Паскаль | Алгоритмический язык |
var s, n: integer; begin readln (s); s := s div 10; n := 1; while s < 51 do begin s := s + 5; n := n * 2 end; writeln(n) end. |
алг нач цел n, s ввод s s := div( s, 10) n := 1 нц пока s < 51 s := s + 5 n := n * 2 кц вывод n кон |
Ответ:
7
Для хранения произвольного растрового изображения размером 128×320 пикселей отведено 20 Кбайт памяти без учёта размера заголовка файла. Для кодирования цвета каждого пикселя используется одинаковое количество бит, коды пикселей записываются в файл один за другим без промежутков. Какое максимальное количество цветов можно использовать в изображении?
Ответ:
8
Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?
Ответ:
9
Откройте файл электронной таблицы, содержащей вещественные числа — результаты ежечасного измерения температуры воздуха на протяжении трёх месяцев.
Задание 9
Найдите разность между максимальным значением температуры и её средним арифметическим значением. В ответе запишите только целую часть получившегося числа.
Ответ:
10
С помощью текстового редактора определите, сколько раз, не считая сносок, встречается слово «долг» или «Долг» в тексте романа в стихах А. С. Пушкина «Евгений Онегин». Другие формы слова «долг», такие как «долги», «долгами» и т. д., учитывать не следует. В ответе укажите только число.
Задание 10
Ответ:
11
При регистрации в компьютерной системе каждому пользователю выдаётся идентификатор, состоящий из 15 символов и содержащий только символы из 8-символьного набора: А, В, C, D, Е, F, G, H. В базе данных для хранения сведений о каждом пользователе отведено одинаковое и минимально возможное целое число байт. При этом используют посимвольное кодирование идентификаторов, все символы кодируют одинаковым и минимально возможным количеством бит. Кроме собственно идентификатора, для каждого объекта в системе хранятся дополнительные сведения, для чего отведено 24 байт на один объект.
Определите объём памяти (в байтах), необходимый для хранения сведений о 20 объектах. В ответе запишите только целое число — количество байт.
Ответ:
12
Исполнитель Редактор получает на вход строку цифр и преобразовывает её. Редактор может выполнять две команды, в обеих командах v и w обозначают цепочки цифр.
А) заменить (v, w).
Эта команда заменяет в строке первое слева вхождение цепочки v на цепочку w. Например, выполнение команды
заменить (111, 27)
преобразует строку 05111150 в строку 0527150.
Если в строке нет вхождений цепочки v, то выполнение команды заменить (v, w) не меняет эту строку.
Б) нашлось (v).
Эта команда проверяет, встречается ли цепочка v в строке исполнителя Редактор. Если она встречается, то команда возвращает логическое значение «истина», в противном случае возвращает значение «ложь». Строка
исполнителя при этом не изменяется.
Цикл
ПОКА условие
последовательность команд
КОНЕЦ ПОКА
выполняется, пока условие истинно.
В конструкции
ЕСЛИ условие
ТО команда1
ИНАЧЕ команда2
КОНЕЦ ЕСЛИ
выполняется команда1 (если условие истинно) или команда2 (если условие ложно).
Какая строка получится в результате применения приведённой ниже программы к строке, состоящей из 70 идущих подряд цифр 8? В ответе запишите полученную строку.
НАЧАЛО
ПОКА нашлось (2222) ИЛИ нашлось (8888)
ЕСЛИ нашлось (2222)
ТО заменить (2222, 88)
ИНАЧЕ заменить (8888, 22)
КОНЕЦ ЕСЛИ
КОНЕЦ ПОКА
КОНЕЦ
Ответ:
13
На рисунке представлена схема дорог, связывающих города А, Б, В, Г, Д, Е, Ж, З, И, К, Л, М. По каждой дороге можно двигаться только в одном направлении, указанном стрелкой.
Сколько существует различных путей из города А в город М, проходящих через город В?
Ответ:
14
Значение выражения 497 + 721 − 7? записали в системе счисления с основанием 7.
Сколько цифр «6» содержится в этой записи?
Ответ:
15
Обозначим через ДЕЛ(n, m) утверждение «натуральное число n делится без остатка на натуральное число m».
Для какого наибольшего натурального числа А формула
¬ДЕЛ(x, А) → (ДЕЛ(x, 6) → ¬ДЕЛ(x, 9))
тождественно истинна (то есть принимает значение 1 при любом натуральном значении переменной x)?
Ответ:
16
Алгоритм вычисления значения функции F(n), где n — натуральное число, задан следующими соотношениями:
F(n) = 1 при n = 1;
F(n) = n + F(n − 1), если n — чётно;
F(n) = 2 × F(n − 2), если n> 1 и при этом n — нечётно.
Чему равно значение функции F(26)?
Ответ:
17
Рассматривается множество целых чисел, принадлежащих числовому отрезку [1016; 7937], которые делятся на 3 и не делятся на 7, 17, 19, 27. Найдите количество таких чисел и максимальное из них. В ответе запишите два целых числа без пробелов и других дополнительных символов: сначала количество, затем максимальное число.
Для выполнения этого задания можно написать программу или воспользоваться редактором электронных таблиц.
Ответ:
18
Квадрат разлинован на N×N клеток (1 < N < 17). Исполнитель Робот может перемещаться по клеткам, выполняя за одно перемещение одну из двух команд: вправо или вниз. По команде вправо Робот перемещается в соседнюю правую клетку, по команде вниз — в соседнюю нижнюю. При попытке выхода за границу квадрата Робот разрушается. Перед каждым запуском Робота в каждой клетке квадрата лежит монета достоинством от 1 до 100. Посетив клетку, Робот забирает монету с собой; это также относится к начальной и конечной клетке маршрута Робота.
Задание 18
Откройте файл. Определите максимальную и минимальную денежную сумму, которую может собрать Робот, пройдя из левой верхней клетки в правую нижнюю. В ответ запишите два числа друг за другом без разделительных знаков — сначала максимальную сумму, затем минимальную.
Исходные данные представляют собой электронную таблицу размером N×N, каждая ячейка которой соответствует клетке квадрата.
Пример входных данных:
1 | 8 | 8 | 4 |
10 | 1 | 1 | 3 |
1 | 3 | 12 | 2 |
2 | 3 | 5 | 6 |
Для указанных входных данных ответом должна быть пара чисел 41 и 22.
Ответ:
19
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче — S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Известно, что Ваня выиграл своим первым ходом после неудачного первого хода Пети. Укажите минимальное значение S, когда такая ситуация возможна
Ответ:
20
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче — S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите два таких значения S, при которых у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
— Петя не может выиграть за один ход;
— Петя может выиграть своим вторым ходом независимо от того, как будет ходить Ваня.
Найденные значения запишите в ответе в порядке возрастания без разделительных знаков.
Ответ:
21
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в два раза. Например, пусть в одной куче 10 камней, а в другой 5 камней; такую позицию в игре будем обозначать (10, 5). Тогда за один ход можно получить любую из четырёх позиций: (11, 5), (20, 5), (10, 6), (10, 10). Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 77. Победителем считается игрок, сделавший последний ход, т. е. первым получивший такую позицию, при которой в кучах будет 77 или больше камней.
В начальный момент в первой куче было семь камней, во второй куче — S камней; 1 ≤ S ≤ 69.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока — значит, описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т. е. не являющиеся выигрышными независимо от игры противника.
Найдите минимальное значение S, при котором одновременно выполняются два условия:
— у Вани есть выигрышная стратегия, позволяющая ему выиграть первым или вторым ходом при любой игре Пети;
— у Вани нет стратегии, которая позволит ему гарантированно выиграть первым ходом.
Ответ:
22
Ниже на четырех языках программирования записан алгоритм. Получив на вход число x, этот алгоритм печатает два числа: L и M. Укажите наибольшее число x, при вводе которого алгоритм печатает сначала 4, а потом 5.
C++ | Python |
---|---|
#include <iostream> using namespace std; int main() { int x, L, M, Q; cin >> x; Q = 9; L = 0; while (x >= Q){ L = L + 1; x = x — Q; } M = x; if (M < L){ M = L; L = x; } cout << L << endl << M << endl; return 0; } |
x = int(input()) Q = 9 L = 0 while x >= Q: L = L + 1 x = x — Q M = x if M < L: M = L L = x print(L) print(M) |
Паскаль | Алгоритмический язык |
var x, L, M, Q: integer; begin readln(x); Q := 9; L := 0; while x >= Q do begin L := L + 1; x := x — Q; end; M := x; if M < L then begin M := L; L := x; end; writeln(L); writeln(M); end. |
алг нач цел x, L, M, Q ввод x Q := 9 L := 0 нц пока x >= Q L := L + 1 x := x — Q кц M := x если M < L то M := L L := x все вывод L, нс, M кон |
Ответ:
23
Исполнитель преобразует число на экране.
У исполнителя есть две команды, которым присвоены номера:
1. Прибавить 1
2. Умножить на 2
Первая команда увеличивает число на экране на 1, вторая умножает его на 2. Программа для исполнителя — это последовательность команд.
Сколько существует программ, для которых при исходном числе 1 результатом является число 20 и при этом траектория вычислений содержит число 10?
Траектория вычислений программы — это последовательность результатов выполнения всех команд программы. Например, для программы 121 при исходном числе 7 траектория будет состоять из чисел 8, 16, 17.
Ответ:
24
Текстовый файл состоит не более чем из 106 символов X, Y и Z. Определите максимальное количество идущих подряд символов, среди которых каждые два соседних различны.
Для выполнения этого задания следует написать программу. Ниже приведён файл, который необходимо обработать с помощью данного алгоритма.
Задание 24
Ответ:
25
Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в два соседних столбца на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке также должны следовать в порядке возрастания.
Например, в диапазоне [5; 9] ровно два различных натуральных делителя имеют числа 6 и 8, поэтому для этого диапазона вывод на экране должна содержать следующие значения:
2 3
2 4
26
Системный администратор раз в неделю создаёт архив пользовательских файлов. Однако объём диска, куда он помещает архив, может быть меньше, чем суммарный объём архивируемых файлов. Известно, какой объём занимает файл каждого пользователя.
По заданной информации об объёме файлов пользователей и свободном объёме на архивном диске определите максимальное число пользователей, чьи файлы можно сохранить в архиве, а также максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Входные данные.
Задание 26
В первой строке входного файла находятся два числа: S — размер свободного места на диске (натуральное число, не превышающее 10 000) и N — количество пользователей (натуральное число, не превышающее 1000). В следующих N строках находятся значения объёмов файлов каждого пользователя (все числа натуральные, не превышающие 100), каждое в отдельной строке.
Запишите в ответе два числа: сначала наибольшее число пользователей, чьи файлы могут быть помещены в архив, затем максимальный размер имеющегося файла, который может быть сохранён в архиве, при условии, что сохранены файлы максимально возможного числа пользователей.
Пример входного файла:
100 4
80
30
50
40
При таких исходных данных можно сохранить файлы максимум двух пользователей. Возможные объёмы этих двух файлов 30 и 40, 30 и 50 или 40 и 50. Наибольший объём файла из перечисленных пар — 50, поэтому ответ для приведённого примера:
2 50
Ответ:
27
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи.
Входные данные.
Файл A
Файл B
Даны два входных файла (файл A и файл B), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
Пример организации исходных данных во входном файле:
6
1 3
5 12
6 9
5 4
3 3
1 1
Для указанных входных данных значением искомой суммы должно быть число 32.
В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
Предупреждение: для обработки файла B не следует использовать переборный алгоритм, вычисляющий сумму для всех возможных вариантов, поскольку написанная по такому алгоритму программа будет выполняться слишком долго.
Ответ:
Завершить тестирование, свериться с ответами, увидеть решения.
1 августа 2020
В закладки
Обсудить
Жалоба
Демоверсия ЕГЭ 2022
Официальная демоверсия от ФИПИ на 2021 год.
Изменения в КИМ ЕГЭ в 2021 году по сравнению с 2020 годом
В 2021 г. ЕГЭ по информатике и ИКТ проводится в компьютерной форме, что позволило включить в КИМ задания на практическое программирование (составление и отладка программы в выбранной участником среде программирования), работу с электронными таблицами и информационный поиск. Таких заданий в работе 9, т.е. треть от общего количества заданий.
Остальные 18 заданий сохраняют глубокую преемственность с КИМ ЕГЭ прошлых лет (экзамена в бланковой форме). При этом они адаптированы к новым условиям сдачи экзамена, в тех случаях, когда это необходимо. Так, например, задание 6 КИМ 2021 г. является преемником задания 8 модели КИМ предыдущих лет. В заданиях этой линии нужно было выполнить фрагмент программы вручную, что в условиях доступности компьютера со средами программирования делает задание тривиальным. Поэтому при сохранении тематики задания была скорректирована постановка вопроса в сторону анализа соответствия исходных данных программы заданному результату её работы.
В отличие от бланковой модели экзамена, в 2021 г. выполнение заданий по программированию допускается на языках программирования (семействах языков) С++, Java, C#, Pascal, Python, Школьный алгоритмический язык. Из примеров фрагментов кода в заданиях в связи с невостребованностью исключены примеры на Бейсике.
Обновлено 5 декабря. Демоверсия утверждена.
→ Демоверсия: demo-inf-2021.pdf
→ Кодификатор: kod-inf-2021.pdf
→ Спецификация: spec-inf-2021.pdf
→ Скачать одним архивом: inf-demo-ege-2021.zip
→ Тренажёр ЕГЭ по информатике в компьютерной форме — kege.rustest.ru
Обобщённый план варианта КИМ ЕГЭ 2021 года по информатике
№ |
Требования к уровню подготовки выпускников, проверяемому на ЕГЭ |
Уровень сложности задания |
Требуется использование спец. программного обеспечения |
Макс. балл за выполнение задания |
Время выполнения (мин.) |
1 |
Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы) |
Б |
нет |
1 |
3 |
2 |
Умение строить таблицы истинности и логические схемы |
Б |
нет |
1 |
3 |
3 |
Знание о технологии хранения, поиска и сортировки информации в реляционных базах данных |
Б |
нет |
1 |
3 |
4 |
Умение кодировать и декодировать информацию |
Б |
нет |
1 |
2 |
5 |
Формальное исполнение алгоритма, записанного на естественно N языке, или умение создавать линейный алгоритм для формального исполнителя с ограниченнь^ набором команд |
Б |
нет |
1 |
4 |
6 |
Знание основных конструкций языка программирования, понята* переменной, оператора присваивания |
Б |
нет |
1 |
4 |
7 |
Умение определять объём памяти, необходимый для хранения графической и звуковой информации |
Б |
нет |
1 |
5 |
8 |
Знание о методах измерения количества информации |
Б |
нет |
1 |
4 |
9 |
Умение обрабатывать числовую информацию в электронных таблицах |
Б |
да |
1 |
6 |
10 |
Информационный поиск средствами операционной системы или текстового процессора |
Б |
да |
1 |
6 |
11 |
Умение подсчитывать информационный объём сообщения |
П |
нет |
1 |
3 |
12 |
Умение анализировать результат исполнения алгоритма |
П |
нет |
1 |
4 |
13 |
Умение представлять и считывать данные в разных типах информационных моделей (схемы, карты, таблицы, графики и формулы) |
П |
нет |
1 |
3 |
14 |
Знание позиционных систем счисления |
П |
нет |
1 |
5 |
15 |
Знание основных понятий и законов математической логики |
П |
нет |
1 |
5 |
16 |
Вычисление рекуррентных выражений |
П |
да |
1 |
9 |
17 |
Умение создавать собственные программы (20-40 строк) для обработки целочисленной информации |
П |
да |
1 |
15 |
18 |
У мение обрабатывать вещественные выражения в электронных таблицах |
П |
да |
1 |
6 |
19 |
Умение анализировать алгоритм логической игры |
П |
нет |
1 |
6 |
20 |
Умение найти выигрышную стратегию игры |
П |
нет |
1 |
6 |
21 |
Умение построить дерево игры по заданному алгоритму и найти выигрышную стратегию |
п |
нет |
1 |
10 |
22 |
Умение анализировать алгоритм, содержащий ветвление и цикл |
п |
нет |
1 |
7 |
23 |
Умение анализировать результат исполнения алгоритма |
п |
нет |
1 |
8 |
24 |
У мение создавать собственные программы (10-20 строк) для обработки символьной информации |
в |
да |
1 |
18 |
25 |
У мение создавать собственные программы (10-20 строк) для обработки целочисленной информации |
в |
да |
2 |
20 |
26 |
У мение обрабатывать целочисленную информацию с использованием сортировки |
в |
да |
2 |
35 |
27 |
Умение создавать собственные программы (20-40 строк) для анализа числовых последовательностей |
в |
да |
2 |
35 |
Всего заданий – 27; из них
по уровню сложности: Б – 11, П – 11, В – 5.
Максимальный первичный балл за работу – 30.
Общее время выполнения работы – 235 мин.
Решения демоверсии ЕГЭ по информатике 2021 год. Демонстрационный вариант ЕГЭ 2021 г. информатика, 11 класс. Разбор демоверсии ЕГЭ 2021 по информатике.
ege-inf-demo2021
скачать
ege-inf-demo2021-reshn
скачать
Смотрите также:
ЕГЭ 2021 ДЕМО информатика КОМПЬЮТЕРНОЕ ЕГЭ. РАЗБОР ДЕМОВЕРСИИ. Школково
Просмотров: 1 679
Решение задания 8 ЕГЭ по информатике ДЕМО- 2021
ОБЯЗАТЕЛЬНО ПОСМОТРИ Разбор ДЕМО варианта ЕГЭ по информатике 2021 посмотреть
Игорь составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует своё кодовое слово. В качестве кодовых слов Игорь использует трёхбуквенные слова, в которых могут быть только буквы Ш, К, О, Л, А, причём буква К появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Игорь?
ФИЗИНФИКА – образовательный проект
Помоги! ПОДПИШИСЬ! ПОСТАВЬ ЛАЙК!!!
Автор урока: Николай Викторович Сафронов
Наша группа в ВК: https://vk.com/fizinfika
Задачи присылать сюда: https://vk.com/topic-171030045_39301372
Наш сайт: https://fizinfika.ru/
Задонатить денежку можно тут – https://www.donationalerts.com/r/nikolya29
Лада Есакова, преподаватель информатики и математики, автор книги «Информатика. Полный курс подготовки к ЕГЭ».
Добрый день, дорогие друзья! С вами я, Есакова Лада, преподаватель информатики с 20-летним стажем.
Сегодня разберем основы комбинаторики и буквенные цепочки.
Задача:
«Все 4-буквенные слова, составленные из букв В, Н, Р, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ВВВВ
2. ВВВН
3. ВВВР
4. ВВВТ
5. ВВНВ
………
Запишите слово, которое стоит под номером 251.»
Обозначим В = 0, Н = 1, Р = 2, Т = 3 и получим вот такой ряд:
1. 0000
2. 0001
3. 0002
4. 0003
5. 0010
Это числовой ряд в четверичной системе исчисления. Нам нужно найти слово, которое стоит под номером 251.
Здесь важный нюанс, на котором часто ребята теряют балл. На первом месте стоит 0, то есть номер строчки на единицу больше самого числа. Поэтому на 251 месте у нас будет стоять число на единицу меньше – 250, но только в четверичной системе исчисления.
Переведем 250 в четверичную систему. Будем делить столбиком. У нас получается 250 = 33224. Теперь переводим цифры в буквы — ТТРР. Вот такой ответ должен получиться.
Вот такие буквенные цепочки – это, по сути, числовые ряды.
Следующая задача:
«Все 6-буквенные слова, составленные из букв С, В, Е, Т, записаны в алфавитном порядке и пронумерованы. Вот начало списка:
1. ВВВВВВ
2. ВВВВВЕ
3. ВВВВВС
4. ВВВВВТ
5. ВВВВЕВ
………
Под каким номером стоит первое из слов, которое начинается с буквы Т?»
Здесь есть еще одна ловушка: нам сказали, что все 6-буквенные слова составлены из этих букв, и очень хочется пронумеровать букву в том же порядке, в котором они представлены – С = 0, В = 1, Е = 2, Т = 3. Вот здесь-то и ошибка.
Если посмотрим на числовой ряд, то увидим, что на первой строчке у нас стоит В, значит, она будет равна 0. Далее появляется Е, значит, она равна 1, С = 2 и Т = 3.
И снова у нас четверичная система исчисления. Необходимо определить, под каким номером стоит первое из слов, которое начинается с буквы Т. Перефразирую вопрос: под каким номером стоит четверичное число, которое начинается на 3? Значит, оно должно выглядеть как 300000. Это число стоит на месте, которое на единицу больше, чем оно само, но в десятичной записи. Необходимо это число, 300000, из четверичной системы перевести в десятичную.
3000004=3*45=3*1024=3072
У нас получается число 3072, а номер строки на единицу больше, то есть номер строки будет 3073. Это и есть ответ задачи.
С такими цифровыми цепочками на сегодня мы закончим. Перейдем к более интересной теме, к элементам комбинаторики, хотя это громко сказано, потому что там от комбинаторики только одна маленькая формула.
Чтобы понять, о чем я сейчас буду говорить, давайте представим такую ситуацию: допустим, надоело нам жить в Москве и решили переехать на необитаемый остров. Для связи с внешним миром мы запасли некоторое количество цветных флажков, которые мы можем прикрепить к флагштокам и при необходимости подать сигнал. У нас есть два флагштока и флажки только двух цветов: красные и синие. Что же при помощи этого мы можем сообщить во внешний мир?
Мы можем составить 4 комбинации:
Если нам этого не хватает, мы можем добавить флажки еще одного цвета. Допустим, у нас еще есть зеленые флажки, и мы можем составить следующие комбинации:
У нас получилось 9 комбинаций.
Если же все-таки у нас флажки только двух цветов, третьего нет, у нас есть другой путь увеличить количество комбинаций, увеличив количество флагштоков. Получаем следующие комбинации:
и их получилось 8 штук.
Мы видим, что количество сообщений, которые мы можем передать внешнему миру, зависит от двух параметров: от количества букв в нашем алфавите (или, в нашем случае, от разных цветов флажков) и от длины слова (или от количества флагштоков).
Количество слов, которые мы можем закодировать, равно количеству букв в нашем алфавите (еще это называется мощностью алфавита) в степени «длина слова» A=ai
«Сколько различных символов можно закодировать, используя код азбуки Морзе длиной не менее четырех и не более пяти сигналов (точек и тире)?»
Если я делаю слово из четырех сигналов, то таких слов я могу сделать 24, если я делаю из пяти сигналов, то таких слов я могу придумать 25. А в задаче как раз этот интервал, то есть и те, и те мне подойдут. Вот столько разных слов я могу составить 24 + 25 = 48.
«Коля составляет таблицу кодовых слов для передачи сообщений, каждому сообщению соответствует свое кодовое слово. В качестве кодовых слов Коля использует 4-буквенные слова, в которых есть буквы А, Б, В, Г, Д, причем буква Д появляется ровно 1 раз. Каждая из других допустимых букв может встречаться в кодовом слове любое количество раз или не встречаться совсем. Сколько различных кодовых слов может использовать Коля?»
Не буду мудрить, придумывать какие-то сложные формулы, а просто распишу, как буква Д может встречаться ровно один раз. Это выглядит так
Д — — —
— Д — —
— — Д —
— — — Д
то есть она может встретиться на каком-то из четырех мест. На остальных трех местах может стоять все, кроме Д, то есть 4 любые буквы по трем позициям, 43. И так в каждом ряду. Все это сложим и получим 4*43=44=256
«Паша составляет таблицу кодовых слов для передачи сообщений. В качестве кодовых слов Паша использует 4-буквенные слова, в которых есть только буквы А, Б, В, Г, Д, Е, Ж. При этом первая буква кодового слова – это буква Д, Е или Ж, а далее в кодовом слове буквы Д, Е и Ж не встречаются. Сколько различных кодов может использовать Паша?»
У нас получается такой вид
Д — — —
Е — — —
Ж — — —
А в остальных местах используются остальные буквы, кроме Д, Е и Ж. Получаем 3*43=3*64=192
«Герасим составляет 7-буквенные коды из букв Г, Е, Р, А, С, И, М. Каждую букву нужно использовать ровно 1 раз, при этом нельзя ставить подряд две гласные или две согласные. Сколько различных кодов может составить Герасим?»
Тут немного схитрим. Необходимо обязательно чередовать гласные и согласные, а для этого посмотрим, сколько у нас гласных. 3. А согласных 4. Поэтому на гласную начать слово я не могу, иначе их не хватит на все слово, и согласные где-то обязательно повторятся. Поэтому слово будет выглядеть таким образом: согласная – гласная – согласная – гласная – согласная – гласная – согласная.
Далее каждую букву я должна использовать ровно один раз.
Вначале состава слова согласных у нас 4, гласных – 3, далее согласных остается 3, т.к. одну я уже использовала, а согласных – 2, затем согласных 2, гласных – одна и согласная осталась одна. Теперь мы перемножаем все эти цифры
и получаем 144.
«Ольга составляет 5-буквенные коды из букв О, Л, Ь, Г, А. Каждую букву нужно использовать ровно 1 раз, при этом Ь нельзя ставить первым и нельзя ставить после гласной. Сколько различных кодов может составить Ольга?»
Давайте пойдем от противного: посчитаем все варианты, а потом выбросим те, которые нам запретили, но сразу выкинем вариант с мягким знаком на первом месте. То есть на первом месте мы можем поставить 4 различные буквы. На втором месте могу поставить все, кроме этой буквы, но зато мы можем добавить Ь, то есть тоже 4. Две буквы уже использовали. Осталось 3, 2 и 1. Все это перемножаю и получаю 96. То есть это все возможные слова, где используется буквы по одному разу, но только не начинающиеся на Ь.
Теперь из этого числа нужно выбросить ситуации, когда Ь стоит после гласной. Это, например, вот так
О Ь — — —
— О Ь — —
— — О Ь —
— — — О Ь
Таких слов 24
О Ь — — — 3*2*1
— О Ь — — 3*2*1
— — О Ь — 3*2*1
— — — О Ь 3*2*1
——
24
Абсолютно такая же ситуация с буквой А
А Ь — — —
— А Ь — —
— — А Ь —
— — — А Ь
———
24
И их тоже 24. То есть 96-48=48.
На этом прощаемся. Если вопросов нет, пока!
Все видео по информатике
Благодарим за то, что пользуйтесь нашими публикациями.
Информация на странице «8 Задание ЕГЭ 2021 | Комбинаторика» подготовлена нашими авторами специально, чтобы помочь вам в освоении предмета и подготовке к экзаменам.
Чтобы успешно сдать необходимые и поступить в ВУЗ или техникум нужно использовать все инструменты: учеба, контрольные, олимпиады, онлайн-лекции, видеоуроки, сборники заданий.
Также вы можете воспользоваться другими статьями из данного раздела.
Публикация обновлена:
09.03.2023