Pagina 1 di 1
help ricorsione URGENTE
Inviato: ven 9 ott 2009, 14:32
da Blallo
Devo creare un programma in c che dato n da tastiera, generi tranite ricorsione tutti i numeri binari composti da n bit
ES: n=3
devo creare e stampare
000
001
010
011 ecc ecc
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 14:39
da targzeta
Ehm, l'aiuto qual'è? Vuoi che te lo facciamo per te
Emanuele
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 14:42
da Blallo
Che mi diate un input, sto studiando da poco la ricorsione e non ancora entro nei meccanismi
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 15:00
da targzeta
Dipende da quali strumenti puoi usare. L'idea potrebbe essere che hai due funzioni, una che dato un numero intero ti stampa la sua rappresentazione binaria, e l'altra, quella ricorsiva, che incrementa di uno un numero. Tipo:
Codice: Seleziona tutto
function incr(limit, num)
{
stampa(num);
if ( (++num) == limit )
return;
incr(limit, num);
}
E' un pò stupidina (non è altro che la traduzione di un ciclo while), però questo problema si presta poco alla ricorsione. limit=2^numero_di_bit. La prima invocazione è incr(2^numero_di_bit, 0);
Però magari ti si chiede anche di implementare la funzione di stampa come ricorsiva. Se puoi usare gli operatori bit a bit è più semplice.
Emanuele
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 15:14
da Blallo
giusto dimenticavo...non devo usare conversioni decimale->binario, quindi dovrei operare su un vettore allocato dinamicamente costituente le cifre del binario
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 15:25
da targzeta
Cioè in pratica dovresti avere un array grande quanto il numero di bit ed inizializzarlo a 0000, o cose di questo tipo e poi lavorarci su?
Emanuele
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 15:27
da Blallo
spina ha scritto:Cioè in pratica dovresti avere un array grande quanto il numero di bit ed inizializzarlo a 0000, o cose di questo tipo e poi lavorarci su?
Emanuele
Esatto. Hai centrato in pieno. Scusami se di solito sono poco chiaro
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 15:32
da targzeta
ok, allora l'idea è la stessa solo che la funzione di incremento non è più num++ ma la devi implementare tu su un array binario. Ora vedo cosa riesco a fare. L'idea ricorsiva non cambia e neanche l'idea di avere due funzioni delle quali una delegata alla stampa.
Emanuele
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 15:51
da targzeta
Ecco qui una possibile implementazione:
Codice: Seleziona tutto
#include <stdio.h>
#define SIZE 3
/* Azzera i primi i bit di a */
void reset(int i, char *a)
{
int j;
for ( j=0; j < i; j++ )
a[j] = '0';
}
/* Stampa l'array a */
void stampa(char *a)
{
int i;
for ( i=SIZE; i >= 0; i-- )
putchar(a[i-1]);
putchar('\n');
}
/* Incrementa a di uno */
void incr(char *a)
{
int i, change;
stampa(a);
for ( change=i=0; i < SIZE; i++ )
if ( a[i] == '0' )
{
a[i] = '1';
reset(i, a);
change=1;
break;
}
if ( change == 0 )
return;
incr(a);
}
int main()
{
char array[SIZE];
reset(SIZE, array);
incr(array);
return 0;
}
Uso la define per semplificarmi la vita, non credo troverai difficoltà a parametrizzare le funzioni.
Emanuele
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 20:50
da Blallo
grazie mille spina
ho analizzato per bene il codice, e mi hai fatto venire in mente un metodo ancora più veloce
Codice: Seleziona tutto
void incr(int *v, int N, int i)
{
int j;
if(i==N)
{
for(j=0;j<N;j++)
printf("%d", v[j]);
printf("\n");
return ;
}
else
{
v[i]=0;
incr(v, N, i+1);
v[i]=1;
incr(v, N, i+1);
}
}
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 22:29
da targzeta
Bhé, non c'è che dire, una soluzione bella ed elegante (solo che io avrei demandato la stampa ad una funzione a parte)
Emanuele
Re: help ricorsione URGENTE
Inviato: ven 9 ott 2009, 22:44
da targzeta
Ho fatto un confronto e stranamente il tuo algoritmo è più lento (per quanto sia affidabile time):
Codice: Seleziona tutto
N=15
Spina
------
real 2.17
user 0.03
sys 0.12
Jimmy
--------
real 2.27
user 0.01
sys 0.17
Codice: Seleziona tutto
N=16
Spina
-------
real 4.75
user 0.06
sys 0.12
Jimmy
---------
real 6.16
user 0.07
sys 0.07
Però il tuo algoritmo ha un altro vantaggio, quello di terminare le ricorsioni ogni N passi. Il mio continua a fare ricorsioni fino a che non raggiunge l'ultimo numero, e questo porta ad un errore quando N è troppo grande. Il tuo invece è più robusto.
Emanuele