Cuprins introducere Ce şanse am să devin un bun programator ? Legile succesului durabil (Ghidul studentului îndărătnic) 6 Probleme de judecată 8
Yüklə 0,57 Mb.
|
RecursivitateaAşa cum am amintit deja, această metodă de programare poate fi privită ca formă particulară de exprimare a metodei Back-Tracking. Cu toate acestea, cei ce cunosc istoria informaticii şi originile programării ştiu că această metodă are totuşi un caracter special. Aceste lucruri dorim să le evidenţiem în continuare. Încă înainte de apariţia primului calculator şi, deci implicit a oricărei tehnici de programare, unii matematicieni erau profund preocupaţi de noţiunea de calculabilitate. Această noţiune îi putea ajuta în efortul lor deosebit de a fundamenta noţiunea elementară de algoritm sau metodă automată de calcul. În paralel, cele mai valoroase rezultate le-au obţinut latino-americanul Alonso Church şi englezul Alan Turing. În timp ce Turing a introdus pentru algoritm modelul matematic abstract cunoscut sub numele de Maşina Turing (care stă la bazele modelului actual de calculator), Church a fundamentat noţiunea de metodă de calcul sau calculabilitatea pe funcţiile recursive. Astfel, teza lui Church afirma că orice funcţie definită pe domeniul numerelor naturale este calculabilă dacă şi numai dacă ea este recursivă. Deşi aparatul teoretic folosit de Church era în întregime matematic (se baza numai pe funcţii numerice naturale), lui nu i-a fost greu să demonstreze că orice algoritm nenumeric se reduce la funcţii recursive şi la mulţimi recursive de numere naturale (pe baza unor codificări riguros alese). Acest din urmă rezultat este cel care ne interesează pe noi şi noi îl vom reformula fără ai afecta valabilitatea: orice algoritm poate fi rescris printr-un algoritm recursiv (limbajul de programare Lisp se bazează în întregime pe acest fapt). Chiar dacă nu constituie o demonstraţie riguroasă, următoarea echivalenţă practică (descrisă în pseudo-cod) este deosebit de convingătoare: orice instrucţiune de ciclare este echivalentă cu un apel recursiv de subprogram sau funcţie.
Observăm că în cazul variantei recursive condiţia de scurt-circuitare a recursivităţii este echivalenta condiţiei de scurt-circuitare a ciclului. Gestiunea contorului se face în acest caz în back-ground, prin mecanismul de stivă sistem. Putem astfel concluziona: toţi algoritmii iterativi pot fi înlocuiţi prin algoritmi recursivi. Avantajul celor recursivi este dat de scăderea dimensiunilor programelor şi de creşterea lizibilităţii. Avantajul celor iterativi este viteza mărită de execuţie prin gestionarea locală a parametrilor de ciclare (eliminîndu-se astfel toate instrucţiunile push şi pop pentru gestionarea stivei). Spre edificare, vă oferim în continuare cîteva probleme clasice (simple) rezolvate în C prin metoda recursivă. În capitolul cu probleme ce necesită back-tracking veţi găsi şi alte soluţii recursive (în C) ale unor probleme ceva mai dificile; astfel se vor putea sesiza mai bine avantajele acestei metode "naturale" de programare. (Întrucît am considerat acest capitol ca fiind destul de "tehnic", prezentăm în continuare doar variantele de program în limbajul C, ce este considerat mai "tehnic" decît limbajul Pascal.) 1. Să se copieze un şir de caractere într-altul. #include char *sir1="primul",*sir2="al doilea"; void strcopy(char *sursa,char *dest){ if ((*dest++=*sursa++)==NULL) return; else strcopy(sursa,dest); } void main(void){ printf("\nInainte, sirul sursa:%s, sirul destinatie:%s",sir1,sir2); strcopy(sir1,sir2); printf("\nSi dupa, sirul sursa:%s, sirul destinatie:%s",sir1,sir2); }
#include #include int n; void patrat(int m){ if(m>n)return; else { printf("%i:%i ",m,m*m); patrat(m+1); } } void main(void){ printf("n=");scanf("%i",&n); patrat(1); }
#include int cmmdc(int m,int n){ if (n==0) return(m); else cmmdc(n,m%n); }
int m,n; printf("m,n=");scanf("%i,%i",&m,&n); printf("cmmdc(%i,%i)=%i",m,n,cmmdc(m,n)); } 4. Se citeşte n, să se găsească primul număr prim mai mare decît n. (Se presupune cunoscută demonstraţia faptului că există p-prim mai mare decît oricare n. Sîntem astfel siguri că algoritmul se opreşte! ) #include #include int n; int are_divizor(int p,int d){ if(d>sqrt(p))return 0; else if(p%d==0) return 1; else are_divizor(p,d+1); } void prim(int p){ if(!are_divizor(p,2)){ printf("\n%i",p); return; }
} void main(){ printf("n=");scanf("%i",&n); prim(n+1); } 5. Să se afişeze primele n numere prime. #include #include int n; int are_divizor(int p,int d){ if(d>sqrt(p))return 0; else if(p%d==0) return 1; else are_divizor(p,d+1); } void prim(int p,int i){ if(i>n)return; if(!are_divizor(p,2)){ printf("%i,",p); prim(p+1,i+1); } else prim(p+1,i); } void main(){ printf("n=");scanf("%i",&n); prim(2,1); }
float a[20],x; float P(int i){ if(i==1)return a[0]; else return P(i-1)*x+a[i-1]; } void citeste_coef(int i){ if(i>n)return; else {printf("%i:",i);scanf("%f",&a[i]);citeste_coef(i+1);} } void main(){ printf("n=");scanf("%i",&n); citeste_coef(0); printf("x=");scanf("%f",&x); printf("P(%f)=%f",x,P(n+1)); }
float a[20],b[20],c[40]; float suma_prod(int i,int j){ if(j==i)return a[i]*b[0]; else return a[i-j]*b[j]+suma_prod(i,j+1); } void calc_coef(int i){ if(i>m+n)return; else c[i]=suma_prod(i,0); } void citeste_coef(float a[],int i){ if(i>n)return; else {printf("%i:",i);scanf("%f",&a[i]);citeste_coef(a,i+1);} } void afis_coef(float a[],int i){ if(i>n)return; else {printf("%f ",a[i]);afis_coef(a,i+1);} } void main(){ printf("m(gradul polinomului P)=");scanf("%i",&m); printf("Introd.coef.polinomului P:"); citeste_coef(a,0); printf("n(gradul polinomului Q)=");scanf("%i",&n); printf("Introd.coef.polinomului Q:"); citeste_coef(b,0); calc_coef(0); afis_coef(c,0); }
if(n<10)return n; else return n%10+suma(n/10); } void main(){ printf("n=");scanf("%i",&n); printf("suma cifrelor=%i",suma(n)); }
Yüklə 0,57 Mb. Dostları ilə paylaş:
|