Скрипты по информатике егэ

Шпаргалка ЕГЭ по информатике. Все необходимое

Скачать шпаргалку для подготовки к ЕГЭ по информатике. Содержимое:
— Логика
— Системы счисления
— Кодирование информации
— Программирование
— Теория игр
и другое

Похожие материалы

Комментарии

Всего комментариев: 0

Привет! Сегодня поговорим о 17 задании ЕГЭ по информатике 2022.

В 17 задании нужно считать числа из файла, проанализировать их и ответить на вопрос задачи.

Будем решать задание на языке Python.

Задача (Минимальное значение)

В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от -10000 до 10000 включительно. Определите и запишите в ответе сначала количество пар элементов последовательности, в которых оба числа делятся нацело на 7, затем минимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два подряд идущих элемента последовательности. Например для последовательности из пяти элементов: 7; 14; 21; -7; 4 — ответ 3 14.

Решение:

Напишем программу на языке Python.

f=open('17_1.txt')

count=0
sm=20000

n1=int(f.readline())

for s in f.readlines():
    n2=int(s)

    if n1%7==0 and n2%7==0:
        count=count+1
        sm=min(n1+n2, sm)
    
    n1=n2

print(count)
print(sm)

В начале подвязываемся к файлу с помощью команды open().

Переменная count отвечает за количество пар, удовлетворяющих условию задачи. Переменная sm — это минимальная сумма элементов подходящих пар.

В начале в переменную sm кладём максимальное число, которое теоретически может получится (10000 + 10000). Это делается для того, чтобы это значение можно было легко «победить» при поиске минимального значения.

Затем считываем в переменную n1 первое число. C помощью конструкции «for s in f.readlines():» можно перебрать остальные числа из файла. В цикле считываем второе число для пары в переменную n2.

После того, как два числа у нас есть, мы анализируем эти элементы на условие задачи. Если одновременно два числа из пары делятся на 7, то мы подсчитываем такую пару.

Если пара подходит, то проверяем сумму элементов этой пары на минимальность. В переменную sm заносится минимальное значение из прежнего значения sm и претендующего нового значения n1+n2.

В конце цикла нужно переложить второе число в переменную n1, чтобы очередное число из файла считалось в переменную n2. Тем самым мы получим новую пару чисел.

Ответ:

Задача (Проверяем на что оканчивается число)

В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от -10000 до 10000 включительно. Определите и запишите в ответе сначала количество пар элементов последовательности, в которых оба числа оканчиваются или на 3, или на 5 (можно неодновременно), затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два подряд идущих элемента последовательности. Например для последовательности из пяти элементов: 3; 15; 25; -3; 4 — ответ 3 40.

Решение:

f=open('17_2.txt')

count=0
sm=-20000

n1=int(f.readline())

for s in f.readlines():
    n2=int(s)

    if (abs(n1)%10==3 or abs(n1)%10==5) and (abs(n2)%10==3 or abs(n2)%10==5):
        count=count+1
        sm=max(n1+n2, sm)
    
    n1=n2

print(count)
print(sm)

Т.к. мы ищем максимальную сумму, то в начале в переменную sm кладём наоборот минимальное значение (-10000-10000=-20000).

Когда ищем на что оканчивается положительное число, мы применяем конструкцию x%10. Т.е. находим остаток от деления на 10. Пример: 16 % 10 = 6. Но для отрицательных чисел это не работает -16 % 10 = 4. Почему такой ответ получается, можете посмотреть в этом видео: https://www.youtube.com/watch?v=BRfgE3pP0_c. Поэтому, чтобы правильно найти на что оканчивается число, применяем функцию abs(), что означает модуль числа.

Здесь мы должны логические выражения для первого и второго числа взять в скобки, потому что логическая операция И имеет приоритет перед ИЛИ.

Ответ:

Задача (Полный квадрат)

В файле содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от -10000 до 10000 включительно. Определите и запишите в ответе сначала количество пар элементов последовательности, в которых хотя бы одно число является полным квадратом некоторого натурального числа, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два подряд идущих элемента последовательности. Например для последовательности из пяти элементов: 9; 15; 23; -3; 4 — ответ 2 24.

Решение:

f=open('17_3.txt')

count=0
sm=-20000

n1=int(f.readline())

for s in f.readlines():
    n2=int(s)

    if (n1>0 and (int(n1 ** 0.5) ** 2) == n1) or (n2>0 and (int(n2 ** 0.5) ** 2) == n2) :
        count=count+1
        sm=max(n1+n2, sm)
    
    n1=n2

print(count)
print(sm)

Здесь мы извлекаем корень из числа с помощью возведения в степень 0.5. Округляем результат в меньшую сторону с помощью функции int(). А затем снова возводим в квадрат. Если мы получили изначальное число, значит, это число и есть полный квадрат некоторого натурального числа.

Возведение в степень в 0.5 работает и для отрицательных чисел. Т.к. в задаче имеют ввиду квадраты натуральных чисел, то мы работаем только с числами, которые больше нуля.

Ответ:

Задача (Тройки чисел)

(А. Кабанов) В файле 17-3.txt содержится последовательность целых чисел. Элементы последовательности могут принимать целые значения от -10 000 до 10 000 включительно. Определите и запишите в ответе сначала количество троек элементов последовательности, в которых числа расположены в порядке возрастания, затем минимальную из разностей наибольшего и наименьшего элементов таких троек. В данной задаче под тройкой подразумевается три идущих подряд элемента последовательности.

Источник задачи: https://kpolyakov.spb.ru/

Решение:

f=open('17-3.txt')

count=0
rz=20000

n1=int(f.readline())
n2=int(f.readline())

for s in f.readlines():
    n3 = int(s)

    if n1 < n2 < n3:
        count=count+1
        mx = max(n1, n2, n3)
        mn = min(n1, n2, n3)
        rz = min(rz, mx-mn)

    n1=n2
    n2=n3


print(count, rz)

С тройками решаем аналогично. До цикла считываем два числа. Внутри цикла считываем третье число.

В конце цикла перекладываем числа: второе число в n1, третье число в n2.

Ответ:

Задача (Любой порядок элементов)

В файле содержится последовательность из 10 000 целых положительных чисел. Каждое число не превышает 10 000. Определите и запишите в ответе сначала количество пар элементов последовательности, у которых сумма элементов кратна 9, затем максимальную из сумм элементов таких пар. В данной задаче под парой подразумевается два различных элемента последовательности. Порядок элементов в паре не важен.

Источник задачи: https://inf-ege.sdamgia.ru/

Решение:

Первый способ (Красивый).

f = open('17.txt')

count_0 = 0
count_1 = 0
count_2 = 0
count_3 = 0
count_4 = 0
count_5 = 0
count_6 = 0
count_7 = 0
count_8 = 0


mx1_0 = 0
mx2_0 = 0
mx_1 = 0
mx_2 = 0
mx_3 = 0
mx_4 = 0
mx_5 = 0
mx_6 = 0
mx_7 = 0
mx_8 = 0


for s in f.readlines():
    n=int(s)

    if n%9==0:
        count_0 = count_0 + 1

        if n>mx1_0:
            if n>mx2_0:
                mx1_0 = mx2_0
                mx2_0 = n
            else:
                mx1_0 = n

    if n%9==1:
        count_1 = count_1 + 1
        mx_1 = max(mx_1, n)

    if n%9==2:
        count_2 = count_2 + 1
        mx_2 = max(mx_2, n)

    if n%9==3:
        count_3 = count_3 + 1
        mx_3 = max(mx_3, n)

    if n%9==4:
        count_4 = count_4 + 1
        mx_4 = max(mx_4, n)

    if n%9==5:
        count_5 = count_5 + 1
        mx_5 = max(mx_5, n)

    if n%9==6:
        count_6 = count_6 + 1
        mx_6 = max(mx_6, n)

    if n%9==7:
        count_7 = count_7 + 1
        mx_7 = max(mx_7, n)

    if n%9==8:
        count_8 = count_8 + 1
        mx_8 = max(mx_8, n)


count = (count_1*count_8) + (count_2*count_7)  + (count_3*count_6) + (count_4*count_5) + (count_0*(count_0-1)//2)
mx = max(mx_1 + mx_8, mx_2 + mx_7, mx_3 + mx_6, mx_4 + mx_5, mx1_0 + mx2_0)

print(count, mx)

Здесь мы ищем количество элементов, у которых остаток при делении на 9 равен нулю, единице, двойке, … и до 8. Подсчитываем эти данные соответственно в переменные count_0, count_1, count_2 … и т.д.

Так же находим максимальное число, которое имеет при делении на 9 остаток равный единице, двойке, … и т.д. Для чисел, которые имеют остаток при делении на 9 ноль, находим два максимальных числа.

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

Если, к примеру, взять число для которого остаток равен 1 и число для которого остаток равен 8, то их сумма будет делится на 9. Найдём количество пар, если нам известно количество и тех, и тех чисел.

Значит, просто нужно перемножить два числа, к примеру, count_1*count_8.

Для чисел, которые делятся на 9 (т.е. остаток равен нулю), количество пар считается немного по-другому. Такие числа можно суммировать между собой, всё равно сумма тоже будет делится на 9. Путь есть у нас количество чисел count_0, которые делятся на 9. Тогда найдём количество пар, которые можно составить из этих элементов.

Здесь вспомним метод умножения, о котором было написано в этой статье.

Найдём количество таких пар, если каждый элемент можно использовать 1 раз. Получается count_0*(count_0-1). Но т.к. в нашем случае пара, когда элементы находятся в одном порядке и в обратном, является одной и той же, то нужно это количество поделить на 2. Т.е количество пар будет (count_0*(count_0-1))/2.

Второй способ (Перебор).

f = open('17.txt')

count=0
mx=0

a = []

#Считываем все числа в массив a
for s in f.readlines():
    n = int(s)
    a.append(n)

# Перебираем все варианты и подсчитываем пары, отвечающие условию задачи.
for i in range(0, len(a)):
    for j in range(i+1, len(a)):
        if (a[i]+a[j])%9==0:
            count = count + 1
            mx = max(a[i]+a[j], mx)
    

print(count, mx)

В этом решении сначала считываем все числа в массив a.

Далее берём число и начинаем его комбинировать со всеми числами, которые стоят после этого числа. Таким образом, мы переберём все возможные комбинации, и у нас не будут пары повторяться.

Ответ:

1.     Кодирование
текста

2.        
Анализ  таблицы истинности

4. Бд  и  файловая система

6. Алгоритмы

Сколько  1, 0, целых A<X<B, вычислить, перевести (-а) в 2сс

Свойства чисел:

1.числа вида 2^k записываются в двоичной системе как единица и k нулей, например:16 = 2⁴ = 10000₂ (числа,
являющиеся степенями 2,3.. ( в любой СС!!)

2. числа вида 2^k-1 записываются в двоичной системе k единиц, например:      15 = 2⁴-1 = 1111₂ (числа
, предшествующие степеням «2»- состоят из «1» и на разряд меньше (в 3 из 2, 4
из 3 , т.е n-1))

3. Двоичное число (другая n CC), оканчивающееся — на 0 – четное(кратно n), — на 1- нечетное (и любое отличное от нуля  число в той СС
говорит о том, что число не кратно n).

Отрицательное число  = 

1) а-1       2) (а-1)из10 перводим в 2сс       3) первая 1
сохраняется,  все остальные цифры переворачиваем 1-0,0-1

Сопоставлять
значений переменных с функциями                    (начинать с «одиночных»)

1. Отрицание
(НЕ,¬ , Ā) меняет знаки: < на >=,> на<=.<= на
>, >= на <

2.
Логическое умножение (И, •, ˄, &)

3.
Логическое сложение (ИЛИ, +, ˅, |)

Порядок
выполнения операций: ( ), не, и, или, →,º ….

1)внимательно читать задание

2)файловая система:?-точно 1 знак, *-произвольное количество или
их отсутствие

 Автомат(10 СС):

1)определяем СС

2)записываем правило a+b, c+d или другое

3)определяем порядок записи  ­, ¯

4) определяем максимально возможное числов этой СС и
максимальные суммы(!!!помнить о правилах сложения в разных СС)

5) помним о разрядах числа (десятки, сотни, единицы)

Автомат(2СС): четное оканчивается 0, нечетное на 1.

Обработка искаженных сообщений, Калькулятор и др.

5. Декодирование (условие Фано)

Условие Фано: ни одно кодовое слово
не является началом другого кодового слова (дерево 0-1): минимальный код,
короткое слово, сумма кодовых слов, только для конкретного слова и др.

Алгоритм Хаффмана
(оптимальный префиксный код): для самого частого- самый короткий код. Самое
частое повторение обычно 1 бит(0),самые малые повторения обычно 2-3 бита
(умножаем и складываем все ветви)

9.        
Кодирование информации (+передача)

7. Анализ диаграмм и таблица Excel

8. Анализ программ (цикл  while)

Звук:  I=n*i*f*t (n-кол-во дорожек, i-бит на отсчет, f-частота дискретизации ,t-время)

1)
запись близка  2) секунды-минуты

3)
перезаписывают  один и тот же файл — пропорция

1кГц=1000Гц, моно-1, стерео-2, квадро -4, …

Графика: I=k*i, N=2ⁱ(k –кол-во пикселей (200dpi= 200ppi=200*200)

                              i -инф. вес 1 пикселя, N-количество цветов)   

1)определить кол-во цветов 

2)не может превышать <
, >=, > , <=

3) перезаписывают  один и тот же файл — пропорция

4) сохраняют каждые t сек(мин)

Передача информации: I_бит=V_{бит/сек}*t_сек ,  V =I_/t,   t=I/V

 I – размер файла, V – скорость , t – время передачи.

1)сравнение
способов передачи А и Б и на сколько

Наименьшая
единица информации 1 бит

1
байт = 8 бит = 2³бит

1Кбайт(килобайт)
= 1024байт = 2¹⁰байт

1Мбайт(мегабайт)
= 1024Кбайт = 2¹⁰Кбайт

1Гбайт(гигабайт) = 1024Мбайт = 2¹⁰Мбайт

!!!Важно в формулу подставлять значения в одинаковых единицах
измерения и переводить конечный результат в запрашиваемые в задаче единицы.

1)по формулам    2) по пропорции 

1)геометрическая или арифметическая прогрессия

2)условие выполнения цикла (с предусловием)

1)вычисляем значения в ячейках по формулам какие можно

2) соотносим числовые величины и графические изображения
(подбираем число или формулу).    Диапазон ячеек А1:D2 от первой ячейки до
последней.    Весь круг соответствует сумме всех значений, по которым
строится диаграмма. Отдельные сектора пропорциональны доле одного значения в
общей сумм

  
В формулах * — умножение, / — деление, $ — абсолютная ссылка,  при
копировании формулы значение не меняется

10. Перебор слов и СС

1)размещения(с повторениями,  букву сколько угодно раз)Варианты =

2)перестановки (без повторов, букву 1 раз, буквы разные) Р=n!

2)перестановки (без повторов, букву 1 раз, есть одинаковые буквы
разные) Р=n!/n₁! ^.n2!..

4) вероятности  формула Шеннона.

5)Слова(определяем СС (= количество букв), переводим в ту СС, из
той в 10)

— На каком месте стоит слово +1

— Какое слово стоит под номером -1

3. Анализ информационной модели

15.  Количество путей

Соотносим количество пересечений дорог и узлов вершин графа,
анализ начинаем с графа (вершин графа)

Потеря  маршрутов, считая «вручную»

Траектория через А и
не через Б –внимательно!

22. Оператор ветвления

Строим дерево внимательно через те точки, которые указаны в
траектории

11.Рекурсия (функция возврата к самой себе)

14.  Алгоритмы формальных исполнителей

1) Вызов функций F(n) или/и G(n)  от предыдущих значений

2) Количество напечатанных

3) Сумма напечатанных

4) Какие выведет числа (!!!Важен порядок вызова (обращения к
рекурсии).

-если write
стоит в начале, то прямой последовательный обход.

— если write
стоит после какой-то первой функции, то выполняется вызов по этой ветке до
конца, по окончанию вызывается оставшаяся функция.

— если write
стоит после всех функций, аналогично предыдущему

Чертежник

Начал и вернулся туда же: (х,у)+…-…=(0,0)

Вернулся в другую точку: (х,у)+…-…=(х₁,у₁)

Повтори  n 
раз   n*(3+2-4…)

Замена команды n*(а+2-4…)=0,   n*(b+3-8….)=0

1)отдельно считаем смещение по x и по y;

2)внимательно читаем вопрос;

3)даём ответ на вопрос, поставленный в задаче.

Робот:  клетка начала и конца
считается закрашенной, движение идет до упора и по условию.

Редактор: циклы считаем с НАЧАЛА!!!

17. Запросы интернета (Диаграммы Эйлера Венна)

23. Логические уравнения

19. Одномерные массивы

Знак
«&»-пересечение запросов (и) , а «|»-объединение запросов (или)

1) Обозначаем зоны запросов буквами a,b,c,d,e,f…..

2) !!! Два множества могут не пересекаться (просматриваем суммы 
пересечений и объединений)

1) замена переменных, если нужно

2) последовательное решение уравнений

Решение системы уравнений – это битовая цепочка (битовый вектор-
единичный объект)

3) уравнения–ограничения на битовый вектор (комбинации)

4) кол-во решений находиться по правилам комбинаторики (чаще
всего аⁿ)

5) варианты комбинаций истинности и лжи для ˄,˅,→, º

Стратегия решения:  трассировочная
таблица , узнать базовый алгоритм и проверить

г) двумерные
массивы(прямоугольная матрица A[i] , B[i]

Цикл for в цикле for
(выполняется первый внешний цикл, потом полностью выполняется внутренний цикл
for, далее 2 эл из 1, и все из
2го ) (прямоугольная матрица)

16. Уравнения в различных СС

26. Стратегия (теория игр)

13.  Вычисление количества информации

21. Анализ программы с
подпрограммами

1)помнить,
что любое число в степени в соответвующей СС=

2)выражения
упрастить и определить СС, если сс 2,3,4,5,…..при вычитании 1  получается на
1 меньше чем СС.

3)
числа  в конце переводим в нужную СС

4)
если произведение степени и числа, применяем правила арифменики  в той СС
(арифметические операции выполняются в одной СС)

5) если
степень числа * на число, применяем арифметические правила той сс в которой
производиться *.

Важно!!!
Арифметика возможна только в одной и той же СС

Описывать стратегию для «выигравшего- выигрышную стратегию, для
проигравшего- все стратегии» (строим дерево игры)

1) камни (камни две кучи, 2 разных хода)

2) фишки (расстояние

3) карточки(таблички) с числами, убирать дубль, если нужно
укоротить, ставить дубль если нужно удлинить

4) слова (считаем количество букв в словах) Игрок 1- нечетные
ходы, Игрок 2- четные ходы

I=k*i, N=2ⁱ  (N-алфавит, k–количество
символов в тексте, i–
инф. вес 1 символа:

КОИ-8(8 бит),  ASCII(8 бит),  Unicode (16
бит), др)

1) количество вариантов (кто прошел –это N из него находим  i  ( N=2ⁱ ), а  I=k*i –это всего.

2) пароли и номера авто: доп. сведения + код+ пароль

!!!Внимательно читать условие (сведения могут быть в 2 коде или
другой СС)

1) Квадратичные
(биквадратные)  уравнения:

Точки минимума = ,  =у(или через F`(x)

Можно искать точки
(max, min), и
значения функций в точке (fmax, fmin). Оценивать
знаки  ­, ¯ функции.

!!!Обязательно
проверять проверять  значения на концах отрезков.

2) вызов функции k=10,64 и
т.п. min или max число

Если ­+1, то
интервал А £ 
х <В

Если ¯-1,  то
интервал А <  х £В

12. IP-адресация

20. Анализ алгоритма с циклами и ветвлениями

24.  Поиск ошибки в программе

25. Обработка
массива

0₁₀=00000000₂    255₁₀=11111111₂

маска-11111111.11111111.11111000.00000000 (1….потом  0)

1)мах количество 1 или 0 в маске

2)мах и min байт
маски

3) 2 байт маски, если 3 =0

4) сколько различных значений маски (сколько масок, варианты)

5)количество ПК  в сети (2 в степени нулей маски )

6) номер ПК в сети (нули маски в проекции на ip-адрес)

7) два ip принадлежат
одной сети (однозначная маска для обоих)

Номер компьютера

Количество адресов в сети

1) Алгоритм Евклида (2 переменные и разность), НОД
прописан в условии, в условии смотреть какое х  нужно вывести х>100, 150…

Выражаем L
через х, L кратно НОД, далее проверяем на числах.

Вычисление НОД(а,b)= НОД(а-b,b)= НОД(а,b—a)

Заменяем большее из двух чисел разностью большего и меньшего до
тех пор, пока они не станут равны. НОД(14,21)= НОД(14,7)= НОД(7,7)=7

Если разница велика и нужно определить количество шагов.
Заменяем большее остатком от деления на меньшее до тех пор, пока меньше не
станет равно нулю. НОД(21,28) (28mod21=7)= НОД(21,7) (21mod7=0)=НОД(0,7)=7

2) Обработка цифр в числе:

— на выводе отмечаем, какие числа выводит программа (указаны в
условии)

— ВАЖНО!!!определить СС в которой обрабатываются числа

x: = а div 10, x: = а div 2, x: = а div 3 , x: = а div 4 , x: = а div 5

ЗНАТЬ!!! числа входящие в конкретную СС (0- число четное!!!)

Перебор цифр в числе за счет цикла ( while x>0  ) пока оно не равно нулю.

— если  определяют не просто число , а разрядное (трехзначное,
двузначное)- это дополнительное условие (первое двузначное-10_n, трехзначное 100_n и т.д конечная граница определяется переводом из 10 сс в нужную)

ЯЗЫК программирования Pascal не понимает другие СС, кроме 10!!

После решения задачи в какой-то СС , переводим полученное число
в 10СС

!!!Проверка на четность:

— в четных СС по последней цифре (0,2,4,6,8 СС)

— нечетных СС по сумме цифр в числе (1,3,5,7,9 СС)

Схема
решения задачи: прогнать задачу на требуемом числе или
на любом удобном Þ чаще всего можно сразу ответить на 1 и 3
вопрос задачи (найти ошибки)  (прогнать и убедиться в правильности)  Þ  после
выполнить 2 задание задачи (найти число работающее правильно )

Решая
задачу делить ее на части:

1)
что выводит (writeln(…)) и
запрашивает readln(…))

2) проверять
инициализацию переменных s:=0, p:=1, k:=0

3)
проверяем условия циклов и условий  (правила их работы) и  сам алгоритм

Проверка
на степень: n=a^k   Þ  , т.е if n=1.

    Формулу для вычисления n-ого элемента арифметической прогрессии: а_n=a₁+d(n-1) формулу для вычисления суммы первых n членов арифметической прогрессии:,           
где a_i – i-ый
элемент последовательности,d – шаг (разность) последовательности

1) Организация ввода данных (уже есть)

2) Инициализация начальных значений некоторых переменных (требуется
задать!)

3)Обработка данных (требуется организовать!)

4) Вывод данных (требуется организовать!)

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

ВАЖНО!!! не писать программу полностью, а «дописать» её в рамках
уже организованного ввода, а также  заданного количества переменных и их
типов: необходимо дописать инициализацию, организовать обработку и вывод.

Для проверки на кратность использовать —

a[i] mod
2 <> 0 (Кратность  n)

18. Логические выражения

1. Если формула истинна (равна 1), и  после упрощения A без
отрицания, то используется закон: A_min = ¬B

    Если формула истинна (равна 1), и после
упрощения A с отрицанием, то используется закон:A_max =
B

2. Если формула ложна (равна 0), и после
упрощения A без отрицания,  то используется закон: A_max =
¬B

Если формула ложна (равна 0), и 2. после
упрощения A с отрицанием, то используется закон: A_min =
B, где B — известная часть выражения