S6 - Subprograme recursive. Divide et impera. Enunturi PDF

Preview

Summary

Seminar 5 Subprograme recursive. Metoda Divide et Impera - exempleEnunțuri : Să se scrie subprogramul recursiv care determină numărul de elemente negative dintr-un vector. Se va scrie și programul apelator. #define _CRT_SECURE_NO_WARNINGS #include <stdio>//nr elem negative vector metoda reduce...

Description

Seminar 5 Subprograme recursive. Metoda Divide et Impera - exemple

Enunțuri: 1. Să se scrie subprogramul recursiv care determină numărul de elemente negative dintr-un vector. Se va scrie și programul apelator. #define _CRT_SECURE_NO_WARNINGS #include //nr elem negative vector metoda reducerii void negat(float v[], int n, int *nr) { if (n == 0)*nr = 0; else { negat(v, n-1, nr); if (v[n-1] < 0)*nr=*nr+1; } } //nr elem negative vector metoda descompunerii int negative(float v[], int st, int dr) { int nr; if (st == dr) { if (v[dr] < 0)nr = 1; else nr = 0; } else nr = negative(v, st, (st + dr) / 2) + negative(v, (st + dr) / 2 + 1, dr); return nr; } void main() { float v[10]; int nr, i, n;

printf("n="); scanf("%d", &n); for (i = 0; i < n; i++) { printf("v[%i]=", i); scanf("%f", &v[i]); } negat(v, n, &nr);//metoda reducerii printf("nr=%d \n", nr); printf(" nr= %d", negative(v, 0, n-1));//metoda descompunerii } 1

2. Să se scrie subprogramul recursiv care determină produsul scalar dintre doi vectori. Se va scrie și programul apelator. #define _CRT_SECURE_NO_WARNINGS #include //produsul scalar dintre doi vetori float produsscalar(float v[], float u[], int n) { //metoda reducerii float ps; if (n == 0) ps = 0; else ps = produsscalar(v, u, n - 1) + v[n - 1] * u[n - 1]; return ps;

}

void main() { float v[10], u[10]; float ps; int i, n; printf("n="); scanf("%d", &n); for (i = 0; i < n; i++) { printf("v[%i]=", i); scanf("%f", &v[i]); } 2

for (i = 0; i < n; i++) { printf("u[%i]=", i); scanf("%f", &u[i]); } ps = produsscalar(v, u, n); printf("ps=%f \n", ps);

}

3. Să se scrie subprogramul recursiv care determină cmmdc dintre două numere naturale. Se va oferi și un exemplu de apel. #define _CRT_SECURE_NO_WARNINGS #include int cmmdc2(int a, int b) { int rez; if (a % b == 0) rez = b; else rez = cmmdc2(b, a % b); return rez; } void main() { int a, b,rez; 3

printf("a="); scanf("%d", &a); printf("b="); scanf("%d", &b); rez = cmmdc2(a, b); printf("rez=%d",rez); }

4. Să se scrie subprogramul recursiv care determină CMMDC dintr-un sir de numere naturale. Se va oferi și un exemplu de apel. #define _CRT_SECURE_NO_WARNINGS #include

// metoda reducerii int cmmdc2(int a, int b) { int rez; if (a % b == 0) rez = b; else rez = cmmdc2(b, a % b); return rez; } int cmmdcn(int v[], int n) { int rez; if (n == 1) rez = v[0]; 4

else { rez = cmmdc2(cmmdcn(v, n - 1), v[n - 1]);

} return rez; } //metoda descompunerii int cmmdcsir(int v[], int s, int d) { int rez; if (s == d) rez = v[s]; else { rez = cmmdc2(cmmdcsir(v, s, (s + d) / 2), cmmdcsir(v, (s + d) / 2 + 1, d));

} return rez; } void main() { int v[100], n, rez, i; printf("n="); scanf("%d", &n); for (i = 0; i < n; i++) { printf("v[%i]=", i); 5

scanf("%i", &v[i]); } rez = cmmdcn(v, n); printf("rez1=%d\n", rez); rez = cmmdcsir(v, 0, n - 1); printf("rez2=%d\n", rez); }

5. Să se scrie subprogramul recursiv care determină suma elementelor impare dintr-un vector. Se va oferi un exemplu de apel. #include #include #define _CRT_SECURE_NO_WARNINGS #include //produsul scalar dintre doi vetori int sumaimpare(int v[], int n)

{ //metoda reducerii

int s; if (n == 0) s = 0;

else if(v[n-1]%2==1)s=sumaimpare(v,n-1)+v[n-1]; else s=sumaimpare(v,n-1); 6

return s; } void main()

{ int v[10];

int s; int i, n; printf("n=");

scanf("%d", &n); for (i = 0; i < n; i++)

{ printf("v[%i]=", i); scanf("%i", &v[i]);

} s = sumaimpare(v, n);

printf("suma elementelor impare=%i \n", s);

}

7

6. Să se scrie subprogramul recursiv care determină produsul primelor n numere impare. Se va oferi un exemplu de apel. #define _CRT_SECURE_NO_WARNINGS #include int produsimpare(int n) { int rez; if (n == 1) rez = 1; else rez = produsimpare(n - 1) * (2*n-1); return rez;

} void main() { int n, rez; printf("n= "); scanf("%i", &n); rez=produsimpare(n); printf("%i", rez); }

8

7. Să se scrie subprogramul recursiv care determină suma cifrelor unui numar intreg. Se va oferi un exemplu de apel. #include int suma_impara(int v[], int stanga, int dreapta) { int rez; if (stanga == dreapta) { if(v[stanga] % 2 == 1) rez = v[stanga]; else rez = 0; } else rez = suma_impara(v, stanga, (stanga + dreapta)/2) + suma_impara(v, (stanga + dreapta)/2 + 1, dreapta); return rez; } int suma_cifre(int num) { int r; if(num == 0) r = 0; else r = suma_cifre(num/10) + num%10; return r; } int main() { //int v[] = {1,2,3,4,5}; int n = 22105; printf("suma cifrelor este: %d\n", suma_cifre(n)); return 0; }

8. Scrieți un subprogram recursiv pentru implementarea metodei bisectiei. Se va oferi un exemplu de apel.

9. Scrieți un subprogram recursiv care rezolvă problema turnurilor din Hanoi. Se va oferi un exemplu de apel. #include void hanoi(int rez[][2], int *nr_mutari, int n, int tija_1, int tija_2, int tija_3) { //tija_1 este tija initiala if(n == 1) { rez[*nr_mutari][0] = tija_1; rez[*nr_mutari][1] = tija_3; (*nr_mutari)++; } 9

else { hanoi(rez, nr_mutari, n-1, tija_1, tija_3, tija_2); rez[*nr_mutari][0] = tija_1; rez[*nr_mutari][1] = tija_3; (*nr_mutari)++; hanoi(rez, nr_mutari, n-1, tija_2, tija_1, tija_3); } } void main() { int n; scanf("%i", &n); int nr_mutari = 0; int mat[100][2]; hanoi(mat, &nr_mutari, n, 1, 2, 3); for(int i = 0; i < nr_mutari; i++) { printf("%d -> %d\n", mat[i][0], mat[i][1]); } } 10. Să se scrie subprogramul recursiv care determină un număr la o putere (xn), precum și programul apelator. #include #include int putere(int a, int b) { if(b==0) return 1; else if(b==1) return a; else return a*putere(a, b-1); } int main() { int a, b; printf("a="); scanf("%d", &a); printf ("b="); scanf("%d", &b); printf("%d", putere(a, b)); return 0;} Temă: 11. Să se scrie subprogramul recursiv care calculează valoarea unui polinom într-un punct dat, precum și programul apelator. 12. Scrieți un subprogram recursiv care calculează (aranjamente de n luate câte k), precum și programul apelator. 13. Să se scrie subprogramul recursiv care determină rezultatul ridicării unei matrice la o putere dată, precum și programul apelator. 10

Se vor studia ambele metode de scriere a unui subprogram recursiv (metoda reducerii și metoda descompunerii).

11...