Programowanie funkcyjne/Podstawy/Ćwiczenia

Praca domowa

• Stopień parzystości liczby całkowitej $x$ to największa taka liczba naturalna $i$, że $x$ dzieli się przez 2ⁱ. Liczby nieparzyste mają stopień parzystości 0, liczby 2 i -6 mają stopień parzystości 1, a liczby 4 i 12 mają stopień parzystości 2. Przyjmujemy, że 0 ma stopień parzystości -1. Napisz procedurę parzystość wyznaczającą stopień parzystości danej liczby całkowitej.

• Udowodnij, że dla każdego naturalnego n, fib n jest równe n-tej liczbie Fibonacciego. Podaj specyfikację dla fibpom i udowodnij ją przez indukcję.

let fib n =
  let rec fibpom a b n = 
    if n = 0 then a else fibpom b (a + b) (n - 1)
  in 
    fibpom 0 1 n;;

• Forma specjalna let-in jest tylko lukrem syntaktycznym i może być rozwinięta do $\lambda$-abstrakcji. W jaki sposób?

Ćwiczenia

W przypadku zajęć laboratoryjnych należy najpierw zapoznać studentów ze środowiskiem i uruchamianiem Ocamla.

Rozwiązaniami poniższych zadań są proste programiki operujące na liczbach całkowitych (bez rekurencji ogonowej i list):

Ćwiczenie [sqrt x]

Sumy kolejnych liczb nieparzystych dają kwadraty kolejnych liczb naturalnych, zgodnie ze wzorem: $\sum _{i=1}^k(2i-1)=k^2$. Wykorzystaj ten fakt do napisania procedury sqrt obliczającej sqrt x $=\lfloor \sqrt{x}\rfloor$.

Rozwiązanie

 let sqrt n = 
   let rec pom k s = 
     if s > n then k-1 else pom (k+1) (s + 2 * k + 1)
   in pom 0 0;;

Ćwiczenie [Test pierwszości]

Napisz procedurę, która sprawdza, czy dana liczba jest pierwsza.

Rozwiązanie

 let isprime x = 
   let rec pom a = 
     if a * a > x then true
     else if x mod a = 0 then false
     else pom (a+1)
   in (x > 1) && (pom 2);;

Ćwiczenie [Zera silni]

Napisz procedurę zera_silni : int -> int, która dla danej dodatniej liczby całkowitej n obliczy ile zer znajduje się na końcu zapisu dziesiętnego liczby n!.

Laboratorium

Ćwiczenie [Odwracanie liczb]

Napisz procedurę, która przekształca daną liczbę w taką, w której cyfry wystepują w odwrotnej kolejności, np. 1234 jest przekształcane na 4321.

Rozwiązanie

let odwroc n = 
  let rec pom x w = 
    if x = 0 then w else pom (x/10) (w*10 + x mod 10)
  in 
    pom n 0;;

Ćwiczenie [Numerologia]

Napisz procedurę, która sprawdza, czy dana liczba jest podzielna przez 9 w następujący sposób: jedyne liczby jednocyforwe podzielne przez 9 to 9 i 0; reszta z dzielenia liczby wielocyforwej przez 9 jest taka sama, jak reszta dzielenia sumy jej cyfr przez 9; jeśli suma cyfr jest wielocyfrowa, to całość powtarzamy, aż do uzyskania liczby jednocyfrowej.

Rozwiązanie

 let rec numerologia x =
   let rec sumacyfr n a =
     if n = 0 then a else sumacyfr (n / 10) (a + n mod 10)
   in
     if x < 10 then x else numerologia (sumacyfr x 0);;

Ćwiczenie [Reszta modulo 11]

Napisz procedurę, która sprawdza czy dana liczba jest podzielna przez 11 w następujący sposób: sumujemy cyfry liczby znajdujące się na parzystych pozycjach, oraz te na nieparzystych pozycjach, różnica tych dwóch liczb przystaje modulo 11 do wyjściowej liczby; krok ten należy powtarzać aż do uzyskania liczby jednocyfrowej.

Rozwiązanie

 let rec mod11 x = 
   let rec pom r1 r2 x =     
     if x = 0 then r1 - r2 else pom (r1 + x mod 10) (r2 + (x / 10) mod 10) (x / 100)  
   in 
     let r = pom 0 0 x
     in 
       if r > 10 then mod11 r
       else if r < 0 then 10 - mod11 ((- r) - 1)
       else r;;

Ćwiczenie [Kodowanie par liczb]

Zaimplementuj kodowanie par liczb naturalnych jako liczby naturalne. To znaczy, napisz procedurę dwuargumentową, która otrzymawszy dwie liczby naturalne zakoduje je w jednej liczbie naturalnej. Dodatkowo napisz dwie procedury, które wydobywają z zakodowanej pary odpowiednio pierwszą i drugą liczbę.

Rozwiązanie

 let para a b =
   let rec pom a b c p =
     if (a = 0) && (b = 0) then c
     else pom (a/10) (b/10) (c + p *(a mod 10) + 10 * p *(b mod 10)) (100*p)
   in pom a b 0 1;;
  
 let rzut_x x =
   let rec pom x p a =
     if x = 0 then a
     else pom (x / 100) (10 * p) (a + (x mod 10) * p)
   in pom x 1 0;;
  
 let rzut_y x =
   let rec pom x p a =
     if x = 0 then a
     else pom (x / 100) (10 * p) (a + ((x/10) mod 10) * p)
   in pom x 1 0;;  

Ćwiczenie [Nietrywialne pierwiastki z 1]

Napisz procedurę, która dla danej liczby $n$ sprawdzi czy pierścień reszt modulo $n$ zawiera nietrywialne pierwiastki z 1 (tj. takie liczby $k$, $k\ne 1$, $k\ne n-1$, że $k^2\equiv 1modn$).

Rozwiązanie

 let pierwiastki n =
   let rec spr p =
     if p >= n-1 then false
     else if (p * p) mod n = 1 then true
     else spr (p+1)
   in
     spr 2;;