Programowanie funkcyjne/Podstawy/Ćwiczenia

Z Studia Informatyczne
Przejdź do nawigacjiPrzejdź do wyszukiwania

Praca domowa

  • Stopień parzystości liczby całkowitej to największa taka liczba naturalna , że dzieli się przez 2i. 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 -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: . Wykorzystaj ten fakt do napisania procedury sqrt obliczającej sqrt x .

Rozwiązanie

Ćwiczenie [Test pierwszości]

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

Rozwiązanie

Ć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

Ć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

Ć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

Ć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

Ćwiczenie [Nietrywialne pierwiastki z 1]

Napisz procedurę, która dla danej liczby sprawdzi czy pierścień reszt modulo zawiera nietrywialne pierwiastki z 1 (tj. takie liczby , , , że ).

Rozwiązanie