Дан
список результатов сдачи экзамена учащимися школ некоторого района, с
указанием фамилии и имени учащегося, номера школы и итогового балла.
Напишите
эффективную по времени работы и по используемой памяти программу
(укажите используемую версию языка программирования, например, Borland
Pascal 7.0), которая определяет список школ, в которых средний балл на
экзамене, набранный учащимися из данной школы выше, чем средний балл по
всему району.
На вход программе в первой сроке подается количество учащихся во всех школах района N.В каждой из последующих N строк находится информация в следующем формате:
<Фамилия> <Имя> <Номер школы> <Балл>
где <Фамилия> – строка, состоящая не более, чем из 20 символов без пробелов,
<Имя> – строка, состоящая не более, чем из 20 символов без пробелов,
<Номер школы> – число от 1 до 99,
<Балл> - число от 0 до 100.
Порядок следования строк – произвольный.
Пример входных данных:
6
Иванов Сергей 1 90
Сергеев Петр 21 80
Петров Кирилл 31 70
Кириллов Егор 1 80
Егоров Николай 21 90
Николаев Иван 31 70
Программа
должна определить количество школ в районе, в которых средний балл на
экзамене, набранный учащимися из данной школы выше, чем средний балл по
всему району и вывести сначала количество таких школ, а в следующей
строке – номера этих школ через пробел. Пример вывода для приведенного
выше примера ввода:
21 21
При выполнении задания следует учитывать, что значение N может быть велико (до 10.000).
Решение задачи №2.
var
SchoolSum, SchoolCount:array [1..99] of integer; {задаем два целочисленных массива, первый массив SchoolSum будет считать сколько баллов набрали ученики конкретной школы, второй массив SchoolCount будет считать количество учеников конкретной школы}
TotalSum, Answer, i, N, Ball, School:integer; {задаем целочисленные переменные: TotalSumm - общая сумма баллов всех школ, Answer - количество школ набравших средней балл выше среднего балла района, i - переменная счетчик, N - количество учащихся всего мониторинга, Ball - количество баллов каждого ученика, School - номер школы}
c: char; {символьная переменная для чтения фамилии и имени}
begin
TotalSum := 0; {начальное значение суммы общих баллов мониторинга равно 0}
for i := 1 to 99 do {задаем цикл (c 1 до 99, так как по условию задачи в мониторинге участвуют до 99) школ для обнуления массивов}
begin
SchoolSum[i] := 0; {начальное значение суммы балов каждой школы равно 0}
SchoolCount[i] := 0 {начальное значение суммы учеников каждой школы равно 0}
end;
Readln(N); {вводим с клавиатуры количества учеников участвующих в мониторинге, переменной N присваиваем значение количества участников мониторинга}
for i:=1 to n do {задаем цикл для ввода с клавиатуры участников мониторинга}
begin
repeat {для того чтобы считать символы фамилии запускаем цикл, который считывает каждый символ до пробела}
Read(c) {считываем символы до пробела}
until c=' '; {проверяем условие с=' ' (является ли символ пробелом), если символ пробел выходим из цикла (прекращаем считывание названия компании}
repeat {задаем цикл для считывания имени аналогично предыдущему циклы}
Read(c)
until c=' ';
Readln(School, Ball); {считываем номер школы (School) и количество баллов (Ball)}
SchoolSum[School] := SchoolSum[School]+Ball; {массив SchoolSum c индексом номера школы School (SchoolSum[School]) увеличивает свое значение на величину балла}
SchoolCount[School]:=SchoolCount[School]+1; {массив SchoolCou c индексом номера школы (ShoolCount[School]) увеличивает свое значение на единицу}
TotalSum:=TotalSum+Ball; {переменная TotalSum увеличивает свое значение на величину балла}
end; {после прохода всего цикла мы ввели с клавиатуры данные, массив SchoolSum для каждой школы посчитал количество баллов, массив SchoolCount посчитал количество учеников каждой школы}
Answer:=0; {начальное значение переменной Answer равно 0}
for i:=1 to 99 do {запускаем цикл, чтобы определить количество школ набравших средний бал выше среднего балла по району}
if SchoolSum[i]*N>TotalSum*SchoolCount[i] {сравниваем средний балл каждой школы со средним баллом по району}
then
Answer:=Answer+1; {если у школы средний балл выше, то переменная Answer увеличивает свое значение на 1}
WriteLn(Answer); {выводим на экран количество школ у которых средний бал выше среднего балла по району}
for i:=1 to 99 do {запускаем цикл, чтобы вывести на экран все школы со средним баллом выше чем средний балл по району}
if SchoolSum[i]*N>TotalSum*SchoolCount[i] {сравниваем средний балл каждой школы со средним баллом по району}
then Write(i, ' ') {если средний балл выше, то выводим на экран номер школы (индекс массива), а затем пробел}
end.
Алгоритм решения задачи:
- Задаем цикл в котором вводим с клавиатуры данные по всем ученикам.
- В этом же цикле подсчитываем количество баллов каждой школы, количество учеников каждой школы, участвующих в мониторинге, и общее количество баллов по району.
- Далее нам необходимо сравнить количество среднего балла каждой школы со средним баллом по району, если средний балл школы по школе больше среднего по району, то счетчик увеличивается на единицу. Выводим результат.
- Для вывода номеров школы, снова сравниваем средний баллы школы и района, и выводим номера школ у которых средний балл больше.
Обратите внимание на сравнение средних результатов школы и района. В Программе это строки if SchoolSum[i]*N>TotalSum*SchoolCount[i]. Для улучшения производительности программы мы не будем использовать следующее сравнение SchoolSum[i]/SchoolCount[i]>TotalSum/N,
так как при таком сравнении программа будет сравнивать дробные цифры
(из-за деления чисел), что уменьшает производительность программы.
Чтобы сравнивать целые числа, преобразовываем неравенство SchoolSum[i]/SchoolCount[i]>TotalSum/N в следующее неравенство SchoolSum[i]*N>TotalSum*SchoolCount[i], при таком варианте сравниваются целые числа. Если вы используете в своей программе деление, то вам снизят балл с 4 до 3.
Возврат к списку задач