Разбор задач части С

Задача С1 (Анализ предложенной программы)

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

В прошлые годы предлагалась следующая задача: "Дана точка. Требуется определить попадание точки в область, заданную графиком". Ошибочно написанная программа, как правило, содержала вложенный оператор if с пропущенными else ветвями, а также содержала ошибки в условиях, характеризующих выделенную область.

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

В этом году предложенная задача была значительно упрощена. Задача состояла в разборе цифр десятичного числа. Для тех учеников, которые могут написать программу перевода десятичного числа в некоторую систему счисления, эта задача представляется элементарной. Выше эта задача была мною подробно рассмотрена. Задача не допускает особых вариаций. Ошибок особых там сделать просто негде. Можно, конечно, неверно записать условие в цикле while или в условном операторе, можно неверно написать оператор присваивания. Но все эти ошибки достаточно очевидны и легко исправляются. Тем не менее задача оценивается в 3 балла, что выше баллов по задаче С2, требующей программирования.

Рассмотрим один из вариантов задачи С1.

<<

Требовалось написать программу, при выполнении которой с клавиатуры считывается натуральное число N, не превосходящее 109, и выводится минимальная цифра этого числа. Программист торопился и написал программу неправильно. Вот вариант этой программы на Паскале:

var N: longint; 
digit, min_digit: integer;
begin
  readln(N);
  min_digit := 0;
  while N > 0 do
  begin
    digit := N mod 10;
    if digit < min_digit then
      min_digit := digit;
    N := N div 10;
  end;
  writeln (digit);
end.
    

Последовательно выполните следующее:

Обратите внимание, что требуется найти ошибки в имеющейся программе, а не написать свою, возможно использующую другой алгоритм решения. Исправление ошибки должно затрагивать только строку, в которой находится ошибка.

>>

Задача сочетает разбор числа и нахождение минимума. Первая ошибка в программе – неверная инициализация переменной min_digit, хранящей минимальное значение. Вторая ошибка, которую скорее следует рассматривать как описку, связана с ошибкой вывода – на печать выводится не переменная min_digit, а переменная digit. Из-за первой ошибки условие в операторе if никогда выполняться не будет и переменная min_digit сохранит значение 0, полученное при инициализации. Из-за второй ошибки на печать будет выведено значение переменной digit, полученное на последнем шаге цикла - старшая цифра введенного числа.

Вот ответ, который следует дать для этой задачи:

Большинство школьников, представивших решение этой задачи, давало правильный ответ на все три вопроса.

Задача С2 (Простая программа на нахождение в массиве чисел максимального (минимального) числа, удовлетворяющего дополнительным условиям)

Привет

Хорошая задача, допускающая вариации, содержательную постановку, позволяющая проверить, сделаны ли первые шаги в освоении программирования, знает ли и понимает ли школьник алгоритмы, входящие в начальный базис алгоритмизации.

Рассмотрим один из вариантов задачи С2.

<<

Дан целочисленный массив из 20 элементов. Элементы массива могут принимать целые значения от 0 до 10000 включительно. Опишите на естественном языке или на одном из языков программирования алгоритм, позволяющий найти и вывести максимальное значение среди трехзначных элементов массива, не делящихся на 3. Если в исходном массиве нет искомого элемента, то вывести сообщение "не найдено".

Исходные данные объявлены, как показано в примере программы на Паскале. Запрещается использовать переменные, не описанные ниже, но разрешается не использовать некоторые из описанных переменных.

Вот начало программы на Паскале:

const 
  N = 20;
var
  a: array[1:N] of integer;
  i, j, max: integer;
begin
  for i := 1 to N do
    readln(a[i]);
  …
end.
    

В качестве ответа следует привести опущенный фрагмент программы.

>>

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

Решим проблему инициализации переменной max. При поиске максимального элемента, удовлетворяющего дополнительным условиям, начальное значение переменной max должно быть меньше любого возможного значения, претендующего на максимум. Поскольку в данной задаче максимум разыскивается среди трехзначных чисел, то при инициализации переменной max достаточно присвоить значение 99 (можно и меньше). Соответствующий оператор присваивания имеет вид:

max := 99;

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

(j > 99) and (j < 1000) and (j mod 3 <> 0)

Здесь переменная j играет роль кандидата. Конечно, для нее следовало бы выбрать другое содержательное имя, например, candidat, но приходится смиряться с требованиями, и не менять имена введенных переменных.

Третья проблема проста. Я не буду ее пояснять в отдельности, а приведу полный фрагмент программы на Паскале, который следует добавить в текст программы:

max := 99;
for i := 1 to N do
begin
  j := a[i]; 
  if (j > 99) and (j < 1000) and (j mod 3 <> 0) then   //кандидат
    if j > max then
      max = j;
end
if max = 99  then writeln("не найден") else writeln(max);
    

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

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

Задача С3 (Анализ игры. Построение графа (дерева) игры)

Непонятно, по каким причинам эта задача включена в раздел С, который следовало бы посвятить программированию. Эту задачу в модифицированном виде стоило бы включить в раздел В. Это самая легкая задача в разделе С. Как правило, если школьники представляли только одну задачу, то это была задача С3. Большинство давало правильное решение задачи. Я не буду приводить той формулировки, которая давалась на экзамене, а рассмотрю более сложный вариант, частным случаем которого является экзаменационный вариант.

Вот как выглядит модифицированный вариант задачи:

<<

Два игрока играют в камушки. Перед ними куча из S камней (1 <= S <= 34). Каждый игрок обладает неограниченным запасом камней. У каждого игрока три возможных хода:

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

>>

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

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

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

Построение полной таблицы избыточно. Нетрудно видеть, что второй игрок выигрывает для значений S, удовлетворяющих следующему условию: $$S = 17 – 3 * k; (0 <=k <=5)$$

Для остальных значений S выигрывает первый игрок.

Задача С4 (Алгоритмически сложная задача)

В разделе С это вторая задача на программирование. Если задача С2 требует от школьника знания классического алгоритма, то для "красивого" решения задачи С4 требуется придумать нестандартный алгоритм. Приведу вариант задачи, данный на экзамене.

<<

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

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

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

Вычисленное контрольное значение: - …

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

Перед текстом программы кратко опишите алгоритм.

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

>>

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

Вычислить R - максимальное произведение двух элементов массива, при условии, что R делится на 35.

Задача формулируется в одну строчку, суть ее сохраняется, но все запутывающие "завитушки" о контрольных значениях, разных элементах устраняются.

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

Приступим к разбору решения. Рассмотрим оба решения этой задачи. Первое достаточно очевидное. Нужно прочитать все числа, запомнить их в массиве. Тогда задача сводится к известной задаче нахождения максимума в массиве. Нужно найти максимальное произведение двух элементов, удовлетворяющее дополнительным условиям. Для этого достаточно организовать цикл по i и внутренний цикл по j, вычисляя произведение элементов a[i] * a[j], анализируя его на выполнение дополнительного условия и сравнивая с текущим максимальным значением произведения элементов. Приведу текст соответствующей программы на языке С#:

static void Main()
  {
    int N;
    Console.WriteLine("Введите количество элементов массива");
    N = int.Parse(Console.ReadLine( ));
    int[] a = new int[N];
    Console.WriteLine("Введите элементы массива");
    for(int i =0; i <N; i++)
      a[i] = int.Parse(Console.ReadLine());

    int R = 0;
    int cand =0;
    for(int i = 0; i < N; i++)
      for(int j = i+1; j < N; j++)
      {
        cand = a[i] * a[j];
        if (cand % 35 == 0  cand > R)
          R = cand;
      }
    Console.WriteLine("R = " + R);
  }
    

В таком варианте программа достаточно проста и доступна для школьников, умеющих писать простые программы. Что касается "завитушек", введенных в формулировку данной задачи, то первое требование о "разных" элементах выполняется автоматически, поскольку внутренний цикл начинается со значения i +1, так что квадраты чисел просто не строятся. "Завитушка" насчет контроля значений просто означает, что нужно ввести "контрольное" значение R и сравнить его с вычисленным. Я не стал этого делать, дабы не затенять суть этой простой программы.

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

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

cand1 = max5 * max7;

cand2 = max35 * max.

Здесь:

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

Вот как может выглядеть подобная программа, написанная на языке С#:

static void Main(string[] args)
{
  int N;
  Console.WriteLine("Введите количество элементов массива");
  N = int.Parse(Console.ReadLine());
  int item;
  int max, max5, max7, max35;
  int index_max35;
  max = max5 = max7 = max35 = 0;
  index_max35 = 0;
  Console.WriteLine("Введите поочередно элементы массива");
  for (int i = 0; i < N; i++)
    {
      item = int.Parse(Console.ReadLine());
      if (item % 35 == 0  item > max35)
      {
        max35 = item;
        index_max35 = i;
      }
      else
      {
        if (item % 5 == 0  item > max5)
          max5 = item;
        if (item % 7 == 0  item > max7)
          max7 = item;
      }
      if (i != index_max35  item > max)
        max = item;
    }
    int R,R_Contr, cand1, cand2;
    cand1 = max5 * max7;
    cand2 = max35 * max;
    if (cand1 > cand2)
      R = cand1;
    else
      R = cand2;
    Console.WriteLine("Вычислено значение R = " + R);
    Console.WriteLine("Введите контрольное значение");
    R_Contr = int.Parse(Console.ReadLine());
    if (R == R_Contr)
      Console.WriteLine("Контроль пройден");
    else
      Console.WriteLine("Контроль не пройден");
  }
    

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

Подводя общие итоги экзамена по информатике, можно отметить, что наиболее легкой была задача С3, с которой справилось большинство школьников, представивших свои работы. Многие школьники представили корректное решение задачи С1. С программированием дело обстоит значительно хуже. Сравнительно простая задача С2 для многих оказалась трудной задачей. Совсем плохая ситуация сложилась с задачей С4, но не потому, что не было представлено ее правильных решений. Но об этой ситуации следует сказать особо.

Печальные итоги проверки экзамена по информатике

Я участвовал в работе комиссии по проверке части С экзамена по информатике. Комиссии было представлено более 500 работ. Членам комиссии было известно, что решения задач были выложены в интернете. Доступными были рекомендованные решения, то есть те самые решения, которые представлялись комиссиям, проверяющим работы. Так что вина за утечку информации лежит не на школьниках, а на людях, отвечающих за честное проведение экзамена.

Представьте себе положение членов комиссии, которые видят, что представленное школьником решение буква в букву повторяет рекомендованное решение. У нас нет никаких сомнений, что решение списано, поскольку оно буквально повторяет рекомендованное решение, которое кстати говоря является далеко не идеальным, поскольку включает лишние проверки и довольно запутанным образом проверяет условие, накладываемое на максимальный элемент. Мы знаем, что представлена работа, не заслуживающая какой-либо положительной оценки, которую следует оценить на "неудовлетворительно".

У нас нет права занижать оценку за списывание. Мы видим правильное решение, должны по правилам ставить максимальный балл, понимая, что оценка не заслужена, что лучшие оценки ЕГЭ получают не лучшие ученики, а обманщики.