meny2.html – INF3110 - H?st 2003 – Universitetet i Oslo_澳门葡京手机版app下载

Ukeoppgaver i INF3110


INF3110/4110 Ukeoppgaver uke 38 (17.-19.9.2003) Oppgave 1 --------- Les l?sningen p? Dronning-oppgaven, ML-kompendiet s.17-18. Skriv en kort forklaring p? hvordan denne fungerer, og hva du eventuelt lurer p?. Oppgave 2 --------- 1. Skriv en rekursiv funksjon i ML, kalt sum, som for gitt n regner ut summen av alle tall fra 1 til n, f.eks. skal sum(5) gi verdien 15. 2. Hvis du n? skriver uttrykket sum(5) * (sum(5)-1) vil sum(5) regnes ut to ganger. Pr?v ? skrive uttrykket p? en annen m?te, ved ? bruke let-konstruksjonen, slik at sum(5) regnes ut bare en gang. Oppgave 3 --------- Fibonacci-tallene er definert ved hjelp av f?lgende funksjon f: f(1) = 1 f(2) = 1 f(n) = f(n-1) + f(n-2), for n > 2 Vi skal lage en ML-funksjon fun fib(n:int): int * int = ... som er slik at funksjonsverdien av fib gir paret best?ende av det n-te Fibonacci-tallet samt det foreg?ende Fibonacci-tallet. For eksempel skal kallet fib(2) gi paret (1,1), fib(3) skal gi (2,1), fib(4) skal gi (3,2), fib(5) skal gi (5,3) og fib(6) skal gi (8,5). Vi definerer det null-te Fibonacci-tallet som 0, og da skal fib(1) gi paret (1,0). Bruk let-konstruksjonen til ? lage en effektiv fib funksjon! Oppgave 4 (Eksamen 1990, del 2a,b,e) --------- I denne oppgaven skal du definere begrepet mengde med f?lgende velkjente funksjoner: has -- som tester om et element er med i en mengde add -- som legger et element inn i en mengde union -- som danner unionen av to mengder inter -- som danner snittet av to mengder empty -- som danner den tomme mengden Hvis for eksempel mengden "ansatte" best?r av elementene: "kari", "anne", "lise", og mengden "stud" best?r av elementene: "lars", "lise", s? vil unionen av de to mengdene best? av: "kari", "anne", "lise", "lars", og snittet av dem vil best? av: "lise". 1. Vi definerer mengde-begrepet som en parametrisert abstrakt datatype p? f?lgende m?te: signature Set_def = sig type ''Elem Set val empty: ''Elem Set val has : ''Elem Set * ''Elem -> bool val add : ''Elem Set * ''Elem -> ''Elem Set val del : ''Elem Set * ''Elem -> ''Elem Set val union: ''Elem Set * ''Elem Set -> ''Elem Set val inter: ''Elem Set * ''Elem Set -> ''Elem Set end; Mengdene skal representeres ved en liste-aktig datastruktur. Vi skal anta at for typen ''Elem finnes det en funksjon fun less(x,y:''Elem): bool = ... som svarer til ? teste at x er mindre enn y. Vi krever at listen som representerer en mengde alltid er sortert med hensyn p? denne ordning (med minste element f?rst), og dessuten at hvert element forekommer h?yst en gang i listen. Funksjonene i grensesnittet skal v?re slik at denne invarianten vedlikeholdes. Spesielt skal has-funksjonen utnytte invarianten ved ? stoppe leting s? snart som mulig. Din oppgave er ? lage en implementasjon av dette grensesnittet, dvs. en ``struktur'' for denne signaturen. 2. Diskuter plassforbruket (lager-behovet) til funksjonene du har laget. 3. Vi velger ? representere en mengde som en funksjon m som er slik at m(x) er sann hvis x er et element i mengden og gal ellers. Lag en implementasjon av Set-grensesnittet med en slik representasjon. Typen ''Elem Set skal n? alts? implementeres slik: type ''Elem Set = ''Elem -> bool;