Разбор 27 задания ЕГЭ по информатике (вторая часть)

На уроке рассмотрен разбор 27 задания ЕГЭ по информатике: дается подробное объяснение и решение задания 2017 года

Объяснение задания 27 ЕГЭ по информатике

27-е задание — «Обработка строк или последовательности чисел; сложность алгоритмов» — характеризуется, как задание высокого уровня сложности, время выполнения – примерно 55 минут, максимальный балл — 4

Программирование: обработка строк или последовательности чисел. Сложность алгоритмов

Решение 27 задания требует знания следующих тем и понятий:

Работа со строками
  • строку можно представить, как одномерный массив, в котором хранятся символы;
  • для того чтобы обратиться к символу строки s с номером i (например, вывести его на экран) используется запись s[i]:
  • s:='лес'; 
    write(s[1]); {на экране буква 'л'}
    
  • при работе со строками используется операция конкатенации или объединения строк в одну; в качестве нее используется знак сложения (+), например:
  • s := '56' + '78'; { получили '5678' }
  • в кодовой таблице ASCII цифры имеют коды от 48 (соответствует цифре 0) до 57 (соответствует цифре 9); функция Ord() служит для получения кода символа, например:
  • k := Ord('0');   { k = 48 }
  • то же самое можно сделать с помощью преобразования типа (перевод типа char к типу integer)
  • k := integer('0'); { k = 48 }
  • функция Chr() служит для обратного перевода: получения символа по его коду, например:
  • c := Chr(48);  { получили в с символ '0' }
  • то же самое можно сделать с помощью преобразования типа (привести тип integer к типу char)
  • c := char(48); { получили символ '0' }

Более подробно ознакомиться с принципами работы со строками можно по ссылке

Работа с записями

Запись в Паскале — это сложный тип данных, который может состоять из нескольких элементов – полей; поля могут иметь различный тип.

Подробно о записях объясняется здесь.

Сложность алгоритмов

Для определения вычислительной мощности, которая потребуется для выполнения компьютером того или иного алгоритма, вводится понятие сложности алгоритма. Существует:

  • временная сложность;
  • пространственная (емкостная) сложность (определяется количеством ячеек памяти, используемых в процессе его выполнения).

Одним из вариантов оценки сложности алгоритма является подсчет количества выполняемых в нем операций.

сложность O(N)

N — размер массива данных

  • если сложность алгоритма характеризуется, как O(N), это значит, что для больших N увеличение в два раза размера массива данных приведет к примерно такому же увеличению (в два раза) количества операций;
  • такая сложность O(N) характерна, например, для алгоритма с одним (или несколькими) простыми циклами без вложенности, в которых выполняется N итераций (проходов цикла);
  • примером алгоритма со сложностью O(N) может служить алгоритм поиска максимального элемента в одномерном массиве:
  • {поиск максимального элемента массива array из N элементов}
    ...
    max := array[1];
    for i:=2 to N do
      if array[i] < max
        max := array[i];
    writeln (max);
    ...
    
    Подсчитаем количество операций для данного алгоритма:
    
  • N — 1 операция присваивания счетчику цикла i очередного значения;
  • N — 1 операция сравнения счетчика со значением N;
  • N — 1 операция сравнения очередного элемента массива со значением max;
  • от 1 до N операций присваивания значения переменной max.
  • существует формула для определения количества операций для алгоритма со сложностью O(N):
  • p = a * N + b
      где a и b – постоянные, которые имеют свои значения для определенных классов задач;

    • так, если задача решена двумя способами: в одном используется несколько циклов от 1 до N, а во втором используется только один цикл, то хотя оба алгоритма имеют сложность O(N), но эффективнее в большинстве случаев является алгоритм с одним циклом, так как постоянная a при подсчете количества операций будет больше в случае с алгоритмом с несколькими циклами.
    сложность O(N2)
    • сложность алгоритма O(N2) означает, что при увеличении в два раза N количество операций возрастет примерно в четыре раза (т.е. количество операций пропорционально квадрату размера массива);
    • примером сложности O(N2) алгоритма является программа с двумя вложенными циклами, в каждом из которых N итераций (проходов); например, алгоритмы сортировки массивов методами «пузырька» или выбора.
    алгоритм со сложностью O(N2) менее эффективен, чем алгоритм со сложностью O(N)
    • экспоненциальная сложность означает, что размер массива входит в показатель степени:
    например сложность O(2N))
    • для больших N такие задачи не эффективны и не решаются за приемлемое время.

    Типы алгоритмов в соответствии с их временной сложностью (перечислены с увеличением их сложности):

    • Постоянный тип - сложность O(1).
    • Логарифмический тип - сложность оценивается как O(log(n)).
    • Примером могут служить алгоритмы, которые сводят большую задачу к набору меньших задач, уменьшая на каждом шаге размер задачи на постоянную величину. Например, двоичный поиск в массиве, когда на каждом шаге размер массива сокращается вдвое.

    • Линейный тип - оценка равна O(n).
    • Квадратный тип - O(n2).
    • Свойственно алгоритмам, обрабатывающим все пары элементов данных.

    • Кубический, полиномиальный тип - O(n3), O(nm).
    • Соответствует алгоритмам, которые обрабатывают все тройки элементов данных.

    • Экспоненциальный тип - O(tp(n)), t- константа, p(n) - некоторая
      полиномиальная функция.
    • Факториальный тип - O(n!). Обладает наибольшей временной сложностью среди всех известных типов.
    • Присуще алгоритмам, которые выполняют перебор всевозможных сочетаний элементов.

      Решение 27 заданий ЕГЭ по информатике


      Разбор 27 задания ЕГЭ по информатике 2017 года ФИПИ вариант 5 (Крылов С.С., Чуркина Т.Е.):

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

      Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеет значения.

      Максимальная оценка за правильную программу - 2 балла.

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

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

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

      Максимальная оценка за правильную программу, эффективную по времени и по памяти, - 4 балла.

      Как в варианте А, так и в варианте Б программа должна напечатать одно число - максимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

      Например:
      2  6
      4  1
      7  3
      2  9
      7  4
      sum=231


      ✍ Решение:

      Задание Б (алгоритм):

      • поскольку в задании указано, что "имеется набор данных, состоящих из пар...", то введем в программу переменную n для количества пар, значение которой будет считываться со стандартного входного потока:
      • n:longint; {количество пар чисел};
      • объявим сами числа типа integer, переменную цикла - i - типа integer и дополнительные переменные, смысл которых будет объяснен ниже. Объявление сделаем в отдельных строках (так делать не обязательно), чтобы можно было ввести удобно комментарии:
      •  x,y: integer; {пара чисел}
         max: integer; {максимальное из пары}
         min: integer; {минимальное из пары}
         sum:longint; {сумма квадратов отобранных чисел}
         min_kvadr:longint; {мин. нечетная разница квадратов max и min}
         i:integer;
      • так как в задании не оговаривается, что пары чисел считывается из файла, значит их необходимо считать со стандартного входного потока оператором readln(); т.е. организуем цикл:
      • for i:=1 to n do begin
          readln(x,y);
          ...

        Допустим имеем пары:

        2 6
        4 1
        7 3
        2 9
        7 4
        
      • Чтобы получить в итоге максимальную сумму, то необходимо суммировать те числа из пар чисел, которые максимальны в паре, т.е. в нашем случае будем суммировать квадраты выделенных чисел из пар:
      • 2 6
        4 1
        7 3
        2 9
        7 4
        
      • но сначала определим максимальное и минимальное число из каждой пары:
      • if x>y then 
        begin 
           max:=x; min:=y 
        end
        else 
        begin 
            max:=y;min:=x 
        end;
      • далее суммируем квадраты максимальных чисел:
      • sum:=sum+sqr(max);
      • поскольку, согласно заданию, сумма должна быть нечетной, то в случае, если сумма будет четной, нам необходимо выбрать пару, в которой разница между квадратами чисел минимальна и при этом нечетна и взять из этой пары не максимальный, а минимальный элемент. Или лучше просто вычислить разницу между квадратами максимума и минимума и затем вычесть ее из получившейся четной суммы. Выделим пару, разница между квадратами чисел которой минимальна и при этом нечетна:
      • 2 6 - разница 4
        4 1 - разница 3
        7 3 - разница 4
        2 9 - разница 7
        7 4 - разница 3
        
      • поиск минимальной и нечетной разницы между квадратами чисел в паре:
      • if((max-min) mod 2 > 0) and ((sqr(max)-sqr(min)) < min_kvadr) then
            min_kvadr:=sqr(max) - sqr(min)
      • для переменной, обозначающей разницу, до цикла необходимо назначить максимально возможное значение:
      • min_kvadr:=1073676289;  {32 767 * 32 767 (самое большое в типе integer) }
      • таким образом, в цикле у нас происходит:
      • 1. поиск максимального и минимального числа из пары;
      • 2. вычисляется сумма максимальных чисел из каждой пары;
      • 3. находится минимальная разница квадратов максимального и минимального числа в парах.
      • после цикла необходимо проверить сумму на нечетность. Если сумма четная (чего НЕ должно быть по условию), то отнимем от суммы вычисленную минимальную разницу. Но при этом учтем, что если не нашлось нечетной минимальной разницы, то выводим 0 (по условию):
      • if sum mod 2 = 0 then begin
          if min_kvadr > 10000 then sum := 0
          else sum:=sum - min_kvadr
        end;

      Эффективная программа (решение):

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      
      var
       n:longint; {количество пар чисел}
       x,y: integer; {пара чисел}
       max: integer; {максимальное из пары}
       min: integer; {минимальное из пары}
       sum:longint; {сумма квадратов отобранных чисел}
       min_kvadr:longint; {мин. нечетная разница квадратов max и min}
       i:integer;
      begin
      sum:=0;
      readln(n);
      min_kvadr:=1073676289;  {32 767 * 32 767, самое большое integer}
      for i:=1 to n do begin
        readln(x,y);
        if x>y then begin max:=x; min:=y end
        else begin max:=y;min:=x end;
        sum:=sum+sqr(max);
        if((max-min) mod 2 > 0) and ((sqr(max)-sqr(min)) < min_kvadr) then
          min_kvadr:=sqr(max) - sqr(min)
      end;
      if sum mod 2 = 0 then begin
        if min_kvadr > 10000 then sum := 0
        else sum:=sum - min_kvadr
      end;
      writeln('sum=',sum)
      end.

      Пример работы программы:

      3
      1 4
      2 4
      3 4
      sum=41
      

      Предлагаем также посмотреть объяснение данного 27 задания на видео:


      Разбор 27 задания ЕГЭ по информатике 2018 года вариант 2 (Крылов С.С., Чуркина Т.Е. "Типовые тренировочные варианты", 10 вариантов):

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

        
      А. Имеется набор данных, состоящий из 5 тройке положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

      Напишите программу для решения этой задачи. В этом варианте задания оценивается только правильность программы, время работы и размер использованной памяти не имеют значения.
      Максимальная оценка за правильную программу - 2 балла.

      Б. Имеется набор данных, состоящий из троек положительных целых чисел. Необходимо выбрать из каждой тройки ровно одно число так, чтобы сумма всех выбранных чисел не делилась на 5 и при этом была минимально возможной. Если получить требуемую сумму невозможно, в качестве ответа нужно выдать 0.

      Постарайтесь сделать программу эффективной по времени и по используемой памяти.

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

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

      Максимальная оценка за правильную программу, эффективную по времени и по памяти, - 4 балла.

      Как в варианте А, так и в варианте Б программа должна напечатать одно число - минимально возможную сумму, соответствующую условиям задачи (или 0, если такую сумму получить нельзя).

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

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

      Входные данные
      Для варианта А на вход программе подается 5 строк, каждая из которых содержит три натуральных числа, не превышающих 10000.
       
      Пример входных данных для варианта А:

      1 3 2
      2 1 2
      2 5 1
      1 3 4
      6 1 1

      Для варианта Б на вход программе в первой строке подается количество троек чисел N (1<=N<=100000). Каждая из следующих N строк содержит три натуральных числа, не превышающих 10000.   Пример входных данных для варианта Б:

      5
      1 3 2
      2 1 2
      2 5 1
      1 3 4
      6 1 1

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

      ✍ Решение:

      Задание Б

      Чтобы получить минимально возможную сумму, будем брать из каждой тройки наименьшее число. Если полученная при этом сумма будет кратна 5, ее придется увеличить. Для этого достаточно в одной из троек, где хотя бы два числа имеют разные остатки при делении на 5, заменить ранее выбранное число на число с другим остатком от деления на 5 из той же тройки. При этом модуль разности между прежним и новым, выбранным из тройки, должен быть минимально возможным.

       
      Пример правильной и эффективной программы для задания Б на языке Паскаль:

      1
      2
      3
      4
      5
      6
      7
      8
      9
      10
      11
      12
      13
      14
      15
      16
      17
      18
      19
      20
      21
      22
      23
      24
      25
      26
      27
      28
      29
      30
      31
      32
      
      const
        aMax = 10000;{наибольшее возможное исходное число}
       
      var
        N: longint; {количество троек}
        a, b, c, tmp: longint;{тройка чисел}
        s: longint;{сумма выбранных чисел}
        D_min: longint;{мин. разница в тройке не кратная 5}
        i: longint;{}
       
      begin
        s := 0;
        D_min := aMax + 1;
        readln(N);
        for i := 1 to N do 
        begin
          readln(a, b, c);
          if (a > b) then begin tmp := a;a := b;b := tmp end;
          if(b > c) then begin
            tmp := b;b := c;c := tmp;
            if (a > b) then begin tmp := a;a := b;b := tmp end
          end; {a,b,c отсортированы по возрастанию}
          s := s + a;
          if((b - a) mod 5 > 0 ) and ((b - a) < D_min) then D_min := b - a;
          if((c - a) mod 5 > 0 ) and ((c - a) < D_min) then D_min := c - a
        end;
        if s mod 5 = 0 then begin
          if D_min > aMax then s := 0
          else s := s + D_min
        end;
        writeln(s)
      end.

      Задание А

      В цикле перебираются все возможные суммы, и среди них ищется удовлетворяющая условию.

    Поделитесь уроком с коллегами и друзьями:

    Добавить комментарий

    Ваш e-mail не будет опубликован. Обязательные поля помечены *

    *
    *

    Вставить формулу как
    Блок
    Строка
    Дополнительные настройки
    Цвет формулы
    Цвет текста
    #333333
    Используйте LaTeX для набора формулы
    Предпросмотр
    \({}\)
    Формула не набрана
    Вставить