Tävlingsprogrammering/Introduktion
"The programmer, like the poet, works only slightly removed from pure thought-stuff. He builds his castles in the air, from air, creating by exertion of the imagination. Few media of creation are so flexible, so easy to polish and rework, so readily capable of realizing grand conceptual structures."
Det går inte att lära sig programmera i teorin. Tanken med denna sida är att genom några enkla tips och exempel försöka ge dig lite inspiration att börja utforska den fascinerande värld som programmeringsbehjälpt problemlösning utgör, och att kanske få dig att ställa upp i vår tävling eller i någon annan av de många programmeringstävlingar som finns.
Vi ska här beskriva tre steg som kan sägas utgöra grunden för den sorts problemlösning som förekommer i programmeringstävlingar.
- Det första steget, Simulera, gör att du får en första användning av ett programmeringsspråk för att lösa ett riktigt problem.
- Det andra steget, Testa alla möjligheter, handlar om att börja tänka i nya banor och utnyttja den oerhörda kraft en dator har tillgänglig. En dator kan aldrig tänka ut lösningen på ett problem. Den kan bara göra beräkningar väldigt väldigt snabbt...
- Det tredje steget är att Rekursera. Det är här som programmeringen börjar lyfta och det blir riktigt kul. Man löser bara en liten bit av ett problem, men genom att lösningen anropar sig själv får programmet liksom eget liv och kan åstadkomma häpnadsväckande saker.
Med dessa verktyg kan du i princip lösa vilket problem som helst. Men det kan ta åtskilliga år för programmet att ge dig svaret. Det är här som algoritmen kommer in i bilden, hur får du programmet att bli effektivt? Mer om det på träningssidorna för PO och IOI.
Steg 1. Simulera
[redigera]FORTSÄTT TALFÖLJDEN (PO-kvalet 2006)
Att fortsätta en påbörjad talföljd är en vanlig sorts uppgift i såväl matteböcker som IQ-tester. Men det smartaste måste väl ändå vara att skriva ett datorprogram som löser problemet en gång för alla.
Betrakta till exempel de så kallade triangeltalen:
1, 3, 6, 10, 15, 21 . . .
Ett mönster framträder om man tittar på skillnaden mellan varje tal och dess föregångare:
2, 3, 4, 5, 6 . . .
Tydligen ökar skillnaden med 1 i varje steg. Men för någon annan talföljd kan skillnaden till exempel öka med 13, minska med 2 eller vara konstant. Det enda som är säkert om de talföljder som förekommer i denna uppgift är att skillnaden mellan två intill varandra stående tal ändras lika mycket i varje steg.
Skriv ett program som frågar efter de tre första talen i talföljden (positiva heltal mindre än 100) och sedan skriver ut de 10 första talen åtskilda med blanksteg.
Körningsexempel:
Första talet ? 1 Andra talet ? 3 Tredje talet ? 6 Talföljden: 1 3 6 10 15 21 28 36 45 55
Simuleringsuppgifter kännetecknas av att det står i uppgiften hur du ska göra. Det handlar ofta om att följa ett förlopp i tiden. Normalt löser man en sådan uppgift på samma sätt som om man skulle lösa den med papper och penna. Detta betyder dock inte att programmet behöver vara lätt att skriva. Man måste fortfarande göra abstraktionen, d.v.s. översätta problemet från vardagligt språk till en noga definierad följd av operationer som en dator kan förstå.
Den givna uppgiften lämnar inte mycket utrymme för olika lösningar. Man inser snabbt att det måste bli fråga om en loop som ska gå 10 gånger och varje gång beräkna ett tal och skriva ut det. Varje tal kan beräknas från det föregående om vi bara vet vad skillnaden ska vara jämfört med föregående tal. Låt oss kalla denna skillnad d. Den är ju inte konstant, men på samma sätt kan den beräknas från föregående skillnad om vi bara vet hur mycket skillnaden ändras mellan varje tal. Och denna ändring, som vi kan kalla f, är ju konstant enligt problemtexten. Så i varje iteration av loopen ska vi först beräkna ett nytt tal k:=k+d, och sedan en ny skillnad d:=d+f. Det enda vi behöver göra innan vi börjar iterera är därför att räkna ut den första skillnaden d samt talet f, vilket är trivialt eftersom vi har fått givet de tre första talen. Hela lösningen i C visas nedan.
#include <stdio.h>
int main(){
int k1,k2,k3,f,d,k,a;
printf("Första talet ? ");
scanf("%d", &k1);
printf("Andra talet ? ");
scanf("%d", &k2);
printf("Tredje talet ? ");
scanf("%d", &k3);
d=k2-k1; //Räkna ut den forsta skillnaden
f=(k3-k2)-(k2-k1); //Räkna ut skillnadens ändring i varje steg, vilken är konstant
k=k1;
printf("Talföljden: ");
for(a=0;a<10;a++){
printf("%d ", k);
k+=d; //Öka talet med den aktuella skillnaden
d+=f; //Öka skillnaden med den konstanta ändringen
}
printf("\n");
return 0;
}
Steg 2. Testa alla möjligheter
[redigera]KLOCKAN (PO-kvalet 2004)
Om någon frågar hur mycket klockan är, svarar de flesta "kvart över fem", 15:29 eller något liknande. Vill man göra det lite svårare så kan man annars svara med vinkeln mellan tim- och minutvisaren, eftersom man ur denna information entydigt kan bestämma klockslaget. Dock är det många människor som är ovana vid detta sätt att ange tider, så det vore bra att ha ett datorprogram som översätter till ett mer normalt format. Du ska skriva ett sådant program.
Vi förutsätter att vår klocka saknar sekundvisare och endast visar ett helt antal minuter (det vill säga: båda visarna hoppar framåt bara på hel minut). Vinkeln avläses genom att utgå från timvisaren och sedan mäta hur många grader medurs minutvisaren ligger (se figur 2). För att undvika decimaler anges vinkeln i tiondels grader (så att 85.5 grader skrivs som 855). Detta tal är alltid ett heltal mellan 0 och 3595 (inklusive) och är, som en följd av att endast hela minuter visas, alltid delbart med 5.
Programmet ska fråga efter en vinkel och sedan skriva ut tiden i vanligt digitalformat, alltså h:mm eller hh:mm, beroende på antalet timmar. Notera att minuterna alltid ska ges med två siffror. Vi förutsätter att det är morgon, så alla tider ska ligga mellan 0:00 och 11:59 (inklusive).
Två körningsexempel:
Vinkel ? 855 Klockan är 1:21 Vinkel ? 3140 Klockan är 3:08
Låt oss först tänka ut hur vi skulle lösa uppgiften manuellt. 85.5 grader motsvarar ungefär en kvart. Så klockan kan vara ungefär 0:15, 1:20, 2:25 eller liknande. Om vi antar att den är ca 0:15 går det förstås lätt att ta fram en formel för exakt var minutvisaren står. Om den står på ett helt minutslag så har vi hittat rätt klockslag, annars får vi testa 1:20 istället, ändra formeln lite och räkna ut minutvisarens placering igen, o.s.v. Detta är inte alls någon dålig metod och det skulle definitivt gå att implementera den i ett datorprogram. Frågan är om uppgiften kan lösas enklare.
Tydligen finns det ingen enkel formel som ger klockslaget när man vet vinkeln. Alltid när man stöter på detta problem ska man ställa sig frågan: Kan vi vända på steken? Om vi visste vad klockan var, skulle vi då kunna räkna ut vinkeln?
Svaret är förstås att vi lätt kan göra det. Varje minut rör sig minutvisaren 6 grader framåt och timvisaren 0.5 grader framåt så om klockan är h:m så står minutvisaren på 6m grader och timvisaren på 30h+0.5m grader (räknat medurs från klockans tolva). Vinkeln mellan dem blir då helt enkelt 5.5m-30h, och sen får man förstås lägga till 360 grader om vinkeln skulle bli negativ.
OK, nu kan vi räkna ut indatan om vi hade vetat utdatan, vad vinner vi då på det? Jo, poängen är naturligtvis att det bara finns 720 olika klockslag, så vi kan helt enkelt testa alla klockslag och se vilket av dem som ger den vinkel vi fick som indata. En lösning i C visas nedan.
#include <stdio.h>
int main() {
int h,m,ang;
printf("Vinkel ? ");
scanf("%d", &ang);
for(h=0;h<12;h++) for(m=0;m<60;m++) {
if((m*55-h*300+3600)%3600==ang){ //Lägg till 3600 tiondelar så talet blir
printf("Klockan är %d:%02d\n",h,m); //positivt och använd MOD (%) för att få
return 0; //resultatet att ligga i intervallet 0..3599
}
}
return 0; //Hit skulle vi komma om vinkeln var ogiltig
}
Även om klockproblemet är lätt så är detta en mycket viktig princip i tävlingsuppgifter och något man alltid ska ha i bakhuvudet. Istället för att skriva ett komplicerat program som gör få beräkningar kan man ibland skriva ett enkelt program som gör fler beräkningar, ofta just genom att lösa problemet baklänges och testa vilket av alla utdata som stämmer med givna indata.
Naturligtvis är det inte alltid bra att låta datorn göra jobbet. Hela teorin för algoritmer bygger på motsatt princip, att få själva beräkningarna att gå snabbare. Men det gäller att ha en känsla för när det är värt att bry sig om exekveringstiden och inte. En bra riktlinje är att allt under en miljon "beräkningssteg" går blixtsnabbt. Upp till hundra miljoner kan gå på en sekund men det beror på vilken typ av beräkningssteg man gör. Över det börjar det bli tungt och en miljard är hopplöst. Så de 720 stegen i klockuppgiften är inte mycket att prata om, det är nästan pinsamt att be en modern dator om hjälp med ett så litet problem.
Steg 3. Rekursera
[redigera]PLANKAN (PO-kvalet 2001)
Man vill skapa en längre planka med hjälp av ett antal mindre brädor. Det finns tre olika typer av brädor, som har längden 1, 2 respektive 3 meter. Det finns ett obegränsat antal av varje typ. Skriv ett program som bestämmer på hur många olika sätt man kan åstadkomma en planka av längden n, 1 ≤ n ≤ 24. I figuren ser du de 7 olika sätten att skapa en planka med längden 4 meter.
Körningsexempel:
Plankans längd ? 4 Det finns 7 olika sätt
Den naturliga lösningen är att generera alla möjliga plankor och räkna dem. Vi kan göra detta genom att först loopa över den första brädans längd (från 1 till 3). För varje val, d.v.s. inuti denna loop, måste vi ha en loop över den andra brädans längd, också från 1 till 3. Och inuti denna en tredje o.s.v. tills vi har fyllt upp hela plankans längd. Hur många sådana loopar som ska köras beror förstås på vilka längder vi har tagit, men vi vet ju att det inte kan vara fler än 24 så i princip kan vi alltid skriva 24 loopar och sen med if-satser se till att inte fler än nödvändigt körs.
Kommer detta ta för lång tid att köra? Vi kan förstås inte säga exakt hur många gånger de innersta looparna kommer att köras (om vi visste det hade vi ju redan svaret på uppgiften), men vi kan göra ett snabbt överslag. Varje gång väljer vi längden 1, 2 eller 3 och ju mindre längd vi väljer desto fler blir looparna. Så antag att vi väljer mellantinget 2 varje gång och att längden är 24 som är maximalt enligt problemtexten. Då kommer det bli i genomsnitt ungefär 12 loopar och var och en går tre gånger. Så någonstans i storleksordningen 3^12 = en halv miljon. Det borde gå!
Låt oss nu se hur programmet ser ut. Det kommer att innehålla någonting i stil med:
sum := 0
for x1 := 1 to 3
sum := sum + x1
if sum < längd
for x2 := 1 to 3
sum := sum + x2
if sum < längd
for x3 := 1 to 3
sum := sum + x3
if sum < längd
for x4 := 1 to 3
sum := sum + x4
if sum < längd
....
fast med 24 loopar. Förutom att detta är jobbigt att skriva kan det leda till alla sorters problem (i mitt allra första PO-kval skrev jag en sådan lösning men fick Internal stack overflow vid kompileringen). Lösningen är att använda en rekursiv funktion.
Låt oss skriva en rutin, av personliga historiska skäl kallad MLX, som tar en heltalsparameter r och genererar alla olika plankor under förutsättning att r meter av plankan redan är färdiggjord. Vid första anblicken verkar detta ganska dumt. Eftersom vi vet att plankan är tom från början är vi förstås bara intresserade av hur många som genereras när vi gör anropet MLX(0).
Fördelen uppkommer när man skriver själva rutinen. För vad vill vi göra när vi har lagt dit den första brädan med längden p, d.v.s. inuti den första for-loopen, om plankan ännu inte är full? Svaret är naturligtvis att vi vill generera alla plankor under förutsättning att p meter av plankan redan är färdiggjord. Eller, med andra ord, vi vill anropa MLX(p). Detta anrop ersätter alltså samtliga av de 23 inre looparna! Hela lösningen i C visas nedan.
#include <stdio.h>
int L, count;
void MLX(int r) { //r är hur lång bit av plankan som redan är byggd
int p;
if(r==L) count++; //Det gick jämnt upp. En lösning hittad.
else if (r < L) { //Fortsätt INTE om plankan redan har blivit för lång.
for(p=1;p<=3;p++) MLX(r+p); //Testa varje brädlängd och rekursera!
}
}
int main() {
printf("Plankans längd ? ");
scanf("%d", &L);
count = 0;
MLX(0);
printf("Det finns %d olika sätt\n", count);
return 0;
}
Återigen har vi valt ett lätt problem för att illustrera principen, men betydelsen av rekursiva funktioner kan inte betonas tillräckligt mycket. Här är några exempel för att reta din aptit. Går du igenom gamla PO-uppgifter kommer du att hitta tiotals andra exempel.
- Tänk dig ett spel där du ska ta dig från en given ställning till en annan genom att göra ett antal drag. Testa att utföra ett drag och rekursera sedan. Om inte slutställningen uppnåddes under denna rekursion så testa ett annat drag och rekursera igen.
- Tänk dig att du vill generera alla permutationer (omkastningar) av en sekvens med tal. Välj vilket tal som ska stå på den n:te platsen genom att loopa över alla tal som ännu inte har valts. Rekursera sedan och välj det n+1:te på samma sätt.
- Tänk dig att programmet ska räkna ut ett matematiskt uttryck av typen 1+(5+(4+7)). Börja med att hitta den yttersta parentesen och räkna ut värdet av denna, 16, genom att rekursera. Sen står det plötsligt bara 1+16.
Det kan vara bra att tänka på att en rekursiv funktion alltid kan skrivas på många likvärdiga sätt. Exempelvis så kan if-satser och liknande placeras antingen när man kommer in i den rekursiva funktionen eller precis innan man anropar den. Sålunda gör den här funktionen exakt samma sak som den ovanstående (fast något snabbare):
void MLX(int r) {
int p;
for(p=1;p<=3 && r+p<=L;p++) {
if(r+p==L) count++;
else MLX(r+p);
}
}
Slutligen noterar vi att antalet sätt att få längden 24 är 1389537. Ökar vi längden till 30 så blir antalet ca 54 miljoner och programmet tar flera sekunder att köra. Går det inte att lösa problemet för större längder? Svaret är att det med minimal ansträngning går att snabba upp programmet så extremt mycket att det får vårt första rekursiva försök, hur smart det än verkar nu, att se ut som ett dåligt skämt. Tekniken kallas Dynamisk programmering eller Memoisering och vi ska återkomma till den på kommande träningssidor.