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

Ukeoppgaver i INF3110


INF3110/4110 L?sningsforslag uke 37 (10.-12.9.2003) Oppgave 1 --------- fun reverser (l: 'a list) : 'a list = case l of [] => [] | x :: xs => reverser(xs) @ [x]; Oppgave 2 --------- fun append (l1: 'a list, l2: 'a list) : 'a list = case l1 of [] => l2 | x :: xs => x :: append(xs, l2); Oppgave 3 --------- 1. fun mindre(x:Data,y:Data):bool = case y of no => false | tall(i) => (case x of no => true | tall(j) => j y | tall(j) => case y of no => x | tall(i) => tall((i+j) div 2); 4. fun snitt(l:Dataliste):Data = case l of [] => no | x::r => snitt2(x,snitt(r)); 5. Fordi rekursjonen g?r til slutten av listen f?r noe regnes ut, vil snitt([tall(7),tall(8),tall(5)]) f?rst regne ut snitt2(tall(8),tall(5)) som gir tall(6), og s? snitt2(tall(7),tall(6)) som ogs? gir tall(6) (pga heltallsdivisjon). Dette er IKKE det samme resultatet som snitt([tall(8),tall(5), tall(7)]) som f?rst tar snittet av tallene 5 og 7, som blir 6, og s? snitt2 av 6 og 8, som til slutt gir tall(7). Oppgave 4 --------- 1. fun Str(t: BTre): int = case t of Tom => 0 | Node(v,i,h) => Str(v) + 1 + Str(h); 2. fun Infiks(t: BTre): int list = case t of Tom => [] | Node(v,i,h) => Infiks(v) @ [i] @ Infiks(h); 3. fun Postfiks(t : BTre): int list = case t of Tom => [] | Node(v,i,h) => Postfiks(v) @ Postfiks(h) @ [i]; 4. fun Prefiks(t: BTre): int list = case t of Tom => [] | Node(v,i,h) => [i] @?Prefiks(v) @?Prefiks(h); 5. fun SettInn(x: int, t: BTre): BTre = case t of Tom => Node(Tom, x, Tom) | Node(v,i,h) => if x <= i then Node(SettInn(x, v), i, h) else Node(v, i, SettInn(x, h)); 6. Et bin?rtre er sortert hvis listen vi f?r ved infiks traversering er sortert. Vi trenger derfor en hjelpefunksjon ListeSortert som sjekker om en liste av heltall er sortert eller ikke. fun ListeSortert(l: int list): bool = case l of [] => true | x1::l1 => case l1 of []? => true | x2::l2 => x1 <= x2 andalso ListeSortert(l1); fun ErSortert(t: BTre): bool = ListeSortert(Infiks(t)); 7. fun Speilvend(t: BTre): BTre = case t of Tom => Tom | Node(v,i,h) => Node(Speilvend(h), i, Speilvend(v)); Oppgave 5 --------- exception helg; fun neste_tid(x:tid) = case x of man t => if t<15 then man (t+1) else (tir 12) | tir t => if t<15 then tir (t+1) else (ons 12) | ons t => if t<15 then ons (t+1) else (tor 12) | tor t => if t<15 then tor (t+1) else (fre 12) | fre t => if t<15 then fre (t+1) else raise helg; fun has x l = case l of [] => false | x'::l' => x=x' orelse has x l'; fun dup(l: tid list) = case l of [] => [] | x'::l' => if has x' l' then x'::(dup l') else dup l' ; Hjelpefunksjonen has er her av typen ''a -> ''a list -> bool. fun dup l = eller fun dup (l: ''a list) = eller fun dup (l): ''a list = eller fun dup (l: ''a list): ''a list = forutsatt at has fungerer p? vilk?rlige lister, slik som v?r has over. Typen til dup blir n?: ''a list -> ''a list. Oppgave 6 --------- fun gjenta2(f,d,l) = case l of [] => d | x :: r => case r of [] => f(x,d) | y :: r' => gjenta2(f,d,(f(x,y)::r')); Oppgave 7 --------- 1. Vi definerer f?rst en funksjon snu som snur ett par. Selve inv-funksjonen kan da enkelt lages ved hjelp av oppdater. fun snu(x: ''Elem Pair): ''Elem Pair = (#2 x, #1 x); fun inv(r: ''Elem Rel): ''Elem Rel = oppdater(snu,r); 2. Vi lager oss f?rst en funksjon ltest som tester om f?rste element i et par er med i den gitte listen. Funksjonen rpart plukker ut andre element av et par, da det bare er disse vi skal ha med i det endelige svaret. fun ltest(s: ''Elem list) (x: ''Elem Pair): bool = has(s, #1 x); (* has kan defineres som f?r: *) fun has(s,e) = case s of []?=> false | e'::s' => e=e' orelse has(s',e); fun rpart(x: ''Elem Pair): ''Elem = #2 x; Funksjonen relto kan da lages ved hjelp av oppdater og plukk som f?lger: fun relto(r: ''Elem Rel, s: ''Elem list): ''Elem list = oppdater(rpart, plukk(ltest(s), r));