Laboration 1 - Algoritmer
Du som läste DD1321 tilpro i höstas kan hoppa direkt till programmeringsuppgiften nedan.
Hederskodex
Läs igenom hederskodexen (se vänstermenyn).
Formaliteter
Laborationerna görs normalt i grupper om två (om det finns utrymme
kan du labba ensam, men större grupper är inte tillåtna).
-
Logga in.
Ni bör båda ha varsitt konto (användarnamn + lösenord).
Logga in på det ena.
- Kursregistrering i rapp.
Gå till rapp
för att aktivera din kursregistrering. Logga in
med ditt kth-konto (som för Mina Sidor) och aktivera kursen DD1320.
Logga sedan ut från rapp och låt labbkompisen göra detsamma.
Kursregistrering i LADOK görs ca tre veckor efter kursstart.
Om du inte finns med i rapp:
Titta på Mina sidor
Om kursen inte finns med där ska du kontakta studievägledningen/kansliet bums.
Annars kan du prova igen imorgon!
- Öppna ett terminalfönster.
Under Applications hittar du Accessories och därunder
Terminal. Prova att skriva whoami i terminalfönstret
för att se vilken av er som är inloggad just nu.
-
Gör en gemensam labbkatalog där du och din labbkamrat kan
jobba.
Fysiskt skapas katalogen
med mkdir hos
en av er. Denne måste också
sätta accessrättigheter
med fs sa
KATALOGNAMN LABBKAMRAT rlidwk . Allt som återstår är att
labbkamraten nu loggar in eller
gör su (switch
user) i ett nytt teminalfönster
och länkar
(ln -s ~LABBKOMPIS/KATALOG) till den gemensamma katalogen.
Vid redovisning ska du kunna förklara hur en länk fungerar.
-
Starta Python.
Vi rekommenderar att du använder:
Emacs + Terminal
Under Applications hittar du Accesories och därunder
GNU Emacs och Terminal. Skriv programmet i Emacs
och kör det i Terminalen med kommandot:
python3 programmet.py
Du kan också mjukstarta med IDLE (rekommenderas dock inte ihop med Tkinter).
Under Applications hittar du Programming och därunder
IDLE (using Python-3.1)
SimaManager
Under Applications och sedan CSC hittar du SimaManager.
I fönstret som öppnas kan du välja kursen tilda.
Denna kö använder du när det är full rulle under labbarna
och du vill få tag på en assistent.
Är det lugnt så är det bara att vifta så kommer vi!
Programmeringsuppgift
I denna uppgift ska du implmentera multiplikation och division av
heltal enbart med hjälp av plus och minus.
Multiplikation
Skriv en funktion mult som tar två heltal (x, y) som parametrar och
returnerar heltalen multiplicerat med varandra. Du får enbart använda
dig av plus och minus. Den enkla lösningen är att du gör en loop som
adderar x med sig självt under y varv.
Funktionen ska kunna multiplicera stora tal utan att det tar orimligt
lång tid. Prova med 12231231232312323 * 5 och 15 * 323241244132443.
Det går att få Nlog(M) men det är inget krav.
Division
Funktionen ska ta två paramtetrar (t, n) och returnera t
heltalsdividerat med n. Den enkla lösningen är att loopa x varv och i
varje varv kolla om mult(n, x) är större än t för i så fall är x-1
svaret.
Det tar orimligt med tid för stora täljare. Det finns smartare lösningar.
Ett lite effektivare alternativ är
att dela upp täljaren i deltal som divideras (ungefär
som liggande
stolen). Deltalen kan vara olika långa. Använd
slicing för att ta ut deltalen. Exempel:
tal = 135212125
antalsiffror = len(str(tal))
treforstasiffror = int(str(tal)[0:3])
Det finns effektivare lösningar men kom ihåg att du får enbart använda
dig av plus, minus och din egen funktion mult. Programmet ska
klara av stora tal utan att det tar orimlig tid. Prova
med div(135212125, 25)
Testprogram
Dina funktioner ska kunna importeras från en annan fil. Skriv därför
inget vanligt main eller testkod direkt i filen. Om du vill göra
testerna i samma fil som funktionerna använd följande
teknik så
att man kan importera dina funktioner utan att köra dina tester.
def main():
# Din teskod här!
if __name__ == "__main__":
main()
Skriv minst fem tester per funktion t.ex. stora tal, små tal, negativa tal.
Skriv ut testet, resultat och förväntat resultat (använd pythons inbyggda funktioner).
Så här kan det se ut.
1 * 100090909 = 100090909, förväntat resultat 100090909
Skriftlig algoritmbeskrivning
Rita
ett flödesdiagram
över dina algoritmer. Skriv därefter ner algoritmerna steg för steg på
papper.
Analys av algoritmen
Med stöd av din algoritmbeskrivning uppskatta vilken komplexitet din multiplikation och division har.
Redovisning
Vid redovisningen kan det bli kö.
Se till att ha gjort alla deluppgifter och gå
vidare med en nästa labb medan du väntar.
- Gjort en delad katalog med din labbkamrat
- Kunna redovisa vad en länk är
- Implementerat mult, div samt 10 relevanta tester
- Ritat ett flödesdiagram
- Skrivit en algoritmbeskrivning med uppskattad tidskomplexitet
Väl labbat av ......................................... medger....................... den ...............
PS Berätta för din assistent hur många timmar du har lagt ner på denna labb!
|
