Sist endret: 23.09.2016  
 

Praksisoppgave - Redd Ratatosk

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 23.10.2017 15:00

Velg språk:
- Python
- Java

Løsningsforslag

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

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
ratatosk.py Funksjonene dfs(node) og bfs(node)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt 2

Oppgave

Du skal implementere dybde- og bredde-først-søk (DFS og BFS) for å finne Ratatosk, som finnes i akkurat én av nodene i et tre. Du kan lese om DFS på side 604 og BFS på side 595 i Cormen. Nedenfor ser du et rammeverk for innlesing av data, og en klasse Node som brukes til å holde styr på treet. En Node har en attributt barn som er en liste med referanser til alle barna.

Du skal lage to funksjoner dfs og bfs som begge tar inn en rotnode som parameter, traverserer treet og returnerer dybden på noden Ratatosk befinner seg i. Rotnoden er på dybde 0. DFS kan enten implementeres ved hjelp av en stakk eller med rekursjon, men i denne øvingen skal du bruke en stakk. Dette er ikke forklart direkte i læreboken, men det står om DFS på side 605. BFS implementeres ved hjelp av en kø (Cormen side 595).

Input består av følgende linjer:

  1. Hvilken funksjon som skal brukes, 'dfs', 'bfs' eller 'velg'. Dersom første linje inneholder verdien 'velg', kan du finne Ratatosk på den måten du vil. Ellers skal du kalle tilsvarende funksjon, for å sjekke at den fungerer. (På tidstestene vil input alltid være 'velg'.)
  2. Antall noder i treet.
  3. Hvilken node som er rot-noden i treet.
  4. Hvilken node Ratatosk befinner seg i (0-indeksert).
  5. Resten av linjene inneholder først et nodenummer (0-indeksert) og så en liste med nummerne til barna til nodene, alt separert med mellomrom.

Hvis det er n noder i treet, vil alle nodene ha et nummer fra og med 0 opp til n, men ikke nødvendigvis i rekkefølge.

Det oppgis at det er like stor sannsynlighet for at ratatosk befinner seg på alle nivåer, og dermed ikke like stor sannsynlighet for at han befinner seg i alle noder.

I eksempelet under er det 10 noder. Node 0 har barna 1, 2 og 3. Rotnoten er node 0 og Ratatosk befinner seg i node 7.

PS: Det er en sterk relasjon mellom lenkede lister, trær og grafer. Et tre er et spesialtilfelle av en graf, og en lenket liste er et spesialtilfelle av et tre. DFS og BFS er generelle graftraverseringsalgoritmer. Hvis du modifiserer funksjonene dine til å merke hvilke noder de allerede har besøkt, fungerer de på generelle grafer.

Rammeverk

#!/usr/bin/python3

from sys import stdin


class Node:
    def __init__(self):
        self.child = []
        self.ratatosk = False
        self.next_child = 0


def dfs(root):
    # SKRIV DIN KODE HER


def bfs(root):
    # SKRIV DIN KODE HER

function = stdin.readline().strip()
number_of_nodes = int(stdin.readline())
nodes = []
for i in range(number_of_nodes):
    nodes.append(Node())
start_node = nodes[int(stdin.readline())]
ratatosk_node = nodes[int(stdin.readline())]
ratatosk_node.ratatosk = True
for line in stdin:
    number = line.split()
    temp_node = nodes[int(number.pop(0))]
    for child_number in number:
        temp_node.child.append(nodes[int(child_number)])

if function == 'dfs':
    print(dfs(start_node))
elif function == 'bfs':
    print(bfs(start_node))
elif function == 'velg':
    # SKRIV DIN KODE HER

Variabelbeskrivelse

Rammeverket oppretter en nodeklasse med folgende egenskaper: barn - en liste over alle nodebarna til noden (noder direkte underlagt noden du staar i) ratatosk - en boolsk variabel som er True om ratatosk finnes i noden nesteBarn - en variabel du kan sette til neste nodebarn naar du bruker dybde-forst-ok

Input-eksempel

dfs
10
0
7
7 8 9
1 4 5
3 6 7
0 1 2 3

Tilhørende output

2

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å.

Godbit

Bit 1: Modifiser programmet ditt til å kunne takle generelle grafer i stedet for trær. Du må da merke nodene etter hvert som du besøker dem. Lag deg input-data som tester at programmet ditt fungerer.

Et generelt tre er ofte oppbygd slik at en node peker til alle barna sine, som vist i denne øvingen. En annen måte å representere et tre på, er at en node peker til sitt første barn, og sitt neste søsken (venstre eller høyre). Alle nodene peker da til 0, 1 eller 2 andre noder, og er da et binærtre. Du ser et eksempel på dette i figuren under.

tree_to_2tree.png

Bit 2: Lag en funksjon som transformerer et tre hvor nodene har pekere til alle barna, til et tre hvor nodene har pekere til første barn og neste søsken. Legg merke til at dette blir et binærtre.

Topologien i et binærtre har en enkel "en-til-en"-relasjon med de positive heltall, som gjør at nodene kan lagres i en array, uten at de trenger å ha pekere. Hvis en node har nummeret i, har venstre barn nummeret 2*i+1, og høyre barn nummeret 2*i+2.

tree_to_2tree.png

Bit 3: Lag en funksjon som putter et binærtre fra oppgaven over inn i en liste. Nodene kan da representeres kun ved sin vekt (altså en float, ikke et Node-objekt). Binærtreet fra Bit 1 er ikke komplett, hvilket betyr at noen av elementene i listen ikke skal være noder. Du kan representere disse med verdien None.