TILDA, ÖVNING 3 19 sept 2007 ************************************************************** Problemträd, breddenförst, djupetförst 1 STRYKORD Ordet orkan är ett strykord eftersom man kan stryka sista bokstaven om och om igen och bara få riktiga ord. orkan - orka - ork - or - o Uppgiften är att finna det längsta strykordet i svenska språket. Ordlistan finns på fil. Rita problemträdet och jämför olika tänkbara algoritmer. 2 SJUOR TILL HUNDRA Det gäller att skriva talet 100 med enbart sjuor och dom fyra räknesätten, till exempel så här. 7 +7 /7 *7 *7 =98 Det var ett gott försök som inte nådde ända fram. För att man ska få använda / måste divisionen gå jämnt ut. Rita problemträdet och diskutera bästa algoritm för att avgöra OM problemet är lösbart. Om man dessutom vill veta hur lösningen ser ut krävs en mer komplicerad datastruktur. Beskriv den och skissa ett program. 3 PERFEKT HASHFUNKTION Hitta på en perfekt hashfunktion för atomer. Hur stor blir hashtabellen? 4 HÅLL REDA PÅ MEDIA (Tildatenta 030308) Under gulfkriget var det väldigt svårt för armestaben att hålla reda på alla TV-bolag som for omkring och rapporterade i öknen. För att hålla reda på dem användes en hashvektor. Koden fungerade inte som avsett och man har nu gett i uppdrag åt en f.d. tildastudent att titta på en misstänkt del av koden: from string import find p=100; hashvektor = [0]*p alfabet="abcdefghijklmnopqrstuvxyz" def put(tvbolagsnamn, tvbolag): hashcode = 0 for i in range(len(tvbolagsnamn)): alfanum = find(alfabet, tvbolagsnamn[i])+1 hashcode += alfanum hashcode = hashcode % p hashvektor[hashcode] = tvbolag Vad är det för fel på koden? Beskriv hur man kan förbättra den. Namnen på TV-bolagen kan antas bestå av högst tre bokstäver. Det kommer inte att förekomma mer än 75 TV-bolag. 5 Nix till telefonförsäljning (TILDA-tenta 000603) Föreningen för konsumentskydd vid marknadsföring per telefon har startat ett register dit den som inte vill bli uppringd av telefonförsäljare kan anmäla sig. Till att börja kommer kontrollen att ske genom att företaget sänder sin telefonlista till nix och får tillbaka en lista där de nixade numren markerats. Vilka av följande metoder kan föreningen använda sig av? Vilken är bäst? Binärträd, bloomfilter, hashtabell. Ett framtida mål är att kontroll också skall kunna ske över internet. Då måste kontrollen ske snabbt men man vill också försäkra sig om att ingen ska kunna få ut en lista över alla nixade telefonnummer. Vilken metod passar bäst för internet-kontrollen? ************************************************************** LÖSNINGAR ************************************************************** 1 STRYKORD Tomt ord är stamfar, söner får man genom att lägga på en bokstav och kolla i ordlistan. Eftersom man inte är ute efter kortaste strykord utan tvärtom längsta är breddenförst inte nödvändigt. Rekursiv djupetförst som går igenom hela trädet och noterar längdrekord är kanske bäst, särskilt eftersom letandet i ordlistan då hela tiden går framåt! Här har jag lagt alla svenska ord i ett binärträd - det tar förstås mycket minne och är onödigt. Man kan i stället läsa filen ord för ord eftersom man aldrig behöver backa. # coding:iso-8859-1 def byggut(ord): global rekord if len(ord)>len(rekord): rekord=ord for tkn in alfabet: if svenska.exists(ord+tkn): byggut(ord+tkn) from bintree import Bintree alfabet="abcdefghijklmnopqrstuvwxyzåäö" rekord="" svenska=Bintree() svenskfil = open("words.txt") for rad in svenskfil.readlines(): svenska.put(rad.strip()) # Strippa returtecknet byggut("") print "Längsta strykord:",rekord 2 SJUOR TILL HUNDRA Som gjort för breddenförst med heltalskö. # coding:iso-8859-1 from queue import Queue q=Queue() def makesons(tal): if tal==100: print "Hundra!" q.put(tal+7) q.put(tal-7) q.put(tal*7) if(tal%7==0): q.put(tal/7) q.put(0) while not q.isempty(): makesons(q.get()) Om man ska skriva ut lösningen: class Node: tal=0 far=None from queue import Queue from sys import exit q=Queue() def insert(tal,far): nod=Node() nod.tal=tal nod.far=far q.put(nod) def makesons(far): tal=far.tal if tal==100: writechain(far) exit() insert(tal+7,far) insert(tal-7,far) insert(tal*7,far) if(tal%7==0): insert(tal/7,far) def writechain(p): if p is None: return writechain(p.far) print p.tal q.put(Node()) while not q.isempty(): makesons(q.get()) 3 PERFEKT HASHFUNKTION Låt a=1, b=2, ..., z=26 och A=0, B=27, ..., Z=675 (25*27) Då blir hash("A")=0 och hash("Zz")=701, så det behövs 702 platser i hashtabellen. Ingen luft - det blir inga krockar! I labb 5 ska ni inte göra en så här stor tabell utan istället använda kvadratisk probning. 4 HÅLL REDA PÅ MEDIA (TILDA-tenta 030308) Det som gör att koden inte fungerar är att det inte finns någon krockhantering. hashvektor[hashcode] = tvbolag; För att lösa det kan man använda t.ex. krocklistor eller linjär probning. Linjär probning fungerar så att om det är upptaget på den givna positionen så söker man tills man antingen hittar nyckeln (den var redan instoppad sedan tidigare) eller tills man hittar ett tomt element i vektorn. Hashkoden är ganska korkat implementerad. Strängarna "AB" och "BA" får samma värde. alfanum = find(alfabet, tvbolagsnamn[i])+1 hashcode += alfanum För att lösa det kan man vikta genom att multiplicera med t.ex. 1, 100 och 10000. Längden på hashvektorn är lite för liten och dessutom inget primtal. Välj istället hashvektorns storlek till exempelvis 151 (dubbelt så stor som förväntade antalet element). 5. Nix till telefonförsäljning (TILDA-tenta 000603) Just nu ringer många och anmäler sig till NIX-registret så det måste gå lätt att lägga till nya. Binärträd går snabbt att söka i men man måste se till att det inte blir obalanserat när nya telefonnummer läggs till. Bloomfilter är besvärligt att stoppa in nya nummer i. Hashtabell se bloomfilter ovan. Bloomfilter är det bästa alternativet för den framtida internet-kontrollen. Man kan räkna med att många har registrerat sig så snabb sökning är nödvändig. Dessutom har bloomfilter fördelen att ingen användare kan få ut telefonnummerlistan.