Презентация на тему: Автономное образовательное учреждение Вологодской области дополнительного

Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
Автономное образовательное учреждение Вологодской области дополнительного
1/33
Средняя оценка: 4.0/5 (всего оценок: 61)
Код скопирован в буфер обмена
Скачать (1311 Кб)
1

Первый слайд презентации

Автономное образовательное учреждение Вологодской области дополнительного профессионального образования « Вологодский институт развития образования » Вологда 2021 год Е.М. Ганичева, методист ЦПКНППМ педагогов АОУ ВО ДПО «ВИРО», к.п.н. Совершенствование качества подготовки обучающихся к государственной итоговой аттестации (ЕГЭ) по информатике и ИКТ

Изображение слайда
2

Слайд 2

Задание №27. Обработка данных, вводимых из файла в виде последовательности чисел Согласно спецификации контрольно-измерительных материалов для проведения в 2021 году единого государственного экзамена по информатике и ИКТ задание №27 проверяет умение создавать собственные программы (20–40 строк) для анализа числовых последовательностей. Коды проверяемых элементов содержания (по кодификатору): 1.6.3. Построение алгоритмов и практические вычисления. Коды проверяемых требований к уровню подготовки (по кодификатору): 1.1.3. Строить информационные модели объектов, систем и процессов. в виде алгоритмов. Задание относится к высокому уровню сложности, требует для решения специальное программное обеспечение и рассчитано на 35 минут.

Изображение слайда
3

Слайд 3

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

Изображение слайда
4

Слайд 4

Многие задачи практического программирования являются задачами на перебор вариантов и выбор среди этих вариантов допустимого или наилучшего по тому или иному критерию. Однако рассмотреть все варианты, в силу чрезвычайно большого их количества, зачастую не представляется возможным. Для ряда задач, сходных по формулировке с проблемами, действительно требующими полного перебора вариантов, можно найти гораздо более эффективное решение. Чаще всего в таких случаях решение сводится к нахождению решений подзадач меньшей размерности, которые запоминаются в таблице и никогда более не пересчитываются, а подзадачи большей размерности используют эти уже найденные решения. Такой метод называется динамическим программированием. В общей же форме под динамическим программированием понимают процесс пошагового решения задачи оптимизации, при котором на каждом шаге из множества допустимых решений выбирается одно, которое оптимизирует заданную целевую или критериальную функцию. Как правило, связь задач и подзадач формулируется в виде некоторого “ принципа оптимальности ” и выражается системой уравнений ( рекуррентных соотношений ). Метод динамического программирования

Изображение слайда
5

Слайд 5

Термин « динамическое программирование » ввел в науку американский математик Ричард Беллман. Динамическое программирование — это способ решения сложных задач путем сведения их к более простым задачам того же типа. Ричард Беллман применил такой подход при решении сложных многошаговых задач оптимизации. Его идея состояла в том, что оптимальная последовательность шагов оптимальна на любом участке. Например, пусть нужно перейти из пункта А в пункт Е через один из пунктов В, С или D (числами обозначена "стоимость" маршрута): Пусть уже известны оптимальные маршруты из пунктов В, С и D в пункт Е (они обозначены сплошными линиями) и их "стоимость". Тогда для нахождения оптимального маршрута из А в Е нужно выбрать вариант, который даст минимальную стоимость по сумме двух шагов. В данном случае это маршрут А-В-Е, стоимость которого равна 25. Как видим, такие задачи решаются "с конца».

Изображение слайда
6

Слайд 6

В компьютерных науках динамическим программированием называют решение исходной задачи на основе известных решений задач того же типа, но меньшего размера. Под размером задачи понимают число N или набор чисел, которые определяют размер исходных данных. Для использования метода динамического программирования необходимо, чтобы: решение задачи имело вложенную структуру, т.е. задача размера N могла быть легко решена при известных решениях задач меньшего размера (от 1 до N-1). решения всех задач меньшего размера, необходимых для построения решения задачи размера N, сохранялись в памяти.

Изображение слайда
7

Слайд 7

Простые задачи Задача 1. С клавиатуры вводится последовательность чисел. Требуется вывести одно число – сумму всех элементов последовательности. Обозначим сумму первых k элементов последовательности через S k. Тогда рекуррентная формула, выражающая S k через предыдущие значения, имеет вид: S k = S k-1 +x, где х – очередное число, прочитанное из входного потока.

Изображение слайда
8

Слайд 8

Простые задачи Задача 2. С клавиатуры вводится последовательность чисел. Требуется вывести одно число – количество всех отрицательных элементов последовательности. Обозначим через Q k количество отрицательных значений среди первых k элементов последовательности.. Тогда рекуррентная формула, выражающая Q k через предыдущие значения, имеет вид:, где х – очередное число, прочитанное из входного потока.

Изображение слайда
9

Слайд 9

Задача 3. С клавиатуры вводится последовательность чисел. Требуется вывести одно вещественное число – среднее арифметическое всех отрицательных элементов последовательности. Обозначим через A k среднее арифметическое всех отрицательных элементов среди первых k элементов последовательности. Пусть - сумма и количество отрицательных элементов среди первых k элементов последовательности. Тогда по определению: Теперь нужно вывести формулу, которая связывает среднее арифметическое с предыдущими значениями этой величины. Предположим, что мы прочитали из входного потока значение х <0. Тогда = Простые задачи

Изображение слайда
10

Слайд 10

В КИМ ЕГЭ по информатике последних лет часто встречаются задачи, в которых необходимо работать с парами чисел, обладающими определенными свойствами. Предполагается, что N>=2 и все числа входной последовательности – целые и положительные. Пары, отличающиеся только порядком перечисления элементов, считаются одинаковыми. Задачи на пары чисел

Изображение слайда
11

Слайд 11

Задача 4. Требуется вывести одно неотрицательное число – количество пар с чётной суммой, образованных различными элементами последовательности. В данной задаче очередное число, прочитанное из входного потока, может образовывать пары с любым из предыдущих элементов последовательности. Будем говорить, что все предыдущие элементы принадлежат множеству выбора пары для следующего элемента. Подходящими будем называть пары, которые удовлетворяют условиям задачи. Задачи на пары чисел

Изображение слайда
12

Слайд 12

Задача 4. Решение: Обозначим через количество подходящих пар для подпоследовательности, состоящей из первых k элементов полной последовательности. Если очередное полученное число х чётно, оно образует подходящие пары (с чётной суммой) только с предыдущими чётными элементами последовательности, а если х нечётно, то оно образует подходящие пары только с предыдущими нечётными элементами. Поэтому для использования метода динамического программирования нужно хранить на каждой итерации количество предыдущих чётных чисел и количество предыдущих нечётных чисел. Задачи на пары чисел

Изображение слайда
13

Слайд 13

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

Изображение слайда
14

Слайд 14

Поскольку для вычисления, и используются только предыдущие элементы последовательностей, и, массивы здесь не требуются и можно обойтись тремя переменными. В блоке инициализации присваиваем им нулевые значения. После ввода очередного значения х из входного потока нужно обновить Q, а затем обновить E или O – в зависимости от чётности х. Так как любое число обязательно либо чётное, либо нечётное и на каждой итерации известно общее количество предыдущих элементов последовательности – оно хранится в переменной k, в программе можно заменить переменную О на k-E.

Изображение слайда
15

Слайд 15

Program P4; var N, i, x, q,e,o : integer; begin Readln ( N ); q:=0; e:=0; o:=0; for i:=1 to N do begin Readln ( x ); if x mod 2 = 0 then begin q := q+e ; e:=e+1; end else begin q:=q+o; o:=o+1; end ; end ; Writeln ( q ); end.

Изображение слайда
16

Слайд 16

Задача 5. Требуется вывести одно неотрицательное число – количество пар с суммой, равной S=20, образованных различными элементами последовательности. Задачи на пары чисел

Изображение слайда
17

Слайд 17

Применим общий подход: получив из входного потока новое значение х, определим, сколько подходящих пар оно может образовывать с предыдущими элементами последовательности. Обозначим через количество подходящих пар в последовательности, состоящей из первых k чисел полной последовательности. По условию все элементы последовательности целые и положительные. Поэтому числа, большие или равные S, не могут образовать ни одной подходящей пары. Если число х меньше S, оно образует подходящие пары со всеми предыдущими элементами, равными S-x. Следовательно, нужно хранить массив значений D, где D[ i ] – это количество предыдущих элементов последовательности, равных i ( 1<= i <= S ). Например, после обработки последовательности 1, 2, 3, 4, 1, 2, 3, 1, 2, 1, 1 массив D имеет вид: В этой последовательности пять раз встретилось число 1, три раза – число 2, два раза – число 3 и один раз – число 4. На этапе инициализации значение переменной Q и все элементы массива D обнуляются. Они обновляются на очередном шаге цикла только тогда, когда из входного потока получено число х, которое меньше S. Задачи на пары чисел i 0 1 2 3 4 … S-3 S-2 S-1 D[ i ] 0 5 3 2 1 0 0

Изображение слайда
18

Слайд 18

Кроме того, надо хранить в памяти массив D: D[x]:=D[x]+1

Изображение слайда
19

Слайд 19

Program P5; var N, i, x, s,q : integer; d : array [1..10000] of integer; begin Readln ( N ); s:=20; for i:=1 to N do d[ i ]:=0; q:=0; for i:=1 to N do begin Readln ( x ); if x < s then begin q := q+d [s-x]; d[x]:=d[x]+1; end ; end ; Writeln ( q ); end.

Изображение слайда
20

Слайд 20

Задача 6. Требуется вывести одно неотрицательное число – количество пар с суммой, меньшей или равной S=20, образованных различными элементами последовательности. Задачи на пары чисел

Изображение слайда
21

Слайд 21

В отличие от задачи 5, в этой задаче подходящими считаются пары с суммой, не только равной, но и меньшей, чем S. Поэтому число х <S, полученное из входного потока на очередной итерации, образует пары со всеми предыдущими числами в диапазоне [ 1, S-x]. Следовательно, в программе потребуется суммирование элементов массива D от D[ 1 ] до D[S-x] включительно. Задачи на пары чисел i 0 1 2 3 4 … S-3 S-2 S-1 D[ i ] 0 5 3 2 1 0 0

Изображение слайда
22

Слайд 22

Program P6; var N, i, k, x, s,q : integer; d : array [1..10000] of integer; begin Readln ( N ); s:=20; for i:=1 to N do d[ i ]:=0; q:=0; for i:=1 to N do begin Readln ( x ); if x < s then begin for k:=1 to s-x+1 do q := q+d [k]; d[x]:=d[x]+1; end ; end ; Writeln ( q ); end.

Изображение слайда
23

Слайд 23

Задача 7. Требуется вывести одно неотрицательное число – количество пар с суммой, большей, чем S=20, образованных различными элементами последовательности. Можно свести эту задачу к предыдущей. Действительно, если мы нашли количество Q всех пар с суммой, меньшей или равной S, то количество пар с суммой, большей S, найдем как: N∙(N – 1) / 2 – Q, где N∙(N – 1) / 2 – количество всех возможных пар. Задачи на пары чисел

Изображение слайда
24

Слайд 24

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

Изображение слайда
25

Слайд 25

Входной файл A для данной задачи имеет следующий вид: 20 5627 5841 5544 6520 1449 3580 2984 5984 6164 2583 9588 3467 1440 8636 7706 8023 6847 6023 577 1545 7361 5893 4221 5994 3118 5054 1546 4062 780 3433 6926 2390 3702 6714 2278 7180 9156 3466 2294 8733 Материалы взяты с официального сайта ФИПИ (http://doc.fipi.ru/ege/demoversii-specifikacii-kodifikatory/2021/inf-ege-2021.zip)

Изображение слайда
26

Слайд 26

Входной файл B для данной задачи имеет следующий вид (фрагмент): 60000 7722 7518 906 1474 859 1688 425 3358 2312 8232 5322 1618 4438 1697 1205 5119 2043 6171 … 4313 8124 7669 170 43 9752 Материалы взяты с официального сайта ФИПИ (http://doc.fipi.ru/ege/demoversii-specifikacii-kodifikatory/2021/inf-ege-2021.zip)

Изображение слайда
27

Слайд 27

В данной задаче мы видим, что файл B содержит 60000 пар и применить для поиска нужной суммы переборный алгоритм с предварительным сохранением всех пар в массив не представляется возможным, поэтому построим универсальный эффективный алгоритм, который подойдёт для обоих файлов. В общем виде алгоритм будет следующим: считываем число, советующее количеству пар; при считывании очередной пары чисел выполняем следующие действия: находим максимум, прибавляем его к общей сумме, находим разность между этими элементами, если она не делится 3 и минимальна среди всех просмотренных пар, то записываем значение этой разности в соответствующую переменную; проверяем сумму после просмотра всех пар, если она не делится 3, то выводим её значение, если делится на 3, то уменьшаем её значение, на величину равную минимальной разности (которая не делится на 3) между элементами одной пары и выводим полученное значение.

Изображение слайда
28

Слайд 28

6 х1 х2 1 3 5 12 6 9 5 4 3 3 1 1 1 3 5 12 1+12=13 5+3=8 3+12=15 1+5=6 1 3 5 12 6 9 1+5+6=12 1+5+9=15 1+12+6=19 1+12+9=22 3+5+6=14 3+5+9=17 3+12+6=21 3+12+9 1 3 5 13 Рекуррентная формула: S:=S+ x1, если х1 >x2, иначе S:=S+x2 Кроме того, нужно хранить минимальное значение разности элементов d=| x1-x2| и в случае, когда полученная сумма будет делиться на 3, вычесть из полученного результата минимальное значение разности элементов пары.

Изображение слайда
29

Слайд 29

Рассмотрим вариант решения данной задачи с использованием языка программирования Pascal. 1. Описываем переменные для обработки данных из файла. var n: integer; // количество пар f: text; i, a: integer; mina, maxa : integer ; //минимальный и максимальный элемент в паре sum : longint ; //максимально возможная сумма d: integer ; //минимальная разность между элементами пары, которая не делится на 3 2. Считываем данные из файла и просматриваем каждую пару. Assign( f, '27-B.txt' ); Reset( f ); Readln ( f, n ); d := 10001; sum := 0; for i := 1 to n do begin readln ( f, mina, maxa );

Изображение слайда
30

Слайд 30

3. В каждой паре определяем минимальный и максимальный элемент. if mina > maxa then begin a := mina; mina := maxa ; maxa := a; end ; 4. Находим минимальную разность между элементами одной пары, которая не делится на 3. if (( maxa - mina) mod 3 <> 0) and ( maxa - mina < d) then d := maxa - mina ; 5. Прибавляем максимальный элемент пары к общей сумме. sum := sum + maxa ; 6. Производим корректировку суммы, если она кратна 3. Выводим ответ. if sum mod 3 = 0 then sum := sum - d; Writeln ( sum );

Изображение слайда
31

Слайд 31

Полный текст программы для решения задания №27 на языке программирования Pascal (в данном примере используются только стандартные средства языка). program task27; var n: integer; // количество пар f: text; i, a: integer; mina, maxa : integer ; //минимальный и максимальный элемент в паре sum : longint ; //максимально возможная сумма d: integer ; //минимальный разность между элементами пары, которая не делится на 3

Изображение слайда
32

Слайд 32

begin Assign( f, '27-B.txt' ); Reset( f ); Readln ( f, n ); d := 10001; sum := 0; for i := 1 to n do begin readln ( f, mina, maxa ); if mina > maxa then begin a := mina; mina := maxa ; maxa := a; end ; if (( maxa - mina) mod 3 <> 0) and ( maxa - mina < d) then d := maxa - mina; sum := sum + maxa ; end ; if sum mod 3 = 0 then sum := sum - d; Writeln ( sum ); end.

Изображение слайда
33

Последний слайд презентации: Автономное образовательное учреждение Вологодской области дополнительного

Для того, чтобы обработать файл A, необходимо в строке связывания файловой переменой с именем файла указать Assign ( f, '27- A. txt ' ). Для файла A из демонстрационного варианта 2021 года данная программы выдаст ответ: 127127. Для того, чтобы обработать файл B необходимо в строке связывания файловой переменой с именем файла указать Assign ( f, '27- B. txt ' ). Для файла B из демонстрационного варианта 2021 года данная программы выдаст ответ: 399762080. За верный ответ на задания 26 и 27 ставится по 2 балла; если значения в ответе перепутаны местами или в ответе присутствует только одно верное значение (второе неверно или отсутствует) – ставится 1 балл. В остальных случаях – 0 баллов. Материалы взяты с официального сайта ФИПИ (http://doc.fipi.ru/ege/demoversii-specifikacii-kodifikatory/2021/inf-ege-2021.zip) Материалы взяты с официального сайта ФИПИ (http://doc.fipi.ru/ege/demoversii-specifikacii-kodifikatory/2021/inf-ege-2021.zip)

Изображение слайда