Introduktion til Partial Sum Applet

Allan Grønlund Jørgensen, 2006

Introduktion til Problemstilling

Med denne applet kan man arbejde med følgende problemstilling. Man er givet et input I som er et array af heltal. Det handler om at kunne svare på en delsum(i,j) query så hurtigt som muligt. Det vil sige besvare spørgsmålet. Hvad er denne sum.

$\displaystyle delsum(i,j) = \sum_{k=i}^j I[k] = I[i] + I[i+1] + \ldots + I[j] $

Eksempel. Indexer i array starter ved 1.

$\displaystyle I = [1,3,2,10,2,5]\quad delsum(1,3) = \sum_{k=1}^3 I[k] = I[1] + I[2] + I[3] = 1 +3 +2 = 6 $

Til dette formål tillades det at gemme en mængde af delsummer fra I og intet andet.

Når man skal besvare en delsum-query skal man så bruge disse gemte delsummer til at lave beregningen. Dog er den eneste tilladte operation, addition(plus).

Så problemstillingen ligger i at gemme færrest mulige delsummer, og samtidigt kunne besvare en vilkårlig delsum-query så hurtigt som muligt.

Appleten er til for at hjælpe med at løse dette problem. Det man kan i denne applet er at tilføje delsummer til den mængde af delsummer der ønskes konstrueret. Man kan så bede appleten om at beregne hvor mange additioner der i værste tilfælde skal til for at lave en delsum query.

For at kunne lave alle summer skal alle delsummer af størrelse 1 (dvs. delsum(i,i)) være i mængden af delsummer. Siden disse er input skal man ikke betale for disse.

Forklaring af Brugergrænseflade

Image init

På figur 2 kan man se hvordan appleten starter med at se ud ved inputstørrelse 4. Øverst ses input-arrayet tegnet med hvid. Over dette er indexerne ind i arrayet

Under dette kommer de delsummer(partial sums) der er indsat i jeres mængde. En delsum vises som et pink rektangel der ligger under den del af inputtet som delsummen representerer. Inde i rektanglet er værdien af delsummen.

Som skrevet tidligere skal alle trivielle delsummer være i mængden og de er derfor allerede indsat. Disse kan ses i den første række af delsummer.

Indsæt Delsum

Man kan tilføje en mænde følgende vis. Start med at holde cursor over det inputelement i ønsker at delsummen skal starte med. I kan nu dragge(tryk musekanp og træk) et rektangel henover de inputelementer i ønsker at have med. Den del af input rektanglet spænder over er delmængden der hvis man slipper museknappen indsættes. Disse vil blive farvet røde for at markere dette. Se 2.1

Når knappen slippes indsættes mængden, og der vil være respons i tekstområdet i bunden.

Image ins

Slet Delsum

For at slette en delsum flyttes cursor hen ovenpå rektanglet der representerer delsummen. Det vil få den til at skifte farve til rød for at markere at man faktisk har flyttet musen over denne delsum.

Herefter venstreklikker man og så skifter farven af rektanglet til hvid for at markere at rektanglet er valgt til at kunne slettes. For at slette trykkes på knappen delete som vil være mulig at trykke på efter et rektangel er valgt.

Image delete

Værste Tilfælde

I højre hjørne af appleten kan man se hvor mange mængder der er indsat udover de indbyggede. For at finde ud af hvor mange additioner en query kan bruge i værste tilfælde trykkes på knappen Display Worst Case.

Den vil i status feltet forklare hvad det værste antal additioner en query skal bruge er, samt en query der skal bruge dette antal additioner. Læg mærke til at ofte vil være flere end en query der kræver dette antal additioner, men kun en vises. På selve skærmen vil dette indtegnes i input ved at farve elementerne i den værste query grøn, og i delsum-delen vil de delsummer der bruges til beregningen også blive farvet grønne. Se 2.3

Image worst2

Upload

For at man indbyrdes kan sammenligne hvor god en løsning man har fundet til problemet er der mulighed for at uploade resultat til en high-score liste. Denne highscore eksisterer for 2 inputstørrelser, 16 og 32. Her kan man sammenligne den konstruerede mængde. med andre mængder som giver sammen antal additioner i det værste tilfælde. Der er en score for alle muligheder for værste antal additioner der kan opnås.

Applet

Bare følg link for at starte applet.

Links til High-Score