Question

Va rog scrieţi un subprogram care returnează numărul valorilor din intervalul
[a,b] care pot fi scrise ca produs de două numere naturale consecutive.
dacă a=10 și b=25, subprogramul returnează 2 (valorile cu proprietatea cerută
sunt 12, 20 ).(c++)

Answer 1

Sa scriem produsul pentru citeva cifre:
0 si 1 : 0
1 si 2 : 2
2 si 3 : 6
3 si 4 : 12
4 si 5 : 20

Exprimam o formula pentru acest sir: a(n)=n*(n+1)=n²+n

Iar pentru problema noastra trebuie ca pentru o valoare a(n), n sa fie natural, deci trebuie sal exprimam pe n:

a(n)=n²+n
n²+n-a(n)=0

n1=[-1-√(1+4*a(n))]/2, putem sa nu verificam acest caz, deoarece numaratorul va fi negativ, ca prin urmare n1 va fi negativ, ceea ce nu e posibil pentru un sir.

n2=[-1+√(1+4*a(n))]/2.

Obtinem unica formula pentru a afla pe n, iar din cele spuse mai sus trebuie sa verificam daca acest numar va fi natural.

Subprogramul:

int value(int a, int b)
{
    int r=0;
    for(int i=a;i<=b;i++)
        if(int((-1+sqrt(1+4*i))/2)==(-1+sqrt(1+4*i))/2)
            r++;
    return r;
}

Answer 2

De asemenea, ai putea reduce numarul de apeluri catre std::sqrt (fapt ce nu este indicat, mai ales cand o apelezi de {b - a + 1} ori) folosindu-te doar de capete.

int f(int a, int b)
{
    int epsilon = std::round(std::sqrt(b + 1));
    a = std::round(std::sqrt(a));
    b = std::round(std::sqrt(b));

    return b - a + (epsilon != b);
}

Asadar, doar trei apeluri catre std::sqrt sunt folosite, nefiind nevoie de a parcurge deloc intervalul propriu-zis.