i
i
“1266-Juvan-problem” — 2010/7/22 — 13:38 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 23 (1995/1996)
Številka 4
Strani 212–215
Martin Juvan:
PROBLEM TRDNIH ZAKONOV
Ključne besede: računalništvo, računalniško programiranje, urejanje
seznamov.
Elektronska verzija: http://www.presek.si/23/1266-Juvan.pdf
c© 1996 Društvo matematikov, fizikov in astronomov Slovenije
c© 2010 DMFA – založništvo
Vse pravice pridržane. Razmnoževanje ali reproduciranje celote ali
posameznih delov brez poprejšnjega dovoljenja založnika ni dovo-
ljeno.
Računalništvo I
PROBLEM TRDNIH ZAKONOV
Obstaj a nekaj problemov , ki jih na začetku poskuša reši ti vsak zagnan
programer. Kdo še ni poskušal poiskati prvih sto pr aštevil , postaviti kra-
ljic na šahovsko desko tako, da se ne napadajo , izpisati vseh permutacij
ali pa s skakačem obi skati vseh polj šahovnice?
Tudi naloga o trdnih zakonih je podobne vrste. Morda je nekoliko
manj znana , čeprav jo najdemo v mnogih knjigah , ki obrav navajo pro-
gramiranje. Opisana je tudi v prvem delu Wirthovega Računalniškega
programiranj a" . Naloga zahteva nasl ednj e: Dani st a skupini n fan tov in
n dekle t . Naš a naloga je, da sestavimo n (zakonskih ) paro v, in sicer tako,
da bodo sklenj eni zakoni trdni . Vsak fant in vsako dekle namreč sestavi
svoj seznam naklonjenosti do oseb nasprotn ega spola. Zakoni so t rdni, če
ne obstajata fant F in dekle D , ki med seboj nista poročena, a j e fant F
bolj naklonjen dekletu D kot svoj i ženi , dekle D pa ima fanta F raj ši od
svojega moža.
Poglejmo primer: Fantje naj bodo Aleš, Igor in Mih a, deklet a pa
Breda , Karin in Neli . Seznami naklonjenosti so naslednj i:
Aleš
Igor
Miha :
Breda , Karin , Neli
Neli , Breda, Karin
Breda, Neli, Kar in
Breda : Igor , Mih a , Aleš
Karin : Aleš, Igor , Miha
Neli : Miha, Aleš, Igor
Pri t em je na začetku seznama oseba, ki jo imajo najrajši , z osebo na
koncu pa bi se poročili le v skrajni sili . Zakoni Aleš-Karin , Igor-Breda
in Miha-Neli naj bi bili trdni, medtem ko zveze Aleš-Br ed a, Igor-Karin
in Miha-Neli ne, saj ima Igor rajši Bredo kot Kar in , Breda pa je bolj
naklonjena Igorju kot Alešu .
Če imamo n fantov in n deklet , j ih lahko med seboj poročimo na
n(n - 1) . . .. ·1 = n! različnih načinov . Nekatere izbire bodo trdnejše od
drugih. Ni pa takoj jasno, da pri poljubnih seznamih naklonjenosti vedn o
obstaj ajo trdni zakoni .
V nadaljevanju prispevka bomo opisa li postopek, ki bo kot vhod dobil
sezname naklo nj enos ti za fa nte in d ekle t a ter vrnil t rdn e zakonske zveze .
Pri tem bomo tudi dokazali, da trdni zakoni vedn o obstaj ajo.
Iskanje trdnih zvez poteka takole: Na začetku nobena oseba ni zaro -
čena. Dokler niso vsi fantj e zaročeni , ponavlj amo. Izberemo nezaročenega
fanta . Ta med deklet i , ki jih še ni zaprosil, zaprosi tisto, ki ji j e najbolj
1 N. Wirth, Računalniško programiranje, 1. del, DMFAS , Ljubljana, 1989.
Računalništvo
naklonjen . Ce dek le ni zaročeno ali pa ima prosilca raje od svoj ega tre-
nutnega zaročenca, razdre morebitno zaroko in se zaroči s prosilcem . Ko
so vsi fantje zaročeni , so pari sestavljeni , zato le še sklenemo zakon e.
Gornji postopek bomo zapisali v obliki podprograma v pascalu, Glav-
ni program, ki poskrbi za vnos podatkov in privlačen izpis (t er tolažb o
za nesrečno , čeprav trdno poročene) , pa bomo izpustili. Predno se lotimo
programiranja, se moramo domeniti, kako bomo v podprogramu predsta-
vili podatke. Kot običajno, bomo fante in dekleta predstavili s števili od 1
do n . Podprogram TrdniZako ni , s katerim sestavljamo pare, bo imel štiri
parametre: tri vhodne in enega izhodnega, v katerem bomo vrnili sesta-
vljene par e. Vhodni podatki so št evilo fantov oziroma deklet n ter t abe li
f in d , s katerima podamo sezname naklonjenosti fantov in deklet . Tako
bo f [iJ ej] število, ki pr edstavlja dekle, ki j e v seznamu naklonjenosti
fanta i na mestu j . Podobno bo d [iJ ej] fant , ki ga ima i-to dekle na
j-tem mestu v svoj em seznamu naklonjenosti. Pare bomo vrnili v tabeli
z . Pri te m bo z Ci] fant , s katerim poročimo i-t o dekle.
{ največje št evilo fan tov oziro ma deklet }
c o n s t
maxN = 50 ;
type
seznam = array[1..maxN] of integer ;
tabela = array[l..maxN] of in t eger ; { podatkovna struktura za }
{ sezname naklonjenosti }
{ Na začetku noben fant ni zaročen. }
{ Fan t i bo naslednjič zaprosil de kle f[i][nasl[i}]. }
{ število trenutno nezaročenih fan tov }
{ seznam trenutno nezaročenih fantov }
{ pomožni št evci }
{ Na začetku noben fant ni zaročen. }
{ Tudi nobeno dekle ni zaročeno. }
{ Fantj e najprej za prosijo de kleta, k i jih imaj o n ajraje. }
procedure TrdniZakoni(n: integer; vzr f,d: tabela; var z: seznam);
{ Sklene trdne zakon e gl ed e na sezname n aklonjenosti f in d }
var
. nasl: se zn am;
stp : int eger;
p rost i : seznam;
i ,j ,k : integer;
begin
stp := n;
for i:= l to n do begin
prost[i] := 1;
zri] := O;
n asl[i] := 1 ;
e n d;
while stp>O do b egin { Dokler ne zaročimo vseh fantov , pona vljamo. }
i := prosti[stp]; { Izberemo nezaročenega fanta. }
j := f[i][nasl[i]]; { Fant i zaprosi dekle j . }
k := 1; { Ali ima dekle j rajši fanta i kot svoj ega zaročenca z[j]? }
while (d(j][k] < > i) and (d(j][k] < > z(j]) do k := k-j-I;
{ Opomba: lahko je z[j]= O }
214
if d[j][k]=l then b egin
if z[j]< >O then
prost[stpJ .- z[j]
else
stp := stp-l;
z[j] := i ;
e n d; { if }
n asl[i ] := n asl[i] + 1;
end; { while stp>O }
e nd; { TrdniZakoni }
Računalništvo I
{ razdremo zarok e }
{ Fant , ki j e bil zaročen z j-tim deklet om, }
{ ni več zaročen . }
{ še en srečen par več .}
{ zaroka }
{ Naslednjič bo fant i zaprosil naslednje dekle }
{ s seznam a . }
Gornji podprogram je kar kr at ek in tudi program ersko ne pr ezahte-
ven , še vedno pa nismo utemeljili , da se izteče , da se torej zun anja zanka
while konča in da so sklenj eni zakoni res t rdni.
Prepričaj mo se najprej , da podprogram ne obtiči v neskončni zanki.
Ves čas postopka je število nezaročenih fantov enako šte vilu nezaročenih
deklet , saj vsako dekle in vsakega fanta zaročimo kvečjemu z eno osebo
nasprotnega spo la . Nobeno zaročeno dekle tudi ne postane nezaročeno ,
morda le zamenja zaročenca z novim fantom , ki mu je bolj nakl onjena.
Ker pa vsak nezaročen fant po vrsti zaprosi vsa dekleta, se vsako dekl e
slej ko pr ej zaroči . Torej se zaročijo in končno tudi poročijo vsa dekleta
in vsi fantj e.
Nekoliko težje se je prepričati, da so sklenjeni zakoni res t rdni. Obi-
čaj no za vsako pomembno zanko v programu poiščemo invarianto, ki se
pri ponovitvah zanke ohranj a . To je las tnost ali skupina lastnosti , ki
nam pomaga, da pokažemo pravilnost delovanja. V našem primeru je
invarianta zunanje zanke while lastnost, da so ves čas izvajanja zanke
sklenjene zaroke trdne pri pogoju , da nezaročenih oseb ne up oštevam o. Na
z ačetku to gotovo dr ži, saj nimamo nobenega zaročenega para. Prever iti
moramo še, da se v vsaki ponovitvi zanke ta lastnost ohrani. Recimo, da
v zanki sprem enimo zaročene pare. Naj bosta fant F in dekle D novo
zaročeni par . Ker so vsi ostali zaročeni pari ostali nespremenjeni , mora
biti med morebitnima nesrečnima osebama, ki porušit a t rdnost zarok ,
bodisi fan t F bodisi dekle D . Ločimo dve mo žnosti :
a) Recim o, da im a fan t F raj ši dekle Dl , ki j e poročena s fan tom FI,
kot svojo zaročenko D . Pot em je fan t F nekoč že zaprosil dekle Dl in
t a ga je zavrnila . Torej j e takrat imela zaročenc a, ki ga je imela raj ši
od fanta F. Ker deklet a zamenj aj o zaročence le s fan ti , ki jih im ajo
še raj ši , ima dekle D l t udi svojega trenut nega zaročenca FI rajši od
fanta F . Fan t F torej ne pok vari t rdnosti zarok .
Računalništvo
b) Naj ima dekle D rajši fanta Fi, ki je zaročen z dekletom Dl, kot pa
svojega zaročenca F. Potem fant Fi še ni zaprosil dekleta D . Ker pa
je že zaprosil dekle Dl , saj je z njo zaročen, jo ima rajši kot dekle D.
Torej tudi dekle D ne more porušiti trdnosti zarok.
Vse zaroke so torej trdne tudi po koncu zunanje zanke while. 'Potem
pa so trdni tudi zakoni, ki nastanejo iz njih.
Če vas zgornji argumenti niso prepričali, lahko trdnost sklenjenih
zakonov preverite tudi s spodnjim funkcijskim podprogramom. Seveda bi
bilo treba tudi tokrat pokazati , da podprogram deluje pravilno, a tako
pikolovski vendarle ne bomo.
function Preveri(n: integer; var f,d: tabela; var z: seznam): boolean;
{ Preveri, ali so zakoni , podani s tabelo z, trdni . Če so , vrne TRUE, }
{ sicer pa FALSE. }
var
trdni: boolean;
i,j,k,l: integer;
begin .
trdni := true;
i := 1; { Za vsakega fanta z[i] preverimo, ali bi zapustil svojo ženo i. }
while trdni and '(i < = n ) do begin
j := 1; { Za vsa dekleta, ki jih ima fant zri] rajši kot svojo ženo, }
while trdni and (f[z[i]][j]<>i) do begin {preverimo, ali bi tudi dekle}
1 := f[z[i]][j]; { zapustilo svojega moža zaradi fanta zri]. }
k := 1; . {Ali ima dekle l rajši fanta z[i] kot svojega moža z[l]? }
while (d[l][k]<>z[i]) and (d[l][k]<>z[l]) do k := k+1 ; .
trdni := d[l] [k]=z[l];
j := j-l-L ;
end;
i := i+1;
end;
Preveri := trdni;
end; { Preveri}
Zgodbe pa tu še ni konec. Podprogram TrdniZakoni lahko upora-
bimo tudi za drugačne naloge in ne le za sestavljanje trdnih zakonov . Tako
lahko na primer z njim sestavimo pare za ples , športno ekipo, pri čemer
igralci navedejo svoja priljubljena igralna mesta, hkrati pa poznamo nji-
hovo uspešnost na posameznih položajih, opravimo razdelitev daril (ali
pa domačih nalog) in še bi lahko naštevali.
Seveda pa ima reševanje z opisanim postopkom tudi svojo slabo stran.
Opisani pristop namreč zahteva, da seznamov naklonjenosti potem, ko jih
določimo, ne smemo več spreminjati. To pa je pri nalogah iz vsakdanjega
življenja zelo redko .
Mariin Juvan