Logică și structuri discrete - Exerciții la cursul 2

1. Șirul lui Fibonacci
Dacă șirul lui Fibonacci e calculat naiv, transcriind direct definiția: F₀ = 0, F₁ = 1, F_n = F_n-1 + F_n-2. se generează un număr foarte mare de apeluri recursive.

• Desenați schema apelurilor care se fac pentru a calcula fib(4). (Puteți să urmăriți apelurile și în interpretorul OCaml, dând directiva de trasare a apelurilor
  # #trace fib;;
  înainte de o evaluare (de exemplu fib 4).
• Scrieți o relație de recurență pentru numărul de apeluri necesare pentru a calcula fib(n). Ce remarcați comparând cu recurența Fibonacci?
• Opțional, scrieți o funcție care calculează fib(n) mai eficient. (Funcția va lua ca parametri ultimii doi termeni anteriori din șir).

2. Ce face funcția?
Când scriem cod, trebuie să putem urmări ce face. Astfel putem arăta fie că el face ce trebuie, fie să găsim unde e greșeala.
Pentru următoarele două funcții (presupuse a lucra cu întregi nenegativi), argumentați cât mai riguros și convingător (ideal: prin inducție după numărul de cifre al lui n) ce rezultat produc.
a) let rec f1 n = if n < 10 then n else f1 (n/10)
b) let rec f2 n = if n < 10 then n else 10 * f2 (n/10) + n mod 10

3. Tipuri cu variante
Definiți în ML un tip int_or_real care poate reprezenta fie un întreg, fie un real. Scrieți o funcție care ia o pereche de valori de acest tip și returnează suma lor (tot de acest tip). Faceți suma după regulile de conversie din C: suma a doi întregi e un întreg; dacă cel puțin un număr e real, suma e un real.

4. Definiții locale
Rezolvați exercițiul 1 de la laboratorul 1 (tipărirea soluțiilor ecuației de gradul 2) folosind o definiție locală pentru discriminantul b²-4ac și încă una pentru rădăcina lui pătrată, evitând recalcularea lor.