i
i
“1127-Juvan-luknja” — 2010/7/14 — 14:25 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 20 (1992/1993)
Številka 2
Strani 78–84
Martin Juvan:
NAJVEČJA LUKNJA
Ključne besede: matematika, računalništvo, algoritmi, programiranje,
pascal.
Elektronska verzija: http://www.presek.si/20/1127-Juvan.pdf
c© 1992 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.
{ največje število financa rjev }
{ širin» Mračne doline }
{ Kako daleč vidijo financarji? }
oot
Sl l'\IOl N"LT' 'll"" __ um: I_"'~-
NAJVEČJA LUKNJA
Kontrabantar Preb risani Pepe je zopet pred velikim poslom . Odloči l se je , da
bo v temnih nočeh skozi Mra čno dolino čez mejo spravljal dragocen tovor.
Toda tudi financarji niso od muh in mu pripravljajo zasede . Ker država ni
preve č bogata , pla če financa rjev pa nizke, se Prebrisani Pepe zlah ka dokoplje
do razporeda ča kaj očih financa rje v. Ta kole piše:
Klas Miha 132
Stot in Lojze 62
Tolar Polde 218
Na koncu seznama je še pripisano , da financarji ča kajo v ravni vrst i, št evila pa
pomenijo oddaljenost v met rih ča kaj oči h financa rjev od desnega roba doline.
Financarj i tud i vedno postavijo po enega moža na levi in desni rob. Toda
Prebrisan i Pepe ne bi bil prebrisan, če ne bi poznal še nekaterih drugih
podatkov. Tako ve, kako široka je Mra čna dolina, pa tud i, da ga v temni
noči financarji lahko opaz ijo le, če se j im približa na manj kot dvajset metrov.
l.e pa ga opazijo, potem mu ni rešitve, saj jim s tovorom ne more uiti. Ker je
Prebr isani Pepe tudi ljubite lj ra čunalnikov , se je odloči l. da sestavi program ,
ki mu bo vsak večer poveda l, ali naj se to noč odpravi čez mejo. Sest avil j e
tak le algor item :
program Luknjal ;
{ Po ve, ali bo im el Pep e delovno noč. }
eonst
Max_Fin = 30 ;
Sirina = 666;
Vidljivost = 20;
ftype
tabela = array [1..Max_Fin] of inte ge r;
zas edeno = ar ray [l. .Sirina) of bool ean ;
var
A: tabela ;
Z: zasedeno ;
i.n: integer;
Najluknja ,TrenLuknja : int eger ;
begin
write('Koliko finan carj ev je to noe na delu: ' ); readln(n) ;
(or i:=l to n do begin { vnos polo žejev financarjev }
write('Polozaj ', i: . finan carja : ' ) ; readln(A[i));
end; { for}
79
for i:=l to Sirina do Z[i]:=false;
for i:=l to n do
Z[A[i]]:=true; { Postavimo financarje na njihova mesta. }
{ Pogledamo, kako veliko luknjo so to noč pustili financarji. }
NajLuknja:=O; TrenLuknja:=l ;
for i:=l to Sirina do
if not Zlil then TrenLuknja:=Trenl.uknja-l-I
else begin
if TrenLuknja> Naj Luknja then NajLuknja: = TrenLuknja;
Trenl.uknja .eel ;
end;
if NajLuknja>2*Vidljivost then { Ali je luknja dovolj velika? }
writeln('Noeojsnja noe bo delovna.')
else
writeln(,To noe bos lahko poeival.');
read ln;
end.
Pa naj bo dovolj zgodbic o kontrabantu in oblasti . Poglejmo raje, s
kakšnim problemom smo se pravzaprav srečali. Naj bo dana končna množica
števil. Označimo jo z A. 5tevili iz množice imenujemo sosednji (glede na
množico A), če med njima po velikosti ni nobenega drugega števila iz množice
A. Le pogledamo nekoliko abstraktneje , smo rešili naslednjo nalogo:
Poišči največjo razliko med dvema sosednjima številoma iz množice A.
Množico A predstavimo s tabelo števil, ki pa seveda ni urejena . Ogledali
si bomo štiri rešitve gornjega problema:
1. rešitev: Prvo rešitev smo že spoznali . Postopek ni predolg in tudi
ne prezapleten , tako da ga zlahka razumemo. Ideja je preprosta. Množico
A, ki je najprej predstavljena z neurejeno tabelo števil, predstavimo raje s
tabelo logičnih vrednosti, torej tako , kot tudi pascal predstavlja rnnozrce.
Tak pristop ima tudi veliko pomanjkljivost. Količina dodatnega prostora,
ki ga potrebujemo poleg vhodnih podatkov, je odvisna tudi od vrednosti
vhodnih podatkov, ne le od njihovega števila . Tako je velikost dodatne logične
tabele sorazmerna z razliko med največjim in najmanjšim številom v množici
A. Ta razlika pa je lahko zelo velika tudi v primeru, ko je moč množice A
majhna . Prav takoje tudi čas, potreben za rešitev problema s tem postopkom,
sorazmeren z razliko med največjim in najmanjšim številom v množici. Prva
rešitev je tako primerna le za množice, pri katerih je razlika med največjim in
BO
najmanjšim številom majhna. Dodatna pomanjkljivost te rešitve je še , da je
ne moremo uporabiti pri množicah realnih števil.
Opisane pomanjkljivosti nas vzpodbudijo, da poskušamo poiskati rešitev,
pri kateri bosta količina dodatnega prostora in čas reševanja odvisna le od
moči množice A, ne pa tudi od vrednosti samih števil.
Pri programiranju bomo privzeli naslednji deklaraciji :
const
Max.,n = 10000;
type { Seveda lahko vzamemo tudi celoštevilsko tabelo. }
tabela = array [1..Max...n] of real ;
2. rešitev: Ta rešitev se povsem izogne težavam s prostorom , ki smo
jih srečali pri prejšnji rešitvi , pa tudi njena časovna zahtevnost je zadovoljiva.
Ideja je takale . Za vsak par števil iz množice A pogledamo, če sta števili
sosednji , in če sta, je absolutna vrednost njune razlike kandidat za končni
rezultat. Trenutno največjo razliko ves čas vodimo v spremenijivki Najluknja.
V njej je na koncu tudi rezultat, ki ga vrne funkcija.
function Luknja2(var A: tabela ; n: integer) : real;
var
i.j.k: integer;
Najluknja: real;
Sosednji : boolean ;
begin {Luknja2}
Najl.uknja .e.O:
for i:=l to n-1 do
for j :=i+1 to n do begin { Ali sta števili Ali] in AfJJ sosednji? }
Sosednji:=true;
k:=l;
while Sosednji and (k <=n) do begin
if (A[k]-A[i])*(A[k]-AUJ)<O then Sosednji :=false ;
k:=k+1 ;
end ; {while}
if Sosednji and (abs(A[i]-AU))»NajLuknja then
Naj Luknja := a bs(A[i]- Am) ;
end; {for}
Luknja2 := Naj Luknja ;
end; {Luknja2}
Kaj ugotovimo s pogojem
(A[k]-A[i])*(A[k]-A[j]) <O ,
se sprašujete? Ta pogoj je izpolnjen natanko tedaj, ko število A[kJ leži strogo
med številoma A[iJ in A[j). Ta rešitev je varčna z dodatnim prostorom, saj
81
smo uporabili le pet dodatn ih spremenljivk in nobene nove tabele . Tudi čas
iskanja rešitve je odvisen le od števila podatkov. Žal pa je ta odvisnost
kubična , kar pomeni , da se ča s ra čuna nja veča sorazmerno s tretjo potenco
števila podatkov. te dolžino vhodne tabele A podvojimo, se čas reševanja
pomnoži z osem . Ko tako funkcijski podprogram Luk nja2 preizkusimo na
tabeli z nekaj sto elementi , hitro ugotovimo , da je še vedno zelo počasen .
(te se je bralec morda ustrašil , da bo moral sam odtipkati nekaj sto števil, da
bo zadovolj ivo preizkusil podprogram, mu svetujem , naj napiše podprogram ,
ki bo v vhodno tabelo A zapisal želeno število naključnih števil in tako
opravil pripravo vhodnih podatkov namesto njega . V Turbo pascal vgrajena
podprograma randomize in random mu bosta pri tem v veliko pomoč.)
3. rešitev: Kaj kompliciram , pravite! Rešitev nalogeje na dlani . Tabelo
števil, ki predstavlja množi co A, uredimo, nato pa med pari zaporednih števil
poiščemo tist i dve, med katerima je največja razlika. Tule je podprogram :
function Luknja 3(var A: tabela; n: integer): real;
var
Najl.uknja: rea l;
i: intege r;
begin { Luknja3}
Uredi(A,n); { Nepedejo če uredimo tab elo A. }
Najl.uknja.e.O : { Poiščemo največjo razliko med pari zaporednih števil. }
for i:= l to n-1 do
if A[i+lI-A[i] >NajLuknja then NajLuknja:=A[i+1]-A[i] ;
Luknja3:=NajLuknja;
end ; { Luknja3}
Kvaliteta zgornje rešitve je seveda odvisna od prave izbire podprograma za
urejanje števil. O metodah za urejanje je napisanih kopica knjig. Najlažje
dostopna je verjetno znamenita Wirthova knjiga Računalniško programiranje.
V njenem drugem delu je narejen pregled standardnih postopkov za urejanje.
Solidna metoda je hitro urejanje (quicksort po angleško) z nekaj izboljšavami
(ne rekur zivna varianta , urejanje kratkih podzaporedij s preprostim vstavljanj-
em , pazljiva izbira delilnega elementa) , v zadnjem času pa se uveljavlja tudi
izboljšano urejanje s kopico (več o njem si bralec lahko prebere v Obzorniku
za matematiko in fiziko, letnik 38 , številka 2, strani 45 do 52) . tasovna
zahtevnost vseh teh metod pa je reda vsaj n > log n. To pomeni , da se čas,
potreben za rešitev problema, povečuje nekoliko hitreje , kot raste velikost
vhodnih podatkov.
Toda naš problem se zdi vendarle preprostejši , kot je urejanje celotne
82
tabele . Sestavljanje postopka, ki reši nalogo v času, sorazmernem z velikostjo
vhodne tabele , je tako pravi izziv za vsakega nadebudnega programerja .
4. rešitev: Priznati moram , da sem ves čas mislil na tole rešitev.
Morda bo koga presenetilo, da si pri njeni izpeljavi pomagamo z varianto
Dirichletovega principa . Ta pravi tole : če n stvari , v našem primeru štev il,
porazdel imo v n+1 predal čkov , v našem primeru intervalov , ostane vsaj eden
od predalčkov prazen. Postopek reševa nja je naslednji :
1. Poiščemo najmanjše in največje št evilo v tabel i in ju shranimo v spre-
menljivki min in ma x.
2. Interval med št eviloma min in ma x razdelimo na n + 1 enako dolgih
podinterva lov. Dolžina posameznega podintervala je torej ma~+f'in =
= : d .
3. Za vsakega od podintervalov ugotovimo , ali je v njem katero od števil iz
vhodne tabele . Za vsak neprazen pod interval nato poiščemo najmanjše
in najve čje število v njem.
4. Ker je podintervalov n-l-l , vhodnih števil paje le n, bo vsaj en podinterval
ostal prazen . Ker pa mejna podintervala nista prazna , bo n aj večja razlika
med sosednjima številoma večja od dolžine podinterva la d . Torej bosta
števili , ki določata najb olj oddaljen sosednji par, pripadali r a z li č nima
podintervaloma. Da dobimo pravilen rezultat , tako zadošča za vsak
neprazen podinterval pregledati razliko med najmanjšim številom v tem
podintervalu in največj im štev ilom v prvem nepraznem podinterva lu na
levi, torej med podinte rvali, ki vsebujejo manjša štev ila.
Vsakega od št irih korakov bomo sprog ramirali tako , da bo porabljeni čas so-
razmeren z dolžino vhod ne t abele. Ker bomo potrebovali dve pomožni tabeli,
podprogram pa želimo uporabljati tudi pri velikih vhodn ih tabelah , bomo
nekaterim pomožnim spremenlj ivkam prostor dodel ili šele med izvajanjem.
function Luknja4(var A: tabela ; n: int eger): real ;
type
intervali = array[O.. Max.n] of real;
prazno = array[O.. Max,n] of boolea n;
var
Minl,Maxl: ) interva li;
P : )prazno;
Min,Max,d,NajLuknja : real ;
i.j: integer;
begin {Luknja4}
Min:=A[l) ; { Poi š čemo najmanjše in največje število v tabeli A. }
Max:=A[l);
for i:=2 to n do begin
83
if Min>A[i) then Min:=A[i) ;
if Max<A[i) then Max:=A[i);
end; { for}
{ Če 50 vsa števila v tabeli enaka, potem kon čemo. }
if Min=Max then begin Luknja4 :=O; exit ; end ;
{ Sicer pa izre čunsmo do/lino podintervalov in pripravimo pomo žni tabeli. }
d:=(Max-Min)/(n+1 ) ;
GetM em(Minl,SizeOf(real)*( n+1)) ;
GetM em(Maxl,SizeOf(real) *(n + 1));
GetMem( P,SizeOf(boolean )*(n+1) );
for i:= O to n do P I [i):=true; { Na ze četku 50 vsi podintervali prazni. }
{ S sprehodom po tabeli A pregledamo vsa š tevila in jih porazdelimo po}
{ ustreznih podintervalih . }
fo r i:= l to n do begin
{ lzre čunemo, v kateri podinterval spada število Ali]. }
{ Če je število na meji dveh podintervalov, je vseeno, kam ga uvrstimo. }
j:=trunc((A[i]-Min)/d); if j=n+1 then j:=n;
if PI [j) then
begin PI [j):=false ; MinIT[j]:=A[i]; MaxIT[j):=A[i) end
else
begin {else}
if A[i)<MinIT[j) then Minil [j):=A[i];
if A[il>MaxIT[j) then Maxl][j) :=A[i];
end; { else}
end ; { for}
i:=O; NajLuknja :=O ; { Poiščemo nejve čjo luknjo. }
j:=l ; { j bo indeks naslednjega nepraznega podintervala. }
while i<n do begin { Poiščemo naslednji neprazni podinterval. }
while P I[j) do inc(j); { Novo luknjo primerjamo z do sedaj nejve č]o. }
if Minil [j)-Maxl j(i»NajLuknja then
Najl.uknja .eMinl ][j]-Maxllli];
i:=j;
inc(j ) ;
end ; { while}
Luknja4 := NajLuknja ;
end ; { Luknja4}
Na koncu si oglejmo še rezultate meritev, ki smo jih dobili s prime rjavo
opisanih rešitev . Prikazuje jih tabela na naslednji strani . Preizkusi so bili
opravljeni na običajnem AT računalniku . Izračunani časi so povprečje nekaj
meritev in so podani v stotinkah sekunde .
Kot smo predvideva li, je druga rešitev bistveno slabša od tretje in četrte,
čeprav se zdi , da je njena povprečna časovna zahtevnost nekoliko boljša od
kubične . Zadnja rešitev je boljša od tretje , njena prednost pa postaja tem
bolj očitna, čim večja je tabela , s katero delamo. Seveda pa moramo to
večjo hitrost reševanja problema tudi plačati . Tako zadnja rešitev potrebuje
precej veE pomnilnika kot trtt ja. Na celo3tevilskih tabclah smo prirncrjali 
tudi prvo in zadnjo rditev. lzkafe st, da sta priblifno enako dobri takrat, ko 
je razrnerje rned dolrino tabele in intervalom, s katersga so vrednasti, akoli 
ena proti dvajsct (to rglrnerjc je scveda odvisno tudi od tipa rabnalnika, na 
katwern opravljarno rneritve). Ec jt razmerje manjse, j c  prirnerncjsa zadnja 
reJitev, sicer pa prva. 
t r  imamo opraviti Ie s crlo&evilskimi tabelami, l a h b  zadnjo rJ i tev I e  
nekoliko izpilimo, tako da uporablja It celoi5twilsko aritmetiko (in mada  Za 
nekoliko vcE dodatntga prortora). K t r  pa jt prispevek fc precej dolg, to 
itbolji4avo prepu$Earno zvcstim b ra lcm t a  (neobvezno) domalio nalogo. 
Martin Juvan