Uppslagsproblem
Jag vet inte hur "officiellt" detta namn är på denna typ av
problem, eller "dictionary problems" (som låter bättre), men
det är
ett rätt passande namn. Samtliga problem av denna typ har
följande drag gemensamt:
* Ett alfabet är definierat som en mängd av bokstäver, t
ex
alla gemener a-z. "Bokstäverna" kan även vara siffror eller
andra tecken. Alfabetet är dessutom en ordnad mängd, dvs en
bokstav i alfabetet
kommer "först", och därefter kommer de andra bokstäverna
i en otvetydig ordning.
* Ett ord är definierat som en sekvens av bokstäver som
uppfyller
vissa regler. Exempelvis kan en regel vara att ordet måste
bestå
av högst 5 bokstäver eller att alla bokstäver i ordet
ska vara olika.
* Ett språk är definierat som mängden av alla giltiga
ord.
Även denna mängd är ordnad eftersom bokstäverna i
alfabetet är ordnade.
* Antalet ord i språket är väldigt stort - det är
i
praktiken omöjligt att generera alla ord inom acceptabel tid.
* Uppgiften går ut på att man givet ett ord i språket
bestämmer
dess ordningsnummer (där 1 oftast är det första ordet)
och/eller
att man givet ordningsnumret tar reda på vilket ord som finns
på denna
plats i språket.
En vanligt förekommande term i dessa sammanhang är
"lexikografisk ordning" vilket innebär sortering i alfabetisk
ordning. Om inget annat sägs
i uppgiften menas normalt ASCII ordning.
Ett enkelt exempel bör räta ut eventuella frågetecken:
Exempel: Låt alfabetet bestå av bokstäverna a-z. Ett
giltigt
ord i språket har exakt 6 bokstäver. Skriv ett program som
avgör vilket ord som
finns på position x i språket. Det första ordet (x=1)
är "aaaaaa"
och detsista ordet är "zzzzzz".
Detta är ett väldigt enkelt exempel - varje bokstav i ordet
kan
väljas fritt från alfabetet oberoende av de tidigare
bokstäverna i ordet. Lösningen till problemet blir i den
närmaste trivialt - det är
egentligen samma sak som att konvertera ett tal från basen 10
till basen 26. Antalet giltiga ord i språket är för
övrigt 26^6 = 308,915,776.
Exempel: Låt alfabetet vara som ovan (a-z) samt att ett giltigt
ord
måste innehålla exakt 6 bokstäver. Dessutom
måste ordet innehålla
6 unika bokstäver.
Vi börjar med att räkna ut antalet ord i språket
(vilket
i och för sig inte är nödvändigt för att
lösa uppgiften). Det är
inte så svårt - första bokstaven kan vara vilken som
helst av a-z, 26 stycken. Andra bokstaven kan vara alla utom den som
valdes nyss, dvs 25 st, osv. Totalt antal blir 26*25*24*23*22*21 eller
26!/(26-6)! = 165,765,600.
Här måste vi dock tänka till lite mer. Eftersom antalet
ord
är så pass många är det förstås helt
meningslöst att försöka
loopa igenom alla ord och kolla vilket som kommer på den
eftersökta platsen. Här måste
vi istället använda den generella metod som man löser i
princip alla sådana
här problem på: man tar först reda på vilken
bokstav som kommer först,
sedan nästa bokstav osv. Man loopar alltså över antalet
bokstäver, inte
över antalet ord. För varje position i ordet loopar vi sedan
över samtliga möjliga bokstäver i denna position och
avgör direkt om detta är den
rätta bokstaven för denna position.
Hur avgör man vilken bokstav som ska vara vid en given position?
Det
är detta som är nyckeln i den här typen av uppgifter -
man räknar
ut (på något sätt), HUR många ord som
börjar med en viss bokstav på
en viss position. Om vi söker ord nummer 7 i alfabetet (OBS:
Här, och i resten av texten,
räknar jag ord 0 som det första ordet i språket - detta
brukar underlätta
en del. Vanligtvis brukar dock uppgiften ha 1 som startindex.) och det
finns 5 ord
som börjar med bokstaven 'a', så kan givetvis inte ordet
starta
med bokstaven 'a'. Istället vet vi nu att det är ord nummer 2
av de
som börjar med 'b' eller en ännu senare bokstav. Om det finns
10 ord som börjar
med bokstav 'b', vet vi nu att ordet börjar med bokstaven 'b'.
Därefter
går vi ett steg framåt i ordet och kollar position nummer
2. Genom att upprepa denna process får vi följande enkla
algoritm: (pseudokod)
x = the ordering number of
the word we're looking for
len = the final number of
letters in the word
curword = ""
for i=0 to len-1
for c=start of
alphabet to end of alphabet
curword[i]=c
y
= number of possible words starting with
curword
if
x<y then break inner loop
x=x-y
end
end
return curword
Koden ovan antar att antalet bokstäver i ordet är detsamma
för
alla ord i språket. Så behöver givetvis inte vara
fallet. Lyckligtvis
finns det ett enkelt trick för att komma runt detta: man
lägger till en extra
bokstav i alfabetet som motsvarar ingen bokstav alls. Givetvis kan
denna speciella "bokstav" endast förekomma i början av ordet
och inte var som helst, så det kan ändå komplicera
beräkningen av antalet ord som börjar
med en viss sekvens av bokstäver.
Vi har nu reducerat problemet till att bestämma _hur_ många
ord
i språket som börjar med en viss sekvens av bokstäver.
Kan vi lösa det
problemet, har
vi löst det ursprungliga problemet genom att helt enkelt applicera
algoritmen ovan.
Vi återgår till exemplet ovan. Hur många ord
börjar
med en given sekvens av t ex 3 bokstäver? Vi vet att bokstav 4 kan
väljas fritt bland de återstående 23 bokstäverna
som inte valts hittills. Sedan
kan bokstav 5 väljas fritt av de 22 kvarvarande bokstäverna
efter det osv. Mer
generellt, antalet ord som börjar med x givna bokstäver
är exakt (26-x)*(25-x)*...*21.
Låt oss studera en lite mer komplicerad uppgift. Vi definierar
ett "zick-zack tal" som ett tal där siffrorna i talet alternerande
är högre
respektive lägre än föregående siffra (och den
andra
siffran är alltid högre än den första. Dessutom ska
alla siffror i talet vara
unika. De sju minsta zick-zack talen som använder siffrorna 1-5
är t ex 13254,
14253, 14352, 15243, 15342, 23154, 24153 (uppgiften är tagen
från BIO
1999).
Problemet är alltså, givet de siffror vi får (och
måste)
använda (t ex 1-5 som ovan), finn det n'te minsta zick-zack talet.
Återigen handlar det helt enkelt om att avgöra hur
många
ord (zick-zack tal alltså) som börjar med en viss sekvens av
bokstäver (siffror).
Här blir det
dock genast svårare, eftersom antalet beror på tidigare val
man
gjort. T ex så finns det två stycken tal som använder
siffrorna
1-5 som börjar med 24... (24153 och 24351) medan det bara finns
ett tal som börjar med
siffrorna 23... (23154).
Tricket för att lösa uppgiften är att finna de faktorer
som
bestämmer antalet möjliga tal som börjar med en viss
sekvens. Det finns ingen standardmetod för att göra detta,
utan det gäller bara att
hitta ett samband, ofta ett rekursivt sådant. I det här
fallet är dessa
faktorer två stycken: antalet möjliga siffror som kan direkt
följa nästa
siffra, samt antalet siffror som är kvar. Det spelar ingen roll
_vilka_ siffror som
är kvar eftersom en siffra _endast_ begränsas av dess
föregående
siffra (att man inte får välja samma siffra flera
gånger är inte
samma typ av begränsning, man kan se det som att man istället
minskar ner utbudet
av lediga siffror). När det gäller inledningen 24... så
är
antalet möjliga siffror för den tredje positionen 2 stycken:
antingen en 1:a eller en
3:a. Antalet siffror kvar är förstås 3. I fallet 23...
måste
nästa siffra vara en 1:a. Notera att antalet möjliga siffror
på position 3 i dessa
fall råkar
vara exakt det antal tal som börjar med sekvenserna 24... och
23...,
men det beror endast på att det är så få siffror
kvar
att välja. Vi har nu krympt problemet ytterligare. Det
återstår att beräkna
antalet möjliga tal givet att vi vet antalet olika siffror som kan
vara på
nästa position, samt hur många siffror som är kvar i
talet. Denna beräkning
kan göras rekursivt. Antag t ex att vi har 7 siffror kvar, och att
nästa
siffra kan vara 3 stycken av dessa. Vi betecknar resultatet av denna
beräkning
som f(7,3). Detta skulle t ex kunna motsvara att vi har kvar siffrorna
1,2,3,5,6,7,8 och att den senaste valda siffran är 4 samt att
nästa
siffra ska vara lägre än den föregående. För
att beräkna
f(7,3) undersöker vi alla 3 möjliga val, dvs i det här
fallet siffrorna 1, 2 och 3. Om vi
väljer 1 så kan vi välja vilken av de 6 kvarvarande
siffrorna nästa gång.
Väljer vi 2 kan vi sedan välja någon av de 5
kvarvarande, osv. Vi får
att f(7,3) = f(6,6)+f(6,5)+f(6,4). Mer generellt,
f(x,y) = f(x-1,x-1) + f(x-1,x-2) + ... + f(x-1,x-y).
Detta kan se lite krångligt ut, men om ni beräknar
några
fler specifika värden på f(x,y) så hoppas jag ni inser
att det blir så.
Återstår gör då basfallen - f(0,0) är
förstås 1 (vi har använt oss av
alla siffror, alltså har vi ett giltig zick-zack tal) och f(x,0)
är förstås 0
(det finns inga giltiga siffror att välja för nästa
siffra). Denna funktion
kan - bör! - förstås beräknas med hjälp av
dynamisk programmering,
så man inte evaluerar samma f(x,y) flera gånger.
Uppgift 1: Implementera Zig-Zag
numbers enligt metoden ovan.
Än så länge har vi bara gått åt ett
håll:
givet ett ordningsnummer, finn ordet. Det är också vanligt
att man måste kunna gå
åt andra hållet (eller åt båda hållen),
dvs givet ett giltigt ord, finn dess ordningsnummer
i språket. Detta problem - att gå åt "andra
hållet"
- är förstår väldigt
snarlikt det första problemet. Faktum är att det finns en
mycket
enkel och effektiv metod för att göra detta om man redan har
en rutin för
att gå åt ena hållet, och den metoden är
binärsökning. Jag utgår
ifrån att ni är bekant med binärsökning, men det
kan vara lätt att glömma
bort att detta är en mycket kraftfull algoritm i många
sammanhang, som man inte får
glömma bort.
Så här kan en binärsökning t ex se ut: (findword
returnerar
det ord som finns på en viss position i språket)
s=word we want to find the
ordering number for
lo=0
hi=number_of_words
while (lo<hi) {
x=(lo+hi)/2
i=strcmp(findword(x),s)
if (i==0)
return x // Word is at this position in language
if (i<0)
lo=x+1
else
hi=x
}
return -1; // Word
not in language
Två saker att notera: jag skriver alltid binärsökning
så
att det undre indexet (lo) pekar på det första talet inom
det kvarvarande intervallet, medan det övre indexet (hi) pekar
på det första talet utanför
intervallet. Detta är ofta mer praktiskt, och det är t ex
så
STL fungerar. Dessutom utgår jag här ifrån att antalet
ord i språket
går att beräkna. Om det skulle vara problematisk kan man
istället sätta hi till MAXINT
eller något annat tillräckligt stort tal (se bara till att
beräkningen
lo+hi inte orsakar overflow!!) och se till att findword returnerar
något specialvärde om man skulle försöka indexera
ett ord som inte finns i språket.
Givetvis kan man göra exakt tvärtom - man skriver en funktion
som
givet ett ord finner ordningstalet, och sedan gör
binärsökningen åt
andra hållet. Detta brukar normalt sätt vara svårare,
om inte annat bli binärsökningen mer komplicerad eftersom
både lo och hi kommer vara strängar istället
för tal, och alla strängar kommer inte tillhöra
språket (att
jämföra med talen, som samtliga är giltiga ordningstal).
Uppgift 2: Givet alla tal
från 1 till n (1 <= n <= 1,000,000,000),
vilket är det m'te (1 <= m <= n) talet i lexikografisk
ordning? T ex om n=16
så är
talen 1-16 i lexikografisk ordning 1, 10, 11, 12, 13, 14, 15, 16, 2,
3,..., 9 och är n=1001 så är de första talen 1,
10, 100, 1000,
1001, 101, 102 etc.
Jag tänkte också kort ge några exempel på
närliggande
problem som också kräver att man arbetar med en siffra i
taget istället för
att loopa igenom
att möjliga tal. (gäller även Bonus Bonds).
Uppgift 3: Antag att vi skriver
ut talen 1, 2, 3, ..., n och räknar antalet siffror vi
använder oss av, var siffra för sig. Om n=12 t ex så
har vi använt oss av 5 ettor (förkommer i talet 1, 10 och 11,
12), en
nolla (i 10), två tvåor (i 2 och 12) och en av varje siffra
3 till 9. Givet
en vektor på 10 element som innehåller det maximala antalet
siffror vi får
använda, hur många tal (från 1) kan vi skriva ut utan
att överskrida
antalet siffror? T ex om indatavektorn är {1,5,1,1,1,1,1,1,1,1}
så är svaret
11 eftersom det krävs 2 tvåor för att skriva ut talen 1
till 12, men
vi har bara en tvåa. Ändrar vi det tredje element till 2
(dvs {1,5,2,1,1,1,1,1,1,1})
så blir svaret 12 - vi har exakt så många siffror av
alla sorter
som krävs för att skriva alla tal mellan 1 och 12.
Tips: Använd binärsökning istället för att
direkt
försöka ta reda på svaret - det är mycket
lättare.
Tävlingsuppgifter
Tillbaka