O Tema

[TheL10n]

Sal, am primit o tema pt acasa cica de gandire in care trebuie sa fac urmatoarele: Se citesc 2 valori intregi, pozitive.Sa se calculeze urmatoarele: -suma valoriloe din intervalul celor doua valori
-sa se afiseze elementele prime din intervalul dat
Mentionez ca programul trebuie scris in C (eu folosesc Visual C++2005 Express Edition ), daca mi-ati da cateva indicatii v-as fi recunoscator

[SoboLAN]

Nu e asa greu. Uite ce rezolvari mi-au venit prima oara in minte:

Code: Select all

    #include <iostream>
    using namespace std;

    short a,b,s=0;

    void suma_interval ()
    {
        for (short x=a+1; x<b; x++) s+=x;
        cout << s << endl;
    }

    void elemente_prime ()
    {
         bool prim;
         for (short i=a; i<=b; i++)
         {
             prim=true;
             for (short j=2; j<=i/2; j++)
                 if (i%j==0) prim=false;
             if (prim && i!=1) cout << i << " ";
         }
         cout << endl;
    }
         
         
    int main ()
    {
        do
        {
             cout << "a="; cin >> a;
             cout << "b="; cin >> b;
        } while (a>b);
        suma_interval ();
        elemente_prime ();
        system("Pause");
        return 0;
    }

PS: La prima cerinta am considerat interval deschis si la a doua interval inchis.

Sunt sigur ca pot scrie un program mai eficient de atat, dar l-am facut in graba. Macar functioneaza. Bafta.

Later Edit: Daca nu intelegi ceva, poti intreba linistit.

[Yeti]

Despre eficienta

Code: Select all

 void suma_interval ()
    {
        for (short x=a+1; x<b; x++) s+=x;
        cout << s << endl;
    }

Pai ce ar fii sa folosim si cunostintele de matematica ? deci atunci in locul forului trebuie atat :

Code: Select all

s= (b-a)*a+(b-a)(b-a+1)/2;

Iar la a doua puteai sa folosesti un sqrt() ca e de ajuns. Deasemnea daca afla ca pirm=false; pune dupa ala un break ca sa nu se mai oboseasca la restul.
La fel astpet intrebarile

[whiskey]

Code: Select all

s= (b-a)*a+(b-a)(b-a+1)/2;

E gresit, daca intervalul e deschis.
Corect e:

Code: Select all

s = (b - a - 1) * (a + b) / 2;

Apropo de viteza: am impresia ca while e mai rapid decat for (in unele limbaje, nu stiu daca si in C/C++ e la fel). Dar aici nu are importanta.

[SoboLAN]

Foarte bune sfaturile, Yeti. Folosind codul urmator am obtinut cea mai buna viteza pentru a=1 si b=10.000 (interval suficient de mare pentru a simti vreo diferenta):

Code: Select all

#include <math.h>
#include <iostream>
using namespace std;

unsigned short a,b,s = 0;

void suma_interval ()
{
     unsigned short x = a + 1;
     while (x < b) s += x++;
     cout << s << endl;
}

void elemente_prime ()
{
     bool prim;
     for (unsigned short i = a; i <= b; i++)
     {
         prim = true;
         for (unsigned short j = 2; j <= sqrt(i); j++)
             if (i % j == 0) 
             { 
                prim = false; 
                break; 
             }
             if (prim && i != 1) cout << i << " ";
     }
     cout << endl;
}
         
int main ()
{
    do
    {
         cout << "a="; cin >> a;
         cout << "b="; cin >> b;
    } while (a > b);
    suma_interval ();
    elemente_prime ();
    system("Pause");
    return 0;
}

La prima cerinta poate ramane asa, oricum nu castigi mai mult de cateva milisecunde, irelevant in cazul asta.

Apropo de viteza: exista vreun tool cu care poti masura in cat timp e executat un program ?

Si inca ceva: Imi puteti explica de ce functioneaza atunci cand scrii ? :

Code: Select all

s = (b - a - 1) * (a + b) / 2;

[Yeti]

Code: Select all

s= (b-a)*a+(b-a)(b-a+1)/2;

E gresit, daca intervalul e deschis.
Corect e:

Code: Select all

s = (b - a - 1) * (a + b) / 2;

Apropo de viteza: am impresia ca while e mai rapid decat for (in unele limbaje, nu stiu daca si in C/C++ e la fel). Dar aici nu are importanta.

Pai uite un exemplu:
Interval 6 9 :

deci care e rezultatul: 7+8 ..... adica 6+1+6+2 .... deci iese 6*(9-6-1) + 1+2 = 6 * (9-6-1) + (9-6-1)(9-6)/2.
Adica pe general s=(b-a-1)a +(b-a-1)(b-a)/2;
In caz ca e deschis intervalul ramane - la bold , ira daca e inchis este +.



SI da asta e mult mai eficient.
Sa vedem in while executa codul acela de b-a ori.
La mine face o sinura adunare si doua inmultiri. Deci ?


Intrebarea ta Sobolan nu il inteleg

[whiskey]

Si inca ceva: Imi puteti explica de ce functioneaza atunci cand scrii ? :

Code: Select all

s = (b - a - 1) * (a + b) / 2;

Magic
Suma primelor n numere e n(n + 1) / 2.
Intr-un interval (a, b) te intereseaza suma numerelor a + 1, a + 2, a + 3, ..., a + n, unde n = b - a - 1 (adica numarul de numere din intervalul (a, b)). Asadar:

Code: Select all

(a + 1) + (a + 2) + (a + 3) + ... + (a + n) =
na + 1 + 2 + 3 + ... + n =
na + n(n + 1) / 2 =
n (a + (n + 1) / 2) = 
(b - a - 1)(a + (b - a) / 2) =
(b - a - 1)(2a + b - a) / 2 =
(b - a - 1)(a + b) / 2

Yeti:
Tu zici ca s = (b-a)*a+(b-a)(b-a+1)/2;
a = 11; b = 15; deci s = 12 + 13 + 14 = 25 + 14 = 39
Dupa formula ta:
s = (15 - 11) * 11 + (15 - 11)(15 - 11 + 1) / 2 = 4 * 11 + 4 * 5 / 2 = 44 + 10 = 54

[Yeti]

Imi da , gresala mea, in postul meu de mai sus cred ca e corect :


Uite ceva cu ce sa masori exact timpul:

#include <iostream>
#include <ctime>
double diffclock(clock_t clock1,clock_t clock2)
{
double diffticks=clock1-clock2;
double diffms=(diffticks*10)/CLOCKS_PER_SEC;
return diffms;
}
int main()
{
clock_t begin=clock();
//program code
clock_t end=clock();
cout<<"Execution time: "<<diffclock(end,begin)<<" ms."<<endl;
return 0;
}

Google face minuni

[andrei]

recomand ca la threadurile cu "am primit o tema" , sa dati indicii, nu uber rezolvarea din prima.

Omul acum poate se simte suparat ca

Sal, am primit o tema pt acasa cica de gandire ...

..n-a trebuit sa o gandeasca deloc.

[Yeti]

Asa sa fie, daca ceri asa. Sa specifice omul ce vrea si ne multumim si cu datul indicatilor, hinturilor