[C] Da binario a intero
Ciao, ho qualche problema con un esempio del libro!!
In questo esempio si scrive un codice che permette la codifica binaria di un intero in modo proprio basilare: no vettori, no cicli annidati.
Si procede così:
1)Si calcola su quanti bit p sarà espressa la codifica, quindi p rappresenta l'esponente della più grande potenza di 2 tale che $2^p >= n$:
Già qui ho qualche problema! Mi sono fatto un esempio con il numero $n=15$ ma qualcosa non mi quadra:
Usando il ciclo for ho
p=1 2<15 -> p=2
p=2 4<15 -> p=4
p=4 8<15 -> p=8
p=8 16>15 Allora mi fermo e p=8
Ma se invece uso la disequazione allora p=4 dato che $2^4=16>15$
2)Si procede bit a bit. Se $n>=p$ il bit generato vale 1, altrimenti è 0
3)Si dimezza p
E i punti 2)3) si ripetono fin quando p>0
Parte di codice:
In tutto questo mi chiedo: va bene che funziona, ma da dove esce questo procedimento?
Non c'è un "calcolo" tipo per le divisioni successive?
Grazie in anticipo!!
In questo esempio si scrive un codice che permette la codifica binaria di un intero in modo proprio basilare: no vettori, no cicli annidati.
Si procede così:
1)Si calcola su quanti bit p sarà espressa la codifica, quindi p rappresenta l'esponente della più grande potenza di 2 tale che $2^p >= n$:
for(p=1; 2*p<=n; p=p*2);
Già qui ho qualche problema! Mi sono fatto un esempio con il numero $n=15$ ma qualcosa non mi quadra:
Usando il ciclo for ho
p=1 2<15 -> p=2
p=2 4<15 -> p=4
p=4 8<15 -> p=8
p=8 16>15 Allora mi fermo e p=8
Ma se invece uso la disequazione allora p=4 dato che $2^4=16>15$
2)Si procede bit a bit. Se $n>=p$ il bit generato vale 1, altrimenti è 0
3)Si dimezza p
E i punti 2)3) si ripetono fin quando p>0
Parte di codice:
int p; for(p=1;2*p<=n;p=p*2); while(p>0)} if(p<=n){ printf("1"); n=n-p; } else printf("0"); p=p/2; }
In tutto questo mi chiedo: va bene che funziona, ma da dove esce questo procedimento?
Non c'è un "calcolo" tipo per le divisioni successive?
Grazie in anticipo!!
Risposte
La cosa è più eclatante con $n=45$.
Seguendo il ciclo for:
p=1 2<45 p=2
p=2 4<45 p=4
p=4 8<45 p=8
p=8 16<45 p=16
p=16 32<45 p=32
p=32 64>45 allora mi fermo e p=32
Ma se seguo la disequazione il primo p utile è p=6 dato che $2^6=64$!! Tralaltro non capisco, se lui vuole la PIU' GRANDE POTENZA allora $p->infty$..
Seguendo il ciclo for:
p=1 2<45 p=2
p=2 4<45 p=4
p=4 8<45 p=8
p=8 16<45 p=16
p=16 32<45 p=32
p=32 64>45 allora mi fermo e p=32
Ma se seguo la disequazione il primo p utile è p=6 dato che $2^6=64$!! Tralaltro non capisco, se lui vuole la PIU' GRANDE POTENZA allora $p->infty$..
è evidente che il for si fermi alla potenza precedente di quella "giusta"visto che fa il controllo sul valore 2*p, evidentemente gli serve per qualche artificio sintattico, ad esempio, visto che dopo devi fare p=p-n non dovresti sottrarre a 45 il 64, cosa che invece accadrebbe se il for si fermasse al 64, quindi si ferma alla potenza precedente.
comunque di solito nessuno ti chiede di fare una funzione del genere, ma solo di capire perchè è giusta così e non ad esempio facendo fermare il for alla potenza immediatamente superiore.
Ciao
comunque di solito nessuno ti chiede di fare una funzione del genere, ma solo di capire perchè è giusta così e non ad esempio facendo fermare il for alla potenza immediatamente superiore.
Ciao
Scusa se rispondo solo ora. Perciò, il for è "sbagliato" ma è finalizzato a far riuscire il procedimento.. mh.. beh almeno me ne faccio una ragione! Sai, per caso, da dove deriva questo procedimento? Cioè io non lo avrei mai pensato..
di solito sono procedimenti studiati a fondo, ma quasi nessuno li usa perché la maggior parte dei linguaggi implementano già la conversione. comunque non è intuitivo, ti devi mettere con carta e penna e provare a capire:
ho un numero ottenibile mediante la somma di potenze di 2, come lo scomporrei a mano?
guardo la potenza di 2 massima contenuta e la sottraggo, poi faccio la stessa cosa nel risultato della sottrazione.
Per farlo automaticamente vedo che invece di fermarmi alla potenza immediatamente superiore e dover mettere un controllo che faccia una cosa diversa al primo passaggio, mi fermo direttamente alla potenza precedente.
se preferisci si potrebbe scrivere il for "giusto" e dividere subito dopo per 2, è la stessa cosa.
a ogni passo del while controlli se quella potenza del 2 è contenuta nel numero, se è contenuta stampi un 1 se non lo è stampi uno zero, a prescindere dalla stampa(1 o 0) dividi p per 2 e continui a controllare la potenza del 2 precedente.
ripeto: nessuno ti chiede di fare un algoritmo del genere, non è naturale da immaginare, devi solo riuscire a capire perchè così funziona e , ad esempio, perchè non funzionerebbe scrivendo il for nell'altro modo...
ad esempio: si può fare la stessa procedura controllando lepotenze del 2 contenute ma in senso crescente?
la risposta è si, solo che stampando i numeri che trovi a schermo li troveresti ribaltati
invece di 101100 troveresti 001101, quindi ti serve scrivere le cifre binarie in un vettore e stampare a schermo il vettore leggendolo al contrario.
ho un numero ottenibile mediante la somma di potenze di 2, come lo scomporrei a mano?
guardo la potenza di 2 massima contenuta e la sottraggo, poi faccio la stessa cosa nel risultato della sottrazione.
Per farlo automaticamente vedo che invece di fermarmi alla potenza immediatamente superiore e dover mettere un controllo che faccia una cosa diversa al primo passaggio, mi fermo direttamente alla potenza precedente.
se preferisci si potrebbe scrivere il for "giusto" e dividere subito dopo per 2, è la stessa cosa.
a ogni passo del while controlli se quella potenza del 2 è contenuta nel numero, se è contenuta stampi un 1 se non lo è stampi uno zero, a prescindere dalla stampa(1 o 0) dividi p per 2 e continui a controllare la potenza del 2 precedente.
ripeto: nessuno ti chiede di fare un algoritmo del genere, non è naturale da immaginare, devi solo riuscire a capire perchè così funziona e , ad esempio, perchè non funzionerebbe scrivendo il for nell'altro modo...
ad esempio: si può fare la stessa procedura controllando lepotenze del 2 contenute ma in senso crescente?
la risposta è si, solo che stampando i numeri che trovi a schermo li troveresti ribaltati
invece di 101100 troveresti 001101, quindi ti serve scrivere le cifre binarie in un vettore e stampare a schermo il vettore leggendolo al contrario.
Grazie insideworld!