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

{{{3}}}

Ć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

{{{3}}}

Ć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

{{{3}}}

Ć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

{{{3}}}

Ć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

{{{3}}}