Puterile lui 2

Rezolvarea problemelor de matematica prin realizarea unor programe.
Pollux
junior
junior
Mesaje: 134
Membru din: 11 Mai 2012, 22:21

Puterile lui 2

Mesaj de Pollux » 16 Iun 2012, 14:25

Se stie ca orice numar natural nenul poate fi scris ca suma de puteri ale lui 2.De exemplu,n=20 se scrie ca 2^4 + 2^2.Scrieti in C++ un program care citeste de la tastatura un numar natural n si scrie exponentii din scrierea lui n ca suma de puteri ale lui 2.

Va multumesc!

xor_NTG
senior
senior
Mesaje: 673
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 16 Iun 2012, 19:32

Hai ca i-am dat de cap dupa vreo ora de munca:

Cod: Selectaţi tot

#include<iostream>
#include<cmath>

using namespace std;
int main&#40;&#41;
&#123;
    int n,x=0;
    float s=0,i;
    cout<<"n="; cin>>n;
    for&#40;i=0; i<=n/2; i++&#41;
    &#123;
        if&#40;pow&#40;2,i&#41;<=n&#41;
        &#123;
            x = i;
        &#125;
        else break;
    &#125;
    s = pow&#40;2,x&#41;;
    cout<<x<<" ";
    for&#40;i=x-1; i>=0; i--&#41;
    &#123;
        if&#40;s + pow&#40;2,i&#41; <= n&#41;
        &#123;
            cout<<i<<" ";
            s+= pow&#40;2,i&#41;;

        &#125;
        else if&#40;s == n&#41;
        break;

    &#125;
    return 0;
&#125;

Sa-ti explic pentru ca acest cod este cam ambiguu la prima vedere. In primul ciclu iau exponentul maxim al scrierii numarului dat sub forma sumei puterilor lui 2. In cazul lui 20, acel s va fi 4.
Apoi afisez secvential exponentii care sunt mai mici decat exponentul maxim luat in primul for dar care respecta conditia aceea din if. s-ul se incrementeaza, daca este egal cu numarul, for-ul se opreste.

Pentru diversificare, o implementare in Python:

Cod: Selectaţi tot

#program_puteri_2_transpunere
import math
n = 0
x = 0
s = 0
i = 0
n = &#40;int&#41;&#40;input&#40;"Enter n&#58; "&#41;&#41;
for i in range&#40;0, n//2+1&#41;&#58;
    if&#40;pow&#40;2,i&#41;<=n&#41;&#58;
        x = i
    elif&#40;pow&#40;2,i&#41;>=n&#41;&#58;
        break
s = pow&#40;2, x&#41;
print &#40;x&#41;
i = x-1
for i in range&#40;x-1,-1,-1&#41;&#58;
    if&#40;s + pow&#40;2,i&#41; <=n&#41;&#58;
        print&#40;i&#41;
        s = s+ pow&#40;2,i&#41;
    elif &#40;s ==n&#41;&#58;
        break
    
    
    
    

Pollux
junior
junior
Mesaje: 134
Membru din: 11 Mai 2012, 22:21

Mesaj de Pollux » 16 Iun 2012, 20:04

wow,mersi!am inteles cu c++ dar python nu am facut la scoala

xor_NTG
senior
senior
Mesaje: 673
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 16 Iun 2012, 20:29

Stiu ca nu se face la scoala python. Acum m-am apucat sa-l invat si eu si incerc sa diversific diferite implementari. Am pus codul pentru a vedea diferentele (extrem de mici) dintre cele doua limbaje.

Visu2412
utilizator
utilizator
Mesaje: 27
Membru din: 08 Sep 2012, 17:39

Mesaj de Visu2412 » 10 Sep 2012, 23:35

Pentru puterile lui 2 nu trebuie sa faceti cicluri FOR sau WHILE, ci se pot face in C++ direct pe biti, si anume operatia de shiftare spre dreapta cu o pozitie.
De exemplu, daca vreau sa calculez 2^n, fac urmatorul algoritm:

Cod: Selectaţi tot

#include<iostream>
using namespace std;
int main&#40;&#41;
&#123;
     int n;
     cin >> n;
     cout << &#40;1<<n&#41;;
     return 0;
&#125;
E mult mai eficient din punctul de vedere al timpului de executie!!!

xor_NTG
senior
senior
Mesaje: 673
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 11 Sep 2012, 10:13

Wow! Eu nu prea am inteles pana acum operatiile pe biti. Am auzit ca sunt extrem de rapide dar niciodata nu am intentionat sa le utilizez. O sa le dau mai multa atentie de acum incolo. Thanks, dude!

yellowheart
utilizator
utilizator
Mesaje: 28
Membru din: 20 Sep 2012, 12:09
Localitate: bucuresti

Mesaj de yellowheart » 09 Oct 2012, 11:07

cum sa nu se faca?eu am facut phyton la scoala!

xor_NTG
senior
senior
Mesaje: 673
Membru din: 30 Apr 2012, 15:53

Mesaj de xor_NTG » 10 Oct 2012, 09:21

Depinde ce scoala ai facut. Daca e una cu specific informatic, evident ca e posibil sa se faca python. In scolile normale nu se face.

yellowheart
utilizator
utilizator
Mesaje: 28
Membru din: 20 Sep 2012, 12:09
Localitate: bucuresti

Mesaj de yellowheart » 10 Oct 2012, 11:49

nu este una cu specific informatic, dar specializarea era mate info intensiv:D

PhantomR
guru
guru
Mesaje: 2861
Membru din: 27 Apr 2011, 18:16

Re: Puterile lui 2

Mesaj de PhantomR » 10 Oct 2012, 14:51

Pollux scrie:Se stie ca orice numar natural nenul poate fi scris ca suma de puteri ale lui 2.De exemplu,n=20 se scrie ca 2^4 + 2^2.Scrieti in C++ un program care citeste de la tastatura un numar natural n si scrie exponentii din scrierea lui n ca suma de puteri ale lui 2.

Va multumesc!

Gospodin
utilizator
utilizator
Mesaje: 1
Membru din: 16 Iul 2015, 18:49

lucrul cu baza 2 e mai scurt codul

Mesaj de Gospodin » 16 Iul 2015, 18:56

#include<iostream>
using namespace std;
int main(){
int n, a = 0;
cin >> n;
while(n != 0){
if(n % 2 == 1)
cout << a<< " ";
n /= 2;
a++;
}
}

crs12decoder
junior
junior
Mesaje: 133
Membru din: 31 Mai 2007, 16:43

Mesaj de crs12decoder » 12 Noi 2015, 01:20

xor_NTG scrie:Wow! Eu nu prea am inteles pana acum operatiile pe biti. Am auzit ca sunt extrem de rapide dar niciodata nu am intentionat sa le utilizez. O sa le dau mai multa atentie de acum incolo. Thanks, dude!
Destul de rar ajungi sa le si folosesti pentru ca nu foarte multe probleme pot fi rezolvate cu simplii operatori logici(cel putin eu, toate cazurile pe care le-am intalnit erau pur teoretice, exemplu cazul din thread). Dar principiul lor e foarte simplu. Trebuie doar sa privesti numarul in binar, restul logicii vine de la sine. AND,NOT,OR,XOR etc. toate aplicate pe bitii care compun numarul(desigur, cu simbolistica de rigoare folosita in C).
Acum depinde cu cine ai facut programarea. Stiu ca in primu' an Carmen Odubasteanu ne-a aratat cate ceva la curs legat de operatii pe biti. Cel mai bine le-ai fi inteles de la Calculatoare Numerice dar de obicei acolo nu se dadea prea mult interes(cel putin la CC).

Scrie răspuns