i
i
“1384-Juvan-Iscemo” — 2010/7/30 — 10:48 — page 1 — #1 i
i
i
i
i
i
List za mlade matematike, fizike, astronome in računalnikarje
ISSN 0351-6652
Letnik 26 (1998/1999)
Številka 6
Stran 355
Martin Juvan:
IŠČEMO BESEDO
Ključne besede: računalništvo, matematika, kombinatorika, faktori-
elni zapis števil, nizi znakov, sestavljanje besed.
Elektronska verzija: http://www.presek.si/26/1384-Juvan.pdf
c© 1999 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.
& imxmo na raqobgo n rdEnih &k, I d b  iz njih sestavimo nt rmliEnih 
besed, v katerih vsaka &I M o p &  n a t h  eakrat. F'ri tern pojm bmda 
am&qje poljubno (konEm) zsporesdje znakw. Smda pa tako wpporedje 
la rdmkdaj dola& besedo alovmkga j e d a  Iz Erk a, h in m WO taka; 
sestavimo naaIednje b d e :  
Vab doga je, da v enem ad mjih pdjubljenih p r o ~ l s i h  je- 
&ov s&svite pqmm, ki b t  vhod vzme skupino n raelEWh Erk in 
naravno Wvilo li: ter med ta! razliEnimi besedami, ki jih l d h  dobinto 
n ~ ~ j e m  danih Erk, poW two, ki je pri ureditvi po a b d  na 
k-tern mestu Pri &k& a, h, rn in &evilu k = 3 je to beseda ham. Pwkusite 
k, kd&m odgwor dobite pri CrU a, b, o, r, v in 15tevilu k = 38. 
Martin 3ara 
IRačunalništvo - Rešitve nalog
IŠČEMO BESEDO - Rešitev s str. 355
Ljudje števila običajno zapisujemo v deseti škem sestavu. V računalništvu
večkrat srečamo t ud i osnove dva, osem in šestnajst. Seveda pa obstaj ajo
tudi bolj nenavadni zapisi. Videli bomo, da je rešitev naloge povez ana z
enim od t akih zapi sov.
Števila lahko zapišemo t udi v "faktorielnem" zapi su. Vsako naravno
število k od O do n ! - 1 lahko enolično zapišemo kot
k = Cn- l . (n - 1)! + Cn - 2 . (n - 2) ! + .. .+ C2 . 2! + Cl . 1! ,
kjer za števke Ci , i = 1, . . . , n - 1, velja Ci E {O, 1, . . . , i - 1, i}. O obstoju
in enoličnosti zapisa se lahko prepričamo z matematično indukcijo .
In kako poiščemo faktorielni zapis števila? Podobno, kot poiščemo
zapise v bolj običajnih sestavih. Dvojiški zap is šte vila poiščemo npr. tako,
da št evilo zaporedoma celoštevilsko delimo z 2 in beležimo ost anke. Delje-
nje končamo , ko število postane enako O. Ostanki , prebrani od zadnjega
proti prvemu, dajo dvojiški zapis izbr anega števila. Npr.:
37
18
9
4
2
1
18
9
4
2
1
O
2 + 1
2 + O
2 + 1
2 + O
2 + O
2 + 1
Torej je 37 = 100101(2)' Posamezna mesta v dvoji škem zapisu so ut ežena s
pot encami števila 2: 1, 2, 4, 8, ... V fak torielnem zapisu pa so posamezna
mesta ut ežena s fakultet ami števil: 1!, 2!, 3!, 4!, . . . Pri iskanju zapisa zato
na pr vem koraku število delimo z 2, na drugem s 3, na tretj em s 4 itn.
Tako dobimo
37 18 2 + 1 k k2 2 + Cl
18 6 3 + O k 2 k3 3 + C2
6 1 4 + 2
1 O 5 + 1 k n - l kn n + Cn- l
Če je število k manj še od n !, potem je zadnji kvocient kn enak O. Fak to-
rielni zapis števila 37 je to rej 37 = 1201(!).
366 Računalništvo - Rešitve nalog I
{ Število razp oložljivih črk. }
{ fak torielni zapis }
{ iskana beseda }
In kakšno zvezo ima faktorielni zapis z iskanj em besed? Recimo, da
imam o na voljo črke a , b , 0 , r in v. Iz njih lahko sestavimo 5! = 120
različnih besed . Iščemo po ab ecedi 38. besedo. Ker je 4! = 24, se besede
od 1. do 24. začno z a , od 25. do 48. se začno z b, od 49. do 72. z
0 , od 73. do 96. z r , zadnjih 24 besed pa se začne z v. Iskana beseda
se torej začne z b. Vseh 24 besed , ki se začno s črko a , bo po abece di
pred njo. Zato moramo le še določiti po abecedi 14. besedo (38 - 24 =
= 14), sestavljeno iz črk a , 0 , r in v. Ponovimo zgornji razmislek . Besed
je 24, prve črke pa jih razdelijo v skupine po 6. Iskana beseda je tako v
3. skupini , zato se začne s po abece di t ret jo črko , črko r. Na enak način
določimo t udi nadaljnj e črke in najdemo iskano besedo : br avo.
Če ste pozorno spremljali gornji ra zmis lek , st e gotovo opazili, da smo
pravzaprav opisali še en način za iskanj e faktor ielnega zapisa. Ker smo
besede oštevilčili od 1 do n! , s faktorielnim zapisom pa opišemo števila
od O do n! - 1, moramo pogledati zapis števila 37: 37 = 1201(! ). Števke
štejemo od O dalje, skupine (oz. začetne črke) pa smo št eli od 1 nap rej,
zato vsako šte vko še povečamo za 1. Dobimo zaporedje 2, 3, 1, 2. Izmed
črk a , b , o, r , v izberemo 2., jo ods t ranimo, med preostalimi vzamemo
3., jo zopet odstranimo, na to 1. , pa 2., na koncu pa dodamo še edino
preostalo črko . Seveda dob imo besedo bravo.
Ponovimo, kako poiščemo k-to besedo. Najprej poiščemo faktorieln i
zapis števila k - 1. (Če imamo n črk, bo zapis imel n -1 števk; ne smemo
pozabi ti na vodilne ničle , če so potrebne, da zago tovimo pr avo dolžino .)
Vsako števko povečamo za 1, nato pa iz zaporedja črk izbiramo črke , kot
narekujejo števke. Vsako izbrano črko sproti odstranim o iz zaporedja.
Črko , ki ost ane, dod am o na konec besede. Opisanega postopka ni težko
sprogramirati. V nadaljevanju je zapisan v turbo pascalu kot funkcija
Poi sc i Bes edo.
fu nction PoisciBesedo(crke: st ring; k: longint ): st ring;
{ Poišče p o abecedi k- to besedo, sestavljeno natanko IZ črk IZ crke. }
{ Črke v nizu crke m orajo biti urejene po abecedi. }
var
n: integer ;
stevka: array [1..255] of byte ;
beseda: st ring;
i: int eger ;
begin
n := length (crke);
( Poi-o zapis B W a  k - 1 v 'Woriehem' mpisu. ) 
k := k - 1; 
for i:=l to n - 1 do begin ( Z s p i s i m a n - 1 W k )  
stevka[n - i] := k mod [i + 1); {Najprej dobbimo mdqio aevko.) 
k := k div (i + I); 
end; 
i f k r O t h e n b e g i n  { ~tevilr.  k je prevddm* } 
wriMn('Toliko razlicnih b a d  ne obstaja'); 
PoisciBesedo := "; 
exit; 
end; 
{ Z@O iskano b&o. } 
beseds :-- "; 
for i:=l to n - 1 do begin 
{ Panho, da 8ditev.e povebrno za aria. ) 
M a  := besada + crlae[stevk.[i] + 11; 
delete(crke, stevka[i] + 1, 1); 
end, 
h d z ~  := beseda + ake; { Dodsmo L prtsmkdo &ka. ) 
Crh, Id j i i  imams na voljo za gradejo b e d ,  smo predstavili 2, ni- 
U)]BL zaakov (tip string). lUa izbira nam olaj8er b h j e  & porabljenih 
Erk. Uparabimo lahko ksr v turbo p d  qgajeni podpmgrm delete (ta 
ima tzi parametre: niz, iz ktltmega briiiemo x u k ,  indelta p ~ e g a  zbrisa~ 
m a k  in iitwilo zbrhdh mdwv). Ebkcija PoisciBesedo dteva,  
da so Erke v pruametru crke urejene po abeoedi, sicer ne deluje pra- 
vilno. Poklibmo jo lahkr, kar s konstantnim nizom in iittfvilom, saj za 
oba parametra upor&ljamo pm08 po vmhsti.. Tako na primer kltc 
PoisciBesedo ( ' a b 0 ~ ~  * , 38) vrns nh bravo. 
MU&R Jwam