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

Ukeoppgaver i INF3110


INF3110/4110 L?sningsforslag uke 38 (17.-19.9.2003) Oppgave 2 --------- 1. Siden vi skal l?se den rekursivt, s? lager vi f?lgende funksjon (men det finnes alts? en formel for dette som fjerner behovet for rekursjon): fun sum(n:int):int = if n= 0 then 0 else n+sum(n-1); 2. let val sum5 = sum(5) in sum5 * (sum5-1) end; Alternativ l?sning med en navnl?s funksjon: Tenk deg at du har regnet ut sum(5), og at variabelen x er bundet til denne verdien. Da f?r du opplagt samme svar ved ? erstatte de to forekomstene av sum(5) med x. Lag deretter en funksjon med x som formell parameter, og send inn sum(5) som aktuell parameter: (fn x => x * (x-1)) (sum(5)); Oppgave 3 --------- fun fib(n)= if n = 1 then (1,0) else let val (a,b) = fib(n-1) in (a+b,a) end; Oppgave 4 --------- 1. structure Set_impl: Set_def = struct type ''Elem Set = ''Elem list; val empty = []; fun has(s,x) = case s of [] => false | x'::r => if less(x,x') then false else if less(x',x) then has(r,x) else true; fun add(s,x) = case s of [] => [x] | x'::r => if less(x,x') then x::s else if less(x',x) then x'::add(r,x) else s; fun del(s,x) = case s of [] => [] | x'::r => if less(x,x') then s else if less(x',x) then x'::del(r,x) else r; fun union(s1,s2) = case s2 of [] => s1 | x::r2 => union(add(s1,x),r2); (* Alternativt: fun union(s1,s2) = case s1 of []?=> s2 | x::r1 => union(r1,add(s2,x)); *) fun inter(s1,s2) = case s2 of [] => [] | x::r2 =>if has(s1,x) then x::inter(s1,r2) else inter(s1,r2); (*Alternativt: fun inter(s1,s2) = case s1 of [] => [] | x::r1 => if has(s2,x) then x::inter(r1,s2) else inter(r1,s2); *) end; 3. structure Set_impl2: Set_def = struct type ''Elem Set = ''Elem -> bool; val empty = fn(x) => false; fun has(s,x) = s x; (* has returnerer bool *) fun add(s,x) = fn(y) => if x = y then true else s y; fun del(s,x) = fn(y) => if x = y then false else s y; fun union(s1,s2) = fn(x) => (s1 x) orelse (s2 x); fun inter(s1,s2) = fn(x) => (s1 x) andalso (s2 x); end; En alternativ skrivem?te for noen av funksjonene: fun empty x = false; fun add(s,x) y = if x = y then true else s y; fun del(s,x) y = if x = y then false else s y; fun union(s1,s2) x = (s1 x) orelse (s2 x); fun inter(s1,s2) x = (s1 x) andalso (s2 x);