Как решать 26 задание в егэ по информатике через эксель
ЕГЭ-16: решение через Excel
В этой презентации рассмотрено решение некоторых
задач из 16 задания ЕГЭ через Excel.
Презентация не подготовит Вас полностью к решению
16-го задания!
Нужно будет также научиться решать задачи
программированием: некоторые типы задач невозможно
или слишком тяжело решить с помощью Excel.
Задача 1
Алгоритм вычисления функции F(n) задан следующими
соотношениями:
F(n) = 1 при n = 1
F(n) = n + F(n–1), если n чётно,
F(n) = 2· F(n–2), если n > 1 и n нечётно.
Чему равно значение функции F(26)?
Решение задачи 1 - Excel
Решение с помощью Excel является усовершенствованным способом решения через
таблицу. Будьте очень аккуратны при решении задач таким методом: очень легко
допустить ошибку, скопировав не в ту ячейку.
Требуется создать таблицу из двух строк и 27 колонок:
Заполним ячейку B2 (значение F(1)). По условию задачи F(1) = 1.
Решение задачи 1 - Excel
Следующая ячейка, которую нужно заполнить, B3 (значение F(2)). 2 – чётное число,
поэтому:
F(n) = n + F(n–1)
Если n = 2, F(2) = 2 + F(1)
Чтобы формулу в дальнейшем можно было растиражировать, везде, там, где в
формуле стоит n и F(n -1), мы поставим ссылки на конкретные ячейки в таблице.
Конкретные значения (2 и 1) подставлять ни в коем случае не нужно!
n = 2 - это ячейка C1
F(n - 1) = F(1) – это ячейка B2
Формула в ячейка выглядит так:
= C1 + B2
Формулу требуется переписать прямо вместе с равно.
Решение задачи 1 - Excel
Получаем:
Для F(4), F(6), F(8), F(10) . F(26) будет работать та же формула, что и для F(2), а для
F(5), F(7), F(9), F(11) . F(25) – та же формула, что и для F(3).
Растиражируем формулу:
до числа 26
Самостоятельно
1.1) Чему равно значение функции F(10)?
F(n) = 1 при n = 1
F(n) = 2·F(n–1) + n + 3, если n > 1
1.2) Чему равно значение функции F(1)?
F(n) = 2n – 5 при n > 12
F(n) = 2·F(n+2) + n – 4, если n 1.3) Чему равно значение F(64)?
F(n) = 1 при n = 1
F(n) = 2·F(n–1), если n чётно,
F(n) = 5n + F(n–2), если n нечётно.
Задача 2
Алгоритм вычисления функции F(n) задан следующими
соотношениями:
F(n) = 5–n при n < 5
F(n) = 4· (n – 5)·F(n–5), если n делится на 3,
F(n) = 3n + 2·F(n–1) + F(n–2), если n не делится на 3.
Чему равно значение функции F(20)?
Решение задачи 2 - Excel
Решение подстановкой выходит очень сложным – слишком много возможностей
допустить арифметическую ошибку. Гораздо удобнее решать эту задачу в Excel.
Требуется создать таблицу из двух строк и 21 колонки:
По условию задачи F(n) = 5–n при n < 5. На самом деле это – выход из рекурсии
(потому что значение F(n) можно вычислить сразу же).
Определим, какую формулу нужно записать в ячейку B2:
5 – это константа, поэтому так и перепишем в формулу;
n находится в ячейке B1. Нельзя подставлять сюда значение 1: так формулу не
получится растиражировать.
Решение задачи 2 - Excel
Итоговая формула для ячейки B2:
=5 – B1
Формула F(n) = 5 – n справедлива при n < 5, т.е. для ячеек B2 – E2. Растиражируем:
до числа 4 (ячейка E2)
Решение задачи 2 - Excel
Получаем:
Для остальных ячеек эта формула уже не подойдёт.
Для n=5:
F(n) = 3n + 2·F(n–1) + F(n–2)
3 и 2 – константы, их просто переписываем в формулу. Значение n для n=5 находится
в ячейке F1, значение F(n-1) находится в ячейке E2, значение F(n – 2) находится в
ячейке D2, значение F(n) (т.е. F(5)) находится в ячейке F2. Итоговая формула в
ячейке F2:
=3*F1 + 2*E2 + D2
Решение задачи 2 - Excel
Для F(6) (ячейка G2):
F(n) = 4· (n – 5)·F(n–5), т.к. 6 делится на 3
4 – константа, так и переписываем, n - это ячейка G1, F(n – 5) – это F(1), т.е. ячейка
B2. Получаем:
= 4 * (G1 - 5) * B2
Решение задачи 2 - Excel
Для F(7) (ячейка H2) формула строится по такому же принципу, как и для F(5).
Получаем, что в ячейку H2 надо записать формулу:
=3*H1+2*G2+F2
Для F(9), F(12), F(15), F(18) формула строится таким же образом, как и для F(6).
Для F(8), F(11), F(14), F(17), F(20) формула строится так же, как и для F(5).
Для F(10), F(13), F(16), F(19) формула строится так же, как и для F(7).
Все значения n "покрыты". Можно тиражировать формулу.
Решение задачи 2 - Excel
нижнем углу выделения и протянуть до
числа 4 (ячейка E2)
Обратите внимание: тиражируются ячейки F2-H2, первые ячейки таблицы мы не
трогаем.
После тиражирования:
полностью значение в ячейки S2-U2 не
влезает, чтобы увидеть ответ, растяните
ячейку U2
Самостоятельно
2.1) Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 2 · n · n · n + n · n при n > 25
F(n) = F(n+2) + 2 · F(n+3), если n Чему равна сумма цифр значения функции F(2)?
2.2) Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = 1+2n при n < 5
F(n) = 2·(n + 1)·F(n–2), если n делится на 3,
F(n) = 2·n + 1 + F(n–1) + 2·F(n–2), если n не делится на 3.
Чему равно значение функции F(15)?
2.3) Алгоритм вычисления функции F(n) задан следующими соотношениями:
F(n) = n + 3 при n < 3
F(n) = (n + 2)·F(n–4), если n делится на 3,
F(n) = n + F(n–1) + 2·F(n–2), если n не делится на 3.
Чему равно значение функции F(20)?
Задача 3
Алгоритм вычисления функций F(n) и G(n) задан
следующими соотношениями:
F(1) = G(1) = 1
F(n) = 2·F(n–1) + G(n–1) – 2, если n > 1
G(n) = F(n–1) +2·G(n–1), если n > 1
Чему равно значение F(14) + G(14)?
Решение задачи 3 – Excel
Создадим таблицу из 3 строк и 15 колонок.
По условию задачи F(1) = 1, G(1) = 1.
Решение задачи 3 – Excel
Разберём формулу F(n) = 2·F(n–1) + G(n–1) – 2, если n > 1
Для F(2) получаем: F(2) = 2*F(1) + G(1) – 2
F(1) – это ячейка B2
G(1) – это ячейка B3
F(2) – это ячейка C2
Т.е. в ячейку C2 нужно записать формулу:
= 2*B2 + B3 – 2
Решение задачи 3 – Excel
Получаем:
Сразу же тиражируем на всю 2-ю строчку. Значения получатся
неправильные, но мы потом их исправим.
Решение задачи 3 – Excel
Разберём формулу G(n) = F(n–1) +2·G(n–1), если n > 1
Для G(2) получаем: G(2) = F(1) + 2*G(1)
F(1) – это ячейка B2
G(1) – это ячейка B3
G(2) – это ячейка C3
Т.е. в ячейку C3 нужно записать формулу:
= B2 + 2*B3
Решение задачи 3 – Excel
Получаем:
Сразу же тиражируем на всю 3-ю строчку. Теперь значения во всей
таблице будут правильными.
Решение задачи 3 – Excel
Растянем последний столбец, чтобы увидеть, чему равны
значения F(14) и G(14).
Т.к. в ответе требуется сумма F(14)+G(14), в какой-нибудь
произвольной пустой ячейке запишем:
= O2 + O3
Самостоятельно
3.1) Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями:
F(n) = G(n) = 1 при n = 1
F(n) = F(n–1) – n· G(n–1), при n > 1
G(n) = F(n–1) + 2· G(n–1), при n > 1
Чему равно значение функции G(18)?
3.2) Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями:
F(n) = G(n) = 1 при n = 1
F(n) = F(n–1) – 2 · G(n–1), при n > 1
G(n) = F(n–1) + G(n–1) + n, при n > 1
Чему равна сумма цифр значения функции G(36)?
3.3) Алгоритм вычисления функций F(n) и G(n) задан следующими соотношениями:
F(n) = G(n) = 4*n – 2 при n > 7
F(n) = F(n+1) - G(n+2) + n, при n G(n) = 2*F(n+2) - G(n+1), при n Чему равно значение F(-9) + G(-9)?
Два игрока, Петя и Ваня, играют в следующую игру. Перед игроками лежат две кучи камней. Игроки ходят по очереди, первый ход делает Петя. За один ход игрок может добавить в одну из куч (по своему выбору) один камень или увеличить количество камней в куче в три раза.
Например, пусть в одной куче 10 камней, а в другой 7 камней; такую позицию в игре будем обозначать (10, 7). Тогда за один ход можно получить любую из четырёх позиций: (11, 7), (30, 7), (10, 8), (10, 21).
Для того чтобы делать ходы, у каждого игрока есть неограниченное количество камней.
Игра завершается в тот момент, когда суммарное количество камней в кучах становится не менее 68. Победителем считается игрок, сделавший последний ход, т.е. первым получивший такую позицию, при которой в кучах будет 68 или больше камней.
В начальный момент в первой куче было шесть камней, во второй куче – S камней; 1 ≤ S ≤ 61.
Будем говорить, что игрок имеет выигрышную стратегию, если он может выиграть при любых ходах противника. Описать стратегию игрока – значит описать, какой ход он должен сделать в любой ситуации, которая ему может встретиться при различной игре противника. В описание выигрышной стратегии не следует включать ходы играющего по этой стратегии игрока, не являющиеся для него безусловно выигрышными, т.е. не являющиеся выигрышными независимо от игры противника.
Выполните следующие задания:
Задание 1
Задание 2
Укажите такое значение S, при котором у Пети есть выигрышная стратегия, причём одновременно выполняются два условия:
Для указанного значения S опишите выигрышную стратегию Пети.
Задание 3
Укажите значение S, при котором одновременно выполняются два условия:
Постройте дерево всех партий, возможных при этой выигрышной стратегии Вани (в виде рисунка или таблицы). В узлах дерева указывайте позиции, на рёбрах рекомендуется указывать ходы. Дерево не должно содержать партии, невозможные при реализации выигрывающим игроком своей выигрышной стратегии. Например, полное дерево игры не является верным ответом на это задание.
Задание 2
Возможное значение S: 20. В этом случае Петя, очевидно, не может выиграть первым ходом. Однако он может получить позицию (7, 20). После хода Вани может возникнуть одна из четырёх позиций: (8, 20), (21, 20), (7, 21), (7, 60).
В каждой из этих позиций Петя может выиграть одним ходом, утроив количество камней во второй куче.
Замечание для проверяющего. Ещё одно возможное значение S для этого задания – число 13. В этом случае Петя первым ходом должен утроить количество камней в меньшей куче и получить позицию (6 * 3, 13) = (18, 13). При такой позиции Ваня не может выиграть первым ходом, а после любого хода Вани Петя может выиграть, утроив количество камней в большей куче. Достаточно указать одно значение S и описать для него выигрышную стратегию.
Задание 3
Возможное значение S: 19. После первого хода Пети возможны позиции: (7, 19), (18, 19), (6, 20), (6, 57). В позициях (18, 19) и (6, 57) Ваня может выиграть первым ходом, утроив количество камней во второй куче.
Из позиций (7, 19) и (6, 20) Ваня может получить позицию (7, 20). Эта позиция разобрана в п. 2. Игрок, который её получил (теперь это Ваня), выигрывает своим вторым ходом.
Таблица-дерево возможных партий:
В таблице изображено дерево возможных партий (и только их) при описанной стратегии Вани. Заключительные позиции (в них выигрывает Ваня) выделены жирным шрифтом.
27-е задание: «Анализ числовых последовательностей»
Уровень сложности — высокий,
Требуется использование специализированного программного обеспечения — да,
Максимальный балл — 2,
Примерное время выполнения — 35 минут.
Проверяемые элементы содержания: Умение создавать собственные программы (20–40 строк) для анализа числовых последовательностей
"О выборе языка программирования. Выбирайте тот язык, которым лучше всего владеете. Никакого повышения или снижения баллов за экзотичность языка не предусмотрено."
Типичные ошибки и рекомендации по их предотвращению:
Программирование: обработка строк или последовательности чисел. Сложность алгоритмов
- строку можно представить, как одномерный массив, в котором хранятся символы;
- для того чтобы обратиться к символу строки s с номером i (например, вывести его на экран) используется запись s[i] :
- при работе со строками используется операция конкатенации или объединения строк в одну; в качестве нее используется знак сложения ( + ), например:
- в кодовой таблице ASCII цифры имеют коды от 48 (соответствует цифре 0) до 57 (соответствует цифре 9); функция Ord() служит для получения кода символа, например:
- то же самое можно сделать с помощью преобразования типа (перевод типа char к типу integer)
- функция Chr() служит для обратного перевода: получения символа по его коду, например:
- то же самое можно сделать с помощью преобразования типа (привести тип integer к типу char)
Запись в Паскале — это сложный тип данных, который может состоять из нескольких элементов – полей; поля могут иметь различный тип.
-
где a и b – постоянные, которые имеют свои значения для определенных классов задач;
- так, если задача решена двумя способами: в одном используется несколько циклов от 1 до N, а во втором используется только один цикл, то хотя оба алгоритма имеют сложность O(N) , но эффективнее в большинстве случаев является алгоритм с одним циклом, так как постоянная a при подсчете количества операций будет больше в случае с алгоритмом с несколькими циклами.
- сложность алгоритма O(N 2 ) означает, что при увеличении в два раза N количество операций возрастет примерно в четыре раза (т.е. количество операций пропорционально квадрату размера массива);
- примером сложности O(N 2 ) алгоритма является программа с двумя вложенными циклами, в каждом из которых N итераций (проходов); например, алгоритмы сортировки массивов методами «пузырька» или выбора.
- экспоненциальная сложность означает, что размер массива входит в показатель степени:
- для больших N такие задачи не эффективны и не решаются за приемлемое время.
Решение 27 заданий ЕГЭ по информатике
Плейлист видеоразборов задания на YouTube:
Задание демонстрационного варианта 2022 года ФИПИ
Задания, начиная с 2021
Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи.
Пример входных данных:
Пример выходных данных для приведённого выше примера входных данных:
Язык Python (Питон):
Ответ: 67303 200157496
Задания предыдущих лет на повторение
На вход программы поступает последовательность чисел, произвести анализ пар
27_4: Разбор 27 задания ЕГЭ по информатике 2019 года вариант 5 (сборник Крылов С.С., Чуркина Т.Е. «Типовые экзаменационные варианты», 20 вариантов):
Компьютер наземной станции слежения получает от объектов-самолётов, находящихся в зоне её работы, идентификационные сигналы, представляющие собой последовательность из N целых положительных чисел. Каждый объект направляет на наземную станцию уникальное число, т. е. все числа в получаемой станцией последовательности различны. Обработка сигнала представляет собой рассмотрение всех пар различных элементов последовательности, при этом элементы пары не обязаны быть переданы непосредственно друг за другом, порядок элементов в паре не важен. Считается, что возникла одна критическая ситуация, если произведение элементов некоторой пары кратно 58.
Необходимо определить общее количество возникших критических ситуаций.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (1
-
Язык Паскаль (версия PascalABC):
var N: integer; a: integer; n58, n29, n2: integer; k58: integer; i: integer; begin readln(N); n58 := 0; n29 := 0; n2 := 0; for i := 1 to N do begin readln(a); if a mod 58 = 0 then n58 := n58 + 1 else if a mod 29 = 0 then n29 := n29 + 1 else if a mod 2 = 0 then n2 := n2 + 1; end; k58 := n58 * (n58 - 1) div 2 + n58 * (N - n58) + n2 * n29; writeln(k58) end.
N58 = 0 N2 = 0 N29 = 0 NX = 0 INPUT N FOR I = 1 TO N INPUT A IF A MOD 58 = 0 THEN N58 = N58 + 1 ELSE IF A MOD 29 = 0 THEN N29 = N29 + 1 ELSE IF A MOD 2 = 0 THEN N2 = N2 + 1 ELSE NX = NX + 1 END IF END IF END IF NEXT I K58 = N58*(N58 - 1)\2 + N58*(N2 + N29 + NX) + N2*N29 PRINT K58
- n58 — количество чисел, кратных 58;
- n29 —количество чисел, кратных 29, но не кратных 2 и 58;
- n2 — количество чисел, кратных 2, но не кратных 29 и 58.
✎ Программа неэффективная (2 балла):
-
Язык Паскаль (версия PascalABC):
var i, j, k, n: integer; a: array[1..1000]of integer;//очередное значение begin readln(n); for i := 1 to n do begin readln(a[i]); end; k := 0; for i := 1 to n - 1 do for j := i + 1 to n do if a[i] * a[j] mod 58 = 0 then k := k + 1; writeln(k); end.
Полный перебор: все числа сохраняются в массиве, рассматриваются все возможные пары и подсчитывается количество подходящих произведений.
На вход программы поступает последовательность из N целых положительных чисел, все числа в последовательности различны. Рассматриваются все пары различных элементов последовательности (элементы пары не обязаны стоять в последовательности рядом, порядок элементов в паре не важен). Необходимо определить количество пар, для которых произведение элементов делится на 26.
Описание входных и выходных данных В первой строке входных данных задаётся количество чисел N (1 ≤ N ≤ 1000). В каждой из последующих N строк записано одно целое положительное число, не превышающее 10 000.
В качестве результата программа должна напечатать одно число: количество пар, в которых произведение элементов кратно 26.
Пример входных данных:
Пример выходных данных для приведённого выше примера входных данных:
Из них на 26 делятся 4 произведения:
Требуется написать эффективную по времени и по памяти программу для
решения описанной задачи.
-
Произведение двух чисел делится на 26, если выполнено одно из следующих условий (условия не могут выполняться одновременно).
А. Оба сомножителя делятся на 26.
Б. Один из сомножителей делится на 26, а другой не делится.
В. Ни один из сомножителей не делится на 26, но один сомножитель делится на 2, а другой – на 13.
Примечание для проверяющего. Условие делимости произведения на 26 можно сформулировать проще, например, так:
(один из сомножителей делится на 26) ИЛИ
(один сомножитель делится на 2, а другой – на 13).
Но в этом случае пара сомножителей может удовлетворять обоим условиям, что затруднит подсчёт количества пар.
При вводе чисел можно определять, делится ли каждое из них на 26, 2 и 13, и подсчитывать следующие значения:
1) n26 – количество чисел, кратных 26;
2) n13 – количество чисел, кратных 13, но не кратных 26;
3) n2 – количество чисел, кратных 2, но не кратных 26.
Примечание для проверяющего. Сами числа при этом можно не хранить.
Каждое число учитывается не более чем в одном из счётчиков.
Количество пар, удовлетворяющих условию А, можно вычислить по формуле n26·(n26 – 1)/2.
Количество пар, удовлетворяющих условию Б, можно вычислить по формуле n26·(N – n26).
Количество пар, удовлетворяющих условию В, можно вычислить по формуле n2·n13.
Поэтому искомое количество пар вычисляется по формуле
✎ Программа эффективна и по времени, и по памяти (4 балла):
Программа на языке Паскаль (версия PascalABC):
var N: integer; a: integer; n26, n13, n2: integer; k26: integer; i: integer; begin readln(N); n26 := 0;n13 := 0;n2 := 0; for i := 1 to N do begin readln(a); if a mod 26 = 0 then n26 := n26 + 1 else if a mod 13 = 0 then n13 := n13 + 1 else if a mod 2 = 0 then n2 := n2 + 1; end; k26 := n26 * (n26 - 1) div 2 + n26 * (N - n26) + n2 * n13; writeln(k26) end.
Программа на языке Python (версия Python 3):
n=int(input()) n26,n13,n2=0,0,0 for i in range(n): a=int(input()) if a % 26 == 0: n56+=1 elif a % 13 == 0: n13+=1 elif a % 2 == 0: n2+=1 k26=n26 * (n26-1) // 2 + n26 * (n-n26) + n2 * n13 print(k26)
Программа на языке Бейсик:
N26 = 0 N2 = 0 N13 = 0 NX = 0 INPUT N FOR I = 1 TO N INPUT A IF A MOD 26 = 0 THEN N26 = N26 + 1 ELSE IF A MOD 13 = 0 THEN N13 = N13 + 1 ELSE IF A MOD 2 = 0 THEN N2 = N2 + 1 ELSE NX = NX + 1 END IF END IF END IF NEXT I K26 = N26*(N26 - 1)\2 + N26*(N2 + N13 + NX) + N2*N13 PRINT K26
Дана последовательность N целых положительных чисел. Рассматриваются все пары элементов последовательности, разность которых чётна, и в этих парах, по крайней мере, одно из чисел пары делится на 19. Порядок элементов в паре неважен. Среди всех таких пар нужно найти и вывести пару с максимальной суммой элементов. Если одинаковую максимальную сумму имеет несколько пар, можно вывести любую из них. Если подходящих пар в последовательности нет, нужно вывести два нуля.
Описание входных и выходных данных
В первой строке входных данных задаётся количество чисел N (2 ≤ N ≤ 10 000). В каждой из последующих N строк записано одно натуральное число, не превышающее 10 000.
Пример входных данных:
Пример выходных данных для приведённого выше примера входных данных:
Пояснение. Из данных пяти чисел можно составить три различные пары, удовлетворяющие условию: (38, 12), (38, 16), (57, 57). Наибольшая сумма получается в паре (57, 57). Эта пара допустима, так как число 57 встречается в исходной последовательности дважды.
Напишите эффективную по времени и памяти программу для решения этой задачи.
Программа считается эффективной по времени, если при увеличении количества исходных чисел N в k раз время работы программы увеличивается не более чем в k раз.
Программа считается эффективной по памяти, если память, необходимая для хранения всех переменных программы, не превышает 1 Кбайт и не увеличивается с ростом N.
Максимальная оценка за правильную (не содержащую синтаксических ошибок и дающую правильный ответ при любых допустимых входных данных) программу, эффективную по времени и памяти, – 4 балла.
Максимальная оценка за правильную программу, эффективную только по времени или только по памяти, – 3 балла.
Максимальная оценка за правильную программу, не удовлетворяющую требованиям эффективности, – 2 балла.
Вы можете сдать одну или две программы решения задачи. Если Вы сдадите две программы, каждая из них будет оцениваться независимо от другой, итоговой станет бо́льшая из двух оценок.
Перед текстом программы кратко опишите алгоритм решения. Укажите использованный язык программирования и его версию.
- ✎ Программа эффективна по времени и памяти
const p = 19; var N: integer; a: integer; m0, m1: integer; mp0, mp1: integer; x, y: integer; i: integer; begin m0 := 0; m1 := 0; mp0 := 0; mp1 := 0; x := 0; y := 0; readln(N); for i := 1 to N do begin readln(a); // для четных if a mod 2 = 0 then begin // если кратное if (a mod p = 0) and (a >= mp0) then begin if mp0 > m0 then m0:= mp0; mp0:=a end else if a > m0 then m0 := a; end else begin // для нечетных if (a mod p = 0)and(a>=mp1) then begin if mp1>m1 then m1:=mp1; mp1 := a; end else if a>m1 then m1:=a; end; end; // writeln('mp0=', mp0, 'm0=', m0); if (mp0 > 0) and (m0 > 0) then begin x := mp0; y := m0; end; // writeln('mp1=', mp1, 'm1=', m1); if (mp1 > 0) and (m1 > 0) and (mp1 + m1 > x + y) then begin x := mp1; y := m1; end; writeln('=', x, ' ', y) end.
const p = 19; var n, i, x, k19n, k19chet, n19chet, n19n, m1, m2: integer; begin readln(n); readln(x); // обнуление всех переменных k19chet := 0; // четный кратный n19chet := 0; // четный некратный k19n := 0; // нечетный кратный n19n := 0; // нечетный некратный m1 := 0; m2 := 0; // максимальные // цикл до n - 1, т.к. первое число уже считали for i := 1 to n - 1 do begin // проверка, если четный и кратный if (x mod p = 0) and (x mod 2 = 0) and (x > k19chet) then begin k19chet := x; end; // проверка, если четный и некратный if (x mod p <> 0) and (x mod 2 = 0) and (x > n19chet) then begin n19chet := x; end; // проверка, если нечетный и кратный if (x mod p = 0) and (x mod 2 = 1) and (x > k19n) then begin k19n := x; end; // проверка, если нечетный и некратный if (x mod p <> 0) and (x mod 2 = 1) and (x > n19n) then begin n19n := x; end; readln(x); // считываем очередное число // если x кратно и есть такое некратное n19chet, сумма с которым была бы больше чем m1 + m2 if (x mod p = 0) and ((x + n19chet) mod 2 = 0) and (x + n19chet > m1 + m2) and (n19chet > 0) then begin m1 := x; m2 := n19chet; end; // если x кратно и есть такое некратное n19n, сумма с которым была бы больше чем m1 + m2 if (x mod p = 0) and ((x + n19n) mod 2 = 0) and (x + n19n > m1 + m2) and (n19n > 0) then begin m1 := x; m2 := n19n; end; // если есть такое кратное k19n, сумма с которым была бы четной и больше чем m1 + m2 if ((x + k19n) mod 2 = 0) and (x + k19n > m1 + m2) and (k19n > 0) then begin m1 := x; m2 := k19n; end; // если есть такое кратное k19chet, сумма с которым была бы четной и больше чем m1 + m2 if ((x + k19chet) mod 2 = 0) and (x + k19chet > m1 + m2) and (k19chet > 0) then begin m1 := x; m2 := k19chet; end; end; writeln(m1, ' ', m2) end.
p = 19 m0 = m1 = mp0 = mp1 = 0 N = int(input()) for i in range(N): a = int(input()) if a % 2 == 0: if a % p == 0 and a >= mp0: if mp0 > m0: m0 = mp0 mp0 = a elif a > m0: m0 = a else: if a % p == 0 and a >= mp1: if mp1 > m1: m1 = mp1 mp1 = a elif a > m1: m1 = a x = y = 0 if mp0 > 0 and m0 > 0: x = mp0; y = m0 if mp1 > 0 and m1 > 0 and mp1 + m1 > x + y: x = mp1; y = m1 print(x,y)
Ещё один путь решения – записать всю последовательность в массив и анализировать её в несколько проходов. Ниже приводится реализующая такой алгоритм программа на языке C++. В этой программе массив с исходными данными обрабатывается два раза: на первом проходе находятся индексы максимального чётного и нечётного элементов, кратных p, на втором проходе – общие чётный и нечётный максимумы. При этом элементы, выделенные как кратные при первом проходе, во время второго прохода из сравнения исключаются. Такая программа эффективна по времени (несмотря на повторную обработку массива, общее время работы пропорционально N), но неэффективна по памяти. Максимальная оценка за такую программу при отсутствии в ней синтаксических и содержательных ошибок – 3 балла.
Запишем все исходные числа в массив, переберём все возможные пары и выберем подходящую. Такое решение не является эффективным ни по памяти (требуемая память зависит от размера исходных данных), ни по времени (количество возможных пар, а значит, количество действий и время счёта с ростом количества исходных элементов растут квадратично). Подобная программа оценивается не выше 2 баллов.
Язык Pascal (версия PascalABC):
const p = 19; var N: integer; a: array [1..10000] of integer; x, y: integer; i, j: integer; begin readln(N); for i := 1 to N do readln(a[i]); x := 0; y := 0; for i := 1 to N - 1 do begin for j := i + 1 to N do begin if ((a[i] - a[j]) mod 2 = 0) and ((a[i] mod p = 0) or (a[j] mod p = 0)) and (a[i] + a[j] > x + y) then begin x := a[i]; y := a[j] end end end; writeln(x, ' ', y) end.
Выбрать из каждой пары одно число
Задание А (более легкое, чем Б)
Имеется набор данных, состоящий из 5 пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеет значения.
Задание Б (более сложное, чем А)
Имеется набор данных, состоящих из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма квадратов всех выбранных чисел была нечетной и при этом максимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.
Напишите программу для решения этой задачи.
Постарайтесь сделать программу эффективной по времени, если время работы программы пропорционально количеству пар чисел N, т.е. при увеличении N в k раз время работы программы должно увеличиваться на более чем в k раз.
Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.
Максимальная оценка за правильную программу, эффективную по времени и по памяти, — 4 балла.
Как в варианте А, так и в варианте Б программа должна напечатать одно число — максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).
✍ Решение:
-
поскольку в задании указано, что «имеется набор данных, состоящих из пар…», то введем в программу переменную n для количества пар, значение которой будет считываться со стандартного входного потока:
Здравствуйте, дорогие друзья. Представляем вашему вниманию элементарное решение 26-го задание ЕГЭ по информатике, которое придумала одна моя ученица. Гарантирую, что такого способа вы не найдёте нигде в Интернете. Прочитав статью вы удивитесь, как одно из самых сложных заданий по программированию из части С решается легче лёгкого с помощью Excel.
Вот само задание:
1) Скачиваем файл.
2) Открываем в любом удобном формате (Блокнот, WordPad, Word).
3) Копируем данные из файла.
4) Создаем лист в Excel.
5) Вставляем данные.
6) В верхней ячейке оставляем первое число
7) Выносим его в ячейку С1
8) Столбец с данными сортируем по возрастанию, вписываем в ячейку В2 значение 1. Для того, чтобы отсортировать по возрастанию необходимо выполнить следующее: на вкладке "Главная" найти справой стороны "Сортировка и фильтр". Нажав на "Сортировку и фильтр", выбрать "Сортировать от А до Я".
9) Находим сумму ячейки и предыдущего значения
10) Растягиваем формулу на весь столбец В
11) В столбце В находим значение, которое будет либо равно значению в ячейке С1, либо меньше. Значение, которое будет больше значения в ячейке С1 ни в коем случае не подходит.
12) Первым ответом к заданию является порядковый номер. В нашем случае это число 568.
13) После данного шага алгоритм делится на две части. Случай 1) в столбце В есть число, равное значению С1. Случай 2) в столбце В есть число, меньшее С1.
14) В первом случае мы выписываем значение из ячейки столбца А, которая соответствует значение в ячейке столбца В.
15) Во втором случае мы находим разницу между С2 и найденным значением в столбце В.
16) Для нахождения второго ответа нам следует прибавить разницу к существующему числу из столбца А, которое соответствует найденному ранее значению из столбца В.
17) В нашем случае разница равна 24. Следовательно, мы получаем число (24+29)=53.
18) Если такое число есть в столбце А, то мы записываем его в ответ.
19) Если такого числа нет, то мы ищем наиболее близкое число, не превышающее это значение. В нашем случае это 50 .
В текстовом файле записан набор натуральных чисел, не превышающих 10⁹. Гарантируется, что все числа различны. Необходимо определить, сколько в наборе таких пар чётных чисел, что их среднее арифметическое тоже присутствует в файле, и чему равно наибольшее из средних арифметических таких пар. Первая строка входного файла содержит целое число N — общее количество чисел в наборе. Каждая из следующих N строк содержит одно число.
В ответе запишите два целых числа : сначала количество пар, затем наибольшее среднее арифметическое.
Как видно из первой строчки, файл содержит N = 5000, что довольно много. Значит любая "дорогая" операция сильно затормозит программу.
В нашей программе требуется исследовать пары чисел. А это значит, что каждому из N элементов файла нужно сопоставить остальные N - 1 элементов файла. Но если мы так пройдем до конца, то все пары чисел пройдут по 2 раза. То есть количество проверок нужно разделить на 2. Итак, у нас ориентировочно Count = N * (N - 1) / 2 сравнений. Помните формулу количества ребер полного графа? Вот это именно тот случай.
Получается, что для N элементов мы имеем квадратичную сложность выбора пар. Если мы попытаемся сделать два вложенных цикла считывания из файла, то столкнемся с большими проблемами:
1. Легко запутаться, так как нужно будет запоминать позиции считывания в файле;
2. Операции обращения к файлу, лежащему в постоянной памяти, очень дорогие по времени. Поэтому даже правильно написанная программу будет работать очень долго. Думаю, что это даже не будет особо зависеть от того HDD у вас или SSD;
Каким тогда может быть решение?
Можно попробовать считать все элементы файла в массив. Да, массив будет большой, но зато мы будем иметь быстрый доступ к нему из RAM. Здесь может показаться, что достаточно записать в массив только четные элементы, ведь пары должны состоять из четных элементов. Однако, это не так. Даже если у нас есть два четных числа, то среднее арифметическое может быть нечетным. Пример: a = 2, b = 20, сред. арифм. = (2 + 20)/2 = 11 - нечетное. Получается, что мы должны записывать все числа из файла: как четные, так и нечетные. Считывание можно организовать следующим образом:
Что делать, если мы имеем все элементы файла в массиве?
Останется перебрать все файлы без повтора (это учитывается во внутреннем цикле for), а при нахождении подходящей пары, запускать цикл проверки по всем элементам, чтобы полным перебором определить, а есть ли среднее арифметическое подходящей пары в массиве. Ну и по ходу делать обновлять максимальное значение среднего арифметического.
Сделать это можно так:
И, казалось бы, всё хорошо и логично, но тогда и не было бы смысла писать об этом заметку. Да, такая программа выдаст вам правильный результат, но займет кучу времени на подсчет.
Как определить время выполнение программы в Pascal
В языке Pascal, как и в других ЯП, можно определить время выполнения с помощью встроенной в модуль Utils функции Milliseconds , которая возвращает текущее время в миллисекундах с момента запуска процесса текущей программы.
Чтобы определить время выполнения конкретного участка кода, можно засечь таймер перед проблемным участком , скорость которого нужно проверить, а затем зафиксировать момент сразу после выполнения этого участка. Разница этих двух переменных будет составлять время выполнения нужного нам участка кода.
Теперь приведу полную реализацию первого наивного решения вместе со временем выполнения:
Первое рабочее решение программы. Выдает верный ответ, но медленно работает на больших файлов. Наш файл состоит из 5000 элементов.
Первое рабочее решение программы. Выдает верный ответ, но медленно работает на больших файлов. Наш файл состоит из 5000 элементов.
Время выполнения такого решения получается 62 минуты 49 секунд. В общем, нужна большая уверенность в правильности программы, чтобы дождаться до её завершения. Мне это было интересно, поэтому я просто поставил на выполнение и пошел пить чай :) Но я понимаю, что на реальном экзамене человек не может позволить себе ждать так долго результат.
Что делать, чтобы ускорить ?
Вот тут начинаются мысли об оптимизации. Что ж, с методом подбора пар мы не сделаем ничего. Здесь придется оставить полный перебор. Но вот можно ли сделать что-то с поиском числа в массиве? Да, на самом деле можно. Мы можем подготовить наши данные для того, чтобы использовать бинарный поиск (иногда называют двоичный поиск).
К сожалению, практика работы с учениками, показала, что во многих школах, даже в физ-мат лицеях, учителя информатики ничего не рассказывают про двоичный поиск, хотя в таких вот задачах ЕГЭ он может понадобиться.
Чтобы использовать этот поиск, нужно отсортировать данные. Я предлагаю отсортировать по возрастанию, хотя сути алгоритма это не меняет. Мы всё равно не будем выводить отсортированный массив из 5000 элементов.
Бинарный поиск (двоичный поиск) – алгоритм поиска в упорядоченном множестве чисел, использующий метод деления области поиска пополам и имеющий логарифмическую сложность. Здесь логарифмическая сложность является той оптимизацией, которая нам поможет ускорить программу.
Для начала попробуем самый простой метод пузырьковой сортировки. Сразу же посмотрим сколько времени он занимает на N = 5000. Для этого напишу отдельную программу, где будет только сортировка для рандомно генерирующегося массива:
Сортировка 5000 элементов занимает 11 секунд. Несколько запусков программы показывают одно и то же число. То есть сортировка не является узким местом будущей оптимизации. Я имею в виду, что дополнительные 11 секунд можно подождать по сравнению 62 минутами.
Бинарный поиск для массива можно реализовать следующим образом:
Теперь давайте объединим всё это в программу и посмотрим что нам даст такая оптимизация:
После данной оптимизации мы имеем время выполнения программы: 7 минут 29 секунд. Из которых 11 секунд уходит на сортировку массива
Такие преобразования ускоряют наш код примерно в 9 раз.
Стоит ли переписывать функцию сортировки? На мой взгляд, это не имеет смысла делать на ЕГЭ. Да, быстрая сортировка будет работать быстрее. Но в силу более сложного алгоритма, который вдобавок ко всему связан с рекурсией, вы можете допустить там ошибку и потерять время на её исправление. Допустим сортировка стала быстрее и выполняется 1-2 секунды. Вы всё равно будете ждать 7 минут, потому что основной код перебора всех пар уже никак не оптимизировать, потому что мы не знаем заранее где в файле находятся четные пары.
Вот такая вот интересная задача, время которой очень сильно зависит от выбора способа решения. То есть на больших файлах можно использовать именно этот способ: сначала сортируем, потом ищем бинарным поиском.
Понравился разбор задачи? Проявите активность: лайк, репост, комментарий.
Если Вам нужен репетитор по физике, математике или информатике/программированию, Вы можете написать мне или в мою группу Репетитор IT mentor в VK
Читайте также: