Как правильно понимать условие?

1) как и в предыдущей задаче, данные «подаются на вход программе», то есть, их можно читать с помощью операторов read (readln), предполагая, что кто-то вводит эти данные с клавиатуры вручную

2) «количество учеников не меньше 10, но не превосходит 100», здесь только вторая часть – полезная информация, она намекает на то, что придется все введенные данные одновременно держать в памяти, выделив массив (или массивы) размером 100 элементов

3) сказано, что фамилия имеет длину не более 20 символов, а имя – не более 15; здесь, по сути, важно лишь то, что фамилия и имя (вместе) занимают меньше 255 символов, то есть, «влезут» в стандартное ограничение (255 символов) для типа string в классических версиях Паскаля

4) после фамилии и имени записаны три оценки (а не одно число, как в прошлой задаче), причем по условию нас НЕ интересуют эти числа, а интересует только средний балл каждого ученика;

5) важно! средний балл – это вещественное число (может иметь дробную часть), тут уже стоит задуматься: все задачи обычно составляются так, чтобы они решались «хорошо», в то же время операции с дробными числами (почти) всегда выполняются с ошибками, поскольку большинство вещественных чисел нельзя точно (стандартными методами) представить в памяти реального компьютера

6) следующий шаг к правильному решению: поскольку число оценок у всех учеников одинаковое, средний балл для каждого это сумма его оценок, деленная на 3; поэтому вместо среднего балла мы можем сравнивать суммы баллов – целые числа!

7) требуется вывести фамилии и имена (баллы не нужны!) трех худших учеников, причем их может быть и больше, если несколько «худших» набрали одинаковую сумму баллов

8) если бы требовался один худший – все решается поиском по массиву; первая идея – найти самого худшего (1 проход), затем – 2-ого с конца (еще 1 проход), и, наконец, 3-его (всего три прохода по массиву)

9) это не лучший вариант (на экзамене будут сняты баллы) по двум причинам:

o в таком методе решения три прохода по массиву, а в самом деле достаточно одного (см. далее), значит, программа неэффективна

o непонятно, что делать в том случае, если худших – больше трех (в предельном случае – вообще все!) – за это также снимут баллы (программа работает не для всех вариантой входных данных)

10) возникает следующий вариант – отсортировать массив про возрастанию суммы (и, следовательно, среднего балла), одновременно переставляя имена и фамилии, а затем вывести самых худших, которые после сортировки окажутся в начале массива

11) этот вариант тоже плох, потому что программа неэффективна; «школьные» алгоритмы сортировки (метод «пузырька», метод выбора) имеют сложность , а надо попытаться найти метод со сложностью

Решение (общий подход):

1) сначала составим программу в самом общем виде на псевдокоде, чтобы определить ее основные блоки, а потом будем их постепенно «расшифровывать» через операторы языка программирования:

{ читаем все данные и запоминаем их }

{ находим три худших результата }

{ выводим фамилии и имена тех, чей результат меньше или

равен «третьему худшему» }

2) до того, как начать писать «нормальный» код, нужно определить, как хранить данные; в данном случае нужно запомнить несколько данных по каждому ученику, их удобнее объединить в запись с двумя полями (фамилия-имя и сумма баллов); таких записей нужно выделить в памяти не менее 100 (по условию), то есть, массив из 100 элементов:

const LIM=100;

var Info: array[1..LIM] of record

name: string;

sum: integer;

end;

Чтение данных:

3) после того, как мы прочитали фактическое число учеников N, в цикле считываем и расшифровываем информацию о них, сохраняя все данные в структурах

for i:=1 to N do begin

{ считываем строку данных }

Info[i].name:= { фамилия и имя };

Info[i].sum:= { сумма баллов };

end;

4) здесь, в принципе, можно использовать тот же подход, что и в первой задаче – читаем строку целиком, затем «разбираем» ее на части с помощью стандартных функций – однако, для разнообразия, мы используем другой подход – будем читать информацию посимвольно, то есть, считывая по одному символу в переменную c типа char;

5) сначала в поле name очередной структуры записываем пустую строку '' (в которой нет ни одного символа, длина равна нулю)

Info[i].name:= ''; { пустая строка }

6) затем считываем символы фамилии и сразу приписываем их в конец поля name:

Repeat

read (c);

Info[i].name:= Info[i].name + c;

until c = ' '; { пока не прочитали пробел }

7) затем также читаем из входного потока имя, до пробела, и записываем его в конец того же поля name:

Repeat

read (c);

Info[i].name:= Info[i].name + c;

until c = ' '; { пока не прочитали пробел }

заметьте, что эти два цикла одинаковы, поэтому ввод имени и фамилии можно записать в виде вложенного цикла так:

Info[i].name:= ''; { пустая строка }

for k:=1 to 2 do

Repeat

read (c);

Info[i].name:= Info[i].name + c;

until c = ' '; { пока не прочитали пробел }

8) важно! обратите внимание, что для организации внутреннего цикла используется другая переменная, k (а не i, потому что i – переменная главного цикла, она обозначает номер текущего ученика)

9) теперь во входном потоке остались три числа, которые мы можем последовательно считывать в целую переменную mark, а затем – добавлять к полю Info[i].sum:

Info[i].sum:= 0;

for k:=1 to 3 do begin

read(mark);

Info[i].sum:= Info[i].sum + mark;

end;

readln;

10) последняя команда readln пропускает все оставшиеся символы до новой строки (из этой мы прочитали все, что нужно)

11) вот полный цикл ввода данных, после его окончания все исходные данные будут записаны в первые N записей массива Info:

for i:=1 to N do begin

{ ввод имени и фамилии }

Info[i].name:= '';

for k:=1 to 2 do

Repeat

read(c);

Info[i].name:= Info[i].name + c;

until c = ' ';

{ ввод и суммирование оценок }

Info[i].sum:= 0;

for k:=1 to 3 do begin

read(mark);

Info[i].sum:= Info[i].sum + mark;

end;

readln;

end;

Поиск трех худших данных:

12) теперь нужно придумать, как за один проход по массиву найти три худших результата;

13) как бы мы решили эту задачу, если бы нам нужно было просмотреть столбик чисел и найти три минимальных? можно сделать, например, так:

o на бумажке вести записи в три столбика, в первом записывать минимальное число, в втором – следующее по величине, в третьем – «третье минимальное»

o сначала пишем первое число в первый столбик, оно – минимальное, потому что других мы не еще видели; пусть это число 14:

o пусть следующее число – 12; оно меньше минимального, поэтому его нужно записывать в первый столбец, а «старое» минимальное число «переедет» во второй столбец

o пусть дальше идет число 10 – теперь оно станет минимальным, его нужно записывать в первый столбец; при этом 12 «переедет» из первого столбца во второй, а 14 – из второго в третий

o пусть следующее число – 11; оно больше минимального, но меньше «второго», поэтому его нужно поставить во второй столбец; число 12 из второго столбца перемещается в третий, а число 14 из третьего столбца удаляется из кандидатов в «три минимальных»

o просмотрев таким образом весь столбик чисел, за один проход (!) можно найти три минимальных элемента

o остается только переложить этот алгоритм на язык программирования

14) выделим в памяти три целых переменных: min1 (минимальный), min2 («второй минимальный»), min3 («третий минимальный»), в виде начальных значений запишем в каждую из них число, заведомо превышающее максимальную возможную сумму трех оценок, например, 20 (>5+5+5)

15) полный цикл поиска выглядит так:

min1:= 20; min2:= 20; min3:= 20;

for i:=1 to N do begin

if Info[i].sum < min1 then begin { новый min1 }

min3:= min2; min2:= min1;

min1:= Info[i].sum;

End

else if Info[i].sum < min2 then begin { новый min2 }

min3:= min2;

min2:= Info[i].sum;

End

else if Info[i].sum < min3 then { новый min3 }

min3:= Info[i].sum;

end;

16) обратим внимание на два момента: во-первых, когда переезжают два элемента, сначала нужно перемещать второй на место третьего, а потом – первый на место второго:

min3:= min2;

min2:= min1;

эти операторы нельзя менять местами, иначе «старое» значение min2 будет потеряно;

во-вторых, если проверять условие Info[i].sum < min2 нужно только тогда, когда очередная сумма не меньше, чем min1, поэтому каждый следующий условный оператор стоит в else -блоке предыдущего, то есть, выполняется только тогда, когда предыдущий не сработал

17) итак, мы нашли три минимальных результата, и остается вывести на экран фамилии и имена тех, у кого сумма баллов меньше или равна min3:

for i:=1 to N do

if Info[i].sum <= min3 then

writeln(Info[i].name);

18) на всякий случай приведем полную программу, она получилась довольно длинная

const LIM = 100;

var Info: array[1..LIM] of record

name: string;

sum: integer;

end;

i, k, N, mark, min1, min2, min3: integer;

c: char;

Begin

readln(N);

{ ввод исходных данных }

for i:=1 to N do begin

Info[i].name:= '';

for k:=1 to 2 do

Repeat

read(c);

Info[i].name:= Info[i].name + c;

until c = ' ';

Info[i].sum:= 0;

for k:=1 to 3 do begin

read(mark);

Info[i].sum:= Info[i].sum + mark;

end;

readln;

end;

{ поиск трех минимальных }

min1:= 20; min2:= 20; min3:= 20;

for i:=1 to N do begin

if Info[i].sum <min1 then begin

min3:= min2; min2:= min1;

min1:= Info[i].sum;

End

else if Info[i].sum <min2 then begin

min3:= min2;

min2:= Info[i].sum;

End

else if Info[i].sum <min3 then

min3:= Info[i].sum;

end;

{ вывод результата }

for i:=1 to N do

if Info[i].sum <= min3 then

writeln(Info[i].name);

End.

19) эту задачу можно решить и без записей, используя два массива: массив символьных строк name и массив целых чисел sum, они объявляются так:

var name: array[1..MAX] of string;

sum: array[1..MAX] of integer;

после этого в приведенной программе нужно заменить везде Info[i].name на name и Info[i].sum на sum.

На что обратить внимание: · в исходных данных выделите то, что не нужно для решения задачи; при чтении эти части можно просто пропускать; · если нам не нужны фамилия и имя отдельно, можно хранить их вместе, в виде одной строки · если нас интересует только сумма оценок, не нужно хранить их в памяти по отдельности · если можно при решении задачи обойтись без вещественных чисел, сделав все вычисления только с целыми числами – нужно поступить именно так (иначе снимут баллы), поскольку операции с вещественными числами во многих случаях случаев выполняются неточно · алгоритм сложности (например, сортировку) нужно использовать только тогда, когда нет алгоритма сложности ; как правило, в задачах ЕГЭ такой алгоритм всегда можно (попытаться) найти; за неэффективный алгоритм при оценке решения будут сняты баллы

За что снимают баллы: · программа работает не для всех исходных данных, не обрабатывает некоторые частные случаи · неверно реализован алгоритм поиска минимального элемента, сортировки и т.п. · неэффективность алгоритма: o используется алгоритм, имеющий сложность , когда есть алгоритм сложности o используется несколько проходов по массиву, когда достаточно одного o лишний расход памяти (используются дополнительные массивы или размер массива определен неверно) o используются операции с вещественными числами, когда можно все решить в целых числах · переменная не описана или описана неверно · переменным не присвоены нужные начальные значения (например, не обнуляются счетчики) или присвоены неверные значения · нет вывода результата в конце программы · перепутаны знаки < и >, логические операции or и and · применяется недопустимая операция, например, div или mod для вещественных чисел · неверно расставлены операторные скобки begin-end · в цикле for используется вещественная переменная (Паскаль) · в цикле while или repeat не изменяется переменная цикла, из-за чего происходит зацикливание · синтаксические ошибки (знаки пунктуации – запятые, точки, точки с запятой; неверное написание ключевых слов); чтобы получить 4 балла, при абсолютно верном решении нужно сделать не более одной синтаксической ошибки; на 3 балла – до трех ошибок, на 2 балла – до пяти и на 1 балл – до семи ошибок

[1] Крылов С.С., Ушаков Д.М. ЕГЭ 2010. Информатика. Тематическая рабочая тетрадь. — М.: Экзамен, 2010.

[2] Для разделения имен каталогов в адресе в разных операционных системах применяют прямой слэш «/» или обратный слэш «\». В системе Windows, которая наиболее распространена в России, стандартным разделителем считается «\», именно такой знак чаще всего используется в задачах ЕГЭ.

[3] Интересующиеся могут посмотреть на коды русских букв в кодировке КОИ-8R

и ужаснуться, осознав, что было бы при использовании букв В и Г.

[4] Самылкина Н.Н., Островская Е.М. Информатика: тренировочные задания. – М.: Эксмо, 2009.

[5] Огастес (Август) де Морган – шотландский математик и логик.

[6] … но которая, к сожалению, почти не нужна на практике. J

[7] Часто килобайт обозначают «Кб», а мегабайт – «Мб», но в демо-тестах разработчики ЕГЭ привели именно такие обозначения.

[8] Фактически это не другой способ решения, а более строгое обоснование предыдущего алгоритма.

[9] Здесь рассматривается только язык Паскаль, который является наиболее распространенным в школах России.

[10] В этом примере используется стандартная нумерация для Паскаля: индексы начинаются с единицы.

[11] Т.Е. Чуркина. ЕГЭ. Информатика. Практикум по выполнению типовых тестовых заданий ЕГЭ.М.: Экзамен, 2010.

[12] В самом деле, есть кодировки с переменным количеством бит на символ, например, кодировка UTF-8, но они не изучаются в школе.

[13] Чаще всего килобайт обозначают «Кб», а мегабайт – «Мб», но в демо-тестах ЕГЭ разработчики привели именно такие обозначения.

[14] Используя ассемблер (язык машинных кодов с символьными командами), можно добраться до бита переноса и использовать его.

[15] Кроме логического сдвига вправо, о котором идет речь, есть еще арифметический, при котором старший бит не меняется.

[16] Здесь рассматривается только язык Паскаль, который является наиболее распространенным в школах России.

[17] Такая процедура называется топологической сортировкой графа.

[18] Здесь считается, что 1 Кбит = 1024 бит = 2¹⁰ бит.

[19] О.Б. Богомолова, Д.Ю. Усенков. Задача о передаче: решение задачи ЕГЭ с помощью диаграмм Ганта // Информатика, № 7, 2011.

[20] Каждая следующая область в полученном решении должна полностью включать предыдущую. Если это не так, тогда или вы ошиблись при построении таблицы истинности, или (не дай Бог!) в условии есть ошибка.

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

[22] Проверьте, что обычно (когда комбинации располагаются по возрастанию соответствующих двоичных чисел), столбец значений аргумента А представляет собой двоичную запись числа 15 = 1111₂, столбец значений аргумента В – числа 51 = 110011₂, столбец значений аргумента С – числа 85 = 10101010₂.

[23] Далее при разборе задачи используется язык Паскаль, который наиболее распространен в школах России.

[24] По традиции нумерация элементов массива в Паскале обычно начинается с единицы, далее N обозначает размер массива (количество элементов).

[25] Вообще говоря, в данной задаче не требуется находить номер минимального элемента, поэтому сначала можно записать в переменную min число 1000 – проверьте, что программа все равно выдаст верное значение.

[26] Или используется перенаправление входного потока из командной строки, но это уже абсолютно неважно…

Поиск по сайту: