1. Haskelli kodutöö
Lahenda järgmised ülesanded Haskelli moodulisse Kt1.
Moodle'ist leiad ka lahendusfaili malli Kt1.hs.
1. ülesanne (0.3p)
Implementeeri naiivne astendamise funktsioon
aste :: Int -> Int -> Int aste x n = undefined
kasutades eeskirja
{$\operatorname{aste}(x,n) = \underbrace{x \cdot x \cdot \ldots \cdot x}_{n \text{ tegurit}} $}.
Kasuta rekursiooni, mitte Haskellisse sisseehitatud astendamisoperaatoreid!
2. ülesanne (0.3p)
Implementeeri permutatsioonide arvu funktsioon
p :: Int -> Int -> Int p n k = undefined
kasutades eeskirja
{$\operatorname{p}(n,k) = \underbrace{n \cdot (n-1) \cdot \ldots \cdot (n-(k-1))}_{k \text{ tegurit}} $}
Kasuta vahetut rekursiooni, mitte faktoriaali!
Rekursiooni väljamõtlemisel võid inspiratsiooni saada 1. ülesande lahendusest.
3. ülesanne (0.3p)
Implementeeri kombinatsioonide arvu funktsioon
c :: Int -> Int -> Int c n k = undefined
kasutades eeskirja
{$\operatorname{c}(n,k) = \binom{n}{k}, $} kus binoomkordaja avaldub reeglitega:
- {$\binom{n}{0} = \binom{n}{n} = 1$},
- {$\binom{n}{k} = \binom{n-1}{k-1} + \binom{n-1}{k}, \quad\text{kui $1\leq{}k\leq n-1$ } $}.
Kasuta antud binoomkordaja rekursioonireegleid, mitte faktoriaali!
4. ülesanne (0.3p)
Implementeeri kiire astendamise funktsioon
qaste :: Int -> Int -> Int qaste x n = undefined
kasutades eeskirja
{$\begin{align*} \operatorname{qaste}(x,n) = &{} \begin{cases} 1 & \text{kui } n = 0 \\ y \cdot y & \text{kui } \texttt{even } n \\ x \cdot y \cdot y & \text{muidu} \end{cases}\\ &\text{kus} \quad y = \operatorname{qaste}(x, n \;\texttt{`div`}\; 2). \end{align*} $}.
Trükimasina kirjas operaator `div` kirjuta/kopeeri täpselt nii rõhumärkide (backtick) vahel, et seda funktsiooni kasutada binaarse operaatorina.
Defineeri abimuutuja y kasutades where või let konstruktsiooni.
5. ülesanne (0.3p)
Implementeeri naiivne jagamise funktsioon
ndiv :: Int -> Int -> Int ndiv x y = undefined
kasutades eeskirja
{$\begin{align*} \operatorname{ndiv}(x,y) ={} &{} f(x,0)\\ &{} \text{kus} \quad f(n,z) = \begin{cases} z & \text{kui }n < y\\ f(n-y,z+1)& \text{muidu} \end{cases} \end{align*}$}.
Defineeri abifunktsioon f kasutades where või let konstruktsiooni.
6. ülesanne (0.5p)
Implementeeri pika jagamise funktsioon
bdiv :: Int -> Int -> Int bdiv n d = undefined
kasutades eeskirja
{$\begin{align*} \text{bdiv}(n,d) = &{} \begin{cases} \texttt{error "invalid argument" } & \text{kui } n<0 \lor d<0\\ \texttt{error "division by zero" } & \text{kui } d = 0\\ f(0, 0, \texttt{finiteBitSize n} - 1) & \text{muidu} \end{cases}\\ &\text{kus} \quad f(r, q, i) = \begin{cases} q & \text{kui } i = -1 \\ f(2*r + g(n, i)-d, q + 2^i, i-1) & \text{kui } 2*r + g(n, i) >= d\\ f(2*r + g(n, i), q, i-1) & \text{muidu} \end{cases}\\\\ &{}\text{ja}\quad g(i, n) = \texttt{shiftR i n .&. 1} \end{align*} $}.
Trükimasina kirjas avaldised kirjuta/kopeeri täpselt nii nagu antud, et kasutada vastavaid Haskelli funktsioone (error, shiftR, finiteBitSize, .&.). Viimaste kasutamiseks lisa faili päisesse import Data.Bits.
Selles ülesandes kasuta astendamiseks Haskellisse sisseehitatud operaatorit ^.
Defineeri abifunktsioonid f ja g kasutades where või let konstruktsiooni.
Kasuta where või let konstruktsiooni ka muude korduvate avaldiste korral.