PDA

Visualizza la versione completa : [C] Numero di uno in un binario


cifa
02-12-2010, 23:53
Scusate è la terza volta che vi rompo le scatole, ma sto proprio agli inizi e mi capita spesso di incappare in problemi stupidi XD

Il mio esercizio è:

Scrivere una funzione int ones(int a, int b, int k) che ritorna il numero di interi compresi tra a e b che nella rappresentazione binaria hanno esattamente k uno. Si assuma che b >= a >= 0 e che k >= 0. Ad esempio, se a = 0, b = 7 e k = 2, la funzione ritorna 3; se a = 0, b = 15, k = 3, ritorna 4; se a = 12, b = 67, k = 3, ritorna 19; se a = 12, b = 67, k = 7, ritorna 0.


Il mio codice è:


#include <stdio.h>
#include <stdlib.h>

int ones (int a, int b, int k);

int main(void) {
int a, b, k;
printf("Inserire a, b, k \n");
scanf ("%d %d %d", &a, &b, &k);
printf ("Il numero di numeri con K uni è: \n %d \n", ones (a,b,k));

}


int ones (int a, int b, int k){
int cnt=0;
int x=a;
int ones=0;
for (; a<=b; a++){
x=a;
while (x!=0){
if (x%2==1) cnt++;
x/=2;
}
if (cnt == k) ones++;
}

return ones;
}




Non funziona però, ad esempio per i valori esempio dell'esercizio 12 67 e 3 mi restituisce 0.
Qualcuno mi può spiegare COSA e PERCHÈ è sbagliato senza darmi il codice corretto ? (vorrei provarci da solo :P)


Grazie mille e scusate l'assillo :(

cifa
03-12-2010, 00:02
Ah mi son scordato di scrivere che hi già individuato nel ciclo esterno il problema dato che l'algorimo del while funziona con un caso specifico

simo_85
03-12-2010, 00:08
Scrivere una funzione int ones(int a, int b, int k) che ritorna il numero di interi compresi tra a e b che nella rappresentazione binaria hanno esattamente k uno
Questa funzione ritorna il numero di bit a uno di un numero binario


int pop(unsigned x)
{
x = x - ((x >> 1) & 0x55555555);
x = (x & 0x33333333) + ((x >> 2) & 0x33333333);
x = (x + (x >> 4)) & 0x0F0F0F0F;
x = x + (x >> 8);
x = x + (x >> 16);
return x & 0x0000003F;
}

Magari ti può essere utile.

cifa
03-12-2010, 07:38
Grazie, però più che la soluzione vorrei capire cosa c'è di sbagliato nel mio codice in modo da imparare qualcosa :D

MdE2005
03-12-2010, 07:46
Non capisco perchè tu faccia questo:

Originariamente inviato da cifa
int ones (int a, int b, int k){
int cnt=0;
int x=a; //questa riga non serve
int ones=0;
for (; a<=b; a++){
x=a;
while (x!=0){
if (x%2==1) cnt++;
x/=2;
}
if (cnt == k) ones++;
}

return ones;
}
[/CODE]

Sai la definizione di k? La tua funzione non fa niente di tutto ciò.

Devi usare la funzione di simo_85..

simo_85
03-12-2010, 15:10
Originariamente inviato da MdE2005
Devi usare la funzione di simo_85..
Comunque la funzione non è implementata da me, solamente fa parte di un ottimo libro che sto studiando.
:ciauz:

MdE2005
03-12-2010, 16:05
Originariamente inviato da simo_85
Comunque la funzione non è implementata da me, solamente fa parte di un ottimo libro che sto studiando.
:ciauz:
Volevo solo far capire all'utente che la strada da seguire necessitava della funzione che hai postato.


Ciao :)

simo_85
03-12-2010, 16:41
Originariamente inviato da MdE2005
Volevo solo far capire all'utente che la strada da seguire necessitava della funzione che hai postato.
Ciao :) Lo so :zizi:

MItaly
03-12-2010, 17:33
Originariamente inviato da simo_85
Comunque la funzione non è implementata da me, solamente fa parte di un ottimo libro che sto studiando.
:ciauz:
Per curiosità, di che libro si tratta? Perché se si tratta di un buon libro di algoritmi, mi farebbe comodo. :)

simo_85
03-12-2010, 17:59
Originariamente inviato da MItaly
Per curiosità, di che libro si tratta? Perché se si tratta di un buon libro di algoritmi, mi farebbe comodo. :)
H's D (http://www.amazon.com/Hackers-Delight-Henry-S-Warren/dp/0201914654/ref=sr_1_1?ie=UTF8&s=books&qid=1291395531&sr=1-1)

Loading