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):

• 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$.

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

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.

Ć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.

Ćwiczenie [Kodowanie par liczb]

Zaimplementuj kodowanie par liczb całkowitych jako liczby całkowite. To znaczy, napisz procedurę dwuargumentową, która koduje dwie liczby dane jako argumenty w jednej liczbie całkowitej. Dodatkowo napisz dwie procedury, które wydobywają z zakodowanej pary odpowiednio pierwszą i drugą liczbę.

Ć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$).