Элементы теории алгоритмов и программирование
материал для подготовки к егэ (гиа) по информатике и икт (11 класс)

Слайд 1

Элементы теории алгоритмов и программирование

Слайд 2

Тема : Анализ программы с циклом. Что проверяется : Знание основных конструкций языка программирования, понятия переменной, оператора присваивания. 1.7.2. Основные конструкции языка программирования. Система программирования. 1.1.4. Читать и отлаживать программы на языке программирования . Что нужно знать: основные конструкции языка программирования : объявление переменных, оператор присваивания, оператор вывода, циклы уметь выполнять ручную прокрутку программы уметь выделять переменную цикла, от изменения которой зависит количество шагов цикла уметь определять количество шагов цикла уметь определять переменную, которая выводится на экран формулу для вычисления n -ого элемента арифметической прогрессии : формулу для вычисления суммы первых n членов арифметической прогрессии : где a – i - ый элемент последовательности, d – шаг (разность) последовательности Задание 6 ( базовый уровень, время – 4 мин)

Слайд 3

Способы Решения Теоретическое Перебор с помощью программы с ручным вводом Перебор с помощью программы С помощью электронных таблиц

Слайд 4

Перебор с помощью программы с ручным вводом можно набрать программу и запускать её много раз, вводя различные значения s ввод 1 – получаем 1024; ввод 100 – получаем 1; вывод – при увеличении s значение, которое выводит программа, уменьшается двоичный поиск: берём середину отрезка [1;100], для числа 50 получаем 2, то есть искомое значение меньше 50 взяв 25, получаем 64 уменьшая вводимое значение на 1, находим, что при 21 программа выводит 64, а при 20 – уже 128 Ответ: 21.

Слайд 5

Перебор с помощью программы На каждой итерации цикла значение s увеличивается, и цикл заканчивается, когда s станет больше или равно 51 s0 := 5 0 ; // начальное значение s должно быть меньше, чем 51 while True do begin // организуем бесконечный цикл s := s0; n := 1; while s < 51 do begin s := s + 5; n := n * 2 end; if n = 64 then writeln (s0 ); // выводим его на экран в том случае, если в результате работы исходного алгоритма получилось число 64 s0 := s0 - 1 ; // уменьшаем начальное значение s0 end ; Программа будет последовательно выводить все числа, при вводе которых исходный алгоритм печатает 64, и последнее выведенное число и будет ответом к задаче Обязательно использовать новую переменную s0, поскольку переменная s изменяется в ходе работы внутреннего цикла

Слайд 6

Перебор с помощью электронных таблиц анализ программы: на каждой итерации цикла значение переменной s увеличивается на 5, а значение переменной n умножается на 2 цикл останавливается, когда значение s станет больше или равно 51 вводим начальные значения (для s пока берём любое значение, например, 1 ): вводим формулы, описывающие законы изменения переменных : протягиваем формулы вниз, пока последнее значение в столбце n не станет равно 64: в столбце А для переменной s полезно установить условное форматирование: при значениях, меньших, чем 51, ячейка выделяется красным цветом : перебором находим минимальное значение ячейки А2, при котором красная область закончится сразу над зелёной ячейкой : такая ситуация будет для значений s от 21 до 25, минимальное из них – 21 Ответ : 21.

Слайд 7

Примеры формулировок При каком ( наименьшем ) наибольшем введенном числе d после выполнения программы будет напечатано 55 ? Запишите число, которое будет напечатано в результате выполнения программы Запишите через запятую наименьшее и наибольшее значение числа d, которое нужно ввести, чтобы после выполнения программы было напечатано 153 ? Сколько различных значений числа d можно ввести, чтобы после выполнения программы было напечатано 246 ? Определите , при каком наименьшем (наибольшем) введённом значении переменной s программа выведет число 128 . Сколько существует различных значений d, оканчивающихся на 8, при вводе которых эта приведенная программа выведет число 50 ? Определите , при каком наименьшем введённом значении переменной s программа выведет число, большее 100 . Определите , при каком наименьшем положительном введённом значении переменной s программа выведет отрицательное число . Определите , при каком наименьшем положительном введённом значении переменной s программа выведет четырехзначное число . Определите , при каком наименьшем положительном введённом значении переменной s программа выведет число s без изменения его значения.

Слайд 8

#include < iostream > using namespace std ; int main() { int s,s0, n ; for (s0=800; s0>400; s0- -) { s=s0; n = 200 ; while (s / n >= 2) { s = s + 5; n = n + 5; } cout << s0 << ' ' << s << endl ; } return 0;}

Слайд 9

Задание 17 ( повышенный уровень, время – 15 мин ) Тема : Перебор целых чисел на заданном отрезке. Проверка делимости Что проверяется: Умение создавать собственные программы (20–40 строк) для обработки целочисленной информации. 1.7.2. Основные конструкции языка программирования. Система программирования. 1.1.5. Умение создавать программы на языке программирования по их описанию .

Слайд 10

Задание 17 ( повышенный уровень, время – 15 мин ) Что нужно знать : время выполнения несущественно для отрезков, заданных для перебора, поэтому можно использовать простой перебор без оптимизации общая структура цикла перебора всех целых чисел на отрезке [ a ; b ] и подсчета количества, для которых выполняется некоторое условие Python : count = 0 for n in range(a, b+1): if условие выполнено : count += 1 print( count ) Pascal : count := 0; for n:=a to b do if условие выполнено then count := count + 1; writeln (count); C ++: int count = 0; for( int n = a; n <= b; n++) if( условие выполнено ) count += 1; std :: cout << count;

Слайд 11

Задание 17 ( повышенный уровень, время – 15 мин ) проверить делимость числа n на число d можно с помощью операции взятия остатка от деления n на d : если остаток равен 0, число n делится на d нацело Python : if n % d == 0: print ("Делится") else : print ("Не делится") Pascal : if n mod d = 0 then writeln ( ' Делится ' ) else writeln ( ' Не делится ' ) C++ : if( n % d == 0 ) std :: cout << " Делится " ; else std :: cout << "Не делится";

Слайд 12

Способы решения с помощью электронных таблиц с собственной программы

Слайд 13

С помощью электронных таблиц введём начальное число в ячейку A1: заполним ряд натуральных чисел до конечного числа; на вкладке Главная выберем команду Прогрессия: введём шаг и конечное значение, заполнение по столбцам: в столбце определим логическое значение: истина, если остаток от деления числа в столбце A делится на 3: двойным щелчком по маркеру заполнения скопируем формулу на весь столбец (пока не кончатся данные в столбце A) в столбце C выведем ИСТИНА, если соответствующее значение в столбце А не делится на 7: (Б.С. Михлин ) Можно записать формулу чуть короче: =ОСТАТ(А1;7), т.к. численное значение, отличное от нуля рассматривается как ИСТИНА

Слайд 14

С помощью электронных таблиц в столбцах D, E, F аналогично выведем ИСТИНА, если соответствующее значение в столбце А не делится на 17, 19 и 27: в столбце G используем функцию ЕСЛИ; если все значения ячеек в столбцах B-F в этой строке истинны, выводим число из А1, иначе – пустую строку: ( Б.С. Михлин ) Можно написать формулу чуть короче, используя диапазон в команде И: =ЕСЛИ(И(B1:F1);A1 ;"") теперь в столбце G мы видим только те числа, которые удовлетворяют условию задачи; прокрутив таблицу вниз, узнаем, что последняя строка имеет номер 6922, поэтому находим количество и максимум для диапазона G1:G6922 в любых свободных ячейках: =СЧЁТ(G1:G6922) =МАКС(G1:G6922) (это последнее число в столбце G) Ответ : 1568 7935 ( И.В. Степанов) чтобы уменьшить таблицу в 3 раза, можно проверять только числа, кратные 3, с шагом 3; первое число на заданном отрезке, кратное 3 – это 1017 (сумма цифр делится на 3).

Слайд 15

Решение С помощью программы #include < iostream > int main() { int count = 0; int maxGood = 0; for ( int n=1016; n<=7937; n++) if( (n % 3 == 0) and (n % 7 != 0) and (n % 17 != 0) and (n % 19 != 0) and (n % 27 != 0) ) { maxGood = n; count += 1; } std :: cout << count << " " << maxGood ; } var count, n, maxGood : integer; begin count:= 0; maxGood := 0; for n:=1016 to 7937 do if (n mod 3 = 0) and (n mod 7 <> 0) and (n mod 17 <> 0) and (n mod 19 <> 0) and (n mod 27 <> 0) then begin maxGood := n; count := count + 1 end; writeln (count, ' ', maxGood ) end.

Слайд 16

#include < iostream > int main(){ int count = 0; int maxGood = 0; for ( int n=3439; n<=7410; n++) if ((n % 2 != n % 6) and ((n % 9 == 0) or (n % 10 == 0) or (n % 11 == 0) )) { maxGood = n; count += 1; } std :: cout << count << " " << maxGood ;}

Слайд 17

Возможные варианты формулировки условий запись в двоичной и шестеричной системах счисления заканчивается разными (одинаковыми) цифрами запись в двоичной системе заканчивается на 11 запись которых в пятеричной системе имеет не менее 6 цифр и заканчивается на 21 или 23 не делятся нацело на 5, 7 и 11 И запись в троичной системе счисления имеет ровно 8 цифр кратны 2, но не кратны 16 И цифра в разряде десятков не менее 4 цифра в разряде десятков принадлежит отрезку [3; 7 ] И цифра в разряде сотен отлична от 1 и 9 . количество цифр в восьмеричной и десятичной записях числа не совпадает И остаток от деления на 7 равен 1 или 5.

Слайд 18

Задание 24 ( высокий уровень, время – 18 минут ) Тема : Обработка символьных строк Что проверяется: Умение создавать собственные программы (10–20 строк) для обработки символьной информации. 1.5.2. Цепочки (конечные последовательности), деревья, списки, графы, матрицы (массивы), псевдослучайные последовательности. 1.1.3. Строить информационные модели объектов, систем и процессов в виде алгоритмов .

Слайд 19

чтение строк из файла в языке Python удобнее всего использовать такую конструкцию: with open("k7.txt", "r") as F: s = F.readline () конструкция with-as – это контекстный менеджер , в данном случае он открывает указанный файл в режиме чтения (второй аргумент « r » при вызове функции open ), записывает ссылку на него в файловую переменную F , выполняет тело блока (читает первую строку файла в переменную s ) и закрывает (освобождает) файл равносилен такому F = open (" k7 . txt ") ... # какие-то операции с файлом F . close () в языке С++ используются потоки : # include < fstream > #include using namespace std ; int main() { ifstream F("k7.txt"); string s; getline (F , s ); ... }

Слайд 20

чтение строк из файла в языке Free Pascal также можно выполнить перенаправление потока ввода, но нужно дополнительно открывать входной поток: assign( input, 'k7.txt' ); reset ( input ); { для FreePascal ! !! } readln ( s ); при работе в среде FreePascal нужно убедиться, что в параметрах компилятора включена поддержка длинных символьных строк ; на всякий случай стоит добавить в первой строке программы директиву {$H+} в языке Pascal ABC . NET можно выполнить перенаправление потока ввода: assign ( input , ' k 7. txt ' ); readln ( s ); программа будет « дума ть », что читает данные, введённые с клавиатуры (с консоли), а на самом деле эти данные будут прочитаны из файла k 7. txt Среда PascalABC НЕ ПОДДЕРЖИВАЕТ работу с длинными символьными строками , поэтому для решения задачи использовать версию PascalABC . NET , которую можно бесплатно скачать с сайта автора www . pascalabc . net .

Слайд 21

Поиск Самой длинной цепочки символов «С» cLen – длина текущей цепочки букв C maxLen – максимальная длина цепочки букв C на данный момент рассмотрим очередной символ строки; если это буква C, увеличиваем cLen на 1 и, если нужно запоминаем новую максимальную длину; если это не буква C, просто записываем с cLen ноль: maxLen = 0 cLen = 0 for c in s: # обработать текущий символ if c == 'C': cLen += 1 ещё одна буква C if cLen > maxLen : # возможно, новая максимальная длина maxLen = cLen else: cLen = 0 # цепочка букв C кончилась

Слайд 22

Поиск Самой длинной цепочки любых символов curLen – длина текущей цепочки одинаковых символов maxLen – максимальная длина цепочки одинаковых символов на данный момент c – символ, из которого строится самая длинная подцепочка в начальный момент рассмотрим один первый символ (цепочка длины 1 есть всегда!): maxLen = 1 curLen = 1 c = s[0] for i in range(1,len(s )): # в цикле, начиная со второго по счёту до конца строки, обработать пару символов s [ i -1] и s [ i ] if s[ i ] == s[i-1]: # если очередной символ s[i] такой же, как и предыдущий, то цепочка продолжается curLen += 1 # увеличиваем длину if curLen > maxLen : # если цепочка побила рекорд maxLen = curLen # запоминаем её длину... c = s [ i ] # и новый базовый символ в переменной c else : curLen = 1 # началась новая цепочка если очередной символ не совпал с предыдущим, началась новая цепочка, и её длина пока равна 1 (это значение записывается в переменную cu r Len ) проверим правильность работы алгоритма в особых случаях: если вся строка состоит из одинаковых символов, значение переменной curLen постоянно увеличивается и в конце станет равно длине символьной строки; то же значение окажется и в переменной maxLen ; если в строке нет пар одинаковых символов, переменная curLen всегда равна 1, такое же значение будет и в переменной maxLen

Слайд 23

Р-01. В текстовом файле k7.txt находится цепочка из символов латинского алфавита A , B , C . Найдите длину самой длинной подцепочки, состоящей из символов C. решение на Паскале : var maxLen , cLen , i: integer; s: string; begin assign(input, 'k7.txt'); readln (s); maxLen := 0; cLen := 0; for i:=1 to Length(s) do if s[ i ] = 'C' then begin cLen := cLen + 1; if cLen > maxLen then maxLen := cLen ; end else cLen := 0; writeln ( maxLen ); end. end . решение на Python : with open( "k7.txt", "r" ) as F: s = F.readline () maxLen , cLen = 0, 0 for c in s: if c == 'C': cLen += 1 if cLen > maxLen : maxLen = cLen else: cLen = 0 print ( maxLen )

Слайд 24

Р-01. В текстовом файле k7.txt находится цепочка из символов латинского алфавита A , B , C . Найдите длину самой длинной подцепочки, состоящей из символов C. Встроенная функция поиска подстроки: ищем строку из одного символа C, потом – из двух символов, из трёх и т.д.; в какой-то момент поиск не даст результата, значит ответ – это длина предыдущей цепочки, которая короче текущей на единицу решение на Паскале : var cc , s: string ; begin assign ( input , 'k7.txt'); readln (s); cc := 'C'; while Pos ( cc , s) > 0 do cc := cc + 'C'; writeln ( Length ( cc )-1 ); end . решение на Python : with open ( "k7.txt", "r" ) as F: s = F.readline () cc = 'C' while cc in s: cc += 'C' print ( len ( cc )-1 )

Слайд 25

Р-01. В текстовом файле k7.txt находится цепочка из символов латинского алфавита A , B , C . Найдите длину самой длинной подцепочки, состоящей из символов C. Команда Найти Встроенные текстовые функции электронных таблиц: FIND (НАЙТИ) или SEARCH (ПОИСК) и REPT (ПОВТОР) Функции НАЙТИ и ПОИСК выводят положение начала искомой подцепочки в заданной цепочке символов или сообщение #ЗНАЧ!, если подцепочка не найдена. Если поиск надо осуществлять с начала цепочки, то третий параметр функций НАЙТИ и ПОИСК можно не указывать. Функция НАЙТИ учитывает регистр символов. Функция ПОИСК не учитывает регистр символов и в ней можно использовать подстановочные символы (* и ?).

Слайд 26

Р-06. В текстовом файле k8.txt находится цепочка из символов, в которую могут входить заглавные буквы латинского алфавита A … Z и десятичные цифры. Найдите длину самой длинной подцепочки, состоящей из одинаковых символов. Для каждой цепочки максимальной длины выведите в отдельной строке сначала символ, из которого строится эта цепочка, а затем через пробел – длину этой цепочки. // язык PascalABC.NET var maxLen , curLen , i: integer; s: string ; // не имеет ограничения на длину строк; в устаревших версиях языка P ascal длина строки не может превышать 255 символов begin assign(input, 'k8.txt'); // перенаправление входного потока с консоли на файл readln (s ); maxLen := 1; curLen := 1; var c := new List; // создаем динамический массив (список), тип данных List (список) c.Add ( s[1] ); //записываем первый символ for i:=2 to Length(s) do // в цикле со второго символа до конца строки if s[ i ] = s[i-1] then begin // если текущий и предыдущий символы одинаковы curLen := curLen + 1 ; // увеличиваем длину подстроки if curLen = maxLen then begin // если нашли новую (не первую) цепочку максимальной длины, добавляем новый символ в список: c.Add ( s[ i ] ); end else if curLen > maxLen then begin // если нашли новую самую длинную цепочку с длиной большей , чем все предыдущие, очищаем список и добавляем в него новый символ. maxLen := curLen ; c.Clear ; c.Add ( s[ i ] ); end end else curLen := 1; foreach var c1 in c do // после окончания обработки нужно вывести все символы и длины цепочек, удобнее всего использовать для этого цикл foreach writeln ( c1, ' ', maxLen ); end.

Слайд 27

Р-06. В текстовом файле k8.txt находится цепочка из символов, в которую могут входить заглавные буквы латинского алфавита A … Z и десятичные цифры. Найдите длину самой длинной подцепочки, состоящей из одинаковых символов. Для каждой цепочки максимальной длины выведите в отдельной строке сначала символ, из которого строится эта цепочка, а затем через пробел – длину этой цепочки. программа на языке Python : s = open('k7.txt').read() count = 0 maxCount = 0 for char in s: if (char == 'E' and count%3 == 0) or \ (char == 'A' and count%3 == 1) or \ (char == 'B' and count%3 == 2): count += 1 if count > maxCount : maxCount = count elif (char=='E'): count = 1 else: count = 0 print( maxCount )

Слайд 28

Задание 25 ( высокий уровень, время – 20 минут ) Тема : Обработка целых чисел. Проверка делимости Что проверяется: Умение создавать собственные программы (10–20 строк) для обработки целочисленной информации. 1. 6 . 3 . Построение алгоритмов и практические вычисления 1.1. 5 . Создавать программы на языке программирования по их описанию

Слайд 29

Решение с помощью программы время выполнения несущественно для отрезков, поэтому можно использовать простой перебор без оптимизации общая структура цикла перебора Pascal : count := 0; for n:=a to b do if условие выполнено then действие // например, подсчет количества count := count + 1; writeln (count); C ++: int count = 0; for( int n = a; n <= b; n++) if( условие выполнено ) действие ; std :: cout << count; Python : count = 0 for n in range(a, b+1): if условие выполнено : действие print( count )

Слайд 30

Решение с помощью программы Количество делителей Количество делителей и сами делители П ростые числа - любое простое число имеет только два делителя Перебор всех возможных делителей d от 1 до n Сохранение в массиве найденных делителей Оптимизация перебора: наименьший из пары делителей, таких что a  b = n , не превышает квадратного корня из n ; нужно только аккуратно обработать случай, когда число n представляет собой квадрат другого целого числа

Слайд 31

Р-02 (демо-2021). Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания. программа на Паскале : const divCount = 2; var n, count, d, i , j, q: longint ; divs : array[1..divCount] of longint ; begin for n:=174457 to 174505 do begin count := 0; q := floor( sqrt (n)); for d:=2 to q do if n mod d = 0 then begin count := count + 2; if count <= divCount then begin divs [count-1] := d; if d <> n div d then divs [count] := n div d; end else break end; if count = divCount then begin for i:=1 to divCount do write( divs [ i ], ' '); writeln end end end. программа на C++ : #include < iostream > #include < cmath > int main() { const int divCount = 2; int divs [ divCount ] = {}; for( int n = 174457; n <= 174505; n++ ) { int count = 0; int q = int ( sqrt (n)); for( int d = 2; d <= q; d++ ) if( n % d == 0 ) { count += 2; if( count <= divCount ) { divs [count-2] = d; if( d != n / d ) divs [count-1] = n / d; } else break; } if( count == divCount ) { for( int i = 0; i < divCount ; i ++ ) std :: cout << divs [ i ] << ' '; std :: cout << std :: endl ; } } }

Слайд 32

Р-02 (демо-2021). Напишите программу, которая ищет среди целых чисел, принадлежащих числовому отрезку [174457; 174505], числа, имеющие ровно два различных натуральных делителя, не считая единицы и самого числа. Для каждого найденного числа запишите эти два делителя в таблицу на экране с новой строки в порядке возрастания произведения этих двух делителей. Делители в строке таблицы также должны следовать в порядке возрастания. программа на Паскале : var i , j, k, d1, d2: longint ; begin for i:=174457 to 174505 do begin k := 0; for j:= 2 to i-1 do if i mod j = 0 then begin k:= k + 1; if k = 1 then d1:= j; if k = 2 then d2:= j; end; if k = 2 then writeln ( d1, ' ', d2 ); end ; end . программа на C++ : #include < iostream > user namespace std ; int main() { int d1, d2; for( int i = 174457; i <= 174505; i ++ ) { int k = 0; for ( int j = 2; j <= i-1; j++ ) if( i % j == 0 ) { k ++; if( k == 1 ) d1 = j; if( k== 2) d2 = j; } if ( k == 2 ) cout << d1 << ' ‘<< d2 << endl ; } return 0; } программа на Python : for i in range (174457, 174505+1): k = 0; for j in range (2, i ): if i % j == 0: k = k + 1; if k == 1: d1 = j if k == 2: d2 = j if k == 2: print( d1, d2 )

Слайд 33

Решение с помощью электронной таблицы Заполняем в строке 2 значениями из отрезка [174457;174505] В столбце А заполняем делителями – это значения от 2 до sqrt (174505) =417, так как по нам не нужно рассматривать единицу и само число в качестве делителя В ячейки по центру записываем формулу, вычисляющую остаток от деления числа из строки 2 на число из столбца А В строке 419 находим количество чисел (это числа от 2 до 417), на которые число из строки 2 делится без остатка Нас интересует только два различных делителя, поэтому в строке 420 для чисел, у которых только один делитель <=417 , находим позицию этого делителя – это и есть первый делитель . Для этого используем функцию ПОИСКПОЗ ; она находит в столбце 0 и определяет его позицию (третий аргумент функции ПОИСКПОЗ означает точное совпадение): В строке 421 находим второй делитель числа

Слайд 34

Задание 26 ( высокий уровень, время – 35 минут ) Тема : Обработка массива целых чисел из файла. Сортировка. Что проверяется: Умение обрабатывать целочисленную информацию с использованием сортировки. 1.6.3. Построение алгоритмов и практические вычисления. 1.1.3. Строить информационные модели объектов, систем и процессов в виде алгоритмов .

Слайд 35

Решение с помощью электронной таблицы Перенос данных в таблицу Excel Подготовка данных для обработки: сохранение нужного числа (8200), удаление лишних строк и т.п. Сортировка данных Выделение ячеек, сумма которых не больше 8200 Запоминаем количество ячеек, сумма значений которых не больше 8200 = 568 Вычисление расхождения 8200 – текущая сумма = 24 Заменяем последнее значение большим - 29+24=53 53 нет, заменяем на 50

Слайд 36

Решение с помощью программы Чтение данных из файла в языке Python для чтения данных удобно использовать менеджер контекста, который открывает файл и закрывает его ; with open("26.txt") as Fin : ... # какие-то операции с файлом если в текущей строке файла находится целое число, то прочитать его в переменную x можно так: x = int ( Fin.readline () ) если в строке записаны два числа, после чтения ( Fin . readline () ) строку нужно разбить на отдельные части по пробелам (каждая часть – символьная запись числа) и затем каждую часть преобразовать в целое число; например, чтение двух чисел: s = Fin.readline () symData = s.split () x, y = map( int , symData ) или в компактной форме x, y = map( int , Fin.readline ().split() ) в языке PascalABC . NET для чтения данных проще всего просто перенаправить входной поток на файл: Assign ( input , '26. txt ' ); после этого можно использовать операторы read и readln , так же, как при вводе с клавиатуры в языке C++ можно читать данные с помощью входного потока ( fstream ): #include < fstream > ... ifstream Fin("26.txt"); Fin >> x ; Fin >> y >> z ;

Слайд 37

Решение с помощью программы Хранение массива данных в языке PascalABC . NET используем динамический массив; когда станет известен его размер, выделаем место в памяти и читаем из входного потока: var data: array of integer; SetLength ( data, N ); for var i:=0 to N-1 do read( data[ i ] ); в языке Python для хранения массива данных используется список; следующая программа показывает чтение массива данных размера N в список data из файла «26. txt » (данные записаны в столбик): data = [0]*N with open("26.txt") as Fin: for i in range(N): data[ i ] = int ( Fin.readline () ) в языке C++ аналогично используется коллекция vector : #include ... vector < int > data(N); for( int i = 0; i < N; i ++ ) Fin >> data[ i ];

Слайд 38

пример PascalABC . NET var S, N: integer; data: array of integer; begin Assign( input, '26.txt' ); readln ( S, N ); SetLength ( data, N ); for var i:=0 to N-1 do read( data[ i ] ); Sort( data ); var total := 0; var count := 0; while count < N-1 do begin if total + data[count] > S then break; total += data[count]; count += 1; end; var delta := S - total; var candidates := data.Where ( x -> x - data[count-1] <= delta ); Println ( count, candidates.Max ) end. Python with open("26.txt") as Fin: data = Fin.readlines () S, _ = map( int , data[0].split() ) del data[0] data = sorted( list(map( int , data)) ) total = 0 for i , val in enumerate(data): if total + val > S: break total += val print( i ) delta = S - total candidates = [x for x in data if x-data[i-1] <= delta] print( max(candidates) )

Слайд 39

Задание 27 (высокий уровень, время – 3 5 мин ) 27 (высокий уровень, время – 3 5 мин) Тема : Обработка данных, вводимых из файла в виде последовательности чисел. Что проверяется: Умение создавать собственные программы (20–40 строк) для анализа числовых последовательностей. 1.6.3. Построение алгоритмов и практические вычисления. 1.1.5 Создавать программы на языке программирования по их описанию Что нужно знать : как прочитать данные из файла основы комбинаторики динамическое программирование

Слайд 40

Решение с помощью программы #include < iostream > #include < fstream > #include < cmath > using namespace std ; int main() { ifstream Fin( "27-b.txt" ); int N, s = 0, dMin = 10001; Fin >> N; for( int i = 0; i < N; i ++ ) { int a, b; Fin >> a >> b; s += max( a, b ); // суммируем максимальные числа из каждой пары int d = abs( a-b ); // выбираем пару , в которой разница между числами минимальная и не делится на 3 (иначе делимость новой суммы на 3 сохранится) if( d % 3 > 0 ) dMin = min( d, dMin ); } if( s % 3 != 0 ) //если полученная сумма не делится на 3 cout << s ; //то выводим s else cout << s- dMin ; // иначе заменим число в одной из пар на второе , минимальное }

Слайд 41

Решение С помощью электронных таблиц загружаем текст в Excel с помощью вкладки Данные/Из текста (используем разделитель - пробел); удаляем первую строку где только одно число (количество ) в столбце C находим максимальное из каждой пары чисел: вставляем в C1 формулу =МАКС(A1:B1) и копируем ее вниз (двойной щелчок на маркере заполнения ) вычисляем сумму чисел в столбце C проверяем кратность 3: находим остаток от деления на 3 по формуле =ОСТАТ(C21;3) если остаток не равен 0, то искомое число найдено; иначе продолжаем… в столбце D для каждой пары находим модуль разности по формуле вида =ABS(A1-B1) ; поскольку нам нужны только пары, в которых разность не делится на 3, записываем 0 в те строчки, где это условие не выполняется; для этого используем условие: =ЕСЛИ(ОСТАТ(A1-B1;3)=0;0;ABS(A1-B1 )) сортируем диапазон по столбцу D по возрастанию и берем из него первое ненулевое число (минимальную разницу в паре) вычитаем его из суммы, полученной ранее: можно заполнить столбец E формулами вида =$C$21-D1, тогда результат будет выведен сразу справа от минимальной разности Для варианта A получаем 127127, для варианта B - 399762080.

Слайд 42

Ресурсы сети Интернет для самообразования учителя по методике преподавания информатики и подготовке к сдаче ЕГЭ Тренажёры для подготовки к компьютерному ЕГЭ (КЕГЭ) Тренажер для подготовки к КЕГЭ (К. Поляков ) Тренажер для подготовки к КЕГЭ (А. Кабанов ) Для самообразования учителя по методике преподавания можно рекомендовать следующие ресурсы сети Интернет: http ://www.fipi.ru - Федеральный институт педагогических измерений https ://inf-oge.sdamgia.ru/ - тренировочные тесты https ://neznaika.pro/oge/inf_oge/ - тренировочные тесты http ://distan-school.ru/oge/?tap=3 - тренировочные тесты http ://kpolyakov.spb.ru/school/oge.htm - тренировочные тесты, в том числе тренировочные тесты для компьютерного ЕГЭ http ://kpolyakov.spb.ru – сайт учителя информатики К.Ю. Полякова Материалы от Alex Danov : Базовые алгоритмы для решения задач ЕГЭ на программирование: https://www.youtube.com/playlist?list=PLXZ932--vmI_-BWxVtEdU-p-_BtnYfR8p Решения задач из сборника 2020 г.: https://github.com/AlexDanov/InfEGE-27-PascalABC Разборы задач 27 (из сборника 2020 г.): https://www.youtube.com/playlist?list=PLXZ932--vmI_ivq9QOC_gpZ2czSe2CLTU