Finne det nest største tallet i en liste
Lov på eksamen
- Datamaskin med programmeringsverktøy
- Lærebok, dokumentasjon og egne notater og programmer
Ikke åpent internett (bare noen utvalgte nettressurser), kommunikasjon med andre eller kunstig intelligens.
Kan den løses uten PC?
Alle deloppgavene kan løses uten PC.
Fra 2027 er det bare kalkulator og skriftlige hjelpemidler på del 2. Vurderingen er gjort med KI og kan inneholde feil.
Du får i oppgave å finne det nest største tallet i en liste (array) med tall. Dersom det finnes flere like tall som er størst, skal ingen av disse regnes som nest størst. Under finner du fire alternative løsninger for denne oppgaven skrevet i pseudokode.
Løsning 1
SET størst TO negativt uendelig tall
FOR hvert tall i listen
IF tall GREATER THAN størst
SET størst TO tall
ENDIF
ENDFOR
Fjern størst fra listen
SET nestStørst TO negativt uendelig tall
FOR hvert tall i listen
IF tall GREATER THAN nestStørst
SET nestStørst TO tall
ENDIF
ENDFOR
DISPLAY nestStørstLøsning 2
SET størst TO første tall i listen
SET nestStørst TO andre tall i listen
IF nestStørst GREATER THAN størst
Bytt størst og nestStørst
ENDIF
FOR hvert tall i listen med start fra tredje tall
IF tall GREATER THAN størst
SET nestStørst TO størst
SET størst TO tall
ELSEIF tall GREATER THAN nestStørst AND tall NOT EQUAL TO størst
SET nestStørst TO tall
ENDIF
ENDFOR
DISPLAY nestStørstLøsning 3
SET størst TO negativt uendelig tall
SET nestStørst TO negativt uendelig tall
FOR hvert tall i listen
IF tall GREATER THAN størst
SET nestStørst TO størst
SET størst TO tall
ELSEIF tall GREATER THAN nestStørst
SET nestStørst TO tall
ENDIF
ENDFOR
DISPLAY nestStørstLøsning 4
Sorter listen i synkende rekkefølge
FOR hvert tall i listen
IF tall NOT EQUAL TO neste tall i listen
DISPLAY neste tall i listen
avbryt for-løkken
ENDIF
ENDFORHvilke to løsninger er riktige?
Vurder og sammenlign de to løsningene du valgte i punkt a.
Fasit
Løsning 1 og løsning 4. Løsning 1 forutsetter at «Fjern størst fra listen» fjerner alle forekomstene av det største tallet.
Begge er riktige. Løsning 1 går gjennom listen to ganger (lineær tid), mens løsning 4 sorterer først og er tregere på store lister, men kortere og enklere å lese. Begge endrer listen, og begge må håndtere lister der alle tallene er like.
LøsningsforslagKI-generert
Vi tester løsningene med to lister: [3, 7, 5] (ingen like tall) og [5, 5, 3]. I den siste listen er 5 størst to ganger, så det riktige svaret er 3.
| Løsning | [3, 7, 5] | [5, 5, 3] |
|---|---|---|
| 1 | 5 | 3 (hvis alle femmerne fjernes) |
| 2 | 5 | 5 (feil) |
| 3 | 5 | 5 (feil) |
| 4 | 5 | 3 |
Løsning 1 finner det største tallet, fjerner det fra listen og finner deretter det største av tallene som er igjen. Det blir riktig så lenge alle forekomstene av det største tallet fjernes. Fjernes bare én forekomst (som liste.remove(x) i Python), blir resultatet det samme som i løsning 3.
Løsning 2 har en sjekk for like tall (tall NOT EQUAL TO størst) inne i løkken. Den starter likevel med de to første tallene uten å sjekke om de er like. For [5, 5, 3] blir både størst og nestStørst 5 før løkken starter, og tallet 3 endrer ikke dette. Løsningen feiler hver gang listen begynner med to like tall og det ikke kommer et større tall senere.
Løsning 3 mangler sjekken for like tall. Når samme største tall kommer en gang til, er det større enn nestStørst, og det blir satt som nest størst.
Løsning 4 sorterer listen synkende. Da ligger alle forekomstene av det største tallet først. Det første tallet som er ulikt tallet foran seg, er det nest største. For [5, 5, 3] er rekkefølgen etter sortering 5, 5, 3, og løkken skriver ut 3.
De to riktige løsningene er derfor 1 og 4.
Hvordan de virker. Løsning 1 bruker to vanlige gjennomganger av listen og finner det største tallet hver gang. Løsning 4 overlater mesteparten av arbeidet til en sorteringsalgoritme og trenger bare å se på tallene øverst i den sorterte listen.
Effektivitet. Løsning 1 går gjennom listen to ganger. I tillegg må den finne og fjerne forekomstene av det største tallet. Tidsbruken vokser proporsjonalt med antall tall (lineær tid). Å sortere en liste tar mer tid, typisk proporsjonalt med med en god sorteringsalgoritme. Løsning 4 blir derfor tregere enn løsning 1 for store lister. For lister med noen hundre eller tusen tall merkes ikke forskjellen.
Lesbarhet og hvor lett de er å implementere. Løsning 4 er kortest. De fleste språk har en innebygd sorteringsfunksjon, så løsningen kan skrives med få linjer. Løsning 1 er også enkel, men lengre. Den krever at vi vet hvordan listefunksjonen for å fjerne elementer virker, siden remove i mange språk fjerner bare den første forekomsten.
Sideeffekter. Begge løsningene endrer listen: løsning 1 fjerner elementer, og løsning 4 endrer rekkefølgen. Trenger programmet den opprinnelige listen senere, må begge jobbe på en kopi.
Spesialtilfeller. Hvis alle tallene i listen er like, finnes det ikke noe nest største tall:
- Løsning 1 ender med en tom liste og viser «negativt uendelig tall». Det må håndteres særskilt.
- Løsning 4 finner ikke to ulike naboer og viser ingenting.
I løsning 4 finnes det heller ikke noe «neste tall» når løkken kommer til det siste tallet. Løkken må derfor stoppe på det nest siste tallet, ellers gir programmet en feil (indeks utenfor listen).
Konklusjon. Løsning 4 er enklest å skrive og lese og passer godt for små og mellomstore lister. Løsning 1 er mer effektiv for store datamengder. Den beste løsningen for store lister er én gjennomgang som ligner løsning 2, men som også tar hensyn til like tall helt fra starten.