mod Ex03 rem \para \bf 3. CVIČENIE Z PREDMETU ÚVOD DO DEKLARATÍVNEHO PROGRAMOVANIA \end \para* http://ii.fmph.uniba.sk/cl/view.php/courses/1-AIN-505-udp/0506ls/ex/ex03.cl rem \para* \it Dátum: \end utorok 28. 2. 2006 \para* \it Odporúčaná verzia CL: \end 5.81.16 \para* \it WWW stránka predmetu: \end http://ii.fmph.uniba.sk/cl/view.php/courses/1-AIN-505-udp/0506ls/?lang=sk \para* \it Kontakt na cvičiaceho: \end mailto:kluka@fmph.uniba.sk rem \para Scroll down to "EXERCISES". \para* Preskočte nasledujúce komponenty po nadpis "CVIČENIA". appldisp/0 Fill_in_d Op(Ent('ctdot'),0) fun/0 Fill_in 'Fill_in_d' Fill_in = 20060228 appldisp/2 Divides_d Infix(Arg(0),25,0,Op(Ent('mid'),0),Arg(1)) appldisp/2 Gcd_d Prefix(90,2,Id(0,'gcd',0), Fenced(Op('(',0),Infix(Arg(0),30,2,Op(',',0),Arg(1)),Op(')',0))) appldisp/2 Comb_d Fenced(Op('(',0),Frac(Arg(0),0,Arg(1)),Op(')',0)) appldisp/1 Fib_d Subsup(Id(1,'F',0),75,Arg(0),None) appldisp/1 Sum_d Prefix(70,2, Underover(Op(Ent('sum'),0),Infix(Id(1,'i',0),25,0,Op('=',0),Num('0',0)),Arg(0)), Id(1,'i',0)) appldisp/1 Fact_d Postfix(Arg(0),60,1,Op('!',0)) rem \para \bf E X E R C I S E S \end \para* \bf C V I Č E N I A \end rem \para \bf Exercise 1. \end Define the function \ft Gcd_d(x,y) \end computing the \it greatest common divisor \end of the numbers \ft x \end and \ft y \end using the Euclidean algorithm. \para* \bf Cvičenie 1. \end Definujte funkciu \ft Gcd_d(x,y) \end počítajúcu \it najväčšieho spoločného deliteľa \end čísel \ft x \end a \ft y \end euklidovským algoritmom. \para The greatest common divisor of \ft x \end and \ft y \end is a number \ft d \end which is a divides \ft x \end and divides \ft y \end, and every number \ft c \end dividing \ft x \end and \ft y \end divides \ft d \end. Formally \para Najväčší spoločný deliteľ čísel \ft x \end a \ft y \end je číslo \ft d \end, ktoré delí \ft x \end a delí \ft y \end a každé číslo \ft c \end, ktoré delí \ft x \end a \ft y \end, delí \ft d \end. Formálne \eq* Divides_d(Gcd_d(x,y),x) & Divides_d(Gcd_d(x,y),y) \end \eq* \a c(Divides_d(c,x) & Divides_d(c,y) -> Divides_d(c,Gcd_d(x,y))) \end \para The Euclidean algorithm is based on two properties of divisibility: \para* Euklidovský algoritmus je založený na dvoch vlastnostiach deliteľnosti: \items \item \para The greatest common divisor of \ft 0 \end and any number \ft x \end is \ft x \end, because all numbers divide \ft 0 \end. \para* Najväčším spoločným deliteľom \ft 0 \end a ľubovoľného iného čísla \ft x \end je \ft x \end, lebo všetky čísla delia \ft 0 \end. \eq* \a xDivides_d(x,0) \end \item \para If \ft y > 0 \end, a common divisor of \ft x \end and \ft y \end divides also \ft x mod y \end, and consequently is a common divisor of \ft y \end and \ft x mod y \end. \para* Ak \ft y > 0 \end, spoločný deliteľ \ft x \end a \ft y \end delí tiež \ft x mod y \end, a teda je spoločným deliteľom \ft y \end a \ft x mod y \end. \eq* \a d(Divides_d(d,x) & Divides_d(d,y) -> Divides_d(d,x mod y)) \end \end \para You perhaps know a less efficient version of the algorithm which is based on the fact that a common divisor of numbers \ft x \end and \ft y \end, \ft x > y \end, divides also \ft x-y \end. \para* Možno poznáte menej efektívnu verziu tohto algoritmu založenú na tom, že spoločný deliteľ čísel \ft x \end a \ft y \end, \ft x > y \end, delí tiež \ft x-y \end. \eq* \a d(Divides_d(d,x) & Divides_d(d,y) -> Divides_d(d,x-y)) \end fun/2 M_gcd M_gcd(x,y) = Fill_in fun/2 Gcd 'Gcd_d' Gcd(x,y) = Fill_in rem \para \bf Exercise 2. \end \header* fun/2 Comb \end Define the \it combinatorial number (binomial coefficient) \end: \ft Comb(n,k) = Comb_d(n,k) \end \para* Hint: Use the properties of the Pascal triangle \para* \bf Cvičenie 2. \end Definujte \it kombinačné číslo (binomický koeficient) \end: \ft Comb(n,k) = Comb_d(n,k) \end \para* Návod: Využite vlastnosti Pascalovho trojuholníka fun/2 M_comb M_comb(n,k) = Fill_in fun/2 Comb 'Comb_d' Comb(n,k) = Fill_in rem \para \bf Exercise 3. \end Define the Fibonacci function as in Ex02. \para* \bf Cvičenie 3. \end Definujte Fibonacciho funkciu ako v Ex02. fun Fib 'Fib_d' Fib(n) = Fill_in rem \para \bf Exercise 3. \end For some functions, one can find a so-called \it tail-recursive \end definition, which can be computed more efficiently than an ordinary recursive definition. A tail-recursive definition simulates \it iteration \end, i.e., a \it while \end or a \it for \end loop in imperative languages such as Pascal or C. \para* \bf Cvičenie 3. \end Pre niektoré funkcie sa dá nájsť tzv. \it chvostovorekurzívna \end definícia, ktorú možno počítať efektívnejšie ako bežnú rekurzívnu definíciu. Chvostovorekurzívna definícia simuluje \it iteráciu \end, t. j. \it while \end alebo \it for \end cyklus v imperatívnych jazykoch akými sú Pascal či C. \para E. g., the Fibonacci function from the previous exercise is computed using a \it while \end-loop as follows: \para Napríklad Fibonacciho funkciu z predchádzajúceho cvičenia vypočítame pomocou \it while \end cyklu nasledovne: \verbatim y := 1; d := 1; while n > 0 do begin t := y+d; y := d; d := t; n := n-1 end; Fib := d \end \para Simulate the \it while \end-loop by a three-argument function \header* fun/3 Fib_while \end \ft Fib_while(n,y,d) \end and use it to define the function \ft Fib_by_while(n) = Fib_d(n) \end. \para* Simujte tento \it while \end cyklus trojargumentovou funkciou \ft Fib_while(n,y,d) \end a použite ju na zadefinovanie funkcie \ft Fib1(n) = Fib_d(n) \end. fun/3 Fib_while Fib_while(n,y,d) = Fill_in fun Fib1 Fib1(n) = Fill_in rem \para The Fibonacci function is also computed by the following \it for \end-loop: \para* Fibonacciho funkciu počíta aj nasledujúci \it for \end cyklus: \verbatim if n = 0 then Fib := 1 else if n = 1 then Fib := 1 else begin y := 1; d := 1; for i := 2 to n do begin t := y+d; y := d; d := t end; Fib := d end \end \para Define an auxiliary function \header* fun/4 Fib_for \end \ft Fib_for(i,n,y,d) \end simulating this \it for \end-loop and for which the equation \ft Fib_d(n+2) = Fib_for(2,n+2,1,1) \end holds. Use \ft Fib_for \end to define the function \ft Fib2(n) = Fib_d(n) \end. \para* Definujte pomocnú funkciu funkciu \ft Fib_for(i,n,y,d) \end, ktorá simuluje tento \it for \end cyklus a pre ktorú platí rovnosť \ft Fib_d(n+2) = Fib_for(2,n+2,1,1) \end. Použite \ft Fib_for \end na zadefinovanie \ft Fib2(n) = Fib_d(n) \end. fun/4 Fib_for Fib_for(i,n,y,d) = Fill_in fun Fib2 Fib2(n) = Fill_in rem \para \bf Exercise 4. \end Implement the following functions by tail recursion. \para Write down two versions of each function, simulating a \it while \end-loop and a \it for \end-loop respectively. \para* \bf Cvičenie 4. \end Implementuje nasledujúce funkcie chvostovou rekurziou. \para Napíšte dve verzie každej funkcie -- jednu simulujúcu \it while \end cyklus a druhú simulujúcu \it for \end cyklus. rem \para \bf a) \end \ft Sum_d(n) \end fun/2 Sum_while Sum_while(n,a) = Fill_in fun Sum1 Sum1(n) = Fill_in fun/3 Sum_for Sum_for(i,n,a) = Fill_in fun Sum2 Sum2(n) = Fill_in rem \para \bf b) \end \def* F1(0) = 0 F1(1) = 1 F1(2) = 2 F1(n+3) = F1(n+2)+F1(n+1)+F1(n) \end fun/2 F1_while F1_while(n,a) = Fill_in fun F11 F11(n) = Fill_in fun/3 F1_for F1_for(i,n,a) = Fill_in fun F12 F12(n) = Fill_in rem \para \bf Exercise 5. \end Implement the function \ft F2 \end by tail recursion. \para Only the \it for \end-loop simulation is applicable now. Why? \para* \bf Cvičenie 5. \end Implementuje funkciu \ft F2 \end chvostovou rekurziou. \para V tomto prípade je použiteľná len simulácia \it for \end cyklu. Prečo? \def* F2(0) = 0 F2(1) = 1 F2(n+2) = n+1+F2(n+1)+F2(n) \end rem \para \bf Exercise 6. \end Rewrite the following recursive definitions to tail recursion. Try to write down both the \it while \end and the \it for \end versions. \para* \bf Cvičenie 6. \end Prepíšte nasledujúce rekurzívne definície do chvostovorekurzívnych definícií. Pokúste sa napísať verzie simulujúce \it while \end i \it for \end cykly. rem \def* Fact_d(0) = 1 Fact_d(n+1) = (n+1)*Fact_d(n) \end rem \def* F3(0) = 0 F3(1) = 1 F3(2) = 2 F3(n+3) = 2*F3(n+2)+5*F3(n+1)+7*F3(n)+10 \end rem \def* F4(0) = 0 F4(1) = 1 F4(2) = 2 F4(n+3) = 6*F4(n+2)+8*F4(n)-5 \end rem \para In the following examples, only a \it for \end-version makes sense. Why? \para* V nasledujúcich príkladoch má zmysel iba \it for \end-verzia. Prečo? rem \def* F5(0) = 0 F5(1) = 1 F5(2) = 2 F5(n+3) = (n+2)*F5(n+2)+F5(n+1)+F5(n) \end rem \def* F6(0) = 0 F6(1) = 1 F6(2) = 2 F6(n+3) = (n+2)*F6(n+2)+n*F6(n+1)+(n+6)*F6(n) \end rem \def* F7(0) = 0 F7(1) = 1 F7(2) = 2 F7(n+3) = 3*(n+1)*F7(n+2)*F7(n+1)+6*n*(n+4)*F7(n)+7 \end