Sist endret: 23.09.2016  
 

Praksisoppgave - På sporet av sprengstoff

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 04.09.2017 15:00

Velg språk:
- Python
- Java

Løsningsforslag

Følgende filer er tilgjengelige etter at fristen har gått ut:
sprengstoff.py

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
sprengstoff.py Funksjonen search(record)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 123

På sporet av sprengstoff

Det er ikke nødvendig å lese historien for å løse oppgaven.

Det finnes mange typer jobber her i verden, og noen er mer ansvarskrevende enn andre. Algemannen er superhelt på heltid, og redder til stadighet jorden fra undergang. Men for at superhelter skal kunne eksistere, er vi avhengige av ondskap. Algemannen lever i symbiose med den onde dr. Brutus Gewalt. Én gang i uken redder vår helt jorden fra undergang ved å avsløre og hindre doktorens utspekulerte plott.

Algemannen sitter i stuen og røyker pipe, når hans gode hjelper Kobra kommer inn med morgenavisen.
- God morgen, sir, og vær så god.
Algemannen bretter ut avisen, og leser overskriftene på fremsiden. En av dem vekker hans oppmerksomhet: "Dr. Gewalt kjøper opp dynamittfabrikk".
- Min gode venn Kobra, jeg lukter ugler i mosen. Når dr. Gewalt gjør noe, er det alltid med onde hensikter. Dette må undersøkes nærmere.
- Tror du doktoren kommer til å tømme bedriften for ressurser, for så å slå den konkurs? sier Kobra spørrende.
- Nei, her er det nok værre ting på gang. Det er allerede onsdag, og Gewalt har ikke prøvd å ta over verden enda. Gjør klar Algobilen!
Når Algemannen har fått på seg den grønne drakten sin, står allerede Kobra og venter ved Algobilen. Han er som vanlig ikledd sine røde shorts og sin blå kappe.

Når heltene kommer frem til fortet til dr. Gewalt, er døren låst og lyset skrudd av.
- Ser ikke ut som om noen er hjemme, kommenterer Kobra.
- Nei, den onde planen er nok allerede satt ut i livet. Vi har ingen tid å miste!
En mystisk ting i blomsterbeddet vekker Algemannens oppmerksomhet. Han bøyer seg ned og undersøker nærmere.
- Aha, en dynamittkubbe! Hvis vi følger lunten, finner vi dr. Gewalt, og rekker hjem til middag.
De to spandekskledde mennene følger lunten, og kommer snart til en ny dynamittkubbe. Lunten går videre.
- Hvis doktoren har lagt ut all dynamitten fra fabrikken, er det nok til å sprenge jorden i fillebiter, kalkulerer Algemannen.
- Å, nei! Vi har et kjempeproblem!

Gewalts dynamittkubber

Oppgave

Du skal lære å traversere (se på alle elementene) en lenket liste. I det utleverte rammeverket er det skrevet kode for å lage en lenket liste. Det viktige i denne øvingen er å forstå hvordan du kan lenke sammen elementer ved hjelp av referanser. Dette er veldig vanlig i objektorientert programmering. Trikset når du lager en lenket liste, er å koble sammen flere objekter av samme klasse, slik at hvert objekt har en referanse (lenke) til ett annet objekt (det 'neste' objektet'). Hvis du så et eller annet sted tar vare på en referanse til det første objektet i lenkingen (det eneste objektet som ikke blir lenket til av noen andre objekter), har du et utgangspunkt for å traverse hele listen av objekter.

Input består av heltall separert av linjeskift. Programmet ditt skal legge inn disse i en lenket liste, traversere den lenkete listen, og skrive ut det høyeste tallet. Du kan tenke på tallene som vekter på dynamittkubber og lenkene du lager mellom kubbene som lunter koblet sammen.

Rammeverk

from sys import stdin


class Record:
    value = None
    next = None

    def __init__(self, value):
        self.value = value
        self.next = None


def search(record):
    # SKRIV DIN KODE HER


def main():
    # reading from stdin and creating a linked list
    first = None
    last = None
    for line in stdin:
        penultimate = last
        last = Record(int(line))
        if first is None:
            first = last
        else:
            penultimate.next = last

    # searching and printing out the result
    print(search(first))


if __name__ == "__main__":
    main()

Variabelbeskrivelse

Rammeverket i denne ovingen bruker Record-objekter. Et Record-objekt har to egenskaper: verdi og neste record. Hvis du har et Record-objekt som heter "record" kan man faa tak i verdien til den ved aa skrive record.value og faa tak i neste record ved aa skrive record.next. Siste record vil ikke ha noen neste record. Da er record.next None. Rammeverket gir deg en variabel, 'records', som er foerste Record-objektet i den lenkede listen. For input-eksempelet vil det vaere et record med verdi 54 hvor neste record er med verdi 37.

Input-eksempel

54
37
100
123
1
54

Tilhørende output

123

Hvordan teste Python-program

Unix

Du kan teste programmet ditt med kommandoen:

    python program.py < input.txt

Windows

  • Lagre programmet ditt på feks m:\tdt4120\
  • Åpne kommandolinje (Start -> Kjør -> cmd)
    • m:
    • cd \tdt4120
    • python.exe program.py < input.txt
  • Merk at hvis du bare skriver "python", ikke "python.exe", ser det ut til ofte å oppstå en feil fordi python prøver å kjøre inputfilen også.