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!
Puterile lui 2
Hai ca i-am dat de cap dupa vreo ora de munca:
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
#include<iostream>
#include<cmath>
using namespace std;
int main()
{
int n,x=0;
float s=0,i;
cout<<"n="; cin>>n;
for(i=0; i<=n/2; i++)
{
if(pow(2,i)<=n)
{
x = i;
}
else break;
}
s = pow(2,x);
cout<<x<<" ";
for(i=x-1; i>=0; i--)
{
if(s + pow(2,i) <= n)
{
cout<<i<<" ";
s+= pow(2,i);
}
else if(s == n)
break;
}
return 0;
}
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 = (int)(input("Enter n: "))
for i in range(0, n//2+1):
if(pow(2,i)<=n):
x = i
elif(pow(2,i)>=n):
break
s = pow(2, x)
print (x)
i = x-1
for i in range(x-1,-1,-1):
if(s + pow(2,i) <=n):
print(i)
s = s+ pow(2,i)
elif (s ==n):
break
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:
E mult mai eficient din punctul de vedere al timpului de executie!!!
De exemplu, daca vreau sa calculez 2^n, fac urmatorul algoritm:
Cod: Selectaţi tot
#include<iostream>
using namespace std;
int main()
{
int n;
cin >> n;
cout << (1<<n);
return 0;
}
Re: Puterile lui 2
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!
lucrul cu baza 2 e mai scurt codul
#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++;
}
}
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
- Mesaje: 131
- Membru din: 31 Mai 2007, 16:43
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).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!
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).