6.Информационные массивы

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

1) абитуриент может выбрать любого экзаменатора и сдать ему один из экзаменов;

2) результаты сдачи каждый экзаменатор записывает в сводную таблицу:

Фамилия абитуриента

Предмет

Оценка

3) абитуриент должен сдать два разных экзамена только по одному разу.

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

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

1) сданы два разных экзамена;

2) получены оценки больше 2.

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

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

const NM=1000;

var fam : array [1..NM] of string[20];

predm : array [1..NM] of string[20];

ball : array [1..NM] of integer;

rez : array [1..NM div 2] of integer;

{номера записей входной таблицы с фамилиями успевающих}

sum_bl : array [1..NM div 2] of integer;

{сумма баллов}

nb : array [1..NM div 2] of integer;

s : array [1..NM] of integer;

n, {количество записей во входной таблице}

k, {количество абитуриентов, допущенных к конкурсу}

i, j, nach, kon, wr : integer;

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

{косвенное упорядочение по фамилиям:}

for i:=1 to n do s[i]:=i;

for i:=1 to n-1 do

for j:=1 to n-i do

if fam[s[j]] > fam[s[j+1]] then

begin wr:=s[j]; s[j]:=s[j+1]; s[j+1]:=wr; end;

nach:=1; k:=0;

while nach < n do

begin i:=nach;

{выделение групп одинаковых фамилий:}

while (i<=n-1) and (fam[s[i]]=fam[s[i+1]]) do

i:=i+1;

kon:=i;

if (kon-nach+1=2) and

(predm[s[nach]]<>predm[s[kon]]) and

((ball[s[nach]]>=3) and (ball[s[kon]]>=3)) then

begin k:=k+1;

rez[k]:=s[nach];

sum_bl[k]:=ball[s[nach]]+ball[s[kon]];

end;

nach:=kon+1;

end;

{косвенное упорядочение по сумме баллов:}

for i:=1 to k do nb[i]:=i;

for i:=1 to k-1 do

for j:=1 to k-i do

if sum_bl[nb[j]] < sum_bl[nb[j+1]] then

begin

wr:=nb[j]; nb[j]:=nb[j+1]; nb[j+1]:=wr

end;

writeln('ведомость успевающих');

for i:=1 to k do

writeln(fam[rez[nb[i]]]:25, sum_bl[nb[i]]:3)

end.

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

добиться трудоемкости порядка n log ₂ n.