Обзор заданий ЕГЭ на языке PascalABC.Net

• 1 слайд

  Использование PascalABC.NET на ЕГЭ.
  ОБЗОР заданий: 16, 17, 24, 25, 26, 27
  ЛяминаИ.В.
  
  

• 2 слайд

  Использование PascalABC.NET на ЕГЭ
  КИМ ЕГЭ-2022 содержат 27 заданий, 17 из которых рекомендовано решать аналитически (и получить за них до 17 первичных баллов), и 10 - с использованием компьютера (за них можно получить до 12 первичных баллов). Рекомендуемое распределение времени предполагает потратить 83 минуты на аналитическое решение заданий и 152 минуты работать с компьютером.
  

• 3 слайд

  Для решения на компьютере
  №3 – база данных (электронная таблица, базовый уровень, 1 балл, 3 мин, прилагаются файлы);
  №9 – электронная таблица (базовый уровень, 1 балл, 6 мин, прилагаются файлы);
  №10 – текстовый процессор (базовый уровень, 1 балл, 3 мин, прилагаются файлы);
  №16 – рекурсивная функция (продвинутый уровень, 1 балл, 5 мин);
  №17 – обработка числовой последовательности (продвинутый уровень, 1 балл, 14 мин, прилагаются файлы);
  №18 – электронная таблица (блуждание робота, продвинутый уровень, 1 балл 8 мин, прилагаются файлы);
  №24 – поиск цепочки в текстовом файле (высокий уровень, 1 балл, 18 мин, прилагаются файлы);
  №25 – поиск чисел по набору натуральных делителей (высокий уровень, 1 балл, 20 мин);
  №26 – оптимизационная задача с сортировкой (высокий уровень, 2 балла, 35 мин, прилагаются файлы);
  №27 – подбор пар (троек) чисел из файла (высокий уровень, 2 балла, 40 мин, прилагаются файлы).
  

• 4 слайд

  Использование PascalABC.NET на ЕГЭ
  
  Целесообразно решать путем программирования в среде PascalАВС.NЕТ,
  а именно, задания с номерами
  16, 17, 24, 25, 26, 27
  

• 5 слайд

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

• 6 слайд

  Задание 16
  (№ 4970) Алгоритм вычисления значения функции F(n)F(n), где n – целое неотрицательное число, задан следующими соотношениями:
  F(0) = 8 F(n) = 5 + F(n / 3) если n > 0 и n делится на 3 F(n) = F(n // 3) в остальных случаях Здесь // означает деление нацело. Определите количество значений n на отрезке [1, 100 000 000], для которых F(n) = 18.
  
  

• 7 слайд

  Задание 16
  (№ 4970) Алгоритм вычисления значения функции F(n)F(n), где n – целое неотрицательное число, задан следующими соотношениями:
  F(0) = 8 F(n) = 5 + F(n / 3) если n > 0 и n делится на 3 F(n) = F(n // 3) в остальных случаях Здесь // означает деление нацело. Определите количество значений n на отрезке [1, 100 000 000], для которых F(n) = 18.
  
  

• 8 слайд

  ЗАДАНИЕ 16
  Если у вас установлена новая версия компилятора, можно использовать условное выражение в формате языка С
  

• 9 слайд

  ЗАДАНИЕ 16
  Pаботать программа может от 20-25 секунд до нескольких минут - в зависимости от мощности компьютера.
  Это плата за рекурсию при большом количестве вычислений.
  
  Но, может быть, вы что-то слышали про мемоизацию (кэширование значений)? Она появилась в компиляторе, начиная с версии 3.8.1. Указываем перед описанием рекурсивной функции атрибут [Cache] - и никаких забот! Увы, не в этот раз. Здесь такой объем вычислений, что кэш переполняется и программа завершается аварийно.
  

• 10 слайд

  ЗАДАНИЕ 17
  (№ 4704) (А. Кабанов) В файле 17-257.txt содержится последовательность целых чисел. Элементы последовательности могут принимать целые положительные значения до 10 000 включительно. Необходимо найти количество кратных 11 и количество кратных 17 элементов последовательности. Если количество кратных 11 больше, чем количество кратных 17, то программа должна вывести количество кратных 11, а также минимальный из них. В противном случае программа должна вывести количество кратных 17, а также максимальный из них.
  
  

• 11 слайд

  ЗАДАНИЕ 17
  Решение с элементами функционального программирования:
  

• 12 слайд

  ЗАДАНИЕ 17
  Решение в парадигме структурного программирования:
  

• 13 слайд

  ЗАДАНИЕ 24
  Что приятно в задании №24 - оно предназначено для выполнения на компьютере и на решение регламент ФИПИ отводит аж 18 минут!
  Первое и главное, что нужно помнить: задачи с анализом символов и построенных из них последовательностей (цепочек) весьма коварны. И дело тут вовсе не происках составителей этих задач, а в терминологии. Из-за нее тексты задач нужно читать крайне внимательно и, возможно, что-то себе схематически прорисовывать.
  

• 14 слайд

  ЗАДАНИЕ 24
  строка - произвольная последовательность символов;
  строчка - строка или ее часть, состоящая из символов, выстроенных в одну линию;
  цепочка (подстрока) - любая часть строки, обладающая некоторыми свойствами.
  Получается, что строка может быть разбита на строчки? Да, с этой целью в строку вводятся специальные символы не имеющие начертания (служебные или "неотображаемые" символы). Этим символам соответствуют некоторые действия, например, переход к новой строчке. PascalАВС.NЕТ умеет читать строку и целиком, и по строчкам, и по отдельным символам. Тут уж ваш выбор.
  
  

• 15 слайд

  ЗАДАНИЕ 24
  Строка может быть задана словесным описанием. Например: "80 символов А и 60 символов Б, перемешанных произвольным образом". Если из условия задачи следует, что перемешивание является обязательным - используйте процедуру Shuffle.
  

• 16 слайд

  ЗАДАНИЕ 24
  Имеются способу преобразования
  

• 17 слайд

  ЗАДАНИЕ 24
  (№ 2506) В текстовом файле k7.txt находится цепочка из символов латинского алфавита A, B, C длиной не более 106 символов. Найдите длину самой длинной подцепочки, состоящей из символов C.
  
  

• 18 слайд

  ЗАДАНИЕ 24
  Но если вспомнить, что у нас не примитивный Паскаль полувековой давности, а современный, задача решается в одну строчку. И здесь нас выручат регулярные выражения.  Расширение строки .MatchValues вернет последовательность подстрок, удовлетворяющих указанному в качестве аргумента регулярному выражению, а спроецировать элементы последовательности в их длины и найти максимальную - вообще не проблема.
  Регулярное выражение тут простейшее. С+ - символ "С", встречающийся один или более раз подряд.
  
  

• 19 слайд

  ЗАДАНИЕ 24
  А как решать тем, кто не дружит с регулярными выражениями? Их код будет несколько длиннее:.
  

• 20 слайд

  ЗАДАНИЕ 25
  На задание №25 регламент ФИПИ отводит 20 минут. Это очень много. Ну что же, отличный резерв времени для решения более серьезных заданий.
  Типовые задачи этой тематики:
  на некотором отрезке найти целые числа, у которых делители обладают заданными свойствами;
  на некотором целочисленном отрезке найти делители чисел, обладающих заданными свойствами;
  найти минимальное (максимальное) натуральное число, у которого делители обладают заданными свойствами;
  найти несколько самых маленьких (самых больших) натуральных чисел, у которых делители обладают заданными свойствами.
  
  

• 21 слайд

  ЗАДАНИЕ 25
  В любом случае требуется находить все (либо все нетривиальные) делители целого числа. Если вам доступна библиотека School (в версии компилятора не ниже 3.7.1.2677 от 05.09.2020), функция Divisors(n) для n типа integer возвращает список типа List<integer> всех делителей этого числа. То же самое делает расширение n.Divisors.
  

• 22 слайд

  ЗАДАНИЕ 25
  (№ 2562) (Демовариант 2021 г.). Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания.
  

• 23 слайд

  ЗАДАНИЕ 25
  Это решение в функциональном стиле:
  

• 24 слайд

  ЗАДАНИЕ 25
  Эта же решение в парадигме структурного программирования:
  

• 25 слайд

  ЗАДАНИЕ 26
  Задание №26 ФИПИ относит к оптимизационным задачам высокой сложности, отводит на решение 35 минут и оценивает его в один или два балла. Дело в том, что к заданию идут два файла данных.  Первый файл (А) небольшой и считается, что его данные можно обработать обычным перебором, получив один балл за решение. Второй файл (В) значительно большего размера и по замыслу авторов задания, переборным методом его не обработать. Предполагается, что если найти решение, будет добавлен второй балл.
  

• 26 слайд

  ЗАДАНИЕ 26
  Полезно помнить, что даже файл В
  без малейших проблем за доли секунды можно целиком считать в оперативную память. Поэтому нет никакой необходимости без нужды читать данные посимвольно или по одному числу.
  

• 27 слайд

  ЗАДАНИЕ 26
  Полезно помнить, что даже файл В без малейших проблем за доли секунды можно целиком считать в оперативную память. Поэтому нет никакой необходимости без нужды читать данные посимвольно или по одному числу.
  

• 28 слайд

  ЗАДАНИЕ 26
  (№ 2638) (А.М. Кабанов) В магазине электроники раз в месяц проводится распродажа. Из всех товаров выбирают K товаров с самой большой ценой и делают на них скидку в 20%. По заданной информации о цене каждого из товаров и количестве товаров, на которые будет скидка, определите цену самого дорогого товара, не участвующего в распродаже, а также целую часть от суммы всех скидок.
  Входные и выходные данные. В первой строке входного файла 26-k1.txt находятся два числа, записанные через пробел: N – общее количество цен (натуральное число, не превышающее 10 000) и K – количество товаров со скидкой. В следующих N строках находятся значения цены каждого из товаров (все числа натуральные, не превышающие 10 000), каждое в отдельной строке. Запишите в ответе два числа: сначала цену самого дорогого товара, не участвующего в распродаже, а затем целую часть от суммы всех скидок.
  Пример входного файла:
  10 3
  1800 3600 3700 800 2600 2500 1800 1500 1900 1200 При таких исходных данных ответ должен содержать два числа – 2500 и 1980. Пояснение: скидка будет на товары стоимостью 3700, 3600, 2600. Тогда самый дорогой товар без скидки стоит 2500, а сумма скидок 740+720+520 = 1980.
  
  

• 29 слайд

  ЗАДАНИЕ 26
  Из условия задачи следует, что второе число - количество строк с данными. Оно равно 1000. В полученном массиве 1002 значения, вычитаем два из первой служебной строки, получается 1000. Все правильно прочиталось. Запомним эти служебные значения и уберем их из массива данных, например, срезом [2:].
  

• 30 слайд

  ЗАДАНИЕ 26
  Требуется отобрать K самых дорогих товаров и найти самый дорогой товар, не попавший в выборку. Упорядочим цены товаров по убыванию, возьмем первые К значений, а следующее, с номером K+1 - это искомая цена товара, не попавшего в распродажу.
  

• 31 слайд

  ЗАДАНИЕ 27
  В заголовке модуля использован термин "поток числовых данных. Это позволяет сделать вывод, что алгоритмы обработки в общем случае не предполагают сохранения данных в массивах или иных контейнерах и данные обрабатываются по мере поступления. Данные числовые, следовательно при обработке очередной строки с данными должны вычисляться (и, возможно, накапливаться) некоторые значения, позволяющие повторно эти данные не читать.
  

• 32 слайд

  ЗАДАНИЕ 27
  В задачах термин "пара" означает, что либо из файла данные считываются по два, либо считываются по одному и тогда пара к каждому подбирается из всех остальных данных, возможно пока еще не полученных. Из заданной пары может отбираться лишь одно значение, могут отбираться пары, у которых сумма или произведение членов обладает какими-то свойствами. Могут составляться пары с какими-то свойствами. В любом случае, уточнение необходимых свойств делается в постановке задачи.
  

• 33 слайд

  ЗАДАНИЕ 27
  Наличие двух исходных файлов данных (А и В) допускает, что для них могут использоваться различные решения. Для небольшого по объему файла А обычно удается составить переборное решение (брутфорс) или воспользоваться электронными таблицами. Файл В имеет большой объем и переборное решение удается получить крайне редко - нужно строить (или вспоминать) алгоритм, подходящий к данному случаю. Решение с файлом А принесет вам один балл, с обоими файлами - 2 балла.
  

• 34 слайд

  ЗАДАНИЕ 27
  (№ 2660) (Демовариант 2021 г.). Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была максимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – максимально возможную сумму, соответствующую условиям задачи.
  Входные данные. Даны два входных файла (27-2660a.txt и 27-2660b.txt), каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
  Пример входного файла:
  6
  1 3 5 12 6 9 5 4 3 3 1 1
  Для указанных входных данных значением искомой суммы должно быть число 32.
  В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
  
  

• 35 слайд

  ЗАДАНИЕ 27
  (№ 2661) Имеется набор данных, состоящий из пар положительных целых чисел. Необходимо выбрать из каждой пары ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 3 и при этом была минимально возможной. Гарантируется, что искомую сумму получить можно. Программа должна напечатать одно число – минимально возможную сумму, соответствующую условиям задачи.
  Входные данные. Даны два входных файла 27-2261a и 17-2261b, каждый из которых содержит в первой строке количество пар N (1 ≤ N ≤ 100000). Каждая из следующих N строк содержит два натуральных числа, не превышающих 10 000.
  Пример входного файла:
  6
  1 3 5 12 6 9 5 4 3 3 1 1
  Для указанных входных данных значением искомой суммы должно быть число 20.
  В ответе укажите два числа: сначала значение искомой суммы для файла А, затем для файла B.
  
  

• 36 слайд

  ЗАДАНИЕ 27