Limbajul C. Numere prime, numere prietene, Fibonacci, listarea valorilor unei functii pe un interval

Toate problemele de mai jos sunt enunturi adaptate sau luate ca atare din cartea scrisa de V.Iorga & colaboratorii, "Programare in C/C++. Culegere de probleme", ISBN 973-568-800-X aparuta in 2003.

Toate enunturile reprezinta probleme de programare procedurala.

1. Descompunerile unui numar par ca suma de numere prime. Problema P2_3. 

Teorie: daca n este un numar par, adica n = 2*k iar k e un intreg oarecare,
atunci o cale ar fi determinarea tuturor numerelor prime pana la n, fie m numarul
acestor numere prime. Scazand din n fiecare dintre cele m numere si verificand daca
rezultatul scaderii este tot numar prim, aflam descompunerile cerute de problema.

Codul si printscreen-ul executiei:

#include <stdio.h>

int EstePrim(int n)
{
int i, count = 0;
if(n == 1 || n == 2) return n;
for(i = 1; i <= n; i++)
{
if(n%i) continue;
else count++;
}
if(count > 2) return -1;
else return n;
}

void Descompune(int m)
{
int j, counter = 0;
for(j = 1; j <= m/2; j++)
    // obs: daca vrem toate descompunerile nedistincte, inlocuim m/2 cu m - 1
{
if(EstePrim(j) != -1)
{
if(EstePrim(m - j) != -1)
                    {
                       printf("\n%d = %d + %d", m, j, m - j);
                     counter++;
                    }
}
 }
if(counter)
 printf("\nAu fost gasite %d descompuneri ale lui %d ca suma de numere prime.", counter, m);
}

int main()
{
int n;
puts("Dati un numar natural par si vom afisa descompunerea sa in numere prime.");
scanf("%d", &n);
if(n%2 || n < 0)
{
printf("\nInput eronat!");
return 1;
}
else Descompune(n);
return 0;
}

2. P2_2. Un program de tabelare pe intervale a functiei ln(1 + x^2). Inputul este reprezentat de capetele a si b si de pasul h.

Codul si printsreen-ul:

#include <stdio.h>
#include <math.h>

void Afiseaza(double a, double b, double h)
{
     double y, z;
     //precizia compararii cu zero o setam la 1E-10
     while(b - a - h > 1e-10)
     {
       z = 1 + a*a;
       y = log(z);
       printf("\nln(%.10lf) = %.10lf.", z, y);
       //afisare cu 10 cifre zecimale
       a += h;
     }
     return;
}
     
int main(void)
{
    double a, b, h;
    puts("\nDati capetele unui interval si pasul, separate de virgula. Pasul: min. 1e-10.");
    scanf("%lf, %lf, %lf", &a, &b, &h);
    if(a > b || h < 1e-10 || a + h > b)
    {
         printf("\nInput eronat.");
         return 1;
    }
    printf("\nVom afisa functia ln(1 + x*x) pe intervalul [%.2lf, %.2lf] cu pasul %.2lf.", a, b, h);
    Afiseaza(a, b, h);
    return 0;
}

O verificare a corectitudinii rezultatelor poate fi facuta aici.

3. Numere prietene. Doua numere naturale sunt prietene daca suma divizorilor unuia (exclusiv numarul) este egala cu valoarea celuilalt numar si reciproc. Cerinta problemei P2_1 este scrierea unui program care gaseste astfel de numere intr-un interval specificat.

Codul si printscreen-ul, cu urmatoarea observatie: in intervalul [a, b], unde a si b numere naturale, trebuie efectuata verificarea oricaror 2 perechi de numere, adica este apelata functia VerPrieten (care apeleaza SumaDivizori!) de un numar de "combinari de b - a luate cate 2". Pentru b - a = 1000 se efectueaza 499500 de verificari iar pentru cele 5000 de numere de la 1 la 5000 se efectueza aproape 12,5 milioane de apeluri de functie care apeleaza alta functie, deci afisarea se face pe parcursul a zeci de secunde sau minute, in functie de sistemul de calcul. In intervalul 1 - 1000 a fost gasita o pereche de numere prietene, iar in intervalul 1 - 5000, trei perechi.

La acest link poate fi accesat un "calculator" de combinari si permutari.

#include <stdio.h>

int SumaDivizori(int n)
{
     int i, suma = 0;
     for(i = 1; i <= n/2; i++)
     {
       if(n%i) continue;
       else suma += i;
     }
     return suma;
}

int VerPrieten(int n, int m)
{
    if(SumaDivizori(n) == m && SumaDivizori(m) == n) return 1;
    else return 0;
}

int main(void)
{
    int a, b, i, j;
    puts("\nIntroduceti limitele naturale ale unui interval inchis.\nVom cauta numerele prietene.");
    scanf("%u, %u", &a, &b);
    if(a >= b) return 2;
    for(i = a; i < b; i++)
      for(j = i + 1; j <= b; j++)
      {
         if(VerPrieten(i, j)) printf("\n%d si %d sunt numere prietene.", i, j);
         else continue;
      }
    return 0;
}

Mai multe despre numerele prietene, evident, pe Wiki:-) 

4. Este adaptarea enuntului problemei P2_8. Se introduc numere intregi pozitive si un terminator de sir negativ. Se vor afisa numerele care apartin sirului Fibonacci si pozitia in sir. Numerele Fibonacci, pornind de la 0, sunt 0, 1, 1, 2, 3, 5, 8 etc, conform relatiei recurente n = n - 1 + n - 2. O lista a numerelor Fibonacci pana la o limita introdusa de utilizator este afisata la finalul programului. In domeniul numerelor intregi fara semn pot fi afisate doar primele 48 de numere Fibonacci.

Codul si printscreen-ul:

void VerFibo(unsigned n)

{

     unsigned i = 3, a = 0, b = 1, c = 0;

     if(!n) 

     {

       printf("\n%u este primul numar Fibonacci.", n);

       return;

     }

     while(c <= n)

     {

       c = b + a;

       if(c == n) 

       {

            if(1 == c) printf("\n%u este valoarea celui de-al doilea si al treilea numar Fibonacci.", n);

            else printf("\n%u este al %d-lea numar Fibonacci.", n, i);

            break;

       }

       a = b;

       b = c;

       i++;

     }

}

void Fibo(unsigned n);

int main(void)

{

    unsigned n;

    int num;

    puts("\nIntroduceti numere naturale. Verificam daca sunt Fibonacci.\nOpriti verificarea cu numar negativ.");

    do

    {

      printf("Numarul:");

      scanf("%u", &num);

      _flushall();

      if(num < 0) break;

      VerFibo(num);

    }

    while(1);

    printf("\nVom lista acum primele n numere Fibonacci. n:");

    //Pentru n > 48 se iese din domeniul intregilor fara semn

    scanf("%u", &n);

    Fibo(n);

    return 0;

}

void Fibo(unsigned n)

{

     unsigned a = 0, b = 1, c, i;

     //Calculul numerelor Fibonacci incepe de la al treilea

     if(!n) return;

     else if(n == 1) printf("%u ", a);

     else if(n >= 2) printf("%u %u ", a, b); 

     for(i = 3; i <= n; i++)

     { 

        c = a + b;

        printf("%u ", c);

        a = b;

        b = c;

     }

}