Laborator 2
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:
să folosim explicit funcții de tipărire (print_int, print_float, print_string, printf, etc.) acolo unde dorim să apară scris ceva, întrucât rezultatele nu vor mai fi explicit tipărite de interpretor.
să punem în ordine codul pe care îl dorim executat. Prin compilare, se produce un program care evaluează, în ordine, toate expresiile din fișierul sursă. E însă o practică bună să definim întâi toate funcțiile necesare, și apoi să explicităm ce se dorește evaluat la rulare:
expresie1; expresie2; ...; expresieN (punând ;; înaintea lor pentru a le separa de restul definițiilor), sau
let _ = ( expresie1; expresie2; ... expresieN )
Liniuța de subliniere e un nume special, cu înțelesul "nu contează", nu se dorește folosirea lui ulterioară, ci doar uniformitatea sintaxei let ... = ...
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.
Exerciții propuse
Ș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. Folosiți let ... in și o funcție auxiliară cu un parametru.
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 un număr p (presupus prim) și calculează ordinul lui a în acest grup (adică cea mai mică putere n pentru care an ≡ 1 mod p).
Fractali
Adaptând programul de la curs, generați alți fractali, cum ar fi triunghiul lui Sierpiński sau curba lui Koch.
Triunghiul poate fi scris după același tipar; diferă doar desenul propriu-zis, și faptul că apar și linii oblice (folosiți comanda l în formatul SVG).
Curba lui Koch se observă că poate fi desenată fără a ridica creionul de pe hârtie, deci e suficientă o singură poziționare inițială cu M. Figura e caracterizată acum prin dimensiune și orientare (unghi); unghiul pentru o sub-figură poate varia cu ± π/3 față de cel al figurii mari.
//informatii luate de pe pagina laboratorului