Datalogilaboration 3 - Sökning

Binärsökning i ordlista är laborationens tema och uppgiften är att bland fembokstavsorden finna alla ordpar av typen alpin pinal, där första ordet delas i 2+3, kuperas till 3+2 och då ger andra ordet. Skriv din kod med följande i baktanken:

Inläsning från fil och linjär sökning

Filen ordlista.txt innehåller 1862 svenska ord, nämligen alla som består av fem olika bokstäver. Ta en titt på filen för att se hur den är uppbyggd.
Skriv sedan ett program kolla1.py som:
  1. Får ett ord från kommandotolken vid start av programmet (t.ex. datorn:~>python dittprogram.py ett_ord).
  2. Programmet frågar efter namn på en fil som ska läsas.
  3. Läser in sedan filen i en lista. Varje ord ska bli ett eget element i listan, m.a.o. listan ska innehålla 1862 element.
  4. När alla ord i filen är inläst och lagrat i listan, ska ett meddelande skrivas ut om att filen är inläst.
  5. Programmet ska sedan kolla om det sökta ordet finns i ordlistan.
se exemplet av en körning av programmet som följer här:
    datorn:~> python Kolla1.py trams
    Ange namn på den fil som ska läsas in: ordlista.txt
    Ordlistan inläst!
    ordet trams finns i listan
Programmet Kolla1 ska innehålla en funktion finns() som får ett ord och en lista med ord som indata och returnerar True eller False efter att funktionen har gjort en linjär sökning på ordet i listan, ett anrop till funktionen finns() skulle kunna se så här ut:
   if finns(listord, sys.argv[1]) :
           print "ordet",sys.argv[1],"finns i ordlistan");
Provkör programmet med ordet gurka och med ordet banan. Förklara bananresultatet!

Linjär sökning efter alpina pinaler

Skriv ett program Kolla2.py som är en modifierad version av kolla1 med följande skillnader:
  1. Programmet ska inte söka efter ett ord som skickas till programmet via kommandotolken.
  2. Istället ska programmet för varje ord i listan bilda ett nytt ord genom att byta plats mellan två första och tre sista tecknen i ordet, och kontrollera sedan om det nya ordet finns i ordlistan.
  3. Om det nya ordet finns i listan ska programmet skriva ut det orginella ordet och nya ordet i formen: pinal -> alpin, när orginella ordet är pinal.

Binär sökning

Skriv ett program Kolla3 som är en kopia av Kolla1. Du ska ändra funktionen finns() så att den gör binär sökning i stället för linjär sökning. Skriv ut alla ord som jämförs med det sökta ordet, m.a.o. där jämförelsen misslyckas.
För att se hur sökningen går till skriv en print-sats som skriver ut de ord som jämförs med det sökta ordet innan programmet kommer fram till det sökta ordet i ordlistan.

Provkör med några olika ord. Hur många sökord blir det som mest? Och hur många blir det som minst?

Binär sökning efter alpina pinaler

Skriv ett program Kolla4 som är en kopia av Kolla2. Kopiera in binärsökningen från Kolla3 men ta bort utskrift av alla ord som jämförs med sökta ordet. Provkör och uppskatta hur många gånger snabbare binärsökningen är!

Försök till sist få underskrift av en lärare.

Fenomenal prestation av ..................................... intygar.............................. den .................


^ Upp till kurssidan.


Sidansvarig: <vahid@nada.kth.se>
Senast ändrad 29 oktober 2004
Tekniskt stöd: <webmaster@nada.kth.se>