Logică și structuri discrete: Tema 3

1. Un număr natural n scris în baza 10 poate fi văzut recursiv ca fiind fie o cifră (dacă e < 10), fie un număr (n / 10) urmat de o cifră (n mod 10). Urmând această definiție putem număra simplu cifrele unui număr:

let rec sumcif n = if n < 10 then n else sumcif (n / 10) + n mod 10

sau putem calcula câte cifre are un număr:

let rec numcif n = if n < 10 then 1 else numcif (n / 10) + 1

Aceste funcții au aceeași structură ca și definitia recursivă cu care lucrează:

dacă numărul e de o cifră (n < 10, cazul de bază), se poate calcula direct răspunsul
altfel, se calculează răspunsul pentru numărul (n/10) format din primele cifre, în afară de ultima, olosind recursiv aceeasi funcție, și se combină (în funcție de problemă) cu ultima cifră pentru a afla răspunsul final.

Folosind aceeași metodă, calculați:

suma cifrelor de pe poziții cu putere pară a bazei 10 (începănd de la ultima cifră din două în două poziții).
numărul de cifre egale cu o cifră c ∈ [0, 9] dată și ea ca parametru.

2. Funcția putere pentru exponent natural (și bază întreagă) se poate scrie recursiv în felul următor:

let rec putere x n = if n = 0 then 1 else x * putere x (n-1)

Similar cu cele de mai sus, definiți recursiv o funcție care ia ca parametru un întreg n și o funcție f, și returnează funcția f compusă cu ea însăși de n ori: f _°f _° ... _°f. Verificați rezultatul cu valori concrete pentru f, n și valoarea în care se aplică funcția.

3. Dacă șirul lui Fibonacci e calculat naiv, transcriind direct definiția:

let rec fib(n) = if n < 2 then n else fib(n-1) + fib(n-2)

se generează un număr foarte mare de apeluri recursive.

Desenați schema apelurilor care se fac pentru a calcula fib(5). (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 5).
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.

Marius Minea

Last modified: Fri Oct 4 17:30:00 EEST 2013