- Czy wiesz jak gigantyczne są w tym roku problemy z dostaniem się do liceów? W czerwcu 2002 uświadomiono mi konsekwencje kandydowania do wielu szkół ponadgimnazjalnych naraz.
Uczniowie gimnazjów kandydujący do kolejnego poziomu szkół średnich są oceniani punktami, których maksymalnie mogą zdobyć 200. Może się też zdarzyć, że poszczególne szkoły różnie ocenią kandydata i dlatego by reprezentować te wielkości w naszym programie konieczna jest deklaracja:
Var punkty:array [kandydaci] of array [szkoly] of real;
Przy wcześniejszym zadeklarowaniu stałych i typów:
const
n=8;
m=5;
p=100;
type
kandydaci=1..n;
szkoly=1..m;
Kolejnymi danymi jakich potrzebujemy o uczniach są ich preferencje tj. lista szkół jakie ich interesują. Szkoły należy ułożyć w kolejności od najbardziej interesującej kandydata do najmniej. W naszym programie najwygodniej będzie to reprezentować tablicą:
Var zgloszenia:array [kandydaci] of array [szkoly] of integer;
której poszczególne pola będą zawierały liczby całkowite począwszy od 1 a skończywszy na ilości niezerowych pozycji w wierszy tablicy. Liczby te będą oznaczały kolejność w jakiej uczeń preferuje szkoły i oczywiście nie mogą się powtarzać.
Program będzie jeszcze musiał wiedzieć ile miejsc ma każda ze szkół, co przechowa nam tablica:
Var limit: array [szkoly] of integer;
Na podstawie tych danych nasz program w pierwszym kroku wygeneruje dla każdego ucznia podania do deklarowanych przez niego szkół i umieści je na odpowiednim miejscu w kolejce do przyjęcia do danej szkoły co przechowa nam tablica:
var miejsca: array [1..100] of array [szkoly] of integer;
Najlepiej będzie napisać procedurę, która umieści danego kandydata w danej szkole:
procedure dodaj_podanie(k:kandydaci;s:szkoly);
var i,z,zz:integer;
begin
i:=1;
while (miejsca[i,s]>0)AND(punkty[k,s]<punkty[miejsca[i,s],s]) do
i:=i+1;
z:=miejsca[i,s];
miejsca[i,s]:=k;
while miejsca[i+1,s]>0 do begin
i:=i+1;
zz:=miejsca[i,s];
miejsca[i,s]:=z;
z:=zz;
end;
miejsca[i+1,s]:=z;
end;
Jak widać składa się ona z dwóch części, z których pierwsza znajduje odpowiednie ze względu na zgromadzone punkty miejsc na liście i wstawia tam nowego kandydata, a druga „rozsuwa” dalszą część tablicy by nie zgubić żadnego z wcześniej dopisanych kandydatów. By wykonać działania dla wszystkich kandydatów i odpowiednich szkół można w głównej części programu umieścić odpowiednie pętle:
for i:=1 to n do
for j:=1 to m do
if zgloszenia[i,j]>0
then dodaj_podanie(i,j);
Tak utworzone kolejki kandydatów mają tę wadę, że na miejscach promowanych przyjęciem do szkół powtarza się wielu kandydatów w różnych szkołach. Musimy więc wyeliminować ich z innych szkół niż ta, do której mają zostać przyjęci robiąc tym samym miejsce dla kandydatów jeszcze nigdzie nie przyjętych. Wykona to dla nas procedura, której będziemy sygnalizować, że dany uczeń ma miejsce wśród przyjętych w chociażby jednej ze szkół:
procedure ma_miejsce(k:kandydaci;s:szkoly);
var pp,i,j:integer;
begin
pp:=zgloszenia[k,s];
for i:=1 to m do
for j:=1 to p do
if (miejsca[j,i]=k)AND(zgloszenia[k,i]>pp)
then usun_podanie(j,i);
end;
Ta procedura jak widać wywołuje inną usuwającą podania:
procedure usun_podanie(l:integer;s:szkoly);
var i:integer;
begin
for i:=l to p-1 do begin
miejsca[i,s]:=miejsca[i+1,s];
if (miejsca[i,s]>0)AND(limit[s]>=i)
then ma_miejsce(miejsca[i,s],s);
end;
end;
Proszę zwrócić uwagę, że ta procedura również wywołuje procedurę ‘”ma_miejsce”, co tworzy taką ciekawą rekurencję i wymaga odpowiedniego uprzedzenia („forward”) w jednoprzebiegowych kompilatorach. Procedurę ”ma_miejsce” należy najpierw wywołać dla wszystkich miejsc premiowanych przyjęciem do każdej ze szkół:
for j:=1 to m do
for i:=1 to limit[j] do
if miejsca[i,j]>0
then ma_miejsce(miejsca[i,j],j);
Po zakończeniu tego procesu można już wydrukować listy wyników:
writeln('Wyniki naboru');
for j:=1 to m do begin
write('Szkola ',j,'[');
for i:=1 to p do
if miejsca[i,j]>0
then if limit[j]>=i
then write(miejsca[i,j],'/',punkty[miejsca[i,j],j]:3:0,';')
else write(-miejsca[i,j],'/',punkty[miejsca[i,j],j]:3:0,';');
writeln(']');
end;
readln;
Nasz program wypisze również te pozycje list kandydatów, którzy nie zostali do danej szkoły przyjęci poprzedzoną znakiem ”-” by ułatwić analizę procesu naboru. Oto przykładowe wyniki:
Poniżej przedstawiono kompletny program z danymi wpisanymi na stałe. Pierwszą rzeczą o jaką warto się pokusić jest wczytywanie danych, ale najlepiej z jakiegoś pliku, którego zapełnianie powierzymy innemu programowi umożliwiającemu dopisywanie danych kolejnych uczniów. W tym programie reprezentuje się ich kolejnymi liczbami całkowitymi, ale w rzeczywistym serwisie wyróżnia się ich 11 cyfrowymi numerami PESEL, co również warto uwzględnić w programie dopisywania kandydatów. Taki program w rzeczywistym systemie przyjmuje też oceny ze świadectwa oraz zadaje pytania onośnie osiągnięć i na tej postawie samoczynnie generuje punkty uwzględniając kryteria jakimi kierują się różne szkoły. Można też inaczej rozwiązać tworzenie kolejek kadydatów do poszczególnych szkół. Najpierw dopisując ich w kolejności zgłaszania, a dopiero potem sortując oddzielnie dla każdej ze szkół. Powinno to pozwolić na oszczędności w czasie przetwarzania dla dużej liczby kandydatów. Można też zastosować jedną ze znanych struktur kolejki priorytetowej.
program nabor;
const
n=8;
m=5;
p=100;
type
kandydaci=1..n;
szkoly=1..m;
const
zgloszenia:array [kandydaci] of array [szkoly] of integer=
((5,4,1,2,3),
(1,5,4,3,2),
(2,1,3,4,5),
(4,2,1,3,5),
(1,5,4,3,2),
(2,1,3,4,5),
(4,2,1,3,5),
(2,3,1,4,5));
punkty:array [kandydaci] of array [szkoly] of real=
((180,190,187,182,183),
(191,180,190,193,192),
(182,181,183,184,185),
(174,172,171,173,180),
(191,180,180,193,192),
(182,181,183,184,185),
(174,172,171,173,190),
(182,183,181,184,185));
limit: array [szkoly] of integer=
(2,2,1,2,1);
var i,j,zg:integer;
miejsca: array [1..100] of array [szkoly] of integer;
procedure dodaj_podanie(k:kandydaci;s:szkoly);
var i,z,zz:integer;
begin
i:=1;
while (miejsca[i,s]>0)AND(punkty[k,s]<punkty[miejsca[i,s],s]) do
i:=i+1;
z:=miejsca[i,s];
miejsca[i,s]:=k;
while miejsca[i+1,s]>0 do begin
i:=i+1;
zz:=miejsca[i,s];
miejsca[i,s]:=z;
z:=zz;
end;
miejsca[i+1,s]:=z;
end;
procedure usun_podanie(l:integer;s:szkoly);
forward;
procedure ma_miejsce(k:kandydaci;s:szkoly);
var pp,i,j:integer;
begin
pp:=zgloszenia[k,s];
for i:=1 to m do
for j:=1 to p do
if (miejsca[j,i]=k)AND(zgloszenia[k,i]>pp)
then usun_podanie(j,i);
end;
procedure usun_podanie(l:integer;s:szkoly);
var i:integer;
begin
for i:=l to p-1 do begin
miejsca[i,s]:=miejsca[i+1,s];
if (miejsca[i,s]>0)AND(limit[s]>=i)
then ma_miejsce(miejsca[i,s],s);
end;
end;
begin
for i:=1 to n do
for j:=1 to m do
if zgloszenia[i,j]>0
then dodaj_podanie(i,j);
for j:=1 to m do
for i:=1 to limit[j] do
if miejsca[i,j]>0
then ma_miejsce(miejsca[i,j],j);
writeln('Wyniki naboru');
for j:=1 to m do begin
write('Szkola ',j,'[');
for i:=1 to p do
if miejsca[i,j]>0
then if limit[j]>=i
then write(miejsca[i,j],'/',punkty[miejsca[i,j],j]:3:0,';')
else write(-miejsca[i,j],'/',punkty[miejsca[i,j],j]:3:0,';');
writeln(']');
end;
readln;
end.
Chociaż program napisano od początku dla tego artykułu to bardzo przypomina program w Delphi z września 2002, który uruchomiony na notebooku posłużył do zachęcania władz oświatowych Poznania i Poznańskiego Centrum Superkomputerowo-Sieciowego by zrealizować kompleksowy system naboru do szkół ponadgimnazjalnych dla całego miasta. W czerwcu 2003 system bardzo efektownie pomógł w naborze stając się pierwszym, który objął wszystkich kandydatów (ok.10tys.) dużego miasta. Zastosowano ten właśnie algorytm zakodowany w języku Java tyle, że dane kandydatów były ściągane z bazy danych a wyniki naboru z powrotem umieszczane w bazie. Kłodą pod nogi systemu okazało się ówczesne zarządzenie MEN, które ograniczało wybór do trzech szkół. To nie tylko było niepotrzebne przy naborze komputerowym, ale zmniejszało możliwości zabezpieczenia się kandydatów przed odrzuceniem ich kandydatury przez kolejne szkoły. W ciągu kilku lat system upowszechnił się w kilkunastu miastach Polski, a jego działaniem zaczęto również obejmować dzieci ze szkół podstawowych i przedszkoli, oczywiście według odrębnych algorytmów. http://nabor.pcss.pl/
Podobnie jak w 2002 roku nabór do szkół ponadgimnazjalnych wzbudził duże zainteresowanie prasy krytycznie ocenającej przygotowanie rekrutacji, tak w 2003 roku nastawienie prasy w Poznaniu było entuzjastyczne i wysoko oceniła pomysł i realizację systemu nabór. Autor artykułu dosyć szczegółowo opisał jak powstawała ta pierwsza wersja NABORu w książce "Cywilizacja Internetu" http://sklep.nakom.com.pl/?page=shop/flypage&product_id=86&category_id=6834dda8e3e6e5aa18bafc63a57fd04a. Natomiast napisany w języku angielskim artykuł o bardziej naukowym charakterze można znaleźć m.in.: http://www.upgrade-cepis.org/issues/2005/6/up6-6Upenet.pdf str.71.