Hvordan løser man NIO-oppgaver?

En (overdrevent enkel) NIO-oppgave kan se omtrent slik ut:


Oppgave

Ola er overbevist om at han har dårlig trynefaktor, for læreren har gitt ham en lang liste med tall som han vil at Ola skal regne ut som hjemmelekse som må leveres kl. 08:15 dagen etter. Dette har ikke Ola særlig lyst til å gjøre for hånd – skriv et program som kan hjelpe ham!

Input

Første linje inneholder et heltall n, som forteller hvor mange tall som skal adderes. Deretter følger en linje med de n heltallene som skal adderes. n vil være mindre enn eller lik 1000000, og hvert enkelt tall vil være mellom -2000000000 og 2000000000. Eksempel:

3
5 8 -4

Output

Én linje, som inneholder summen av de n tallene. Summen kommer garntert til å være mindre enn eller lik to milliarder. Eksempel:

9


Oppgaveteksten er en eller annen situasjon som skaper behovet for en eller annen utregning, ofte formulert som en litt humoristisk (og litt tåpelig) historie. Noen ganger er oppgaveteksten skrevet slik at den distraherer litt fra hva oppgaven egentlig handler om, så det gjelder å ikke henge seg for mye opp i detaljene der og heller få en forståelse for hva selve utregningen handler om. I dette eksempelet er det ganske enkelt snakk om å addere tall – alt snakket om lekser og innleveringsfrist er irrelevant.

Inputen kommer alltid til å oppfylle betingelsene i oppgaveteksten! Når man skriver programmer i den virkelige verden, er det veldig viktig at man sjekker at inputen faktisk er gyldig (dette kalles å gjøre inputvalidering), men siden dette er en konkurranse og den ikke handler om inputvalidering, har vi sørget for at man ikke trenger å bry seg om dette. Så i dette eksempelet kan programmet uten videre anta at det faktisk bare kommer til å stå heltall i inputen, og at vært tall vil få plass i en int. Noen ganger sier oppgaveteksten også at svaret kommer til å holde seg innenfor en viss grense; det kan du også stole på – selv om det selvfølgelig er mulig at summen av en million tall på opptil to milliarder blir mye mer enn to milliarder, vil inputen være slik at summen holder seg innenfor to milliarder (dvs. at man enten blir bedt om å summere noen få store tall, eller mange små tall, eller mange tall som både er positive og negative). I noen slike oppgaver må du likevel passe på dersom du gjør mellomregninger hvor resultatene underveis kanskje kan bli større.

Det er også veldig viktig at outputen er eksakt på det formatet som blir beskrevet (inkludert linjeskift etter hver linje), og at programmet ditt ikke produserer mer output enn nødvendig. Du kan altså ikke skrive ut hjelpetekster som f.eks. “Skriv inn et tall:” eller “Svaret er:”. Dersom du er på Windows og bruker system("PAUSE") i slutten av programmet for å hindre at konsollvinduet lukker seg når programmet er ferdig, må du fjerne denne før du sender inn. Du kan godt printe ekstra tekst som debuggingshjelp underveis, men du må fjerne dette før du sender inn. main() er også nødt til å returnere 0.

Vi kommer antageligvis ikke til å lese koden din, så kommentarer trengs ikke. Det er heller ikke nødvendig at koden er spesielt lesbar, men for din egen del bør du prøve å ha ryddig kode og forståelige variabelnavn.

Hele besvarelsen må ligge i én .cpp-fil, og det er denne (ikke .exe-filen) du skal sende inn. Dersom du bruker Visual Studio, er det dermed viktig at du krysser av for Empty Project når du lager et nytt prosjekt. Dersom du definerer dine egne klasser, må du også ha klassedeklarasjonen i selve .cpp-filen, selv om dette ikke er god praksis til vanlig.

En perfekt besvarelse av oppgaven ovenfor ser dermed slik ut:

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    int sum = 0;
    for (int i = 0; i < n; i++) {
        int number;
        cin >> number;
        sum += number;
    }
    cout << sum << endl;
    return 0;
}

Når du leverer inn koden, blir den kompilert av vår datamaskin, og programmet blir først kjørt én gang mot et datasett som ligner på eksempelet i oppgaveteksten. Resultatet herfra vises som “Public score”. Trykk “Play”, og så blir programmet ditt kjørt flere ganger med forskjellig input av økende størrelse og vanskelighetsgrad, så får du poeng ut fra hvor mange inputsett programmet ditt svarte rett på – dette vises som “Total score”, og er den faktiske poengsummen din. Det at programmet ditt svarer rett på eksempelinputen i oppgaveteksten er altså ikke noen garanti for at du får full score. Dersom programmet ditt svarer feil på noen av datasettene, føles det litt som å famle i blinde fordi du ikke får se inputen som programmet ikke klarte – men det er litt av utfordringen! ;-) Da må du prøve å tenke ut situasjoner som faller innenfor det oppgaveteksten beskriver og som kanskje ikke programmet ditt takler, og kanskje lage dine egne datasett (kanskje du til og med må skrive et eget program for å generere datasett så du får testet ut ting). Heldigvis du kan sende inn så mange ganger du vil, og den beste besvarelsen på hver oppgave teller – du trenger altså ikke å være redd for å sende flere ganger.

Konkurranseserveren har dessverre noen bugs som gir villedende tilbakemelding i noen tilfeller. De vi vet om hittil er:

  • Compilation failed – Time out: Antageligvis er det stor trafikk på serveren; vent litt og send inn på nytt.
  • Execution killed because of forbidden file access: Programmet ditt bruker for mye minne. Grensen er 256 MB hvis ikke oppgaveteksten sier noe annet.
  • Execution killed because of forbidden syscall rt_sigprocmask.: Du har utført en ulovlig handling på en STL-container (vector, set, map, queue osv.), f.eks. at du går utenfor grensene eller prøver å kopiere et område som ikke eksisterer, eller du har glemt å fjerne system("PAUSE") før innsending.
  • Execution killed with signal 8: Du har utført en matematisk ugyldig operasjon, f.eks. å dele på 0. Merk at hvis du har en int-variabel som du gjentatte ganger dobler, vil variabelen til slutt overflow’e og muligens bli 0. Dette vil ikke i seg selv føre til en krasj, men hvis du deler noe på den variabelen, vil det krasje.
  • Execution killed with signal 11: Programmet ditt prøver å lese eller skrive til minne det ikke eier – typisk fordi du går utenfor grensene på et array eller en vector. Merk også at det er farlig å lage store arrays eller arrays med dynamisk størrelse på denne måten: int numbers[size]; – bruk heller dynamisk minneallokering: int * numbers = new int[size]; .

Komme i gang med C++, del 2: Grunnleggende programmering

Her er en (ganske) kort guide til å komme i gang med programmering. Vi forutsetter at du allerede har installert et utviklingsmiljø; hvis ikke, les artikkelen som det er linket til. Det tar tid å lære seg programmering, og det beste er å ha en skikkelig lærebok eller en god tutorial på nettet, så vi oppfordrer til å finne informasjon på egen hånd etter å ha lest denne artikkelen. Uansett er det viktig at du prøver deg frem og eksperimenterer med hva du kan få til med det du lærer – man kan få til utrolig mye gøy med programmering, og det er bare fantasien som setter grenser!

Hva er en datamaskin?

“Datamaskin” heter “computer” på engelsk, og det betyr “beregner”. En datamaskin er nettopp det – en beregningsmaskin. Alt vi ser på skjermen og hører på høyttalerne er et resultat av enormt mange matematiske utregninger. Datamaskinen eier ikke et fnugg av intelligens; den er kun i stand til å følge instruksjoner om hva den skal regne ut. Programmering går ut på å gi datamaskinen de instruksjonene som må til for at den skal gjøre det vi ønsker.

Programmeringsspråk og kildekode

Internt jobber datamaskinen bare med tall – selv instruksjonene om hva den skal gjøre har forskjellige tallkoder. Dette er veldig tungvindt for mennesker å forholde seg til, og derfor bruker man programmeringsspråk for å skrive programmer på mer lettforståelige måter, og så finnes det egne programmer, såkalte kompilatorer, som oversetter det vi har skrevet til noe datamaskinen kan forstå. Det finnes hundrevis av forskjellige programmeringsspråk; i konkurranseprogrammering er C++ det mest utbredte, og vi skal derfor bruke det. Det er dessverre ikke det enkleste språket å komme i gang med, men følger de samme prinsippene som de fleste andre språk.

All programkoden skrives i kildekodefiler, som i utgangspunktet er vanlig tekstfiler. Det vil si at de ikke inneholder formatering (farger, skrifttyper, fet, kursiv osv.) slik man kan lage i f.eks. Word. Dermed kan man lage kildekodefiler med svært enkle programmer, f.eks. Notepad. Men ofte bruker man en mer avansert teksteditor, som er et skriveprogram som vet om forskjellige programmeringsspråk og kan gi oss hjelp til å skrive kode i disse språkene – f.eks. ved å automatisk fargelegge koden på en slik måte at den blir lettere å lese. I stedet for en vanlig teksteditor går det også an å bruke en IDE (Integrated Development Environment), som er et mer avansert program som kombinerer en teksteditor med mer avanserte verktøy, f.eks. en kompilator og en debugger (et program som kan hjelpe en med å finne feil programmet man lager).

Overordnet programstruktur og output

Her er det enkleste C++-programmet som det går an å lage:

int main() {
	return 0;
}

(For å lage alle mellomrommene foran return trykker du Tab-tasten (til venstre for Q). Dette kalles for innrykk, og selv om C++ ikke bryr seg om hvorvidt det er der eller ikke, er det viktig for at mennesker skal kunne lese koden lettere.) Du kan lage et nytt prosjekt i IDE’en din, skrive inn denne koden og kjøre (starte) programmet – men da vil du merke at dette programmet ikke gjør noe som helst – det starter opp og avslutter rett etterpå, så det er jo ikke så veldig spennende. At det likevel er tre linjer der skyldes at C++ har en del regler for hvordan programmer skal struktureres (alle språk har sine egne strukturregler, som ofte fører til en del ekstra kode som ikke har så mye formål annet enn at det “må være der”) – vi skal straks se litt på disse.

Alle nyttige programmer gir output, dvs. at de viser noe på skjermen, lager en fil, spiller av lyd eller gir en eller annen form for resultat vi kan se eller høre. Det skal en del mer til for å spille av lyd, vise bilder eller å lage 3D-grafikk, men når man først har litt programmeringserfaring, er det ikke så vanskelig å lære seg hvordan man gjør det. Men siden konkurranseprogrammering stort sett handler om å lage programmer som regner ut tallsvar og tekstsvar på oppgavene, skal vi holde oss til konsollprogrammer, altså programmer som kommuniserer med brukeren via tekst som vises i et konsollvindu (også kalt terminal).

Tekstoutput gjøres ved hjelp av cout, som er en kommando for å skrive ut (printe) ting på skjermen – programmerere bruker altså disse ordene ikke bare om å sette tekst på papir, men også om å sette tekst på skjermen. Etter cout kan man gjentatte ganger skrive << fulgt av en ting man vil printe. Dette kan være tall, for eksempel 42, 3.14 eller -1234567890 (merk at man må bruke punktum som desimaltegn, siden C++ er engelsk, og at det er begrenset hvor store tall man kan skrive inn - prøv å skrive større og større tall inntil du får en feilmelding). Man kan også printe tekst; programmeringsordet for tekst er streng (string på engelsk). En streng angis med gåseøyne, f.eks. "Hello world!". Prøv å bytte ut koden du skrev i sted med dette:

#include <iostream>

using namespace std;

int main() {
	cout << "Hello world!" << endl;
	return 0;
}

Tips til de som bruker Visual Studio: For at konsollen ikke skal forsvinne med en gang programmet er ferdig, start programmet ved å trykke Ctrl-F5 på tastaturet. Eventuelt kan du legge inn linjen system("pause"); før linjen return 0;.

Et program utføres én linje av gangen, ovenfra og ned. Noen av linjene er ikke direkte instruksjoner om hva programmet skal gjøre, men er ment som opplysninger om programmet selv. Den første linjen, #include <iostream>, forteller at vi ønsker å benytte ett av de mange bibliotekene (samling med ferdigskrevet kode) som følger med C++, nemlig det som heter iostream. Dette biblioteket inneholder funksjonalitet for input og output. Hva using namespace std; egentlig betyr er ikke så viktig for oss, men det gjør at det blir litt mindre å skrive når vi skal bruke den innebygde funksjonaliteten i C++ (uten dette måtte man ha skrevet std::cout i stedet for cout). Disse to linjene vil man nesten alltid ha med. int main() { markerer starten av selve programmet vårt, og return 0; } markerer slutten - disse to linjene må alltid være der, og i første omgang skal all den interessante koden vår ligge mellom disse linjene. Merk at de fleste kodelinjene må slutte med semikolon.

Prøv å skrive ut flere ting i samme program, både innenfor samme kodelinje og ved hjelp av flere kodelinjer. Eksperimenter også med plasseringen av endl, som er det som skaper nye linjer.

Variabler og input

Et program som viser akkurat det samme hver gang er ikke spesielt spennende. For at et program skal kunne gjøre forskjellige ting hver gang det kjøres, må det lese input, dvs. at de som bruker programmet skal kunne mate opplysninger inn i programmet. Programmet kan så gjøre beregninger basert på inputen og gi svaret som output. Programmer lagrer opplysninger, for eksempel dataene som er blitt gitt som input, eller mellomresultater programmet har regnet ut, i variabler. Vi skal først se litt på hvordan variabler fungerer. En variabel oppfører seg omtrent som x og y i matematikk: den har et navn, den inneholder en verdi, og verdien kan endre seg underveis. Før man kan bruke en variabel må man deklarere den: da oppgir man datatypen til variabelen og hva den skal hete. En datatype bestemmer hva slags opplysninger variabelen kan inneholde. Det finnes en del innebygde datatyper i C++, men den vi skal bruke først heter int - det er en forkortelse for integer, som betyr heltall. En variabel av typen int kan inneholde heltall mellom -2147483648 og 2147483647 (det er en teknisk årsak til at grensene blir akkurat disse tallene, som har å gjøre med at tall lagres i det binære tallsystemet inni datamaskinen - int-variabler lagres med 32 bits, og da kan man representere 232 forskjellige tall). Slik deklarerer vi en variabel x med typen int:

int x;

Å putte en verdi i en variabel kalles for tilordning. Dette gjøres med likhetstegnet, som har en veldig annerledes betydning i programmering enn i matematikk. La oss først gjøre selve tilordningen:

x = 1;

Den første tilordningen til en variabel kalles initialisering. Det går an å deklarere og initialisere på én gang:

int x = 1;

er det samme som

int x;
x = 1;

Når du har deklarert en variabel, kan du skrive den ut:

int x = 42;
cout << x << endl;

Merk forskjellen på å skrive x, som vil gi deg verdien i den variabelen, og å skrive "x", som vil gi teksten x. Merk også at det er forskjell på store og små bokstaver - prøv å endre én av x'ene til X og se hva som skjer (deklarasjonen vil bestemme hva som er "riktig").

Etter at du har deklarert en variabel, men før du initialiserer den, er den uinitialisert. Da vil den inneholde en mer eller mindre tilfeldig verdi. Prøv å bare gjøre

int x;
cout << x << endl;

Hva en variabel heter er fullstendig likegyldig; C++ bryr seg ikke. Den eneste regelen er at de må starte med en bokstav eller en understrek, at det må være et sammenhengende ord uten mellomrom, og at det ikke må krasje med nøkkelordene i språket (reserverte ord som har spesialbetydning, blant annet int, if og for). Så programmet ovenfor hadde vært helt likt hvis det så sånn ut:

int OlaErKul = 1;
cout << OlaErKul << endl;

Variabelnavn bør velges slik at de gir mening for dem som leser programmet - navnet bør beskrive hva variabelen inneholder eller brukes til.

Man kan lage flere variabler, og bruke operatorer for å utføre de fire regneartene:

int x = 4;
int y = 3;
int z = (x + y) * 2;
cout << z - 1 << endl;

Presedensen (reglene for hvilke operatorer som skal regnes ut først) og parentesene fungerer akkurat som i vanlig matematikk - forsøk å skrive x + y * 2 i stedet og se hva svaret blir. Merk igjen at likhetstegnet ikke er en ligning - det er en utregning som gjøres der og da av høyre side av likhetstegnet, og en tilordning av resultatet til venstre side. Så hvis vi etterpå endrer x eller y, har fortsatt z samme verdi:

int x = 4;
int y = 3;
int z = x + y;
cout << z << endl;
x = 8;
y = 15;
cout << z << endl;

Dette betyr også at vi kan bruke den samme variabelen både på venstre og høyre side av likhetstegnet; det er da den gamle verdien som blir brukt for å regne ut den nye:

x = x + 1;

vil ha som effekt å øke verdien av x med 1.

Divisjonsoperatoren er litt spesiell, for den vil alltid runde ned til nærmeste heltall dersom man dividerer to heltall på hverandre. Hvis minst ett av tallene man dividerer på hverandre er desimaltall, vil resultatet bli et desimaltall:

cout << 15 / 4 << endl;
cout << 15.0 / 4 << endl;
cout << 15 / 4.0 << endl;
cout << 15.0 / 4.0 << endl;

Desimaltall kan ikke lagres i int-variabler, men de kan lagres i double-variabler ("double" står for "double-precision floating-point number", som er en gammel databetegnelse på desimaltall med ca. 16 desimaler):

double pi = 3.14;

Når vi mater faste tall inn i variablene våre, gjør programmet altså det samme hver gang vi kjører det, noe som er litt kjedelig. Vi som programmerere kan jo sitte og endre tallene som vi vil, men hvis vi skulle gitt det ferdigkompilerte programmet til noen andre, kan ikke de se koden, og de vil tro at programmet bare kan regne ut svaret på det samme regnestykket hver gang. Det er mye bedre hvis brukerne av programmet får lov til å mate inn verdiene. Dette kalles lesing av input, og gjøres slik:

cin >> x;

Denne linjen vil få programmet til å stoppe og vente på at brukeren skriver inn et tall og trykker enter. Når man skriver programmer som vanlige folk skal bruke, er det lurt å bruke cout før cin for å printe en beskjed om at brukeren skal skrive inn noe - ellers tror brukeren bare at programmet har hengt seg. Husk også at variabelen du leser inn i må være deklarert først. Hvis brukeren skriver inn noe som ikke passer med datatypen til variabelen, vil programmet gi mystiske resultater (det går an å korrigere dette, og det bør man vanligvis også gjøre - men i konkurranseprogrammering antar vi at all inputen blir skrevet inn rett).

Merk at det ikke går an lese input inn i en variabel samtidig som man deklarerer den, så cin >> int x; er ikke lov. Derimot er det lov å lese inn i flere variabler etter hverandre:

cin >> x >> y >> z;

(ingen endl til slutt). Variablene husker ikke hvor opplysningene kom fra, og du kan bruke en variabel som har mottatt input akkurat på samme måte som om du hadde initialisert variabelen i koden. Dersom variabelen inneholdt en verdi før man leser input til den, forsvinner den gamle verdien.

Matematiske funksjoner

Kvadratrøtter kan regnes ut ved hjelp av en innebygd funksjon som heter sqrt, som befinner seg i biblioteket cmath. En funksjon kalles (startes) ved å skrive navnet dens fulgt av en start- og sluttparentes. Parentesene inneholder argumentene til funksjonen, dvs. opplysningene funksjonen må ha for å gjøre jobben sin. sqrt trenger ett argument, nemlig tallet man skal finne kvadratroten av. Resultatet, eller returverdien, fra sqrt er et desimaltall, og har dermed typen double:

#include <iostream>
#include <cmath>

using namespace std;

int main() {
    double x;
    cin >> x;
    double result = sqrt(x);
	cout << result << endl;
	return 0;
}

Nå kan vi f.eks. løse annengradsligninger ved hjelp av abc-formelen. Merk at det går an å deklarere flere variabler av samme datatype på én gang, og å lese inn i flere variabler etter hverandre på samme linje. I koden nedenfor må man skrive inn tre tall: det første kommer inn i a, det andre i b og det tredje i c. Det finnes ingen operator for å opphøye - det finnes en funksjon for det som heter pow, men den enkleste måten å opphøye en variabel i to er å gange den med seg selv. Merk at i koden under deklarerer vi flere variabler på samme linje.

double a, b, c;
cout << "Enter a, b, and c: ";
cin >> a >> b >> c;
double result = (-b + sqrt(b * b - 4 * a * c)) / (2 * a);
cout << result << endl;

Hvis man skal gjøre lignende utregninger flere ganger, kan det kan ofte lønne seg å trekke ut de felles delene av utregningen i egne variabler (både slik at man slipper å gjenta seg selv, og slik at datamaskinen slipper å regne ut det samme flere ganger), sånn som her, hvor vi regner ut begge løsningene av annengradsligningen:

double a, b, c;
cin >> a >> b >> c;
double root = sqrt(b * b - 4 * a * c);
double firstResult = (-b + root) / (2 * a);
double secondResult = (-b - root) / (2 * a);
cout << firstResult << " " << secondResult << endl;

If og else

Nesten alle programmer vil ha behov for å ta avgjørelser basert på input eller verdier som er regnet ut basert på inputen, for å kunne reagere forskjellig på forskjellige situasjoner. Til dette kan vi bruke if/else. Til en if oppgir man en matematisk betingelse som programmet skal sjekke om er sann eller usann. Hvis betingelsen viser seg å være sann, vil det som står i krøllparentesene etter if bli kjørt; hvis ikke vil det som står etter else bli kjørt. Uansett hvilken av grenene som velges, fortsetter kjøringen med første linje etter avslutningskrøllparentesen til else etterpå.

int age;
cout << "How old are you? ";
cin >> age;
if (age < 11) {
	cout << "You're too young to watch The Hobbit." << endl;
}
else {
	cout << "You're old enough to watch The Hobbit." << endl;
}

< betyr "mindre enn", akkurat som i matematikk. Mindre enn eller lik er <=, større enn eller lik er >=, ulik er != og lik er ==. Det er vikitg at det er to likhetstegn når man skal sjekke om to ting er like; det går an å skrive if (a = b), men dette vil ha en annen effekt enn if (a == b), som er riktig måte å sjekke om a og b er like.

Prøv å lage følgende:
- Et program som ber brukeren om å skrive inn to tall, og så viser summen, differansen, produktet og kvotienten av de to tallene. Prøv først å lagre tallene som brukeren skriver inn i en int, og deretter i en double.
- Et program hvor brukeren kan mate inn enkle regneuttrykk som f.eks. 4 + 5, 23 * 4.2 og 19.2 / 2.4 . Til å ta vare på operatoren trenger du å bruke datatypen char, som kan inneholde ett enkelt tegn. Hvis du har en char-variabel c og vil sjekke om den inneholder et plusstegn, kan du gjøre slik: if (c == '+').
- Et program som regner ut og printer begge løsningene av en annengradsligning, men som bare printer én løsning hvis tallet under roten blir 0, og som printer "There are no solutions" hvis tallet under roten blir negativt.

I neste artikkel kommer vi til å lære om løkker, som gjør at programmet kan gjenta de samme handlingene på mange forskjellige opplysninger etter hverandre - dette kan man bruke til å lage enkle spill, eller til å regne på større samlinger med tall.

Segment trees

La oss si at du har en liste a med n tall, og du gjentatte ganger vil bli stilt spørsmålet “hva er summen av tallene fra og med indeks a til, men ikke med, indeks b?”. (Vi bruker “til, men ikke med” fordi det er mer behagelig å regne med enn “til og med”, men prinsippene blir de samme som om det hadde vært “til og med”.) Dersom ba alltid er det samme, kan man bruke en sliding window-algoritme til å forhåndsberegne alle svarene på O(n) tid og deretter svare på q spørsmål på konstant tid per spørsmål, altså total kjøretid O(n + q) – men dette er vanligvis ikke tilfelle. Likevel kan man bruke forhåndsberegning til sin fordel, ved å observere at summen av tallene fra og med a til, men ikke med, b (la oss kalle dette f(a, b)) – er lik f(0, b) – f(0, a). En slik sum av tallene fra 0 og utover kalles for en prefikssum. Dersom vi har alle de n prefikssummene fra og med f(0, 1) til og med f(0, n), kan vi svare på spørsmål i konstant tid per spørsmål. Utregningen av prefikssummene går på lineær tid siden f(0, i) = f(0, i – 1) + a[i - 1]. Dermed får vi igjen en kjøretid på O(n + q).

Dette er jo strålende, men noen ganger arbeider man med dynamiske data: innholdet i listen kan endre seg over tid. Ofte formulerer man slike problemer ved at man starter med en liste med n nuller, og så kommer den en sekvens av operasjoner, hvor hver operasjon enten er en oppdatering (update) eller et spørsmål (query). Totalt vil det komme u oppdateringer og q spørsmål, men hvilken rekkefølge de kommer i er ikke kjent. Slike oppgaver er som regel online, dvs. at for hvert spørsmål som kommer inn, må man svare på det med en gang; man kan ikke lese hele sekvensen med operasjoner først og så svare på alle spørsmålene etterpå. I en slik situasjon kan man jo fortsatt bruke prefikssum-trikset, men da vil hver oppdatering av et tall føre til at man må oppdatere opptil n av prefikssummene (i verste fall er det det første tallet som endres, og da må alle prefikssummene oppdateres) – kjøretiden blir da O(un + q), som er ugunstig hvis det er mange oppdateringer i forhold til spørsmål, men helt fint dersom man vet at det er mange spørsmål i forhold til spørsmål. Dersom man vet at det i stedet er mange oppdateringer i forhold til spørsnål, kan man like godt droppe alle fancy algoritmer, bare vedlikeholde et vanlig array og kjøre en vanlig summering for hvert spørsmål; kjøretiden blir da O(u + qn).

Ofte vet man ikke om det er flest oppdateringer eller spørsmål, evt. vet man at det er omtrent like mange av dem, og da er begge kjøretidene over ganske dårlige. Heldigvis kan vi gjøre det bedre ved å vri litt på prefikssumtrikset: kan vi strukturere summene på en annen måte, slik at hver oppdatering ikke påvirker like mange av de forhåndsberegnede summene? Dette kan vi gjøre på følgende måte:

  1. Dersom lengden av listen ikke er en toerpotens, er det greiest å utvide den til å bli en toerpotens (prøv å finne en bit shifting-basert algoritme får å runde et tall opp til nærmeste toerpotens) og bare fylle på med nuller i de ekstra posisjonene.
  2. Summer alle etterfølgende par av tall: a[0] + a[1], a[2] + a[3], a[4] + a[5] osv. (dvs. f(0, 2), f(2, 4), f(4, 6))
  3. Summer alle etterfølgende par av disse parsummene igjen, slik at man får f(0, 4), f(4, 8) osv.
  4. Summer alle etterfølgende par av disse kvadruppelsummene igjen, slik at man får f(0, 8), f(8, 16) osv.
  5. Fortsett til man når “toppen” og har summen av alle tallene, altså f(0, n).

Vi kan illustrere de forskjellige summene på denne måten:

              78
           /       \
       35             43
     /   \           /   \
  21      14      22      21
  / \     / \     / \     / \
11  10   2  12   8  14  15   6
/ \ / \ / \ / \ / \ / \ / \ / \
4 7 9 1 0 2 4 8 5 3 7 7 7 8 2 4

Hver node representerer altså summen av tallene fra en del av listen, og fra-og-med- og til-men-ikke-med-indeksene kan gjerne lagres på hver node slik at de senere beregningene blir enklere:

                                            0-16
                                  /                       \
                     0-8                                             8-16
                /           \                                   /            \
         0-4                     4-8                     8-12                    12-16
     /         \             /         \             /         \              /         \
   0-2         2-4         4-6         6-8         8-10       10-12        12-14       14-16
  /   \       /   \       /   \       /   \       /   \        /   \       /   \       /   \
0-1   1-2   2-3   3-4   4-5   5-6   6-7   7-8   8-9   9-10  10-11 11-12 12-13 13-14 14-15 15-16

Man kan velge å lagre tallene i en faktisk trestruktur, men det er også mulig å bruke ett array per nivå i treet, eller til og med å legge alle elementene i samme array: da bør man la indeks 0 være ubrukt, legge roten i indeks 1, legge de to nodene på nest øverste nivå i indeks 2 og 3, osv.: 0 78 35 43 21 14 22 21 11 10 2 12 8 14 15 6 4 7 9 1 0 2 4 8 5 3 7 7 7 8 2 4. Gitt en node på indeks i vil barnenodene dens befinne seg på indeksene 2i og 2i + 1, og foreldrenoden vil befinne seg på indeks floor(i / 2).

Dersom n er en toerpotens, inneholder treet 2n – 1 elementer; treet har høyde lg n, og det tar linær tid å konstruere treet. Dersom vi nå får en oppdatering, tar det logaritmisk tid å oppdatere alle delsummene som inneholder det aktuelle elementet. Hvis f.eks. elementet på indeks 5 i den opprinnelige listen skal settes til 5, kan dette gjøres ved å øke alle delsummene som er markert her med 3 (siden tallet opprinnelig var 2):

               *
           /       \
        *             43
     /   \           /   \
  21       *      22      21
  / \     / \     / \     / \
11  10   *  12   8  14  15   6
/ \ / \ / \ / \ / \ / \ / \ / \
4 7 9 1 0 * 4 8 5 3 7 7 7 8 2 4

Det vil si at det tar lg n tid å behandle en oppdatering. Men hvordan kan vi behandle et spørsmål om summen av elementene fra og med indeks a til, men ikke med, indeks b? Nå bør vi prøve å utnytte trestrukturen best mulig, ved å finne frem til de “bredeste” nodene som dekker over deler av det området vi er ute etter (uten å dekke over tall som er utenfor området). Hver node i treet vil representere en delsum som enten:

  • Bare inneholder elementer fra området det spørres om
  • Delvis inneholder elementer fra området det spørres om
  • Ikke inneholder noen elementer fra området det spørres om

La oss kalle disse nodetypene for B, D og I. Ved å traversere treet med et dybde først-søk får man undersøkt nodene fra toppen og nedover, kan man kategorisere nodene ut fra området de dekker over. For hver node må dybde først-søket returnere summen av den delen av det aktuelle listesegmentet som den noden bidrar med. Heldigvis trenger man bare å se på noen få av nodene:

  • Noder av type B er veldig bra, for der kan man bare bruke tallet i den noden direkte uten å se på noen av barna dens, for vi vet at vi er interessert i alle tallene som noden dekker.
  • Noder av type I er også bra, for der vet vi at vi ikke er interessert i noen av nodene som ligger lenger ned, så denne noden bidrar med summen 0.
  • Noder av type D er ikke nyttige i seg selv, så man må gå videre ned og se på barna dens, og denne noden bidrar med summen av barnas summer.

Når man implementerer dette dybde først-søket skikkelig, vil søket bare være innom noen få av nodene. Nedenfor har vi markert med nodetype-bokstaven de nodene man vil støte på dersom man spør om summen fra og med indeks 5 til, men ikke med, indeks 12:

               D
           /       \
        D              D
     /   \           /   \
   I       D       B       I
  / \     / \     / \     / \
11  10   D   B   8  14  15   6
/ \ / \ / \ / \ / \ / \ / \ / \
4 7 9 1 I B 4 8 5 3 7 7 7 8 2 4

Antall noder man trenger å se på per spørsmål vil være proporsjonalt med høyden til treet, altså lg n. Altså kan vi behandle u oppdateringer og q spørsmål på O((u + q) lg n), som er vesentlig mye bedre. Denne datastrukturen kalles et segment tree. Merk at den også fungerer for å finne f.eks. største eller minste tall, eller i det hele tatt en hvilken som helst funksjon av en liste som er slik at f(AB) = f(A) op f(B) (der AB betyr en liste som består av dellistene A og B, og hvor op er en eller annen matematisk operasjon). Her er treet man ville ha fått hvis man var ute etter det minste tallet:

               0
           /       \
       0               2
     /   \           /   \
   1       0       3       2
  / \     / \     / \     / \
 4   1   0   4   3   7   7   2
/ \ / \ / \ / \ / \ / \ / \ / \
4 7 9 1 0 2 4 8 5 3 7 7 7 8 2 4

Merk at dette kan brukes som en alternativ løsning på “Pyramid”-oppgaven, men sliding window er enklere.

OPPGAVE: “Beads” (oppgave F) fra IDI Open 2011 (testdata her). (Vi har ikke gitt noe pseudokode i denne artikkelen, for øket utfordring.)

Bonusoppgave (vi sier ikke hva løsningsmetoden er): “The valley of Mexico” fra IOI 2006 (datasett her).

Sliding window-algoritmer

La oss si at vi har en liste med n tall, og at vi ønsker å finne summen av alle sammenhengende dellister med k elementer (k <= n). Brute force-løsningen er:

for (int i = 0; i < n - k + 1; i++) {
    int sum = 0;
    for (int j = i; j < i + k; j++) {
        sum += numbers[j];
    }
    cout << sum << endl;
}

Kjøretiden er O((n – k) * k), som tilsvarer O(n^2) hvis k er proporsjonal med n. Men trenger vi å regne ut hele summen på nytt for hvert element? Summen av element 1 til k er jo det samme som summen av element 0 til k – 1, bortsett fra at vi legger til element k og fjerner element 0. Dette kan vi fortsette med videre bortover – altså vedlikeholder vi en løpende sum over et “vindu” som vi skyver bortover, og hele tiden justere den ved å trekke fra elementet som forsvinner ut og legge til elementet som rykker inn. Dette kalles en sliding window-algoritme:

// Bygg opp det initielle vinduet
int windowSum = 0;
for (int i = 0; i < k; i++)
    windowSum += numbers[i];
cout << windowSum << endl;
// Skyv vinduet bortover (i markerer starten av det nye vinduet, 
// som altså starter på element i og slutter på element i + k - 1)
for (int i = 1; i < n - k + 1) {
    windowSum += numbers[i + k - 1] - numbers[i - 1];
    cout << windowSum << endl;
}

Men hva gjør vi når informasjonen om element x har rykket ut og element y har rykket inn ikke er nok til å svare på det vi lurer på om hvert vindu? Dette skjer eksempelvis når det vi lurer på er hva som er den største verdien i vinduet. Til dette kan vi bruke en heap, også kjent som en prioritetskø (priority queue). Denne datastrukturen kommer i to utgaver. En max-heap er en struktur hvor du kan legge inn elementer i en hvilken som helst rekkefølge, og hver gang du tar ut et element, vil du få det største elementet i heapen. En min-heap vil alltid gi deg det minste elementet. Å sette inn og å ta ut fra en heap som inneholder n elementer tar O(lg n) tid. Det anbefales å studere hvordan en heap er bygd opp, men til daglig bruker vi den ferdigbygde implementasjonen i C++, som heter priority_queue og ligger i <queue>.

Tanken er altså å bruke en heap til å holde rede på elementene som til enhver tid ligger i vinduet – dermed vet vi at det største elementet i vinduet vil ligge øverst i heapen. Men hvordan skal vi fjerne elementet som skal ut hver gang vi forskyver vinduet? Det å fjerne et element (annet enn toppelementet) fra en heap er egentlig ikke så vanskelig, men det krever at man vedlikeholder en peker til elementets plassering inni heapen, slik at man ikke bruker tid på å finne ut hvor elementet befinner seg. Dette støttes ikke av priority_queue i C++. Heldigvis kan man bruke følgende triks: vi kan ganske enkelt la være å fjerne elementene etterhvert som vi forskyver vinduet, men hver gang vi henter ut det største elementet, kontrollerer vi at elementet befinner seg inni det nåværende vinduet – hvis ikke, forkaster vi det og henter ut på nytt. For raskt å kunne finne ut hvorvidt elementet vi hentet ut av heapen befinner seg inni vinduet eller ikke, registrerer vi både tallverdien og indeksen når vi legger noe inn i heapen. Fordi heap-operasjonene har kjøretid O(lg n), blir det ingen merkbar ytelsesforskjell pga. de ekstra elementene. (Tilsvarende triks kan man bruke i Dijkstras korteste vei-algoritme.)

Når vi skal ha egendefinerte structs inni en heap, er vi nødt til å fortelle heapen hvordan elementene skal sorteres – dette må gjøres ved å overloade <-operatoren (og det må gjøres etter at man har definert structen, og før resten av koden). En detalj her er at priority_queue alltid er en max-heap, så hvis du ønsker en min-heap må du implementere den slik at hvis element a er mindre enn element b, slik at du vil at a skal havne øverst, må a < b returnere false (slik at heapen tror at a er størst og dermed skal gis ut først):

#include <queue>
#include <iostream>

using namespace std;

struct Entry {
    int value;
    int index;
};

bool operator < (const Entry & a, const Entry & b) {
    if (a.value == b.value)
        return a.index < b.index;
    return a.value < b.value;
}

OPPGAVE: Implementer resten av algoritmen for å finne største verdi inni et sliding window av størrelse k ved hjelp av en heap. Heapen kan deklareres slik: priority_queue<Entry> window;. Nye elementer deklareres og legges inn slik: Entry e = {someValue, someIndex}; window.push(e);. Største element hentes ut slik: Entry e = window.top();, og slettes slik: window.pop();. Løsningen står nedenfor.

int main() {
    // Les input
    int n, k;
    cin >> n >> k;
    vector<int> numbers(n);
    for (int i = 0; i < n; i++)
        cin >> numbers[i];
    
    // Bygg opp det initielle vinduet
    priority_queue<Entry> window;
    for (int i = 0; i < k; i++) {
        Entry entry = {numbers[i], i};
        window.push(entry);
    }
    cout << window.top().value << endl;
    // top() returnerer toppelementet uten å fjerne det, 
    // og pop() fjerner toppelementet uten å returnere det, så man trenger begge to
    
    // Skyv vinduet bortover (i er elementet som skal inn, så i - k + 1 er det første elementet i det nye vinduet)
    for (int i = k; i < n; i++) {
        Entry newEntry = {numbers[i], i};
        window.push(newEntry);
        Entry greatest;
        while (true) {
            greatest = window.top();
            if (greatest.index > i - k) // Bare avbryt løkken dersom elementet vi fikk ut er inni det nåværende vinduet
                break;
            else
                window.pop();
        }
        cout << greatest.value << endl;
    }
}

Dersom man hadde slettet elementene fra heapen med en gang de gikk ut av vinduet, ville heapen aldri ha inneholdt mer enn k elementer, og kjøretiden ville ha blitt O(n lg k). Med vår fremgangsmåte risikerer vi at heapen ender opp med å inneholde alle elementene (hvilken situasjon vil forårsake dette?), så kjøretiden blir O(n lg n), som er omtrent like bra, og mye bedre enn O(n^2).

OPPGAVE: “Pyramid” fra IOI 2006 (testdata her). I tillegg til at det er to todimensjonale sliding windows inni hverandre (som man riktignok ikke trenger en heap til, så vidt jeg husker) trenger man et ekstra triks for å få optimal kjøretid.

Dynamisk programmering

Memoisering (memoization) og dynamisk programmering (dynamic programming / DP) er to ganske like teknikker for å designe algoritmer, og de kan brukes på mange forskjellige problemstillinger. Selve teknikken er relativt enkel, men den kan anvendes på mange kreative måter, så det krever mye oppgavetrening å bli vant med det.

Idéen bak teknikkene illustreres fint av problemet med å regne ut Fibonacci-tall. Fibonacci-tallene er en tallrekke som begynner med to ettall, og deretter er hvert tall summen av de to forrige: 1, 1, 2, 3, 5, 8, 13, 21, … Dette kan defineres rekursivt slik:
f(0) = 1
f(1) = 1
f(n) = f(n – 1) + f(n – 1) når n > 1
Dette implementerer vi enkelt i C++:

long long fib(int n) {
    if (n < 2)
        return 1;
    return fib(n - 1) + fib(n - 2);
}

Med unntak av at selv long long (64-bits heltall) fort blir en for liten datatype fordi Fibonacci-tallene blir svært store ganske fort, har denne fremgangsmåten et problem som blir åpenbart når vi prøver å mate inn større og større verdier: allerede for så små verdier som 40 blir den uholdbart treg, og det vil vise seg at hver gang man øker n med 1, vil kjøretiden øke med en faktor på ca. 1.6. Hva skyldes dette, når det er en så enkel beregning?

Hvis vi tegner opp en call graph, vil vi se hva som går galt: f.eks. må fib(5) regnes ut ved hjelp av fib(4) og fib(3). Men fib(4) må regnes ut ved hjelp av fib(3) og fib(2), så hele utregningen av fib(3) gjøres to ganger – og det blir bare verre og verre jo lenger ned man går:

fib(5)
    fib(4)
        fib(3)
            fib(2)
                fib(1)
                fib(0)
            fib(1)
        fib(2)
            fib(1)
            fib(0)
    fib(3)
        fib(2)
            fib(1)
            fib(0)
        fib(1)

Løsningen på dette er å innføre memoisering (uten r – ordet kommer fra “memo”, altså huskelapp, ikke fra memorisering), som går ut på å bruke et array eller et hashmap til å holde rede på svarene underveis etterhvert som man finner dem, slik at man slipper å gjøre nye utregninger av svar man allerede har funnet. (Et hashmap er et slags dynamisk array hvor indeksene kan være hva som helst, også f.eks. strenger (så det kalles nøkler i stedet for indekser), og hvor man kan sette inn nøkler ved behov. I C++ er hashmap implementert i klassen map.) Det første den rekursive funksjonen da må gjøre er å slå opp i arrayet / hashmap’et for å sjekke om svaret allerede er regnet ut. Dersom man bruker et array må man preallokere det til rett størrelse (pass på off-by-one-feil – hvis du trenger arrayindekser opp til og med n, må arrayet ha størrelse n + 1) og fylle ut elementene med sentinel-verdier (verdier som ikke er gyldige svar, og som man da kan bruke til å detektere at plassen ikke er fylt ut ennå). Enten man bruker array eller hashmap må man også starte med å legge inn basetilfellene.

Memoisering med array:

#include <iostream>

using namespace std;

const long long EMPTY = -1;

long long fib(int n, long long * mem) {
    if (mem[n] != EMPTY) // Har vi svaret fra før av?
        return mem[n];
    long long result = fib(n - 1, mem) + fib(n - 2, mem);
    mem[n] = result; // Husk å lagre resultatet i arrayet!
    return result;
}

int main() {
    int n;
    cin >> n;
    // Allokering
    long long * mem = new long long[n + 1];
    // Initialisering med sentinel-verdier
    for (int i = 0; i < n + 1; ++i) {
        mem[i] = EMPTY;
    }
    // Basetilfeller
    mem[0] = 1;
    if (n > 1) //...ellers er ikke arrayet stort nok
        mem[1] = 1;
    cout << fib(n, mem) << endl;
    return 0;
}

Man kunne godt ha hatt arrayet som en global variabel – det ville ha gått marginalt raskere, men kan bli rotete i store programmer.

Memoisering med hashmap:

#include <iostream>
#include <map>

using namespace std;

long long fib(int n, map<int, long long> & mem) { // Viktig å sende map'et som referanse for å unngå kopiering
    if (mem.find(n) != mem.end()) // Har vi svaret fra før av?
        return mem[n];
    long long result = fib(n - 1, mem) + fib(n - 2, mem);
    mem[n] = result; // Husk å lagre resultatet i arrayet!
    return result;
}

int main() {
    int n;
    cin >> n;
    // Allokering (sentinel-verdier trengs ikke i et map)
    map<int, long long> mem;
    // Basetilfeller
    mem[0] = 1;
    mem[1] = 1;
    cout << fib(n, mem) << endl;
    return 0;
}

Dersom man hadde printet et mellomresultat hver gang man fant det, ville man ha sett at resultatene dukker opp nedenfra og opp, selv om vi angrep problemet ovenfra og ned. Dette kan man utnytte til å lage en marginalt mer effektiv løsning som ikke bruker rekursjon (og som dermed også vil fungere i situasjoner hvor n kan være stor), ved at man bare itererer over tabellen og fyller den ut:

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    long long * mem = new long long[n + 1];
    mem[0] = 1;
    if (n > 1)
        mem[1] = 1;
    for (int i = 2; i <= n; ++i) { // Husk <= i stedet for den vanlige <
        mem[i] = mem[i - 1] + mem[i - 2];
    }
    cout << mem[n] << endl;
    return 0;
}

Dersom man ikke er interessert i mellomresultatene, trenger man ikke arrayet en gang:

#include <iostream>

using namespace std;

int main() {
    int n;
    cin >> n;
    if (n < 2) {
        cout << 1 << endl;
        return 0;
    }
    long long previous = 1;
    long long current = 1;
    long long next;
    for (int i = 2; i <= n; i++) {
        next = current + previous;
        previous = current;
        current = next;
    }
    cout << current << endl;
    return 0;
}

I praksis bruker man vanligvis DP, med mindre man er i en situasjon hvor man vet at ikke alle mellomresultatene vil være nødvendig å beregne – da vil memoisering gå raskere fordi den aldri regner ut mellomresultater som ikke vil trenges senere.

DP brukes ofte når man er i en situasjon hvor man har et problem hvor løsningen består av en sekvens med handlinger, og det gjelder å finne den optimale sekvensen (ut fra en eller annen definisjon av “optimal sekvens), og hvor man i hvert steg kan velge mellom flere forskjellige handlinger – men hvor man ikke kan forutsi hvilken handling som er best. La oss betrakte myntutdelingsproblemet: man har n kroner som skal deles ut ved hjelp av færrest mulig mynter og sedler. Løsningen er altså en sekvens av valører (mynt- og seddelverdier). Med det norske myntsystemet kan man bruke en grådig algoritme: del hele tiden ut den største valøren som er mindre enn eller lik det gjenværende beløpet. Men med noen myntsett fungerer ikke dette: hvis myntsettet f.eks. består av enkroninger, firekroninger og femkroninger, vil den grådige algoritmen dele ut åtte kroner som én femmer og tre enkroninger, mens den optimale løsningen er to firekroninger. Nå er vi altså i en situasjon hvor man ikke kan forutsi hvilken handling som er best. Løsningen er å prøve alle mulige handlinger og se hva som skjer. La oss si at man skal dele ut 13 kroner. Den beste måten å gjøre det på vil enten være å først dele ut en enkroning og så dele ut 12 kroner på best mulig måte, eller å først dele ut en firekroning og så dele ut 9 kroner på best mulig måte, eller å først dele ut en femkroning og så dele ut 8 kroner på best mulig måte. Hvilken av disse som er best, vet vi ikke – så vi prøver alle sammen, og løser først delproblemene med å dele ut hhv. 12, 9 eller 8 kroner. Disse vil føre til nye delproblemer, som etterhvert vil begynne å overlappe – dermed trenger man memoisering eller DP.

OPPGAVE: Skriv et program som løser myntutdelingsproblemet med DP. Inputen består av først en linje med to tall n og k: og antallet valører og antallet beløp som skal deles ut. Deretter kommer en linje med n heltall, som er valørene (1 vil alltid være inkludert, men tallene er ikke nødvendigvis sortert – bruk og sort() til å sortere en vector), og så kommer k linjer med ett tall på hver: beløpene som skal deles ut. For hvert beløp, skriv ut det optimale antallet mynter.

Eksempelinput:

3 2
1 5 4
8
13

Eksempeloutput:

2
3

OPPGAVE: Andre ganger er problemstillingen todimensjonal, slik som i følgende IOI-oppgave fra 2004: http://olympiads.win.tue.nl/ioi/ioi2004/contest/day2/phidias.pdf . Løs denne også.

I myntutdelingsproblemet og i Phidias antar man at man har ubegrenset tilgang på mynter av de forskjellige valørene. Faktisk er det en forutsetning for DP at det ikke finnes delte ressurser som spises opp av løsningen, for da er det ikke sikkert at en løsning på et delproblem kan brukes (siden delproblemløsningen pluss måten vi kom oss frem til det delproblemet til sammen bruker for mye ressurser). Men noen ganger kan man håndtere slike delte ressurser ved å innføre en ekstra dimensjon. La oss si at du skal på bilferie, og har lagt opp en rute som går innom n byer (og dermed består av n – 1 veistrekninger mellom disse byene). Avstanden mellom hver by er et heltallig antall mil. I hver by finnes det en bensinstasjon, hvor bensinprisen er et heltallig antall kroner per liter. Bilen er en SUV som sluker eksakt én liter per mil. Hvordan kan man komme seg fra start til slutt på billigst mulig måte, gitt at man starter med tom tank som rommer et gitt, heltallig antall liter og ikke er interessert i å ha noe bensin igjen på tanken når man ankommer den siste byen? For å klare dette, holder det ikke å løse problemet “hva er billigste måte å komme seg til by i på?” ved å løse problemet “hva er billigste måte å komme seg til by i – 1 på?”, fordi billigste måte å komme seg til en by på involverer å kjøre tanken tom akkurat når man ankommer byen, noe som ikke er smart dersom bensinen er kjempedyr i den byen. Vi er nødt til å innføre mengden gjenværende bensin på tanken som en dimensjon (dvs. som et parameter) i problemstillingen, slik at vi kan løse problemet “hva er billigste måte å komme seg til by i på dersom jeg skal ha j liter igjen på tanken når jeg kommer dit?” ved å løse problemet “hva er billigste måte å komme seg til by i – 1 på dersom jeg skal ha k liter igjen på tanken når jeg kommer dit?” for forskjellige verdier av k og se hvilken som er billigst. Problemet er altså todimensjonalt her også, men uten at det er åpenbart fra oppgaven.

OPPGAVE: Skriv et program som løser bensinstasjonproblemet med DP. Første linje inneholder n og t: antall byer og kapasiteten til tanken; andre linje inneholder n – 1 heltall som er avstandene mellom de forskjellige byene; tredje linje inneholder n – 1 heltall som er bensinprisene i de forskjellige byene unntatt den siste (fordi prisen der er uinteressant siden man ikke skal fylle der). Output er prisen for den billigste måten å klare det på.

Eksempelinput:

5 25
5 22 10 15
40 10 30 22

Eksempeloutput:
(Kommer)

(Merk: Denne oppgaven kan muligens løses grådig også, men vi har ikke bevist at den grådige løsningsmetoden er korrekt.)

Til sist: merk at noen ganger er det flere potensielle sluttilstander, og man kan ikke forutsi hvilken som er best – da må løse for alle disse, og så avslutte med å løpe gjennom alle de potensielle sluttilstandene for å finne den beste.

Brute Force

Brute force

Er nyttig når man ikke kommer på bedre løsninger. Som regel består det i å prøve alle mulige løsninger (rekkefølger, subset osv.).

Alle permutasjoner

Dersom løsningen man leter etter er en rekkefølge (permutasjon), vil det å prøve alle ta O(N!) tid. 10! er allerede 3.6 millioner, så dette blir fort upraktisk rundt N = 13 selv på raske datamaskiner.

Det mest berømte problemet som går ut på å finne en rekkefølge er “The Travelling Salesman Problem” (TSP). Her skal en besøke en gitt liste med steder, og målet er å finne den rekkefølgen som minimerer den totale reiselengden.

void tspBruteForce(int currNode, double currLen, int currStep) {
  // Continue only if this route is promising:
  if (currLen + dist[currNode][0] < bestTrip) {
    // If this is the last node:
    if (currStep == numSteps) {
      currLen += dur[currNode][0];
      currPath[currStep] = 0;
      bestTrip = currLen;
      for (int i = 0; i <= numSteps; ++i) {
        bestPath[i] = currPath[i];
      }
    } else {
      // Try all possible routes:
      for (int i = 1; i < numSteps; ++i) { 
        if (!visited[i]) {
          visited[i] = true;
          currPath[currStep] = i; 
          tspBruteForce(i, currLen+dist[currNode][i], currStep+1);
          visited[i] = false; 
        } 
      } 
    } 
  } 
}

Fordelen med en rekursiv funksjon fremfor STL next_permutation er at man har mulighet til å avbryte søket tidlig om rekkefølgen man holder på med er håpløs (og det er de ofte i TSP). Sett at man allerede har funnet en løsning med lengde 1000. Om man holder på å evaluere enda en rekkefølge men kun har besøkt 50% av stedene og allerede har brukt en lengde som er >= 1000, kan man trygt unnlate å teste alle permutasjoner som starter med denne rekkefølgen. (tspBruteForce gjør en lignende avgrensing, som antar at trekantulikheten dist[A][C] <= dist[A][B] + dist[B][C] holder – raskeste vei hjem er direkte hjem, ikke via andre steder).

Rekursiv testing av alle rekkefølger er temmelig vanlig som en løsning som gir noen poeng på mange oppgaver, så om man ikke føler seg trygg på det er det verdt det å sette seg ned og mestre dette.

Alle subset

En enkel metode for å teste alle subset av N elementer er å telle opp til 2^N. Etthvert subset av N elementer kan representeres ved hvilke bits som er satt i et tall mellom 0 og 2^N. F.eks tallet 5 = 101 (base 2) og det kan man tolke som at element nummer 0 er i settet, element 1 er det ikke, og element 2 er i settet.

Hvordan finne ut om bit nummer i er satt i et heltall x i C++:

if (x & (1 << i))

Hvordan sette bit nummer i til 1 (strengt tatt ikke nødvendig for å teste alle subset, men ofte brukt om man skal bruke bitmasks til andre ting, f.eks bygge opp en løsning nedenfra og opp):

x = x | (1 << i)

Hvordan sette bit nummer i til 0 (som over, ikke så nødvendig for BF, men kjekt i andre tilfeller):

x = x & ~(1 << i)

Ta f.eks en oppgave der man har kasser med forskjellig vekt, og vil laste en lastebil med en bestemt maksgrense for vekt slik at man har lastet mest mulig vekt på lastebilen. Da kan man prøve alle subset av kassene med denne metoden:

int best = 0;
for (int bitmask = 0; bitmask < (1 << n); ++bitmask) {
  int tot = 0;
  for (int i = 0; i < n; ++i) {
    if (bitmask & (1 << i)) {
      tot += weight[i];
    }
  }
  if (tot < limit && tot < best) best = tot;
}

Selv om dette ikke er like ille som å prøve alle rekkefølger, tar det fort tid. Kompleksiteten er O(2^N), og det begynner å bli problematisk når N er mellom 20 og 30 avhengig av hvor tungt det er å teste hvert subset.

Pruning

Når grenene blir for lange i hekken eller i treet, klipper vi dem. Dette kalles “pruning”. I algoritmeverdenen brukes pruning også til å unngå å gå for dypt inn i løsninger som er håpløse. Som i eksempelet med Travelling Salesman-problemet, der man kan slutte å evaluere en sti (og alle løsninger som starter med denne stien, når lengden av stien er større enn en løsning vi allerede har funnet). Slik pruning kan i mange tilfeller være forskjellen på en løsning som fungerer helt greit på de tilfellene man er interessert i, og en løsning som bruker år og dag.

Oppgaver

Rush Hour, se siste side i IOI 2005 Newsletter 8.

Vi jobber alltid med 6×6 grid. Første linje i input er antallet biler N. Deretter N linjer med tre heltall, X Y Z L, der X er X-koordinaten (regnet fra øverste venstre hjørne) og Y er Y-koordinaten til bilens øverste venstre hjørne. Z er 0 om bilen er horisontalt plassert, og 1 om bilen er vertikalt plassert. L er bilens lengde og er enten 2 eller 3.

Output er ett heltall, det minste antall trekk som trengs for å flytte bilen ut utgangen (ett skritt ut).

F.eks for tegningen som er i newsletter:

12
2 0 1 2
3 0 0 3
3 1 1 2
0 2 0 2
2 2 1 2
0 3 0 2
3 3 0 2
5 3 1 3
0 4 1 2
1 4 1 2
2 4 0 2
3 5 0 2

Output

50

Introduksjon til søking i grafer

I denne posten vil vi ta for oss noen grunnleggende algoritmer for å søke i grafer. Vi begynner med å introdusere noen problemer for å motivere algoritmene, deretter vil vi dekke to datastrukturer kalt queue og stack, før vi ser nærmere på bredde-først søk og dybde-først søk.

Penger på tur

En vennegjeng har vært på interrail; Og som man ofte gjør på tur for enkelhetens skyld har de lagt ut for hverandre i forbindelse med diverse felles utgifter. Nå er de kommet hjem igjen og tiden er inne for å gjøre opp. Problemet er at det ikke bare er fryd og gammen å være på tur, så en del vennskap har gått dunken grunnet trange togkupèer og løse mager. De som er blitt uvenner nekter å snakke med hverandre, og det er enda mindre tenkelig at de vil utveksle penger seg i mellom. Gitt hvor mye penger hver enkelt har lagt ut og hvilke personer som forsatt er venner er din oppgave å finne ut om det er mulig å gjøre opp for turen slik at alle har betalt like mye.

Epler og pærer

Som nyansatt barnehagearbeider tok du med deg en pose epler og en pose pærer første dag på jobb i håp om å oppnå litt godvilje. Til din forferdelse når du ankommer jobb oppdager du at det er en skålvekt midt på uteplassen. Alle voksne vet jo at ingen epler eller pærer veier like mye, dette gjør desverre ikke barn. Du ser allerede for deg bråket som oppstår når to venner som har fått samme frukt sammenligner dem på vekten og innser at den ene har fått mer enn den andre. På den andre siden er også barn klar over at epler og pærer ikke kan sammenlignes, så dette kommer ikke til å bli et problem. Du haster bort til nærmeste barnehageansatt og ber om en raskt introduksjon angående hvem som er venner i barnehagen. Gitt alle vennskapene blant barna er din oppgave å gi en utdeling av epler og pærer slik at dersom to barn er venner så får de forskjellig type frukt eller si at en slik fordeling ikke eksisterer. Du kan anta at du har tilstrekkelig med epler og pærer til å realisere en hver løsning.

Utrykningstid

Brannsjefen i byen er bekymret for utrykningstiden deres på tross av at brannstasjonen er plassert midt i sentrum. Grunnen er at de i det siste har fått mange falske alarmer om brann. Han vil derfor at du skal vurdere følgende senario: de får en alarm og rykker ut til denne, den viser seg å være falsk, men på veien har de mottatt en ny alarm. Hvor mange kryss må brannbilen maksimalt kjøre gjennom før han kommer frem til neste potensielle brann? Grunnen til at kryssene er interessant er at på veiene slipper bilene stort sett frem brannbilen, mens det i kryssene fort kan bli kaos. Gitt en oversikt over alle kryssene i byen og hvordan de er koblet sammen er din oppgave å returnere hvor mange kryss brannbilen må gjennom i verste tilfellet fra den ene utrykningen til den neste.

Queue

I C++ er det en datastruktur som heter queue (kø). Denne fungerer nettopp slik en kø bør, først inn resulterer i først ut også. La oss ta en titt på et eksempel.

#include<iostream>
#include<queue>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    queue<int> numbers;
    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        numbers.push(x);
    }
    
    while(!numbers.empty()) {
        int x = numbers.front();
        numbers.pop();
        cout << x << endl;
    }

    return 0;
}

Her ser du de fire viktigste tingene du bør kunne om en kø:
- Hvordan du lager en kø,
- hvordan du legger til elementer i en kø (push),
- hvordan du henter det neste elementet i en kø (front) og
- hvordan du fjerner det fremste elementet i køen (pop).

Om du hadde gitt denne koden inputen:

4
1 2 3 4

Hadde output vært følgende:

1
2
3
4

Stack

Om du derimot hadde valgt å bruke en stack som køsystem ville du endt opp med verdens mest urettferdige kø. Den vil nemlig hele tiden gi ut den som sist ble puttet på stacken.

#include<iostream>
#include<stack>

using namespace std;

int main()
{
    int n;
    cin >> n;
    
    stack<int> numbers;
    for(int i = 0; i < n; ++i) {
        int x;
        cin >> x;
        numbers.push(x);
    }
    
    while(!numbers.empty()) {
        int x = numbers.front();
        numbers.pop();
        cout << x << endl;
    }

    return 0;
}

Eneste forandringen er at vi nå bruker en stack i stedet for queue. Om vi hadde gitt programmet samme input nå, ville output blitt

4
3
2
1

Bredde-først søk

Et bredde-først søk er et søk som starter i en node og undersøker grafen på følgende måte: Først undersøker den noden selv, deretter alle nodene som har avstand 1 til start, deretter alle som har avstand 2 osv.

Under et søk deler vi nodene i grafen inn i uoppdaget, oppdaget og utforsket (henholdsvis hvit, grå og svart på figuren over). Når vi utforsker en node vil alle dens naboer som er uoppdaget bli oppdaget. Hvordan vi velger neste node vi skal utforske avgjøres av typen søk, og for bfs (bredde-først søk) er det den noden som er ble oppdaget først av de ikke-utforskede nodene. En kø er perfekt for denne oppgaven. Ved å alltid utforske noden fremst i køen og ved å legge uoppdagede naboer inn i køen når vi utforsker en node vil vi oppnå akkurat denne lagvise oppførselen som et bfs skal ha. Under finner du en oversikt over hvordan oppdaget-listen og køen ville sett ut under animasjonen over, det kan være en god øvelse å verifisere dette.

     Oppdaget                Kø
(a)                       (a)
(a, b, c)                 (b, c)
(a, b, c, d, e)           (c, d, e)
(a, b, c, d, e, f, g)     (d, e, f, g)
(a, b, c, d, e, f, g)     (e, f, g)
(a, b, c, d, e, f, g, h)  (f, g, h)
(a, b, c, d, e, f, g, h)  (g, h)
(a, b, c, d, e, f, g, h)  (h)
(a, b, c, d, e, f, g, h)  ()

Både bfs og dfs (dybde-først søk, som vi skal se på i neste avsnitt) kan løse mange forskjellige problemer på grafer. De kan blant annet sjekke om det finnes en sti mellom to noder, finne sammenhengende komponenter, sjekke om nodene i en graf kan fargelegges slik at for hver kant har de to endepunktene ulik farge, finne sykler osv. Men en av de egenskapene som gjør bfs veldig anvendelig er at den undersøker nodene i grafen ut i fra distansen fra start, noe som gjør at et bfs ikke bare finner en vilkårlig sti mellom to noder, men en korteste sti. Under ser du et program som tar en graf, start og slutt som input og verifiserer om det finnes en sti mellom disse eller ikke.

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector< vector<int> > graph(n);
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    int start, stop;
    cin >> start >> stop;
    
    vector<bool> visited(n, false);
    queue<int> next;

    next.push(start);
    visited[start] = true;

    while(!next.empty()) {
        int pos = next.front();
        next.pop();
        
        for(int i = 0; i < graph[pos].size(); ++i) {
            int nghbr = graph[pos][i];
            if(!visited[nghbr]) {
                next.push(nghbr);
                visited[nghbr] = true;
            }
        }
    }

    if(visited[end])
        cout << "Det er en sti mellom " << start <<
            " og " << stop << endl;
    else
        cout << "Det er ikke en sti mellom " << start <<
            " og " << stop << endl;

    return 0;
}

Dybde-først søk

Vi også kjapt nevne dybde-først søk. I denne posten vil vi ikke utforske de egenskapene et dfs har som et bfs ikke har, annet at det grunnet sin rekursive natur kan ha en litt penere implementasjon. Den virkelige kraften til dfs vil vi komme innom på et senere tidspunkt i en ny post. Forskjellen fra bfs er at et dfs utforsker den noden den oppdaget sist først i stedet for den noden den oppdaget først. Dette gjør at ved kun å bytte fra queue til stack vil bfs implementasjonen vår bli en dfs implementasjon. Det finnes dog en vanligere (og kanskje lettere om du er komfortabel med rekursjon) måte å implementere et dfs på, nemlig ved hjelp av rekursjon.

#include<iostream>
#include<vector>

using namespace std;

void dfs(int pos, vector<bool>& visited, const vector< vector<int> >& graph)
{
    if(visited[pos])
        return;
    visited[pos] = true;
    
    for(int i = 0; i < graph[pos].size(); ++i)
        dfs(graph[pos][i], visited, graph);
}

int main()
{
    // les inn grafen
    
    vector<bool> visited(n, false);
    dfs(start, visited, graph);
    
    // visited[stop] er nå true hvis og bare hvis
    // det eksisterer en sti fra start til stop
}

Kjøretid

Både bfs og dfs har kjøretid lineær i antall noder og kanter, nemlig O(n+m). Vi kan derfor anvende algoritmene på grafer med en million noder på under et sekund om vi har en datamaskin fra dette årtusenet. Det som ofte er mest tidkrevende er å lese grafen, dette gjør at man ofte holder seg til grafer rundt 100 000 noder og kanter når det kommer til konkurranser.

Vi retter nå oppmerksomheten vår mot problemene vi introduserte i begynnelsen og hvordan vi kan bruke bfs og dfs til å løse dem. Prøv deg gjerne selv før du forsetter.

Penger på tur

Observer at dersom grafen er sammenhengende (det finnes en sti mellom alle par av personer) så er svaret alltid ja. Dersom grafen ikke er sammenhengende, la oss se på en sammenhengende komponent i grafen. Ettersom det ikke er mulig å flytte penger mellom denne komponenten og resten av grafen er man avhengig av at komponenten kan gjøre opp internt for at svaret skal være ja. Og når kan en komponent gjøre opp internt, jo når gjennomsnittsforbruket i denne komponenten er likt gjennomsnittsforbruket i hele grafen. Vi må derfor sjekke at hver komponent kan gjøre opp internt og dersom dette er tilfelle er svaret ja. Input er på følgende form:

n (antall personer)
<n heltall hvor det ite tallet sier hvor mye person i la ut på turen>
m (antall vennskap)
<m linjer med par av tall som beskriver vennskapene>

Under finner du et løsningsforslag til problemet. Merk at vi bruker dfs til å finne både størrelsen (size) og summen av alle pengene som ble brukt (u) i komponenten, og dermed kan vi finne gjennomsnittsforbruket i komponenten (u/size). Om vi lar tot være det totale forbruket og n antall personer så er gjennomsnittsforbruket for hele turen tot/n, og dermed er det bare å teste at for komponent er u/size == tot/n. Merk at dette kan føre til skumle flyttallsfeil (moral: unngå alltid flyttall om du kan) og derfor tester vi heller for u*n == tot*size (manipulasjon ved hjelp av enkel algebra).

#include<iostream>
#include<vector>

using namespace std;

int used(int pos, int& size, vector<bool>& visited,
    const vector<int>& money, const vector< vector<int> >& graph)
{
    if(visited[pos])
        return 0;
    
    visted[pos] = true;
    ++size;

    int ret = money[pos];
    for(int i = 0; i < graph[pos].size(); ++i)
        ret += used(graph[pos][i], size, visited, money, graph);

    return ret;
}

int main()
{
    int n;
    cin >> n;
    
    vector<int> money(n);
    for(int i = 0; i < n; ++i)
        cin >> money[i];

    int m;
    cin >> m;
    
    vector< vector<int> > graph(n);
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    int tot = 0;
    for(int i = 0; i < n; ++i)
        tot += money[i];

    vector<bool> visited(n, false);
    bool valid = true;
    for(int pos = 0; pos < n; ++pos) {
        if(visited[pos])
            continue;

        int size = 0;
        int u = used(pos, size, visited, money, graph); 

        if(u*n != tot*size)
            valid = false;
    }

    if(valid)
        cout << "Oppgjørets time er kommet" << endl;
    else
        cout << "Pengene er tapt" << endl;

    return 0;
}

Epler og pærer

Om vi lar noder representere barna og kantene vennskapene dem i mellom, kan oppgaven beskrives som å plassere epler og pærer på nodene slik at for hver kant er det et eple på ene siden og en pære på andre siden. For å abstrahere ytterligere lar vi de nodene som får eple bli røde og de som får pære grønne. Spørsmålet er nå redusert til om vi kan fargelegge grafen med to farger (rød og grønn) slik at for hver kant så har de to endepunktene ulik farge. Dette er noe vi har sagt tidligere at både et bfs og et dfs kan løse. Observasjonen er som følger; La v være en node i grafen og anta at det finnes en gyldig fargelegging som bruker to farger. Da finnes det en gyldig fargelegging som farger v rød, for om v var grønn i den antatte løsningen kan vi bare fargelegge alle nodene motsatt, vi vil forsatt ha en gyldig fargelegging og v vil være rød. Ta derfor en vilkårlig node og farg den rød, nå må alle dens naboer farges grønne, deres naboer må være røde igjen osv. Om du forsetter denne prosessen vil du til slutt ende opp enten med en gyldig fargelegging eller en node som skulle vært fargelagt både rød og grønn og da er svaret nei. Slik kan dette implementeres ved hjelp av et bfs:

#include<iostream>
#include<vector>
#include<queue>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;
    
    vector< vector<int> > graph(n);
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // -1 betyr ufarget, 0 betyr rød og 1 grønn
    // På denne måten kan vi bruke color til å angi farger,
    // men også hvilke noder som er besøkt.
    vector<int> color(n, -1);
    
    // Denne løkken er nødvendig for å sørge for at hele grafen
    // blir fargelagt også om den ikke er sammenhengende
    boolean valid_coloring = true;
    for(int i = 0; i < n; ++i) {
        if(color[i] >= 0)
            continue;
        
        queue<int> next;
        next.push(i);
        color[i] = 0;
        
        while(!next.empty()) {
            int pos = next.front();
            next.pop();
            int next_color = (color[pos]+1)%2;
        
            for(int i = 0; i < graph[pos].size(); ++i) {
                int nghbr = graph[pos][i];
                if(color[nghbr] == color[pos]) {
                    valid_coloring = false;
                } else if(color[nghbr] == -1) {
                    color[nghbr] = next_color;
                    next.push(nghbr);
                }    
            }
        }    
    }
    
    if(!valid_coloring) {
        cout << "Fjern skålvekten! Det kommer til å bli krangling.." << endl;
    } else {
        for(int i = 0; i < n; ++i)
            cout << i << " får " <<
                (color[i] == 0 ? "eple" : "pære") << endl;
    }
    
    return 0;
}

Utrykningstid

I denne oppgaven var vi interessert i hvor langt det kunne være mellom to utrykningslokasjoner. Altså, om vi representerer kryssene med noder og veier mellom dem med kanter, hvor langt er det mellom de to nodene som ligger lengst fra hverandre i grafen. Dette er også kalt diameteren til grafen. Dette skal vi gjøre på følgende måte, vi implementerer et bfs som gitt en node finner ut hvor langt det er til nodene lengst unna også bruker vi dette søket på samtlige noder i grafen. Ettersom vi gjør dette for hver node er ikke kompleksiteten til algoritmen O(n+m) lenger, men O(n*(n+m)). En god tommelfingerregel er å putte inn grensen for verdiene i kompleksiteten og dele på noe mellom 10^7 og 10^8 ut i fra hvor “tunge” operasjoner du gjør for å finne ut hvor mange sekunder programmet ditt vil bruke. Så om n, m < 5000 gir dette oss 5000*(5000 + 5000) / 10**8 = 0.5 som er på oppunder hva som går.

#include<iostream>
#include<vector>
#include<queue>
#include<cmath>

using namespace std;

int biggest_dist(int v, const vector< vector<int> >& graph)
{
    int INF = 2*graph.size(); // Større enn noen distanse
    vector<int> dist(n, INF);
    
    dist[v] = 0;
    queue<int> next;
    next.push(v);

    int bdist = 0;
    while(!next.empty()) {
        int pos = next.front();
        next.pop();
        bdist = dist[pos];
        
        for(int i = 0; i < graph[pos].size(); ++i) {
            int nghbr = graph[pos][i];
            if(dist[nghbr] > dist[pos]+1) {
                dist[nghbr] = dist[pos]+1;
                next.push(nghbr);
            }
        }
    }
    
    // Vi trekker fra en ettersom vi ønsker antall kryss
    // og ikke antall kanter (som man vanligvis måler distanse i)
    return max(0, bdist-1);
}

int main()
{
    int n, m;
    cin >> n >> m;
    
    vector< vector<int> > graph(n);
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }
    
    int dist = 0;
    for(int i = 0; i < n; ++i)
        dist = max(dist, biggest_dist(i, graph));
    
    cout << dist << endl;

    return 0;
}

Sortering og binærsøk

Sortering og søk er nært knyttet til hverandre. Om bøkene i bokhyllen din er plassert i helt tilfeldig rekkefølge, er det vanskelig å finne akkurat den boken du leter etter, spesielt hvis du har mange bøker. Om bøkene derimot er sortert alfabetisk etter tittel, er jobben enkel. Men er det verdt arbeidet å sortere hele bokhyllen for lett å finne bøker? Svaret avhenger av hvor ofte du trenger å finne en bestemt bok.

 Sortering

Hvor mye arbeid er det egentlig å sortere en samling med N elementer? Det kommer an på hvordan vi utfører jobben, altså hvilken sorteringsalgoritme vi bruker. Vi skal se på to sorteringsalgoritmer, der den ene er svært mye mer effektiv enn den andre når antallet elementer er høyt.

Insertion sort

En intuitiv måte å sortere bokhylla på er å ta alle bøkene ut av hylla og legge dem i en stabel på gulvet. Så tar vi den boka som ligger øverst i stabelen og setter inn i hylla på riktig sted. Siden det ikke er noen bøker i hylla, setter vi den første boka lengst til venstre på hylla. Den neste boka i stabelen må vi finne riktig plass til, så vi sammenligner tittelen med boka som allerede står i hylla. Er den tidligere i alfabetet, setter vi den til venstre. Er den senere i alfabetet, setter vi den til høyre.

Slik fortsetter vi så lenge det er bøker i stabelen: Vi tar boka som ligger øverst i stabelen, sammenligner med boka lengst til høyre i bokhylla. Hvis tittelen på boka fra stabelen er senere i alfabetet enn tittelen på boka fra hylla, setter vi boka til høyre. Hvis ikke, flytter vi boka vi sammenlignet med en plass til høyre og gjør samme sammenligning med boka ett steg lenger til venstre i hylla.

Du kjenner kanskje igjen denne algoritmen fra oppgave 15 i innledende runde 2012/2013.

Hvis vi har N bøker, må vi i verste fall gjøre N * (N – 1) / 2 sammenligninger. Dette inntreffer hvis stabelen tilfeldigvis er sortert i omvendt rekkefølge av den vi ønsker. Vi sier at algoritmen har asymptotisk tidskompleksitet O(N^2) (ta en titt på O-notasjon om dette var et ukjent begrep).

Du tenker kanskje at det er unødvendig å sammenligne med alle bøkene i hylla en etter en, og vil heller bruke binærsøk for å hoppe raskt til stedet der boka fra stabelen skal settes inn. I dette tilfellet tjener vi ikke noe på den asymptotiske tidskompleksiteten, siden vi fortsatt er nødt til å flytte alle bøkene til høyre for der den nye boka skal settes inn.

Merge sort

Det er ikke nødvending å kunne detaljene i denne algoritmen, men siden tankegangen går igjen mange steder anbefaler vi likevel at du prøver å sette deg inn i den. Det er dog svært nyttig å vite at det finnes sorteringsalgoritmer med tidskompleksitet O(N lg N) og hvordan du benytter disse i C++.

Når antallet elementer N blir stort, er N^2 et problem. Tenk om vi f.eks skal sortere en million elementer. Da vil selv en maskin som kan gjøre ca. 1 milliard operasjoner i sekundet holde på i 1000 sekunder. Og ofte vil vi sortere enda mange flere elementer.

Merge sort er et eksempel på en divide and conquer algoritme. Slike algoritmer deler opp problemet man ønsker å løse i mindre delproblemer som er enklere å løse. I tilfellet med merge sort deles arrayet man ønsker å sortere i to, og man sitter igjen med to sorteringsproblemer med mindre størrelse. Dette kan man gjøre rekursivt, helt til man sitter igjen med sorteringsproblemer med kun ett element. Et array med ett element er jo uansett sortert.

Så gjenstår bare å sette sammen løsningene fra delproblemene til en løsning for det større problemet. Vi må ta to sorterte arrays fra hvert delproblem og sette dem sammen til et sortert array. Dette kan gjøres med et antall operasjoner som er proporsjonalt med antallet elementer i de to arrayene, ved hele tiden å holde styr på hvilket element fra hver av de to arrayene som er det minste som ikke har blitt satt inn i det nye felles-arrayet.

Kompleksiteten til merge sort er O(N lg N). Dette kommer av at det er lg N (toerlogaritmen til N) “nivåer” i rekursjonen, og på hvert nivå er det N elementer som skal prosesseres. Analysen og mer om merge sort finner du her. Skal vi sortere en million elementer trenger vi altså et antall sammenligninger som er i størrelsesorden N lg N, altså ca. 20 millioner. Dette er trivielt sammenlignet med de 1000 milliarder operasjonene den forrige algoritmen bruker.

Det finnes mange flere sorteringsalgoritmer! Her finner du en liste over noen av de mest populære.

Sorteringsbiblioteket i C++

Du får tilgang til sorteringsbiblioteket i C++ ved å inkludere algorithm:

#include <algorithm>

Hvis du vil sortere en array (vi anbefaler at du alltid bruker vector i stedet for array), kan du gjøre som i dette korte programmet:

#include <iostream>
#include <vector>
#include <algorithm>

using namespace std;

int main() {
  int n;
  cin >> n;
  vector<int> tall(n);
  for (int i = 0; i < n; ++i) {
    cin >> tall[i];
  }

  sort(tall.begin(), tall.end());  // Sorter tallene stigende

  for (int i = 0; i < n; ++i) {
    cout << tall[i] << " ";
  }
  cout << endl;

  return 0;
}

Den sorteringsalgoritmen som C++ benytter har kompleksitet O(N lg N).

Binærsøk

I første runde spurte vi hvor mange gjetninger du trenger for å finne et tall mellom 1 og 100 (inklusive) når du hver gang får vite om du gjettet for høyt, lavt eller riktig. Dette er et eksempel på binærsøk, som er en svært viktig algoritme.

Hvis vi kommer til en bokhylle med N bøker som allerede er sortert på tittel, kan vi finne den bestemte tittelen vi er ute etter med O(lg N) operasjoner (et antall som er proporsjonalt med toerlogaritmen til N). Vi gjør dette på samme måte som i oppgaven med å gjette riktig tall, nemlig ved å hele tiden gjette midt i intervallet. Når vi gjetter for høyt (eller alfabetisk etter det vi søker etter), søker vi videre i det lavere intervallet, og omvendt om vi gjetter for lavt.

Et typisk binærsøk i en mengde kan se slik ut:

int find_binary(vector<int> N, int x) {
  int a = 0, b = N.size();  // Nedre og oevre grense for det vi leter etter
  while (b - a > 1) {
    int g = (b+a)/2;
    if (N[g] > x) {
      b = g;
    } else {
      a = g;
    }
  }
  if (N[a] == x) return a;
  else return N.size();
}

Denne koden finner en indeks til verdien x i et sortert array. Hvis verdien x ikke finnes, returneres en ugyldig indeks (en mer enn bakerste element).

Tilsvarende kode kan brukes til å søke i arrays med andre typer verdier, f.eks strings, eller til å søke etter reelle tall (uten at disse nødvendigvis befinner seg i et array). Et eksempel på bruk av binærsøk til å finne et reelt tall uten array, er oppgave 2 fra inntaksrunden i 2011/2012.

Introduksjon til grafer

Når vi ønsker på løse et problem er et av de viktigste spørsmålene en kan stille seg hvilken informasjon som er relevant for å løse nettopp dette problemet. Ved å fjerne informasjon man ikke trenger er det ofte lettere å komme til kjernen, den informasjonen som er relevant. I denne posten skal vi se nærmere på en modell som er veldig utbredt, nemlig grafer. En graf består av en mendge noder og en mengde kanter. Nodene blir ofte visualisert som prikker og kantene som streker mellom nodene.

Rendered by QuickLaTeX.com

Grafer kan brukes til å representere alt fra veinett til vennskap. Kanskje har du på et tidspunkt fått tegnet vennskapsgrafen din på et sosialt media? Da vil nodene representere personer og kantene vennskap mellom disse. I noen tilfeller ønsker vi å legge mer informasjon på grafen enn bare hvem som er koblet sammen, for eksempel vil en kant som representerer en vei mellom to kryss være mer interessant for en GPS om den også oppgir lengden på veien, fartsgrenser osv. Og hva med enveiskjørte gater? Dette ordner vi med rettede kanter, kanter som har en startende og en sluttende. I denne posten vil vi dog konsentrere oss om urettede og uvektede grafer; Altså de av typen på figuren ovenfor. Dersom to noder har en kant mellom seg sier vi at de er naboer.

Representasjon på datamaskiner

De to mest brukte representasjonene av en graf på en datamaskin er kalt nabomatrise og naboliste. En nabomatrise er en tabell der hvert element forteller om et spesifikt par med noder har en kant mellom seg eller ikke, mens en naboliste lister alle naboene til hver node i grafen. De har begge sine fordeler og ulemper.

Nabomatrise

Om grafen har n noder vil en nabomatriserepresentasjon være en tabell av størrelse n*n der elementet i rad 0 og kolonne 2 forteller om det er en kant mellom node 0 og node 2 i grafen. Om vi tar en ny titt på eksempelgrafen vår, men gir hver node et nummer kan vi prøve å lage tabellen.

Rendered by QuickLaTeX.com

Nabomatrisen for denne grafen er under. Vi har brukt T (True) for å merke at en kant eksisterer og F (False) for at den ikke er der. Sjekk selv at bare dersom node i og j har en kant mellom seg, så er posisjon i, j (og j, i) T i tabellen.

-  0  1  2  3  4  5
0  F  T  T  T  T  T
1  T  F  T  F  T  T
2  T  T  F  T  T  T
3  T  F  T  F  T  F
4  T  T  T  T  F  F
5  T  T  T  F  F  F

Lese grafen og lagre den i en nabomatrise

Dersom input er en graf er den ofte gitt på følgende format:

n m (to heltall hvor n er antall noder i grafen og m er antall kanter)
m linjer på formen i j (som betyr at det er en kant mellom i og j)

Å lese denne typen input og lagre den i en nabomatrise kan gjøres på følgende måte:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector< vector<bool> > graph(n, vector<bool>(n, false));
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a][b] = true;
        graph[b][a] = true;
    }

    // Do your stuff

    return 0;
}

Fordeler og ulemper

Fordelen med en nabomatrise er at du på konstant tid (ta en titt på O-notasjon om dette var et ukjent begrep) kan sjekke om to noder er naboer eller ikke. Ufordelen kommer frem om man for eksempel ønsker å liste alle naboene til en node i en graf med “få” kanter. Tenk deg at en node bare har 2 naboer, man må forsatt sjekke hele raden for å finne alle naboene, som tar O(n) tid.

Naboliste

En naboliste er rett og slett en liste over alle nodene, hvor hvert element igjen er en liste med alle naboene til denne noden. På denne måten kan man enkelt iterere over alle naboene til en spesifikk node. Eksempelgrafen vår ville blitt representert på følgende måte:

0: 1, 2, 3, 4, 5
1: 0, 2, 4, 5
2: 0, 1, 3, 4, 5
3: 0, 2, 4
4: 0, 1, 2, 3
5: 0, 1, 2

Lese grafen og lagre den i en naboliste

Gitt input på samme form som for nabomatrisen kan dette gjøres på følgende måte:

#include <iostream>
#include <vector>

using namespace std;

int main()
{
    int n, m;
    cin >> n >> m;

    vector< vector<int> > graph(n);
    for(int i = 0; i < m; ++i) {
        int a, b;
        cin >> a >> b;
        graph[a].push_back(b);
        graph[b].push_back(a);
    }

    // Do your stuff

    return 0;
}

Fordeler og ulemper

Når vi ønsker å se på alle d naboene til en node kan vi gjøre dette i O(d) tid i stedet for O(n). Dette vil spille en stor rolle angående kjøretid når vi skal se på bredde-først-søk og dybde-først-søk. Ufordelen er at vi også bruker O(d) tid på å sjekke om to noder er naboer.

Nå har du lært litt om hvordan man kan lagre en graf på en datamaskin. I de neste postene skal vi ta for oss bredde-først-søk og dybde-først-søk, to algoritmer som du kan anvende på grafer for forskjellige formål.

Komme i gang med C++, del 1: Installasjon av utviklingsmiljø

Også tilgjengelig på NIOs hovedside.

Windows

Vi anbefaler at du installerer Microsoft Visual C++ 2010 Express. Klikk på “Visual C++ 2010 Express”-linjen og deretter på “Install now” – da får du laste ned en liten fil som heter vc_web.exe. Kjør denne filen når den er lastet ned, og svar “Ja” eller “Fortsett” hvis du blir spurt om programmet får lov til å gjøre endringer på datamaskinen. For at du skal få installert Visual Studio må Windows-brukeren din være administrator eller du må ha et administratorpassord. Hvis du har en skolemaskin som du ikke er administrator på, spør systemansvarlig på skolen om de kan installere det for deg. Merk at du må være koblet til internett mens du installerer.

  • Hvorvidt du krysser av for “Yes, send information about my setup experiences to Microsoft Corporation” når installasjonsprogrammet starter er ikke viktig.
  • Velg “I have read and accept the license terms” (du kan lese hele betingelsesteksten hvis du vil, men den inneholder ikke noe skummelt).
  • Ikke velg å installere SQL Server 2008 Express (med mindre du har lyst til å lære deg å programmere mot databaser, noe som er kult, men ikke nyttig for NIO).
  • Behold den foreslåtte installasjonsmappen (C:\Program Files\Microsoft Visual Studio 10.0\), trykk Install, og finn på noe annet mens nedlastingen og installasjonen pågår. Trykk på Exit når installasjonen er ferdig.

Når installasjonen er ferdig, gå til Start-menyen og velg “Microsoft Visual Studio 2010 Express” -> “Microsoft Visual C++ 2010 Express” (dette ligger under “Programmer”/”Programs” hvis du har Windows XP). Første oppstart tar lengre tid enn vanlig. Klikk på “New Project…”, velg “Win32 Console Application”, og fjern krysset for “Create directory for solution”. Velg en (ny) mappe hvor du vil putte koden din, f.eks. E:\Programmer.

Når du klikker OK dukker “Win32 Application Wizard” opp. Velg “Application Settings” ute til venstre, la det stå på “Console application” og kryss av for “Empty project”. Klikk Finish.

Nå skal det se sånn ut:

Vi må nå legge til en kildekodefil. Høyreklikk på “Source Files”-mappen i “Solution Explorer”-vinduet ute til venstre og velg “Add” -> “New Item…”, velg “C++ File (.cpp)” og kall filen f.eks. main.cpp:

Skriv inn koden nedenfor eksakt slik den står her:

#include <iostream>

using namespace std;

int main() {
    cout << "Hello world!" << endl;
    cin.get();
    return 0;
}

Trykk enten F5 på tastaturet eller klikk på knappen med den grønne pilen for å starte programmet. Første gang du gjør dette vil du bli spurt om “This project is out of date. Would you like to build it?” Kryss av for “Do not show this dialog again” og klikk “Yes”. Nå burde et såkalt konsollvindu dukke opp og vise teksten “Hello world!”:

Gratulerer; du har skrevet og kjørt ditt første C++-program! Trykk Enter, så forsvinner vinduet og programmet avslutter. Det var litt strevsomt å komme i gang, men når Visual Studio og prosjektet først er oppe, kan man konsentrere seg om kodingen. Hvis du ikke har programmert før, skal vi snart publisere en kom i gang-guide for det også.

Hvis du skriver feil i koden, vil det sannsynligvis dukke opp en rød strek i nærheten, og når du prøver å kjøre programmet, vil du første gang få en melding om “There were build errors. Would you like to continue and run the last successful build?” Kryss av for “Do not show this dialog again” og klikk “No”. Gå til “View”-menyen og velg “Other Windows” -> “Error List” og klikk på “Errors”-knappen i vinduet som dukker opp, så får du en liste over feil.

Hvis du vil lage et nytt program, går det an å starte en ny utgave av Visual Studio og lage et nytt prosjekt med et annet navn. Men dette er litt strevsomt, så det kan være enklere å bruke det samme prosjektet, og bare sette inn en annen kildekodefil i stedet. Høyreklikk på main.cpp i Solution Explorer-vinduet og velg “Exclude From Project”. (Filen blir ikke slettet; den vil forsvinne fra prosjektet, men vil fortsatt ligge på E:\Programs\HelloWorld\main.cpp.) Nå kan du legge til en ny kildekodefil med et annet navn (kildekodefilene kan hete hva som helst, men det skal alltid stå int main() i koden). Hvis du vil ha main.cpp tilbake, kan du høyreklikke på “Source Files” og velge “Add” -> “Existing Item”. Men det går ikke an å ha flere kildekodefiler med main() i prosjektet samtidig.

Mac

På Mac anbefaler vi å laste ned “Command Line Tools for XCode” herfra: https://developer.apple.com/downloads/ (man må registrere seg for å få tilgang). Når du har registrert deg, søker du etter “command line tools” og velger nyeste utgave for din versjon av OS X som vist på bildet.

Når den er lastet ned åpner du .dmg-filen og starter installasjonsprogrammet.

Du trenger ikke endre noe i prosessen.

For å prøve om installasjonen var vellykket åpner du Terminal (CMD+SHIFT og skriv inn “Terminal”) og så skriver du kommandoen:

g++ --version

Resultatet bør se omtrent slik ut:

Nå er du klar for å kompilere kode! Åpne en ren tekst editor, f.eks GEdit (om du ikke allerede har en favoritteditor, er dette et godt valg, siden den er lett å lære og er tilgjengelig under finalen i Bergen og i de internasjonale rundene).

Du kan nå kopiere koden fra http://www.cplusplus.com/doc/tutorial/program_structure/ inn i filen, lagre den som f.eks helloworld.cpp og kompilere:

g++ helloworld.cpp -o helloworld

Hvis alt gikk bra, fikk du ingen feilmeldinger.

Da kan du også kjøre programmet med kommandoen

./helloworld

Nå ser du at programmet har skrevet ut teksten “Hello World!” på kommandolinjen. Da er alt satt opp!

Linux

All programvaren du trenger følger sannsynligvis med din Linux-distribusjon og er allerede installert. Følg instruksjonen for Mac fra stedet med kommandoen:

g++ --version