Sist endret: 23.09.2016  
 

Praksisoppgave - Flexradix

[Oppgave] [Levering] [Highscore]

Innleveringsfrist: 25.09.2017 15:00

Velg språk:
- Python
- Java

Løsningsforslag

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

Rammeverk

Du trenger ikke benytte rammeverket, du kan skrive programmet som du vil.
Filnavn Hva skal endres
flexradix.py Funksjonen flexradix(A, d)
 

Test-data

Inndata Korrekt utdata
input_eksempel_01.txt output_eksempel_01.txt

Oppgave

I denne oppgaven skal du implementere en sorteringsalgoritme i lineær tid.

Programmet ditt skal sortere en liste med strenger av ulik lengde, fra 1 til $d$. Strengene kan kun inneholde bokstavene a til z i ASCII. Strengene skal sorteres alfabetisk (leksikalsk), slik at for eksempel "agg" kommer før "alge".

Utfordringen i denne øvingen ligger i å utnytte informasjonen dere har om den maksimale lengden $d$ på strengene, og at strengene kun inneholder små bokstaver mellom a til z, til å sortere i lineær tid. At den skal sortere i lineær tid vil i dette tilfellet si at kjøretiden skal være lineær som funksjon av den totale strenglengden (summen av lengdene til alle strengene) og ikke som funksjon av $d$. Om du har 99 strenger med lengde 1 og én streng med lengde 100, så er problemstørrelsen 199, ikke $100 * 100 = 10,000$, som tilsvarer det en vanlig Radix-Sort ville ha jobbet med.

Som vanlig er det ikke lov å bruke noen innebygde sorteringsfunksjoner i Python under noen deler av programmet ditt.

Rammeverk

#!/usr/bin/python3

from sys import stdin
from string import ascii_lowercase as chars
from random import randint, choice
from operator import itemgetter
from collections import defaultdict


def flexradix(A, d):
    # Du må mest sannsynlig lage egne hjelpefunksjoner for denne funksjonen for å løse oppgaven.
    # Funksjonen skal returnere listen A sortert.
    # SKRIV DIN KODE HER


def main():
    d = int(stdin.readline())
    strings = []
    for line in stdin:
        strings.append(line.rstrip())
    A = flexradix(strings, d)
    for string in A:
        print(string)


if __name__ == "__main__":
    main()

Variabelbeskrivelse

Rammeverket i denne oppgaven gir folgende variabler. - 'A' is a list of strings. - 'd' length of the greatest string.

Input-eksempel

6
kobra
alge
agg
kort
hyblen

Tilhørende output

agg
alge
hyblen
kobra
kort

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