Программирование в заданиях ЕГЭ

Описание презентации по отдельным слайдам:

• 

  1 слайд

  Программирование
  в заданиях ЕГЭ
  Чтобы решать задачи, нужно их решать.
  

• 

  2 слайд

  Задание С1
  Уровень сложности: повышенный
  Максимальный балл: 3
  Время на выполнение: 30 минут.
  Решаемость – 48 %
  Рекомендации по подготовке учащихся:
  Решить задачу математически.
  Написать соответствующую программу.
  Провести тестирование программы для различных наборов исходных данных
  Предложить учащимся вариант программы с ошибками
  Учащиеся исправляют ошибки в предложенной программе
  Оценивают: можно ли в условном операторе использовать составное условие с применением AND или OR
  

• 

  3 слайд

  Пример 1. Условие задачи:
  Требовалось написать программу, которая решает уравнение ax=b относительно х. Учитывается, что а может принимать любые значения, в том числе и 0. Программист сделал в программе ошибки.
  
  Последовательно выполните задания:
  Приведите пример таких чисел a и b, при которых программа неверно решает поставленную задачу.
  Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы.
  

• 

  4 слайд

  Пример неправильно записанной задачи:
  var a,b,x: real;
  begin
  readln(a,b);
  if a<>0 then writeln(b/a:0:2)
  else if b<>0 then writeln(‘x – любое’)
  else writeln(‘корней нет’)
  end.
  1) Пример исходных данных, при которых программа неверно решает поставленную задачу: a=0, b=5. Результат – «х - любое», на самом деле – корней нет.
  

• 

  5 слайд

  2) Возможно следующее исправление задачи:
  var a,b,x: real;
  begin
  readln(a,b);
  if a<>0 then writeln(b/a:0:2)
  else if b=0 then writeln(‘x – любое’)
  else writeln(‘корней нет’)
  end.
  

• 

  6 слайд

  Пример 2. Условие задачи:
  Требовалось написать программу, которая определяет, лежит ли точка A(x, y) в треугольной области, изображенной на рисунке. (Внутри понимается в строгом смысле – точка не может лежать на границе области). В результате выдается соответствующее текстовое сообщение Программист сделал в программе ошибки.
  Последовательно выполните задания:
  Приведите пример таких чисел x и y, при которых программа неверно решает поставленную задачу.
  Укажите, как нужно доработать программу, чтобы не было случаев её неправильной работы.
  Укажите, как можно доработать программу, чтобы она содержала логические операции AND или OR
  

• 

  7 слайд

  Программа на Паскале:
  var x,y: real;
  begin
  readln(x,y);
  if x<3 then
  begin
  if y<1 then
  if x+y>0 then writeln(‘точка лежит внутри области’)
  else writeln(‘точка не лежит внутри области’)
  else writeln(‘точка не лежит внутри области’);
  end;
  writeln(‘точка не лежит внутри области’);
  end.
  

• 

  8 слайд

  X<3
  y<1
  X+y>0
  попадает
  Не попадает
  Не попадает
  да
  нет
  да
  да
  нет
  нет
  Не попадает
  var x,y: real;
  begin
  readln(x,y);
  if x<3 then
  begin
  if y<1 then
  if x+y>0 then writeln(‘точка лежит внутри области’)
  else writeln(‘точка не лежит внутри области’)
  else writeln(‘точка не лежит внутри области’);
  end;
  writeln(‘точка не лежит внутри области’);
  end.
  

• 

  9 слайд

  1) Пример исходных данных, при которых программа неверно решает поставленную задачу: x=1, y=0.5. Результат – «Точка не лежит внутри области», на самом деле точка принадлежит области.
  2) Возможно следующее исправление задачи:
  var x,y: real;
  begin
  readln(x,y);
  if x<3 then
  begin
  if y<1 then
  if x+y>0 then writeln(‘точка лежит внутри области’)
  else writeln(‘точка не лежит внутри области’)
  else writeln(‘точка не лежит внутри области’);
  end;
  else writeln(‘точка не лежит внутри области’);
  end.
  

• 

  10 слайд

  3) Пример возможной доработки задания с использованием логических функций:
  var x,y: real;
  begin
  readln(x,y);
  if (x<3) and (y<1) and (x+y>0) then writeln(‘точка лежит внутри области’)
  else writeln(‘точка не лежит внутри области’);
  end.
  
  

• 

  11 слайд

  Задание С2
  Уровень сложности: высокий
  Максимальный балл: 2
  Время на выполнение: 30 минут.
  Решаемость – 35 %
  Примеры возможных задач:
  суммирование массива;
  проверка упорядоченности массива;
  слияние двух упорядоченных массивов;
  сортировка;
  поиск заданной подстроки в последовательности символов;
  поиск корня делением пополам;
  поиск наименьшего делителя целого числа;
  разложение целого числа на множители (простейший алгоритм);
  умножение двух многочленов.
  

• 

  12 слайд

  Пример № 1. Условие задачи:
  В двумерном массиве размерностью 10 х 10 найти произведение максимального и минимального элементов, лежащих выше главной диагонали.
  Решение:
  Для хранения значений максимума и минимума будем использовать переменные max и min соответственно. В теле цикла проверяем: лежит ли элемент выше главной диагонали. Если да, будем сравнивать этот элемент массива с уже найденным максимумом. И если элемент окажется больше, то в переменную max занесем значение этого нового элемента. В противном случае сравниваем этот же элемент с уже найденным минимумом, и если он окажется меньше минимума, то в переменную min занесем значение этого элемента. В конце найдем произведение min и max.
  

• 

  13 слайд

  Программа на Паскале:
  const n=10;
  var a: array [1..n; 1..n] of integer;
          i, j, max,min: integer; n: byte;
       begin                             
     {Ввод массива}
      for i:=1 to n do
             for j:=1 to n do
                 readln (a[i, j]);
      min:=a[1,2]; max:=a[1,2];
  {ищем максимум и минимум выше главной диагонали}
  for i:=1 to n-1 do
              for j:=i+1 to n do
  begin
  if a[i,j]>max then max:=a[i,j]
  else if a[i,j]<min then min=a[i,j];
  end;
  writeln(min*max);
  readln
  end.
  

• 

  14 слайд

  Пример № 2. Условие задачи:
  В массиве из 50 элементов, заполненном произвольными целыми числами, найдите два числа, произведение которых максимально. Вложенные циклы не используйте.
  
  Решение:
  Из условия задачи очевидно, что искомые числа – это либо два максимальных элемента массива, либо два минимальных отрицательных элемента массива. Для промежуточного хранения двух минимумов и двух максимумов элементов массива С будем использовать целочисленные переменные min1, min2, max1, max2. В теле цикла сначала найдем искомые два минимума или два максимума, а затем выясним, произведение какой пары чисел больше.
  

• 

  15 слайд

  Программа на Паскале:
  сonst n=50;
  var c:array [1..n] of integer;
  max1, max2, min1, min2, Sum, I: integer;
  i, j: real;
  begin
  for i:=1 to n do
  readln(c[i]);
  max1:=c[1];
  max2:=c[1];
  min1:=c[1];
  min2:=c[1];
  for i := 2 to N do
  begin
  {находим два максимума и два минимума}
  if c[i]>max1 then
  
  begin
  max2:=max1;
  max1:=c[i];
  end
  else
  if c[i] > max2 then
  max2:=c[i];
  if c[i]<min1 then
  begin
  min2:=min1;
  min1:=c[i];
  end
  else
  if c[i] < min2 then
  min2:=c[i];
  end;
  If min1*min2 > max1*max2 then
  write(min1,’ ‘,min2)
  else
  write(max2,’ ‘,max1);
  readln
  end.
  

• 

  16 слайд

  Пример № 3. Условие задачи:
  Опишите на русском языке или одном из языков программирования алгоритм вычисления разности между средним арифметическим максимального и минимального значений элементов заданного целочисленного массива из 30 элементов и средним арифметическим всех элементов этого массива
  Решение:
  Введем целочисленные переменные Max, Min и Sum, в которые будем заносить соответственно значения максимального и минимального элемента в просмотренной части массива, а также накапливать сумму значений элементов. Присвоим им в качестве начального значение первого элемента массива. Также определяем две переменные SM и SA типа real для хранения средних значений. В цикле от второго элемента до конца массива: прибавляем элемент к сумме, сравниваем его с Max, если он больше, заносим его значение в переменную Max. В противном случае сравниваем его с Min, если он меньше, заносим его значение в переменную Min. По окончании цикла вычисляем среднее арифметическое Max и Min, заносим его в переменную SM. В переменную SA заносим частное от деления суммы элементов на количество элементов в массиве. Выводим разность SM - SA. Пример алгоритма с учетом однократного прохода по массиву:
  

• 

  17 слайд

  Программа на Паскале:
  сonst N=30;
  var a:array [1..N] of integer;
  Max, Min, Sum, I: integer; SM, SA: real;
  begin
  Max := a[1];
  Min := a[1];
  Sum := a[1];
  for I := 2 to N do
  begin
  readln(a[i]);
  Sum := Sum + a[i];
  if a[i] > Max then Max := a[i]
  else
  if a[i] < Min then Min := a[i];
  end;
  SM := (Max + Min)/2;
  SA := Sum/N;
  writeln(SM - SA);
  end.
  

• 

  18 слайд

  Основные ошибки при выполнении задания:
  • неверное описание переменных (массивов)
  (2 % учащихся);
  • неверный тип данных (7 % учащихся);
  • неверная организация ввода-вывода данных (12 % учащихся);
  • в организации работы циклов (неверное определение граничных значений счетчиков циклов) (7% учащихся);
  • в организации работы с массивами (выход за пределы массива при организации циклов) (6 % учащихся);
  • 5% ошибок в расстановке операторных скобок.
  • 7% учащихся не знакомы с массивами и решают задачу, используя просто входную последовательность чисел;
  • не выполнена инициализация переменных у 6% учащихся (не заданы или неверно заданы первоначальные значения переменных, например, при поиске максимального (минимального) элемента массива).
  

• 

  19 слайд

  Задание С3
  Уровень сложности: высокий
  Максимальный балл: 3
  Время на выполнение: 30 минут.
  Решаемость – 48 %
  Пример 1. Условие:
  Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (5,2). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x,y) в одну из трех точек: или в точку с координатами (x+3,y), или в точку с координатами (x,y+3), или в точку с координатами (x,y+4). Выигрывает игрок, после хода которого, расстояние от фишки до точки с координатами (0,0) не меньше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
  

• 

  20 слайд

  Вывод: выигрывает второй игрок при любом ходе первого игрока.
  Первый ход второго игрока может быть 5,6-8,6 или 5,5-8,5.
  

• 

  21 слайд

  Пример 2. Условие:
  Даны три кучи камней, содержащих соответственно 2, 3 и 4 камня. За один ход разрешается или удвоить количество камней в меньшей куче(если их две – то в каждой из них), или добавить по 1 камню в каждую из всех трех куч. Выигрывает тот игрок, после хода которого во всех трех кучах суммарно становится не менее 23 камней. Игроки ходят по очереди. Выяснить, кто выигрывает при правильной игре – первый или второй игрок. Ответ обоснуйте.
  

• 

  22 слайд

  При правильной стратегии выигрывает второй игрок при любом ходе первого игрока.
  Ход второго игрока может быть одним из следующих:
  

• 

  23 слайд

  Задание для самостоятельного выполнения:
  Два игрока играют в следующую игру. На координатной плоскости стоит фишка. Игроки ходят по очереди. В начале игры фишка находится в точке с координатами (2, 3). Ход состоит в том, что игрок перемещает фишку из точки с координатами (x, y) в одну из трех точек: или в точку с координатами (2x, y), или в точку с координатами (x, 2y), или в точку с координатами (x, y+2). Выигрывает игрок, после хода которого расстояние от фишки до точки с координатами (0, 0) больше 13 единиц. Кто выигрывает при безошибочной игре обоих игроков – игрок, делающий первый ход, или игрок, делающий второй ход? Каким должен быть первый ход выигрывающего игрока? Ответ обоснуйте.
  

• 

  24 слайд

  Вывод: выигрывает второй игрок при любом ходе первого игрока.
  Первый ход второго игрока может быть 4,3 - 4,6 или 2,5 - 4,5.
  

• 

  25 слайд

  Основные ошибки при выполнении задания:
  неверно подсчитаны координаты точки 2% учащихся;
  1,5 % учащихся не учла изменения условия задачи (решали на «камушки»);
  • неверно указали выигравшего игрока (19%);
  • неверно указали первый ход выигравшего игрока (7%);
  • 1,5% учащихся в приведенном решении явно не выделили ответ на вопрос задачи (не указано, кто выигрывает, какой первый ход он должен сделать;
  5% - не указали все варианты ходов играющих.
  23% - стратегия игры описана неверно или отсутствует вовсе (бездоказательно).
  

• 

  26 слайд

  Задание С4
  Уровень сложности: высокий
  Максимальный балл: 4
  Время на выполнение: 60 минут.
  Решаемость – 22 %
  Процедуры и функции для обработки текстовых файлов:
  assign – сопоставляет переменную и внешний файл;
  reset – открыть файл на чтение;
  rewrite – открыть файл на запись;
  аppend – открыть файл для дописывания информации;
  close – закрыть открытый файл;
  eof – проверяет, достигнут ли конец файла;
  eoln – достигнут ли при чтении конец строки;
  SeekEof – проверяет, достигнут ли конец файла, пропуская разделители;
  SeekEoln – проверяет, достигнут ли конец строки при чтении из файла, пропуская разделители;
  read (readln) – считывает одно или более значений из файла в одну или более переменных;
  write (writeln) – записывает одно или более значений в файл;
  

• 

  27 слайд

  Тип record
  Например: в строке записана:
  Иванов 1993 м
  
  var person: record
  fio: string;
  g: integer;
  p: char
  end;
  

• 

  28 слайд

  Пример 1. Обработка символьных величин:
  Текст на русском языке записан в массиве a[1...500] of char. Помимо русских букв в нём встречаются пробелы и знаки препинания. В массиве p[‘А’..’Я’] of integer необходимо записать сведения о том, сколько каких букв встречается в этом тексте. При подсчете строчные и прописные буквы не различаются.
  На вход программы подается значение n<=500 – количество букв в тексте. В следующей строке входных данных расположены сами буквы (без разделителей).
  
  Решение: Программа должны учитывать, что в тексте встречаются другие символы, отличные от букв.
  

• 

  29 слайд

  Программа на Паскале:
  var a:array [1..N] of char;
  p:array[1..33] of integer;
  i: integer; c:char;
  begin
  readln(N);
  for c := ‘А’ to ‘Я’ do p(c):=0;
  for i:=1 to N do
  if a[i] in [‘A’..’Я’,’а’..’я’] then
  begin
  c:=upcase(a[i]);
  p(c):=p(c)+1;
  end;
  for c := ‘А’ to ‘Я’ do writeln(c,’ - ’,p(c))
  end.
  

• 

  30 слайд

  Пример 2. Обработка символьных величин:
  Определить, сколько букв содержит самое длинное слово во введенной строке символов. На вход программы подается строка, состоящая не более чем из 255 символов. Слова разделены одним или несколькими пробелами. Вывести искомое число.
  Решение: использование признака конца слова ‘ ‘ (пробел).
  readln(s);
  s:=s+’ ‘;
  max:=0
  k:=0;
  for i:=1 to length(s) do
  begin
  if s[i] <> “ ‘ then k:=k+1
  else
  begin
  if k>max then max:=k;
  k:=0;
  end;
  end;
  writeln(max);
  

• 

  31 слайд

  Пример 3. Обработка записей:
  На вход программы подаются сведения о результатах экзаменов выпускников 11-х классов школы. В первой строке вводится количество выпускников N. Сведения о каждом выпускнике имеют формат:
  <Фамилия> <Имя> <Класс> <Оценки>
  Здесь <Фамилия> - строка, состоящая не более чем из 20 символов;
  <Имя> - строка, состоящая не более чем из 15 символов;
  <Класс> - номер класса и буква;
  <Оценки> - строка, содержащая оценки за экзамены выпускника, причем количество оценок у учащихся может быть различным.
  <Фамилия>, <Имя>, <Класс> ,<Оценки> разделены одним пробелом.
  Напишите программу, которая будет выводить фамилии и имена тех выпускников 11 А класса, у которых нет двоек и троек и средний балл больше, чем 4,5.
  

• 

  32 слайд

  Программа на Паскале:
  var p: record
  name: string;
  sum: integer;
  end;
  c: char;
  n, m, k, i: integer;
  b: boolean;
  begin
  readln(n);
  for i:=1 to n do
  begin
  p.name:=‘’;
  repeat
  read(c);
  p.name:=p.name+с;
  until c:=‘ ‘;
  repeat
  read(c);
  p.name:=p.name+с;
  
  until c:=‘ ‘;
  repeat
  read(c);
  until c:=‘ ‘;
  p.sum:=0;
  b:=true;
  n:=0;
  while not eoln do
  begin
  read(m);
  if m in [2,3] then b:=false
  else p.sum:=p.sum+m;
  n:=n+1
  end;
  if b and p.sum>4.5*n and c:=‘А’ then writeln(p.name);
  readln;
  end;
  end.
  

• 

  33 слайд

  Пример 3. Обработка записей при чтении из файла:
  Сведения о результатах экзаменов выпускников 11-х классов школы записаны в файле input.txt. Сведения о каждом выпускнике имеют формат:
  <Фамилия> <Имя> <Класс> <Оценки>
  Здесь <Фамилия> - строка, состоящая не более чем из 20 символов;
  <Имя> - строка, состоящая не более чем из 15 символов;
  <Класс> - номер класса и буква;
  <Оценки> - строка, содержащая оценки за экзамены выпускника, причем количество оценок у учащихся может быть различным.
  <Фамилия>, <Имя>, <Класс> ,<Оценки> разделены одним пробелом.
  Запишите в файл output.txt фамилии и имена тех выпускников 11 А класса, у которых нет двоек и троек и средний балл больше, чем 4,5.
  

• 

  34 слайд

  Программа на Паскале:
  var p: record
  name: string;
  sum: integer;
  end;
  c: char;
  n, m, k, i: integer;
  b: boolean;
  input, output: text
  begin
  assign(v,’input’);
  reset (v);
  assign(o,’output’);
  rewrite(o);
  repeat
  p.name:=‘’;
  repeat
  read(v,c);
  ……
  while not seekeoln do
  ………
  readln(v);
  end;
  until seekeof(v);
  close(o)
  end.
  

• 

  35 слайд

  Пример 4. Обработка записей:
  На вход программе передается число N. Затем идет N строк, участников олимпиады разных школ, следующего формата:
  < Фамилия > < Инициалы > < Номер школы >.
  Номер школы не более чем двухзначное число.
  Требуется написать программу, которая выведет номер школы (школ), с которых в олимпиаде участвовало больше всего учеников.
  

• 

  36 слайд

  Программа на Паскале:
  var s : array[1 .. 99] of integer;   
  { Количество учеников с i-той школы }   
  n, i, sn, max : integer;          
  { N, i, номер школы, макс. кол-во учеников }   
  c : char;    { для хранения «лишней»
  информации }
  begin
  for i := 1 to 99 do
  s[i] := 0;
  readln(n);
  max := 0;
  for i := 1 to n do
  begin   
  repeat       
  read(c);   
  until c = ' ';{ Пропуск фамилии}   
  repeat       
  read(c);   
  until c = ' ';  { Пропуск инициалов }  
  readln(sn);   { Считывание № школы } 
  s[sn] := s[sn] + 1;              
      if s[sn] > max then max := s[sn];
  end;
  if max < > 0 then
  begin   
  for i := 1 to 99 do
  begin       
  if s[i] = max then writeln(i);   
  end;
  end;
  end.
  

• 

  37 слайд

  http://www1.ege.edu.ru
  Статистические данные взяты с сайта:
  Список использованной литературы:
  1. Андреева Е.В. Методика обучения основам программирования, 2006 г.
  2. А. Шень Программирование: теоремы и задачи, М.: МЦНМО, 2004.