Подготовка ребёнка к ЕГЭ по информатике. Часть девятая

07.02.19

Разработка - Математика и алгоритмы

Последний уровень. Часть 2.

27 задание. Часть вторая

 

Предисловие

 

Вот и вторая часть по решению 27 здания. В этот раз будут рассматриваться демонстрационные варианты с 2014 по 2016 годы. Здесь будет представлена задача по нахождению контрольного значения, которая не была представлена ранее, а также две экспериментальных задачи.

 

Источник: Демонстрационный вариант ЕГЭ 2016 г. ИНФОРМАТИКА и ИКТ, 11 класс.

 

1. В физической лаборатории проводится долговременный эксперимент по изучению гравитационного поля Земли. По каналу связи каждую минуту в лабораторию передаётся положительное целое число – текущее показание прибора «Сигма 2015». Количество передаваемых чисел в серии известно и не превышает 10 000. Все числа не превышают 1000. Временем, в течение которого происходит передача, можно пренебречь. Необходимо вычислить «бета-значение» серии показаний прибора – минимальное чётное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Если получить такое произведение не удаётся, ответ считается равным –1.

 

Вам предлагается два задания, связанных с этой задачей: задание А и задание Б. Вы можете решать оба задания или одно из них по своему выбору. Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание – 0 баллов. Задание Б является усложнённым вариантом задания А, оно содержит дополнительные требования к программе.

 

А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования. ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А. Максимальная оценка за выполнение задания А – 2 балла.

 

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик). Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта.

 

Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм. ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, – 4 балла. Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, – 3 балла.

 

НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ.

 

Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно положительное целое число – очередное показание прибора.

 

Пример входных данных:

11

12

45

5

3

17

23

21

20

19

18

17

 

Программа должна вывести одно число – описанное в условии произведение либо –1, если получить такое произведение не удаётся. Пример выходных данных для приведённого выше примера входных данных: 54

 

Выбираем Б.

Отметим, что программа похожа по ходу своего решения на первую задачу из 7 части цикла статей. По аналогии создаем массив из такого количества элементов, какой требуется минимальный минут промежуток. Далее заполняем массив первыми шестью элементами последовательности. Затем для всех последующих чисел – с 1 по последнее – найдем минимальное четное и второй минимум среди оставшихся чисел, такой, что промежуток между первым и вторым минимумами не менее 6. Для соблюдения промежутка будем делать постепенный сдвиг массива.

 

program minimumevenamountoftwonumberswithintervalsixminutes;

var

a:array[1..6]of integer;

AmountOfNumbers, FirstIndex, SecondIndex, MinimumEvenMultiolyOfTwoNumbers,

InputNumber, FirstMinimumNumber, SecondMinimumNumber, temporary:integer;

begin

writeln('Введите количество чисел в последовательности = ');

readln(Amountofnumbers);

for FirstIndex := 1 to 6 do

begin

writeln('Введите число = ');

readln(a[FirstIndex]);

end;

FirstMinimumNumber := 1001;

SecondMinimumNumber := 1001;

MinimumEvenMultiolyOfTwoNumbers := FirstMinimumNumber*SecondMinimumNumber;

for FirstIndex := 7 to AmountOfNumbers do

begin

writeln('Введите число = ');

readln(InputNumber);

if a[1]<FirstMinimumNumber then

FirstMinimumNumber := a[1];

if (a[1] mod 2 = 0) and (a[1] < SecondMinimumNumber) then

SecondMinimumNumber := a[1];

if InputNumber mod 2 = 0 then

temporary := InputNumber*FirstMinimumNumber

else if SecondMinimumNumber < 1001 then

temporary := InputNumber*SecondMinimumNumber

else

temporary := 1001*1001;

if temporary < MinimumEvenMultiolyOfTwoNumbers then

MinimumEvenMultiolyOfTwoNumbers := temporary;

for SecondIndex:=1 to 5 do

a[SecondIndex]:=a[SecondIndex+1];

a[6]:=InputNumber;

end;

if MinimumEvenMultiolyOfTwoNumbers = 1001*1001 then

writeln('-1')

else

writeln(MinimumEvenMultiolyOfTwoNumbers);

end.

 

Источник: Демонстрационный вариант ЕГЭ 2015 г. ИНФОРМАТИКА и ИКТ, 11 класс.

 

2. На спутнике «Фотон» установлен прибор, предназначенный для измерения энергии космических лучей. Каждую минуту прибор передаёт по каналу связи неотрицательное вещественное число – количество энергии, полученной за последнюю минуту, измеренное в условных единицах. Временем, в течение которого происходит передача, можно пренебречь.

 

Необходимо найти в заданной серии показаний прибора минимальное произведение двух показаний, между моментами передачи которых прошло не менее 6 минут. Количество энергии, получаемое прибором за минуту, не превышает 1000 условных единиц. Общее количество показаний прибора в серии не превышает 10 000.

 

Вам предлагается два задания, связанные с этой задачей: задание А и задание Б. Вы можете решать оба задания А и Б или одно из них по своему выбору.

 

Итоговая оценка выставляется как максимальная из оценок за задания А и Б. Если решение одного из заданий не представлено, то считается, что оценка за это задание составляет 0 баллов. Задание Б является усложненным вариантом задания А, оно содержит дополнительные требования к программе.

 

А. Напишите на любом языке программирования программу для решения поставленной задачи, в которой входные данные будут запоминаться в массиве, после чего будут проверены все возможные пары элементов. Перед программой укажите версию языка программирования. ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ А. Максимальная оценка за выполнение задания А равна 2 баллам.

 

Б. Напишите программу для решения поставленной задачи, которая будет эффективна как по времени, так и по памяти (или хотя бы по одной из этих характеристик).

 

Программа считается эффективной по времени, если время работы программы пропорционально количеству полученных показаний прибора N, т.е. при увеличении N в k раз время работы программы должно увеличиваться не более чем в k раз. Программа считается эффективной по памяти, если размер памяти, использованной в программе для хранения данных, не зависит от числа N и не превышает 1 килобайта. Перед программой укажите версию языка программирования и кратко опишите использованный алгоритм.

 

ОБЯЗАТЕЛЬНО укажите, что программа является решением ЗАДАНИЯ Б. Максимальная оценка за правильную программу, эффективную по времени и по памяти, равна 4 баллам.

 

Максимальная оценка за правильную программу, эффективную по времени, но неэффективную по памяти, равна 3 баллам. НАПОМИНАЕМ! Не забудьте указать, к какому заданию относится каждая из представленных Вами программ. Входные данные представлены следующим образом. В первой строке задаётся число N – общее количество показаний прибора. Гарантируется, что N > 6. В каждой из следующих N строк задаётся одно неотрицательное вещественное число – очередное показание прибора.

 

Пример входных данных:

11

12

45.3

5.5

4

25

23

21

20

10

12

26

 

Программа должна вывести одно число – описанное в условии произведение.

 

Пример выходных данных для приведённого выше примера входных данных: 48

Выбираем Б.

Отметим, что программа похожа по ходу своего решения на первую задачу из этой статьи. По аналогии создаем массив из такого количества элементов, какой требуется минимальный минут промежуток. Далее заполняем массив первыми шестью элементами последовательности. Затем для всех последующих чисел – с 1 по последнее – найдем минимальное и второй минимум среди оставшихся чисел, такой, что промежуток между первым и вторым минимумами не менее 6. Для соблюдения промежутка будем делать постепенный сдвиг массива.

 

program minimumamountoftwonumberswithintervalsixminutes;

var

a:array[1..6]of real;

MinimumMultiplyOfTwoNumbers,InputNumber, MinimumNumber:real;

AmountOfNumbers, FirstIndex, SecondIndex:integer;

begin

writeln('Введите количество чисел в последовательности = ');

readln(Amountofnumbers);

for FirstIndex := 1 to 6 do

begin

writeln('Введите число = ');

readln(a[FirstIndex]);

end;

MinimumNumber := 1001;

MinimumMultiplyOfTwoNumbers := MinimumNumber*MinimumNumber;

for FirstIndex := 7 to AmountOfNumbers do

begin

writeln('Введите число = ');

if a[1] < MinimumNumber then

MinimumNumber := a[1];

readln(InputNumber);

if InputNumber < MinimumNumber then

MinimumNumber := InputNumber;

if InputNumber*MinimumNumber < MinimumMultiplyOfTwoNumbers then

MinimumMultiplyOfTwoNumbers := InputNumber*MinimumNumber;

for SecondIndex:=1 to 5 do

a[SecondIndex]:=a[SecondIndex+1];

a[6] := InputNumber;

end;

writeln(MinimumMultiplyOfTwoNumbers);

end.

 

Источник: Демонстрационный вариант ЕГЭ 2014 г. ИНФОРМАТИКА и ИКТ, 11 класс.

 

3. По каналу связи передаётся последовательность положительных целых чисел, все числа не превышают 1000. Количество чисел известно, но может быть очень велико. Затем передаётся контрольное значение последовательности – наибольшее число R, удовлетворяющее следующим условиям:

 

1) R – произведение двух различных переданных элементов последовательности («различные» означает, что не рассматриваются квадраты переданных чисел; допускаются произведения различных элементов последовательности, равных по величине);

 

2) R делится на 21.

 

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

 

Напишите эффективную, в том числе по используемой памяти, программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет проверять правильность контрольного значения.

 

Программа должна напечатать отчёт по следующей форме: Вычисленное контрольное значение: … Контроль пройден (или – Контроль не пройден)

 

Перед текстом программы кратко опишите используемый Вами алгоритм решения. На вход программе в первой строке подаётся количество чисел N. В каждой из последующих N строк записано одно натуральное число, не превышающее 1000. В последней строке записано контрольное значение.

 

Пример входных данных:

6

70

21

997

7

9

300

21000

 

Пример выходных данных для приведённого выше примера входных данных: Вычисленное контрольное значение: 21000

Контроль пройден.

 

Будем находить максимальное число, кратное 7, максимальное число, кратное 3, максимальное число, кратное 21 и просто максимальное число, не кратное 21 (всего 4 числа). Запрашиваем контрольное значение. Если оно равно произведению максимального числа кратного 3 на максимальное число кратное 7, или  произведению максимального числа кратного 3 на максимальное число кратное 21, или  произведению максимального числа кратного 7 на максимальное число кратное 21, или  произведению максимального числа не кратного 21 на максимальное число кратное 21, то контроль пройден. Иначенет.

 

program referencevalue;

var

amountofnumbers, InputNumber, Index, MaxInputNumbermod7, MaxInputNumbermod3,

MaxInputNumbernotmod21,MaxInputNumbermod21, Referencevalueend:integer;

begin

MaxInputNumbermod7 := 0;

MaxInputNumbermod3 := 0;

MaxInputNumbermod21 := 0;

MaxInputNumbernotmod21 := 0;

writeln('Введите количество чисел в последовательности = ');

readln(amountofnumbers);

for Index:=1 to amountofnumbers do

begin

writeln('Введите число = ');

readln(InputNumber);

if (InputNumber mod 7 = 0) and (InputNumber mod 3 <> 0) and (InputNumber> MaxInputNumbermod7) then

MaxInputNumbermod7 := InputNumber;

 

if (InputNumber mod 7 <> 0) and (InputNumber mod 3 = 0) and (InputNumber> MaxInputNumbermod3) then

MaxInputNumbermod3 := InputNumber;

 

if (InputNumber mod 7 = 0) and (InputNumber mod 3 = 0and (InputNumber> MaxInputNumbermod21)then

MaxInputNumbermod21 := InputNumber;

 

if (InputNumber mod 7 <> 0) and (InputNumber mod 3 <> 0and (InputNumber> MaxInputNumbernotmod21)then

MaxInputNumbernotmod21 := InputNumber;

 

end;

writeln('Введите контрольное значение = ');

readln(referencevalueend);

if referencevalueend mod 21 = 0 then

if (referencevalueend = MaxInputNumbermod7*MaxInputNumbermod3) or

(referencevalueend = MaxInputNumbermod21*MaxInputNumbermod3) or

(referencevalueend = MaxInputNumbermod21*MaxInputNumbermod7) or

(referencevalueend = MaxInputNumbernotmod21*MaxInputNumbermod21) then

writeln('Контроль пройден = ', referencevalueend)

else

writeln('Контроль не пройден')

else

writeln('Контроль не пройден');

end.

 

Вывод

 

Таким образом, наибольшую трудность представляют задачи, в которых определено наименьшее расстояние между значениями последовательности (первая и вторая задачи из представленных). К сожалению, не удалось рассмотреть все. Будет третья часть по теме.

См. также

Метод Дугласа-Пойкера для эффективного хранения метрик

Математика и алгоритмы Платформа 1C v8.2 Конфигурации 1cv8 Россия Абонемент ($m)

На написание данной работы меня вдохновила работа @glassman «Переход на ClickHouse для анализа метрик». Автор анализирует большой объем данных, много миллионов строк, и убедительно доказывает, что ClickHouse справляется лучше PostgreSQL. Я же покажу как можно сократить объем данных в 49.9 раз при этом: 1. Сохранить значения локальных экстремумов 2. Отклонения от реальных значений имеют наперед заданную допустимую погрешность.

1 стартмани

30.01.2024    1757    stopa85    12    

33

Алгоритм симплекс-метода для решения задачи раскроя

Математика и алгоритмы Бесплатно (free)

Разработка алгоритма, построенного на модели симплекс-метода, для нахождения оптимального раскроя.

19.10.2023    4431    user1959478    50    

34

Регулярные выражения на 1С

Математика и алгоритмы Инструментарий разработчика Платформа 1С v8.3 Мобильная платформа Россия Абонемент ($m)

Что ж... лучше поздно, чем никогда. Подсистема 1С для работы с регулярными выражениями: разбор выражения, проверка на соответствие шаблону, поиск вхождений в тексте.

1 стартмани

09.06.2023    7469    4    SpaceOfMyHead    17    

56

Модель распределения суммы по базе

Математика и алгоритмы Платформа 1С v8.3 Россия Абонемент ($m)

Обычно под распределением понимают определение сумм пропорционально коэффициентам. Предлагаю включить сюда также распределение по порядку (FIFO, LIFO) и повысить уровень размерности до 2-х. 1-ое означает, что распределение может быть не только пропорциональным, но и по порядку, а 2-ое - это вариант реализации матричного распределения: по строкам и столбцам. Возможно вас заинтересует также необычное решение этой задачи через создание DSL на базе реализации текучего интерфейса

1 стартмани

21.03.2022    7856    7    kalyaka    11    

44

Изменения формата файлов конфигурации (CF) в 8.3.16

Математика и алгоритмы Платформа 1С v8.3 Бесплатно (free)

Дополнение по формату файлов конфигурации (*.cf) в версии 8.3.16.

16.12.2021    4448    fishca    13    

36

Интересная задача на Yandex cup 2021

Математика и алгоритмы Бесплатно (free)

Мое решение задачи на Yandex cup 2021 (frontend). Лабиринт. JavaScript.

12.10.2021    8846    John_d    73    

46

Механизм анализа данных. Кластеризация.

Математика и алгоритмы Анализ учета Платформа 1С v8.3 Анализ и прогнозирование Бесплатно (free)

Подробный разбор, с примером использования, встроенного механизма кластеризации 1С.

31.08.2021    7814    dusha0020    8    

70
Комментарии
В избранное Подписаться на ответы Сортировка: Древо развёрнутое
Свернуть все
1. vipetrov2 08.02.19 06:03 Сейчас в теме
Еще раз убедился в деградации системы образования и в заданиях ЕГЭ. Здесь больше усилий прилагаешь для понимания той мысли, которую автор задания вложил в текст. А сложность задания очень низкая, решается 1 циклом, множества разных творческих решений нет.
Недавно смотрел рабочие тетради для обучения чтению. Там столько всякого лишнего понаписано, как будто ребенок читать умеет, у него глаза разбегаются и он вообще ни чего не понимает. А матерей спрашиваешь, как они учили детей и выясняется, что они дома сами учили по советским букварям, где на странице одна большая буква для изучения, 2-5 слогов с этой буквой, также пару слов на эту букву и главное картинки предметов на эту букву и все. Ни чего лишнего.
pm74; wowik; +2 Ответить
Оставьте свое сообщение