Подготовка к ЕГЭ. Часть С. C4: Обработка данных, вводимых в виде символьных строк (написать программу средней сложности из строк).

Задача 1. На вход программе подаются сведения о номерах школ учащихся, участвовавших в олимпиаде. В первой строке сообщается количество учащихся N, каждая из следующих N строк имеет формат: где – строка, состоящая не более чем из 20 символов, – строка, состоящая из 4-х символов (буква, точка, буква, точка), – не более чем двузначный номер. и, а также и разделены одним пробелом. Пример входной строки: Иванов П.С. 57 Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран информацию, из какой школы было меньше всего участников (таких школ может быть несколько). При этом необходимо вывести информацию только по школам, пославшим хотя бы одного участника. Следует учитывать, что N>=1000.

Как правильно понимать условие? 1) на первый вопрос – как именно вводятся данные – находим ответ в самом начале условия: вроде бы «дежурная» фраза «на вход программе подаются…» означает, что данные нужно читать не из файла, а со стандартного входного потока; это, в свою очередь, значит, что можно использовать привычные операторы read (readln), предполагая, что кто-то вводит эти данные с клавиатуры вручную 2)итак, сначала вводится количество записей в файле N, а затем N строк с информацией; заметим, что из всей этой информации нас интересует (в каждой строке) только номер школы, остальное можно просто отбрасывать 3) номер школы стоит после второго пробела в строке 4) « – не более чем двузначный номер» – крайне важная информация; она и позволяет найти хорошее решение задачи - школ не более 99! 5) что означает выражение «как можно более эффективная программа»? прежде всего, данные читаются только один раз, за один проход, нельзя «вернуться» и прочитать что-то вновь

в программе не выполняются никакие лишние действия используемые алгоритмы имеют минимальную сложность расходуется минимальный возможный объем памяти; например, чтобы найти количество отрицательных элементов массива, не нужно вводить второй массив; если нам достаточно держать в памяти одну введенную строку, не нужно одновременно хранить все прочитанные строки 6) зачем нужно уточнение «N>=1000»? этим авторы задачи намекают на то, что не нужно считывать все данные в оперативную память, а потом уже их обрабатывать; основная обработка должна быть сделана сразу, в том же цикле, где читаются входные данные 7) будем считать, что в исходных данных нет ошибок (так принято на олимпиадах и экзаменах), иначе обработка разнообразных ошибок будет составлять основную часть программы

Решение: 1. по условию, единственная информация, которая нужна в итоге для вывода результата – это количество участников по каждой школе 2. так как номер школы состоит (по условию!) не более, чем из двух цифр, всего может быть не более 99 школ (с номерами от 1 до 99) 3. поэтому можно ввести массив C из 99 элементов; для всех k от 1 до 99 элемент C[k] будет ячейкой-счетчиком, в которой накапливается число участников от школы с номером k; сначала во все элементы этого массива записываются нуль (обнуление счетчиков): for k:=1 to 99 do C[k]:=0; («счетчик необходимо сначала обнулить») 4. основной цикл обработки вводимых строк : for i:=1 to N do begin { читаем очередную строку } { определяем номер школы k } C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы } end;

5. поскольку данные вводятся в виде символьной строки, нужно выделить в памяти переменную s типа string 6. для чтения очередной строки будем использовать оператор readln 7. как выделить из строки номер школы: по условию он закодирован в последней части строки, после второго пробела; значит, нужно найти этот второй пробел, вырезать из строки весь «хвост» после этого пробела, и преобразовать его из символьного формата в числовой 8. чтобы найти первый пробел и «отрезать» первую часть строки с этим пробелом, можно использовать команды p := Pos(' ', s); s := Copy(s, p+1, Length(s)-p); первая команда определяет номер первого пробела и записывает его в целую переменную p, в вторая – записывает в строку s весь «хвост», стоящий за этим пробелом, начиная с символа с номером p+1; длина хвоста равна Length(s)-p, где Length(s) – длина строки;

9. поскольку нас интересует часть после второго пробела, эти две строчки нужно повторить два раза, в результате в переменной s окажется символьная запись номера школы, для преобразования ее в форму числа можно использовать функцию Val: Val(s, k, r); эта процедура (Turbo Pascal, Borland Pascal, PascalABC, среда АЛГО) преобразует символьную строку s в числовое значение k; с помощью переменной r обнаруживается ошибка: если раскодировать число не удалось (в строке не число), в r будет записан нуль (здесь мы не будем обрабатывать эту ошибку, полагая, что все данные правильные); 10. таким образом, основной цикл выглядит так: for i:=1 to N do begin readln(s); { читаем очередную строку } { выделяем часть после второго пробела } p := Pos(' ', s); s := Copy(s, p+1, Length(s)-p); p := Pos(' ', s); s := Copy(s, p+1, Length(s)-p); { определяем номер школы k } Val(s, k, r); C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы } end;

11. можно избежать дублирования двух строк в теле цикла, «свернув» их во внутренний цикл, но это вряд ли сильно упростит запись: for k:=1 to 2 do begin p := Pos(' ', s); s := Copy(s, p+1, Length(s)-p); end; 12. дальше стандартным алгоритмом определяем в массиве C минимальный элемент Min, не учитывая нули (школы, из которых не было участников): Min := N; for k:=1 to 99 do if (C[k] 0) and (C[k]

14. полное решение (максимальное количество школ мы задали в виде константы LIM): const LIM = 99; var C:array[1..LIM] of integer; i, p, N, k, r, Min: integer; s:string; BEGIN readln(N); for i:=1 to N do begin readln(s); { читаем очередную строку } { выделяем часть после второго пробела } p := Pos(' ', s); s := Copy(s, p+1, Length(s)-p); p := Pos(' ', s); s := Copy(s, p+1, Length(s)-p); { определяем номер школы k } Val(s, k, r); C[k] := C[k] + 1; { увеличиваем счетчик k-ой школы } end; Min := N; for k:=1 to LIM do if (C[k] 0) and (C[k]

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

проверьте, правильно ли заданы (и заданы ли вообще) начальные значения для всех переменных будьте внимательны, когда в массиве есть «мертвые» элементы, которые не нужно учитывать; проверяйте, что в этом случае ваши алгоритмы (например, поиск минимального элемента) работают правильно проверьте, правильно ли расставлены операторные скобки begin- end, ограничивающие тело цикла; их обязательно нужно ставить, если в теле цикла несколько операторов при использовании функции Pos не забывайте, что первый параметр – что ищем (образец), а второй – где ищем чтобы эксперту было легче понять вашу программу (особенно, если она получилась «нестандартной»), пишите комментарии; объясняйте, что хранится в основных переменных если это возможно, желательно работать только с целыми числами; этим вы избежите проблем, связанных с округлением и неточностью хранения дробных вещественных чисел в памяти компьютера

На вход программе подаются сведения о сдаче экзаменов учениками 9-х классов некоторой средней школы. В первой строке сообщается количество учеников N, которое не меньше 10, но не превосходит 100, каждая из следующих N строк имеет следующий формат:, где – строка, состоящая не более чем из 20 символов, – строка, состоящая не более чем из 15 символов, – через пробел три целых числа, соответствующие оценкам по пятибалльной системе. и, а также и разделены одним пробелом. Пример входной строки: Иванов Петр Требуется написать как можно более эффективную программу (укажите используемую версию языка программирования, например, Borland Pascal 7.0), которая будет выводить на экран фамилии и имена трех худших по среднему баллу учеников. Если среди остальных есть ученики, набравшие тот же средний балл, что и один из трех худших, то следует вывести и их фамилии и имена.