Recursivitate
Mediul de lucru: compilarea și rularea
Pentru exemple simple, e convenabil să folosim interpretorul: le
putem rula direct, și ne prezintă rezultatul,
fără a fi nevoie să mai folosim funcții de
tipărire.
Pentru a scrie programe care pot fi utilizate independent (cum e desenarea
de fractali scrisă la curs), vom folosi compilatorul.
În primul rând, trebuie să ne structurăm programul în mod corespunzător:
Compilarea și rularea programului
Compilăm programul din terminal cu comanda
ocamlc program.ml
Compilatorul va produce un fișier executabil cu numele implicit a.out . Putem să specificăm și un alt nume dorit: ocamlc -o nume program.ml.
Programul executabil poate fi rulat din terminal, specificând numele lui, precedat de ./ (explicitând numele complet, inclusiv catalogul curent). Rulăm deci:
./a.out
dacă am compilat cu numele implicit, sau ./nume dacă am specificat alt nume pentru executabil.
Șiruri recurente
Având ca exemplu progresia aritmetică discutată la curs,
scrieți pentru progresia geometrică:
- o funcție recursivă, folosind valori constante pentru primul termen și rație
- o funcție care are ca parametri și aceste două valori
- definiți o funcție pentru progresia de la punctul 1 dând parametri funcției scrise la punctul 2
Expresii numerice
Folosind definiția tipului expresie de la curs, scrieți în ML reprezentarea pentru expresiile: 2 * (3 - 8) + 4 și 2 + 4 - 5 * 3 .
Cel mai mare divizor comun
Știind că cmmdc(a, b) = cmmdc(b, a mod b) dacă b ≠ 0, scrieți o funcție recursivă pentru cel mai mare divizor comun. Care e cazul de bază ?
Aplicarea repetată a unei funcții
în laboratorul trecut am scris funcții de ordin superior
(funcționale) care aplicau o funcție de 2, 3, 4 ori.
Definiți (recursiv) o funcție care ia ca parametru un întreg n și o funcție, și returnează funcția compusă cu ea însăși de n ori.
Lucrul cu cifrele unui număr
Un număr e reprezentat uzual în scris ca un șir de cifre în baza 10.
Un șir e o noțiune recursivă (un element, sau un
șir urmat de un element).
Putem spune atunci că un număr n e fie o singură cifră, fie ultima cifră (n mod 10) precedată de alt număr (n / 10).
Folosind această definiție scrieți funcții recursive care calculează: suma cifrelor unui număr, numărul de cifre, produsul lor, cifra maximă / minimă, etc.
Resturi modulo p
Am amintit că mulțimea resturilor nenule modulo un
număr prim p formează un grup multiplicativ.
Scrieți o funcție care ia ca parametru un număr
întreg a și calculează ordinul lui
în acest grup (adică cea mai mică putere n
pentru care an ≡ 1 mod p
Marius Minea
Last modified: Tue Oct 1 15:30:00 EEST 2013