4.15. Apel prin valoare si apel prin referinta

2019/02/20 in Programare in C

In limbajul C, la apelul unei functii, fiecarui parametru formal i se atribuie valoarea parametrului efectiv care-i corespunde. Deci, la apelul unei functii se transfera valorile parametrilor efectivi. Din aceasta cauza, se spune ca apelul este prin valoare (call by value, eng.).

Exemplu:

Fie functia factorial de prototip:

double factorial(int n);

definita la exercitiul 4.27. Functia factorial si folosita in Programul 081. La apelul:

fact = factorial(10);

se atribuie parametrului formal n valoarea 10. Aceasta atribuire se face inainte de executia primei instructiuni a functiei factorial. De aceea, prin acest apel functia factorial calculeaza pe 10!.

In unele limbaje de programare, la apel nu se transfera valorile parametrilor efectivi, ci adresele acestor valori. In acest caz, se spune ca apelul este prin referinta (call by reference, eng.).

Intre cele doua tipuri exista o diferenta esentiala si anume:

Asa se intampla, de exemplu, in cazul limbajului FORTRAN, unde apelul este prin referinta.

De aici rezulta ca la apelul prin valoare transferul datelor este unidirectional, adica valorile se transfera numai de la functia care face apelul catre functia apelata, nu si invers.

Exista situatii cand se doreste ca functia apelata sa modifice valorile parametrilor efectivi. Unele limbaje permit ambele tipuri de apeluri. Asa este, de exemplu, cazul cazul limbajului Pascal. Parametrii declarati in Pascal prin var se transfera prin referinta.

In limbajul C++, spre deosebire de limbajul C, exista ambele apeluri, ca si in limbajul Pascal.

Apelul prin valoare este util in cazul in care functia apelata nu trebuie sa modifice valorile parametrilor efectivi, deoarece in felul acesta parametrii efectivi sunt protejati fata de eventualele modificari care ar putea aparea din greseala.

Aceasta inseamna ca o functie poate sa modifice parametrii ei formali fara riscul ca prin modificarea respectiva sa influenteze valorile parametrilor efectivi corespunzatori.

In limbajul C, un parametru efectiv poate fi numele unui tablou. De exemplu, fie o functie, pe care o numim sum si care insumeaza elelntele unui tablou de tip int. Aceasta functie are doi parametri:

tab este numele tabloului a caror elemente se insumeaza;
n este numarul elementelor tabloului.

Ea returneaza suma:

tab[0] + tab[1] +...+ tab[n]

Conform celor spuse mai sus, functia are urmatorul antet:

int sum(int tab[], int n)

Amintim ca daca un parametru efectiv este un nume de tablou unidimensional, atunci parametrul formal corespunzator se poate declara fara a indica, intre parantezele patrate, limita superioara a indicelui sau.

Daca a este un tablou declarat ca mai jos:

int tab[10];

atunci pentru a insuma elementele tabloului respectiv vom putea folosi apelul:

x = sum(a,10);

Deoarece a este numele unui tablou, a are ca valoare adresa primului sau element, adica adresa lui a[0]. Deoarece apelul este prin valoare, parametrul tab primeste valoarea lui a deci tab are si el ca valoare adresa lui a[0]. Rezulta ca tab[0], tab[1], ..., tab[9] reprezinta aceleasi elemente ca si a[0], a[1], ..., a[9]. De aceea, corpul functiei sum referindu-se la elementele lui tab, se refera de fapt la elementele lui a:

for(s=0; n>0; n--)
  s += tab[n-1];

Se observa ca, in acest caz, desi apelul s-a facut prin valoare (valoarea lui a s-a atribuit lui tab), s-a realizat un apel prin referinta, deoarece valoarea atribuita parametrului formal este o adresa.

In acest caz, functia apelata poate modifica elementele tabloului al carui nume s-a folosit ca parametru efectiv.

Intr-adevar, in exemplul de mai sus, atribuirea:

tab[3] = 100;

scrisa in corpul functiei sum are ca efect atribuirea valorii 100 elementului a[3].

In concluzie, in limbajul C, apelul este prin valoare. Acest apel devine prin referinta in cazul in care parametrul efectiv este numele unui tablou.

Ulterior se va vedea ca apelul prin referinta poate fi realizat in limbajul C si in cazul variabilelor simple, folosind pointeri.

Exercitii:

4.35. Sa se scrie o functie care calculeaza valoarea unui polinom folosind schema lui Horner.

Parametrii functiei sunt:

c tabloul cu coeficientii polinomului - este de tip long double;
n gradul polinomului - este de tip int;
z valoarea variabilei - este de tip long double.

Tabloul c contine coeficientii polinomului in ordine descrescatoare a puterilor lui x:

c[0] este coeficientul lui xn;
c[1] este coeficientul lui xn-1;
...
c[n-1] este coeficientul lui x;
c[n] este termenul liber.

Se stie ca un polinom p(x) cu coeficientii c[0], c[1], ..., c[n], in ordine descrescatoare a puterilor lui x, se poate pune sub forma:

p(x)=((...((c[0]*x + c[1])*x + c[2]*)x +...+ c[n-2])*x + c[n-1])*x + c[n]

Fie:

s = c[0]

Se observa ca paranteza cea mai interioara are ca valoare, valoarea expresiei:

s*x + c[1]

Sa atribuim lui s valoarea acestei expresii:

s = s*x + c[1]

In continuare trebuie sa se evalueze valoarea expresiei:

s*x + c[2]

Atribuim din nou lui s valoarea acestei expresii:

s = s*x + c[2]

In general, la al i-lea pas se evalueaza expresia:

s*x + c[i]

si apoi valoarea ei se atribuie lui s:

s = s*x + c[i]

Deci calculul valorii polinomului p(x) revine la ecuatia repetata a atribuirii:

s = s*x + c[i]

pentru i = 1, 2, ..., n, valoarea initiala a lui s fiind c[0]. Aceasta conduce la instructiunea for:

for(s = c[0], i = 1; i <= n; i++)
  s = s*x + c[i];
float polinom(float x, int n, float c[])
{
    float s;
    int i;
	
    for(s = c[0], i = 1; i <= n; i++)
      s = s*x + c[i];
    return s;
}

4.36. Sa se scrie un program care realizeaza urmatoarele:

a[0] este coeficientul lui xn, a[1] este coeficientul lui xn-1 etc.

#include <stdio.h>
#include <stdlib.h>
#include "FUNCTIA085.C"

#define MAXGRAD 100

main()
{
    float x, a[MAXGRAD+1];
    int i, n;
    char t[255];

    /*citeste pe x*/
    do {
        printf("valoarea lui x: ");
        if(gets(t) == NULL) {
            printf("s-a tastat EOF\n");
            exit(1);
        }
        if(sscanf(t, "%f", &x) == 1)
            break;
        printf("nu s-a tastat un numar\n");
    } while(1);

    /*citeste pe n*/
    do {
        printf("valoarea lui n: ");
        if(gets(t) == NULL) {
            printf("s-a tastat EOF\n");
            exit(1);
        }
        if(sscanf(t, "%d", &n) == 1 && n >= 0 && n <= 100)
            break;
        printf("nu s-a tastat un intreg din intervalul [0, 100]\n");
    } while(1);

    /*citeste coeficientii polinomului*/
    for(i = 0; i <= n; i++)
        do {
            printf("coeficientul a[%d]: ", i);
            if(gets(t) == NULL) {
                printf("s-a tastat EOF\n");
                exit(1);
            }
            if(sscanf(t, "%f", &a[i]) == 1)
                break;
            printf("nu s-a tastat un numar\n");
        } while(1);

    printf("x = %g\tgrad = %d\tval pol = %g\n", x, n, polinom(x, n, a));
}

4.37. Sa se scrie o functie care citeste cel mult n numere si le pastreaza in tabloul ndtab care este de tip double. Functia returneaza numarul numerelor citite.

int ndcit(int n, double ndtab[])
{
    int i;
    double d;
    char t[255];
	
    for(i = 0; i <= n; i++) {
      printf("elementul[%d] = ", i);
	  if (gets(t) == NULL)
	    return i;
	  if (sscanf(t, "%lf", &d) != 1)
	    break;
	  ndtab[i] = d;
    }
    return i;
}

4.38. Sa se scrie o functie care citeste componentele unui vector precedate de numarul lor. Functia returneaza numarul componentelor vectorului respectiv.

Aceasta functie foloseste functia definita la exercitiul anterior - FUNCTIA086A.C.

int dvcit(int nmax, double dvector[])
{
    int i, n;
    char t[255];
	
    do {
      printf("elementul[%d] = ", i);
	  if (gets(t) == NULL) {
	    printf("s-a tastat EOF\n");
	    exit(1);
	  }
	  if (sscanf(t, "%lf", &n) == 1 && n > 0 && n <= nmax)
	    break;
	  printf("nu s-a tastat un intreg din intervalul [1, %d]\n", nmax);
    } while(1);
    if ((i = ndcit(n, dvector)) != n) {
      printf("nu s-a reusit citirea celor n = %d componente\n", n);
      printf("s-au citit numai %d componente\n", i);
    }
    return i;
}

4.39. Sa se scrie un program care citeste componentele vectorilor x si y, calculeaza si afiseaza produsul lor scalar.

Componentele celor doi vectori se tasteaza astfel:

Programul foloseste functia definita la exercitiul anterior - FUNCTIA086B.C.

#include <stdio.h>
#include <stdlib.h>
#include "FUNCTIA086A.C"
#include "FUNCTIA086B.C"

#define MAX 1000

main()
{
    int i, n;
    double x[MAX], y[MAX], s;

    /*citeste pe n si componentele vectorului x*/
    n = dvcit(MAX, x);

    /*citeste componentele vectorului y*/
    if (ndcit(n, y) != n) {
        printf("nu sunt n = %d componente pentru y\n", n);
        exit(1);
    }

    /*calculeaza produsul scalar*/
    s = 0.0;
    for (i=0; i <= n; i++)
      s += x[i]*y[i];
    printf("(x, y) = %g\n", s);
}

4.40. Sa se scrie o functie care sorteaza in ordine crescatoare elementele unui tablou de tip float.

Spunem despre un tablou tab, de elemente numerice, ca este sortat crescator (descrescator), daca elementele lui satisfac relatia:

tab[i] <= (>=) tab[i+1]

pentru i = 0, 1, 2, ..., n-2, unde:

n este numarul elementelor tabloului tab;

Functia care realizeaza sortarea are doi parametri:

tab tabloul de sortat;
n este numarul elementelor tabloului.

Exista mai multe metode de sortare, care difera intre ele prin ordinul de marime al pasilor care trebuie necesari pentru a realiza sortarea.

Cele mai simple metode sunt si cele mai putin eficiente si necesita un numar de pasi de ordinul n*n, n fiind numarul elementelor de sortat. Prezentam mai jos o astfel de metoda, care este cunoscuta sub denumirea de metoda bulelor (eng. bubble sort).

Ea consta in urmatoarele:

Se compara primele elemente ale tabloului de sortat si daca nu sunt in ordinea ceruta (de ex. crescatoare), se permuta intre ele. Apoi se compara elementul al doilea cu cel de-al treilea si se procedeaza la fel. In general, se compara doua elemente invecinate, sa zicem al i-lea cu al i+1-lea si daca nu sunt in ordinea ceruta, atunci ele se permuta. Se procedeaza in acest fel cu toate perechile de elemente invecinate ale tabloului de sortat. Apoi procesul se reia de la inceput. El se intrerupe cand se constata ca toate elementele invecinate ale sirului sunt in ordinea ceruta (in cazul de fata, crescatoare).

Exemplu:

Fie sirul de numere:

8, 3, 9, 5, 4, 7

pe care dorim sa il ordonam crescator.

Prima parcurgere a sirului:

8 3 9 5 4 7 - sirul initial;
3 8 9 5 4 7 - dupa permutarea lui 8 cu 3;
3 8 5 9 4 7 - dupa permutarea lui 9 cu 5;
3 8 5 4 9 7 - dupa permutarea lui 9 cu 4;
3 8 5 4 7 9 - dupa permutarea lui 9 cu 7;

A doua parcurgere a sirului:

3 8 5 4 7 9 - sirul dupa prima parcurgere;
3 5 8 4 7 9 - dupa permutarea lui 8 cu 5;
3 5 4 8 7 9 - dupa permutarea lui 8 cu 4;
3 5 4 7 8 9 - dupa permutarea lui 8 cu 7;

A treia parcurgere a sirului:

3 5 4 7 8 9 - sirul dupa a doua parcurgere;
3 4 5 7 8 9 - dupa permutarea lui 5 cu 4;

La a patra parcurgere a sirului nu se mai face nicio permutare deoarece perechile de elemente vecine sunt in ordine crescatoare, deci sirul este ordonat crescator.

O proprietate a acestei metode este aceea ca la fiecare parcurgere a sirului de numere, cel putin un element ajunge sa-si ocupe pozitia sa finala in conformitate cu ordonarea avuta in vedere. Astfel, dupa prima parcurgere elementul ajuns pe ultimul loc nu va mai fi permutat, ocupandu-si locul final. In exemplul de mai sus 9 a ajuns pe ultimul loc dupa prima permutare, care este si pozitia lui finala. Acelasi lucru se intampla cu 8 dupa a doua parcurgere a sirului. Intamplator, si 7 a ajuns in pozitia sa finala dupa a doua parcurgere s.a.m.d.

Daca se ordoneaza crescator un tablou de numere, atunci dupa prima parcurgere a elementelor lui, elementul maxim va avea indicele cel mai mare . Dupa cea de-a doua parcurgere, maximul dintre elementele ramase (fara a lua in considerare ultimul element) va ocupa penultima pozitie din tablou s.a.m.d.

Se obisnuieste sa se spuna ca elementele urca in pozitiile lor la fel ca si bulele de aer in apa care fierbe, de unde si denumirea metodei.

Functia de mai jos contine un ciclu pentru parcurgerea elementelor tabloului tab. In acest ciclu se compara elementele vecine curente si daca acestea nu sunt in ordine crescatoare ele se permuta. Deoarece dupa o parcurgere a sirului se reincepe parcurgerea lui, acest ciclu este continut intr-un altul care realizeaza executia repetata a ciclului de parcurgere a sirului. Se ajunge la urmatorii pasi:

  1. Cat timp sirul nu este sortat se executa pasul 2. Altfel se intrerupe procesul de sortare.
  2. Se parcurge sirul si se permuta perechile de elemente invecinate care sunt in ordine descrescatoare. Pasul 2 se realizeaza printr-un ciclu for de forma:

    for (i = 0; i < n-1; i++)
  if (tab[i] >= tab[i+1]) {
    t = tab[i];
    tab[i] = tab[i+1];
    tab[i+1] = t;
}
    Acest ciclu trebuie repetat atat timp cat elementele tabloului tab nu sunt in ordine crescatoare. Problema care se pune in legatura cu executia repetata a acestui ciclu for este aceea de a sti cand s-a ajuns in situatia in care elementele tabloului tab sunt in ordine crescatoare. Observam ca in acest caz ciclul for se executa fara a mai face permutari. Deci, tabloul este sortat cand ciclul for il parcurge fara a se mai face permutari. Acest fapt poate fi detectat folosind o variabila, fie ea ind, care se anuleaza inaintea fiecarei executii a ciclului for si se seteaza la valoarea 1 in cazul in care ciclul respectiv face o permutare. In felul acesta, variabila ind are valoarea 1 dupa executia ciclului for daca acesta a facut cel putin o permutare si zero in caz contrar.

    In concluzie, variabila ind are valoarea 0 cand sirul este sortat si 1 in caz contrar. Variabila ind se gestioneaza astfel:
    • initial ind are valoarea 1;
    • inainte de instructiunea for, ind se face egal cu 0;
    • in secventa de permutare a doua elemente invecinate, ind se face egal cu 1.
    Se obtine secventa:

    ind = 0;
for (i = 0; i < n-1; i++)
  if (tab[i] > tab[i+1]) {
    t = tab[i];
    tab[i] = tab[i+1];
    tab[i+1] = t;
    ind = 1;
}
    Aceasta secventa se executa repetat atata timp cat ind nu este egal cu 0, adica tabloul nu este sortat. In acest scop se foloseste un ciclu while care are ca si corp secventa de mai sus:

    while(ind) {
  ind = 0;
  for (....
}
void ordcresc(float tab[], int n)
{
    int i, ind;
    float t;
	
    ind = 1;
    while(ind) {
      ind = 0;
      for (i = 0; i < n-1; i++)
        if (tab[i] > tab[i+1]) {
          t = tab[i];
          tab[i] = tab[i+1];
          tab[i+1] = t;
          ind = 1;
        }
    }
}

4.41. Sa se scrie un program care citeste un sir de numere separate prin caractere albe si le afiseaza in ordine crescatoare. Dupa ultimul numar se tasteaza un caracter nenumeric. Se presupune ca la intrare exista cel putin 2 numere si cel mult 1000.

Numerele se citesc apeland functia ndcit definita la exercitiul 4.37. Sortarea lor in ordine crescatoare se realizeaza folosind functia ordcresc (FUNCTIA087.C).

#include <stdio.h>
#include <stdlib.h>
#include <conio.h>
#include "FUNCTIA086A.C"
#include "FUNCTIA087.C"

#define MAX 1000

main()
{
    float tnr[MAX];
    int n, i;

    if ((n = ndcit(MAX, tnr)) < 2) {
        printf("s-au citit mai putin de doua numere\n");
        exit(1);
    }
    ordcresc(tnr,n);
    for (i = 0; i < n; i++) {
        printf("tnr[%d] = %g\n", i, tnr[i]);
        if ((i+1)%23 == 0) {
            printf("actionati o tasta pentru a continua\n");
            getch();
        }
    }
}

4.42. Sa se scrie o functie care cauta un element de valoare data a intr-un tablou numeric sortat crescator. Functia returneaza indicele unui element de valoare egala sau -1 in cazul in care nu exista un astfel de element.

Elementul de valoare a poate fi gasit comparand fiecare element al tabloului cu a pana cand se gaseste un element egal cu a. In cazul in care nu exista un astfel de element in tablou, compararea se face cu toate elementele tabloului pentru a putea constata ca nu exista elementul cautat. O astfel de metoda de cautare, numita cautare liniara, desi foarte simpla, necesita un numar relativ mare de comparari.

In cazul tablourilor sortate se poate utiliza o metoda de cautare mult mai rapida, numita metoda cautarii binare. Aceasta consta in urmatoarele:

Fie tab tabloul in care se cauta un element de valoare a si care este sortat crescator. Deci:

tab[0] <= tab[1] <= ... <= tab[n-1]
  1. Se compara elementul din mijlocul tabloului (de indice [(n-1) / 2]) cu a.
  2. Daca acesta are valoarea egala cu a, inseamna ca s-a gasit un element de valoare a si se returneaza indicele lui. Altfel se continua cu punctul 3.
  3. Daca elementul din mijloc este diferit de a, atunci, din cauza ca tabloul este sortat, elementul cautat este fie in prima jumatate a tabloului, fie in a doua jumatate si se poate stabili exact in care jumatate urmeaza a se face cautarea si anume:
    • daca tab[(n-1)/2] > a, atunci elementul cautat se poate afla numai in prima jumatate a tabloului tab si cautarea se va face in subtabloul: 
      tab[0] <= tab[1] <= ... <= tab[(n-1)/2 - 1]
    • daca tab[(n-1)/2] < a, atunci elementul cautat se poate afla numai a doua jumatate a tabloului tab si cautarea se va face in subtabloul: 
      tab[(n-1)/2 + 1] <= tab[(n-1)/2 + 2] <= ... <= tab[n-1]
  4. Dupa determinarea subtabloului in care trebuie sa se faca cautarea se procedeaza in mod analog, adica se detrmina elementul aflat la mijlocul acestui subtablou si apoi se procedeaza ca la pasii 2 si 3 si asa mai departe.

Exemplu:

Fie tabloul tab de 10 elemente care au valorile:

tab[0] = 3 tab[1] = 4 tab[2] = 7
tab[3] = 10 tab[4] = 13 tab[5] = 20
tab[6] = 21 tab[7] = 35 tab[8] = 41
tab[9] = 48

Se cere indicele elementului de valoare 20.

Avem: n = 10 si [(n-1)/2] = [9/2] = 4.

Se compara tab[4] cu 20: tab[4] = 13 < 20, deci pentru cautarea urmatoare se va alege jumatatea a doua a tabloului, de la tab[5] la tab[9].

Elementul din mijlocul acestui tablou este de indice [(5+9)/2] = 7. Avem: tab[7] = 35 > 20, deci se va face cautarea in prima jumatate a acestui subtablou, adica de la tab[5] la tab[6].

In continuare se alege elementul de indice [(5+6)/2] = 5, deci tab[5]. Cum tab[5] = 20, rezulta ca in acest moment a fost gasit elementul cautat si se revine din functie cu valoarea 5 (indicele elementului cautat).

Pentru determinarea, la fiecare pas, a subtabloului in care se va face cautarea se vor folosi doua variabile, inf si sup, prima avand ca valoare indicele primului element al subtabloului curent selectat, iar cea de a doua indicele ultimului sau element. Pasii procesului de cautare vor fi:

  1. inf = 0 - indicele primului element al tabloului;
  2. sup = n-1 - indicele ultimului element al tabloului;
  3. i = (inf + sup) / 2 - indicele elementului din mijlocul tabloului;
  4. Daca tab[i] = a, cautarea se termina si se returneaza valoarea lui i. Altfel se continua cu pasul 5.
  5. Daca tab[i] > a, atunci sup = i-1
    Limita superioara se coboara la valoarea i-1 pentru a selecta prima jumatate a tabloului.
    Se reia de la punctul 3.

    Altfel, inseamna ca tab[i] < a si atunci inf = i+1
    Limita inferioara creste la valoarea i+1 pentru a selecta jumatatea a doua a tabloului.
    Se reia de la punctul 3.

Acest proces se desfasoara corect in cazul in care, in tablou, exista cel putin un element de valoare a. In caz contrar, el continua indefinit. Se observa ca la pasul 5 de mai sus, una dintre limite se modifica si anume, daca se modifica limita superioara sup, atunci aceasta descreste, iar daca se modifica limita inferioara inf, atunci aceasta creste. Initial inf <= sup

Deoarece la fiecare pas la care nu s-a gasit elementul cautat, una dintre variabilele inf sau sup se modifica si inf creste, iar sup descreste, rezulta ca inegalitatea de mai sus nu va mai fi satisfacuta dupa un numar finit de pasi, adica se ajunge sa fie satisfacuta relatia: inf > sup.

Aceasta se intampla cand in tablou nu exista un element de valoare a. Deci procesul de calcul indicat mai sus se intrerupe fie la gasirea elementului cautat, fie cand se ajunge ca inf sa-l depaseasca pe sup.

Sa reluam exemplul de mai sus pentru a = 22. Si in acest caz se va ajunge la subtabloul: tab[5] = 20, tab[6] = 21 si inf = 5, sup = 6.

La pasul 3 se determina: i = [(5+6) / 2] = 5.

Apoi se ajunge la pasul 5, deoarece tab[5] != 22.

Cum tab[5] = 20 < 22, rezulta ca inf = i+1 = 5+1 = 6. Se revine la pasul 3 unde se atribuie lui i valoarea: i = [(inf + sup) / 2] = [(6 + 6) / 2] = 6.

Se ajunge din nou la pasul 5, deoarece tab[6] != 22.

Cum tab[6] = 21 < 22, se modifica din nou inf: inf = i+1 = 7.

In acest moment, inf > sup si deci procesul de calcul se intrerupe, concluzia fiind ca tabloul respectiv nu contine un element de valoare a.

int dcautbin(double tab[], int n, double a)

/* cauta in tab un element de valoare egala cu a; 
returneaza indicele elementului respectiv sau -1, 
daca nu exista un astfel de element*/

{
    int i, inf, sup;
	
    inf = 0;
    sup = n-1;
    while(inf <= sup) {
      i = (inf + sup) / 2;
      if (tab[i] == a)
          return i;
      if (tab[i] > a)
          sup = i-1;
      else
          inf = i-1;
    }
	
    /*se ajunge aici cand inf > sup, ceea ce inseamna ca in tab 
    nu exista un element de valoare a*/
	
    return -1;
}

4.43. Sa se scrie un program care citeste un sir de intregi separati prin caractere albe si-i afiseaza pe cei care sunt numere prime si sunt in intervalul [0, 1000].

Dupa ultimul numar se tasteaza un caracter nenumeric.

Acest program genereaza la inceput un tablou cu numere prime. In acest scop se realizeaza o functie pe care o numim prim. Ea are doi parametri: tprim si n. Primul parametru este un tablou de tip int, ale carui elemente sunt numerele prime care nu-l depasesc pe n:

tprim[0]=1, tprim[1]=2, tprim[2]=3, tprim[3]=5 etc.

El este sortat crescator si ultimul element tprim[m] este cel mai mare numar prim care nu il depaseste pe n:

tprim[m] <= n

Functia prim returneaza numarul numerelor prime pastrate in tprim (adica m + 1).

Primele trei numere prime (1, 2 si 3) se pastreaza in mod automat, daca n > 3.

Pentru a determina ca un numar m > 2 este prim, este suficient sa stabilim ca el nu este divizibil cu niciunul din numerele prime mai mici decat el. De fapt, este suficient sa testam divizibilitatea lui cu numerele prime ale caror patrate nu il depasesc. De asemenea, vom observa ca singurul numar prim par este 2. Deci un numar m > 2 este prim daca:

  1. m este impar;
  2. m nu se divide cu niciunul din numerele prime consecutive p1, p2, ..., pk ale caror patrate nu-l depasesc pa m (p1 = 3); Deci pk este cel mai mare numar prim pentru care pk2 < m.

Daca tabloul contine deja i numere prime:

tprim[0], tprim[1], ..., tprim[i-1] (unde i > 2)

atunci pentru a determina urmatorul numar prim vom proceda astfel:

  1. tprim[i] = tprim[i-1] + 2, deoarece numerele prime mai mari decat doi nu sunt pare;
  2. se testeaza daca tprim[i] este prim; in acest scop se cauta daca exista printre numerele prime:
    tprim[2], tprim[3],... vreunul care sa-l divida pe trim[i]. Asa cum am aratat mai sus, nu trebuie incercate toate elementele tabloului tab, ci numai acele elemenete care satisfac relatia (1):

    tprim[j]*tprim[j] <= tprim[i] (unde j = 2,3, ...)
    In cazul in care exista un element care satisface atat relatia (1) cat si relatia (2):

    tprim[i] % tprim[j] == 0
    numarul tprim[i] nu este prim si se va trece la pasul 3 de mai jos. Altfel tab[i] este prim, se mareste i cu o unitate si procesul de calcul se reia de la punctul 1.
  3. Cum tprim[i] nu este prim, acesta se mareste cu 2 si procesul se reia de la punctul 2.

Procesul de calcul de mai sus se continua atata timp cat tprim[i] <= n.

Dupa generarea numerelor prime, programul citeste un intreg si daca acesta apartine intervalului [0, 1000], il cauta in tabela de numere prime. Apoi se afiseaza numarul respectiv insotit de un mesaj corespunzator. Dupa afisare se revine la citirea numarului urmator cu care se procedeaza analog. Executia programului se intrerupe la intalnirea unui caracter care nu apartine unui intreg.

Cautarea numarului citit in tabloul de numere prime se face prin metoda cautarii binare. In acest scop se utilizeaza o functie asemanatoare cu functia dcautbin definita in exercitiul precedent. In acest caz se va folosi functia icautbin. Diferenta intre cele doua functii consta in aceea ca dcautbin cauta o valoare de tip double intr-un tablou de tip double, iar icautbin cauta o valoare de tip int intr-un tablou de tip int.

#include <stdio.h>
#include <stdlib.h>

#define MAX 1000

int icautbin(int tab[], int n, int a)

/* cauta in tab un element de valoare egala cu a;
returneaza indicele elementului respectiv sau -1,
daca nu exista un astfel de element */

{
  int i, inf, sup;

  inf = 0;
  sup = n-1;
  while (inf <= sup) {
    i = (inf + sup) / 2;
    if (tab[i] == a)
      return i;
    if (tab[i] > a)
      sup = i-1;
    else
      inf = i+1;
  }
return -1;
}

int prim(int tprim[], int n)

/* pastreaza in tprim numerele prime care nu il depasesc pe n */

{
  int i, j, k;

  tprim[0] = 1;
  if (n <= 1)
    return 1;
  tprim[1] = 2;
  if (n <= 2)
    return 2;
  tprim[2] = 3;
  if (n <= 3)
    return 3;
  tprim[3] = 5;
  i = 3;
  
  while (tprim[i] <= n) {
  
/* se cauta existenta unui divizor prim >= 3 pentru tprim[i] */

    j = 2;
    while ((k=tprim[j]*tprim[j]) < tprim[i] && tprim[i] % tprim[j])
	
/* ciclul continua atat timp cat tprim[j]*tprim[j] < tprim[i] 
si restul impartirii lui tprim[i] la tprim[j] este diferit de zero */

      j++;
	  
/* ciclul while continua se termina cand cel putin una din 
conditiile de mai sus nu este adevarata */

    if (k > tprim[i]) {
	
/* tprim[i] este prim deoarece nu exista un divizor prim a lui 
tprim[i] al carui patrat sa fie mai mic sau egal cu tprim[i] */

      i++;
      tprim[i] = tprim[i-1] + 2;
	
/* tprim[i-1] fiind prim, urmatorul numar prim va fi cel putin 
cu 2 mai mare decat el */

	}
	else
	
/* tprim[i] nu este prim deoarece s-a determinat un 
j asa incat
tprim[j]*tprim[j] = tprim[i]
sau
restul impartirii lui tprim[i] la tprim[j] este zero;
in ambele cazuri tpri[i] nu este prim;
se mareste cu 2 */

      tprim[i] += 2;
  }
return i;
}

main()
{
    int nrprime[MAX];
    int nrcrt;
    int n;
	
    n = prim(nrprime, MAX);
	
/* n este numarul numerelor prime care nu depasesc pe 1000 */	

    do {
        printf("Tastati un numar intreg de cel mult 3 cifre: ");
        if (scanf("%d", &nrcrt) != 1)
          exit(0);
        if (nrcrt == 1 || nrcrt == 2 || nrcrt == 3) {
          printf("%d este un numar prim din intervalul [0, 1000]\n", nrcrt);
          continue;
        }
        if (nrcrt > 3 && nrcrt < 1000 && icautbin(nrprime, n, nrcrt) != -1)
          printf("%d este un numar prim din intervalul [0, 1000]\n", nrcrt);
        else
          printf("%d nu este un numar prim din intervalul [0, 1000]\n", nrcrt);
    } while(1);
}

Observatie:

Conditia:

tprim[j]*tprim[j] < tprim[i]

poate fi inlocuita cu echivalenta ei:

tprim[j] < sqrt(tprim[i])

care este mai eficienta pentru numere relativ mari, daca se calculeaza radacina patrata in afara ciclului while interior:

...
while (tprim[i] <= n) {
j = 2;
k = sqrt(tprim[i]);
while (tprim[j] < k && tprim[i] % tprim[j])
  j++;
  if (tprim[j] > k) {
  ...
}

5. Clase de memorie