АРХИВ СТАТЕЙ ЖУРНАЛА «МОЙ КОМПЬЮТЕР» ЗА 2003 ГОД

Конкурсы на ладони

Все журналы \ Номер 32/255 `2003 от 18.08.2003 \ Конкурсы на ладони

Дмитрий ПАВЛОВ dpav@ukrpost.net

Давным-давно, когда автор получил номер МК с результатами третьего трурлевого конкурса и подсчитал свой результат, оставляющий желать лучшего, он задался вопросом: а как же идут дела у остальных участников? Насколько лучше или хуже? Бодренько подсчитав результаты еще для двух участников, понял, что так дело не пойдет. А не поручить ли это дело компьютеру? Но для этого надо писать программу! Прикинув, что все равно это будет быстрее, чем считать вручную, я сделал выбор. Доставать с полки свой любимый Turbo Assembler почему-то не хотелось, однако на старых дискетах нашелся tpc.exe. Так появилась программа — герой этой статьи, о всех подробностях рождения которой я и хочу поведать читателям. Для этого давайте забудем, что программа уже написана, и представим, что есть только реальная жизненная задача…

Для начала предлагаю определиться, что нам нужно. Итак, мы будем писать программу, которая из результатов отдельных конкурсов будет определять суммарный результат — количество баллов, набранных каждым из участников, и эти суммарные результаты представлять в виде списка-рейтинга, отсортированного в порядке уменьшения суммарных баллов участников.

В самом общем виде задача поставлена, детали будем уточнять в процессе работы над алгоритмом. Однако алгоритма пока тоже никакого нет, поэтому предлагаю начать с самых общих соображений, описывая каждый шаг алгоритма сначала очень широко и постепенно конкретизируя. Это называется программированием сверху вниз, каковое считается очень хорошим тоном и помогает проектировать крупные программы. К сожалению (по себе знаю), не каждому удобен такой стиль — некоторые незаметно для себя переходят к противоположным принципам, «снизу вверх», основное внимание уделяя конкретным, не самым важным подпрограммам и деталям.

Оба стиля имеют и достоинства, и недостатки. Стиль «снизу вверх» дает оточенные, оптимизированные отдельные процедуры и подпрограммы, однако весьма трудозатратен, а также приводит к ситуации, когда за деревьями (отдельными подпрограммами) не видно леса (самой программы), причем чем деревьев больше, тем труднее. Стиль «сверху вниз» изначально оперирует более крупными блоками, поэтому здесь скорее виден лес, но не видно деревьев, из-за чего в целом программа получается неоптимальной. Идеальным является применение стиля «сверху вниз» на начальных этапах и «снизу вверх» на конечных.

Каждый программист может овладеть и тем, и другим стилем, однако предпочтения, по-видимому, индивидуальны и определяются психологическими различиями. Впрочем, это уже тема отдельной статьи.

Итак, опишем нашу будущую программу таким образом:

Конечно, можно придумать такие задачи, для которых любая из этих стадий не требуется, однако большая часть программ (и наша тоже) содержит именно такую последовательность операций.

Теперь попробуем конкретизировать каждый шаг. На шаге вывода данных, видимо, сделать пока ничего нельзя — нам просто нужно вывести отсортированный список. На этапе ввода, очевидно, необходимо ввести в компьютер результаты отдельных конкурсов, в общем случае их больше одного. Обработка явно распадается на стадию накопления данных и стадию сортировки. Последняя, понятно, проводится лишь после того, когда все данные введены. А в стадии накопления результат зависит лишь от текущих и уже введенных данных, поэтому его можно объединить со вводом.

Теперь надо произвести дальнейшую конкретизацию. Давайте подумаем над вводом-выводом. Очевидно, в данном случае лучший выход — ввод-вывод из файлов/в файл, так как перспектива вводить данные с клавиатуры вручную может понравится только Трурлю (он же робот, ему все равно :-)). Дальше, как вы заметили, я написал цикл в максимально общем виде, не задавая его тип. Давайте подумаем, какой именно тип цикла будет наилучшим здесь. Для цикла типа for обязательно надо знать число повторений. В нашем случае, конечно, это число известно — это количество конкурсов; однако эту величину нужно знать и компьютеру. А поскольку это величина переменная, ее надо либо ввести с клавиатуры (что неприятно, хотя и не настолько, как если бы пришлось вводить все результаты), либо из файла, однако в файл нам ее тоже придется вводить самим. А нельзя ли заставить компьютер подсчитывать эту величину?

Предлагаю следующее решение. Давайте представим, что данные находятся в файлах с последовательными названиями, скажем, 1.dat, 2.dat, …, n.dat. Тогда, перебирая названия начиная с 1 до n, компьютер сможет считать из них информацию, однако на файле n+1 возникнет ошибка — «файл не найден», что и будет служить сигналом того, что информации больше нет, а количество конкурсов равно n. Для такого цикла лучше всего подходит цикл типа while или repeat..until.

Далее, попытаемся разобраться с самой «туманной» стадией накопления данных. Процедура накопления сводится к тому, что для каждого участника данного конкурса сначала проверяется, участвовал ли он уже в предыдущих конкурсах, путем поиска в списке участников, и если да, текущие баллы добавляются к уже имеющейся сумме за прошлые конкурсы, если же нет, он вносится в список участников со своими текущими баллами. Так как число участников в конкретном конкурсе неизвестно, их тоже есть смысл обрабатывать в цикле типа while.

Итак, теперь наш алгоритм выглядит так:

На этом я предлагаю закончить теоретические рассуждения по пошаговой конкретизации алгоритма, хотя это можно делать еще долго, и перейти сразу к конечной стадии этого процесса — работающей программе. В качестве языка реализации я выбрал, как вы уже догадались, Turbo Pascal 7.0. А после листинга программы я попытаюсь пояснить значения тех или иных блоков программы. Заранее прошу извинить за англо-русско-мумбо-юмбский диалект, использованный в именах переменных :-).

Итак, вот исходный текст программы.

{Програма подсчета результатов конкурсов "Мой Компьютер" }
{Version 1.05, last revision 15.06.2003}
{Version 1.04, revision 12.06.2003}
Const
	N_PeopleMax=500;
	N_KonkursMax=50;
	InNameMask='konkurs';
	OutFName='!Rating.txt';

var
      InFName: string[12];
  InFile,OutFile: text;

TempStr1,TempStr2: string;
     n,k,p,i,m: integer;
	 N_People: integer;
         c: integer;

Peoples: array [1..N_PeopleMax] of string[70];
      Results: array [1..N_PeopleMax,1..N_KonkursMax] of byte;
        Sum: array [1..N_PeopleMax] of byte;
        Key: array [1..N_PeopleMax] of integer;

procedure SwapInt(var x1,x2:integer);
var temp:integer;
begin
  temp:=x1;x1:=x2;x2:=temp;
end; {Procedure SwapInt}

Procedure Sort;
var s:boolean;
begin
 m:=N_People;
 repeat
   s:=true;
   for i:=1 to m-1 do 
    if Sum[Key[i]]<Sum[Key[i+1]] then begin SwapInt(Key[i],Key[i+1]); s:=false; end;
 dec(m);
 until s or (m=1); 
end; {Procedure Sort}

Procedure ScanPeople(Str:string; var Pos:integer);
begin
 Pos:=1;
 while ((Pos<=N_People) and (Peoples[Pos]<>Str)) do inc(Pos);
 if Pos>N_People then begin Peoples[Pos]:=Str; inc(N_People); end;
end; {Procedure ScanPeople}

begin

writeln('Программа обработки результатов конкурсов журнала "Мой Компьютер".');
writeln('(C) 2002-2003 Павлов Дмитрий ');writeln; writeln;

k:=1; N_People:=0;
InFName:=InNameMask+'. 1';

{Открытие файла ввода данных}
{$I-} assign (InFile, InFName); reset (InFile); {$I+}

{Считывание файлов ввода в цикле}
while IOResult=0 do begin
  writeln('Обработка файла ',InFName,'...');
  while not EOF(InFile) do
    begin
     readln(InFile,TempStr1);
     ScanPeople(TempStr1,p);
     readln(InFile,TempStr2); Val(TempStr2,n,c);
     Results[p,k]:=n; Sum[p]:=Sum[p]+n;
  end; {while}
  close(InFile);
  inc(k); Str(k:3, TempStr1);InFName:=InNameMask+'.'+TempStr1;
  {$I-} assign (InFile, InFName); reset (InFile); {$I+}
end; {while}

if k=1 then begin writeln('Нет исходных файлов данных.'); halt; end;

writeln('Всего: ', k-1, ' конкурсов, ', N_People, ' участников.');
writeln; writeln('Сортировка...');

{Инициализация масива ключей для сортировки и собственно сортировка}
for i:=1 to N_People do Key[i]:=i;
Sort;

{Вывод результатов в файл}
assign (OutFile,OutFName); rewrite (OutFile);
for i:=1 to N_People do writeln(OutFile, Peoples[Key[i]],#9,Sum[Key[i]]);
close(OutFile);
writeln('Результаты записаны в файл ', OutFName,'.');

end.

В программе не применяются никакие дополнительные библиотеки, в частности модуль Crt (uses Crt), чтобы выполнение программ не вызывало сообщений об ошибках на быстрых компьютерах (знаменитая runtime error 200). К тому же размер откомпилированной программы крайне невелик — около 5 Кб.

В блоке констант описаны константы — максимальное количество конкурсов (50) и максимальное количество участников конкурсов (500), которое способна обработать программа. Также описана маска для поиска файлов с исходными данными и файл, в который будут выведены результаты.

В блоке описания переменных самыми интересными являются массивы Peoples (имена участников), Results (все результаты всех конкурсов для каждого участника), Sum (сума баллов по всем конкурсов для участников). Массив Key является массивом ключей для окончательной сортировки. А в переменной N_People хранится текущее количество участников.

Процедуры: SwapInt — вспомогательная процедура для подпрограммы Sort, меняющая местами значения двух переменных, а сама Sort, понятно, служит для сортировки. К своему стыду, автор не смог вспомнить «в полевых условиях» более сложный и эффективный алгоритм, чем пузырьковая сортировка (немного улучшенная), которую называют «самым медленный алгоритмом всех времен и народов». Однако пусть читатель не волнуется — при таких объемах информации алгоритм сортировки маловажен, для пользователя ведь все равно, выполнится сортировка за 0.1 или 0.01 секунды.

В процедуре ScanPeople проводится накопление результатов уже описанным выше способом: программа ищет участника в массиве Peoples, при нахождении текущие баллы добавляются к уже имеющейся сумме в массиве Sum, а если такого там нет, новичок вносится в список участников со своими текущими баллами, а количество участников увеличивается на 1.

В теле основной программы выполняются следующие действия: в цикле находятся файлы вида konkurs. 1, konkurs. 2, konkurs. 3 и т.д., из каждого файла по две строки считывается информация об участнике (первая строка — имя участника, вторая — его балл за этот конкурс), и выполняется процедура ScanPeople. Таким образом обрабатываются все участники всех конкурсов.

Далее производится сортировка, и вывод результатов в файл !rating.txt.

Я надеюсь, программа, несмотря на свою относительную простоту, будет полезна читателям МК, тем более что ее можно переделать под свои нужды. Если возникнут какие-то вопросы, можете обращаться к автору за пояснениями по электронной почте.

Автор не является программистом и даже не претендует на это звание. Однако работа собственноручно написанной программы дает ощущение, которое несравнимо ни с чем. Ведь компьютер выполняет именно то, что вам нужно, при этом именно вы объяснили, что именно нужно. И если читатели, которые считают, что писать программы — это очень сложно и наверняка не для них, попробуют встать на такой путь общения с компьютером, я буду считать свою задачей выполненной. Удачи вам на этом пути!

Рекомендуем ещё прочитать:

Мысли о Паскале. (№6/229 `2003) Владислав Демьянишин
СW@Pгань страничку. (№9/232 `2003) Дмитрий Свирепчук
Сизам, откройся! (№10/233 `2003) Роман (Romeo) Радченко
Выпадение… списка. (№28/251 `2003) Александр Чабан
Мысли о Паскале. (№28/251 `2003) Владислав Демьянишин
100! (№36/259 `2003) Дмитрий Ельчанинов
Его Величество Случай. (№40/263 `2003) Александр А. Гайша
Вопрос, конечно, интерфейсный…. (№43/266 `2003) Ratan
SDеLай сам. (№45/268 `2003) Владимир [Farcaller] Пузанов
Мысли о Паскале. (№45/268 `2003) Владислав Демьянишин

Предыдущая статья Назад К списку журналов Следующая статья