help ricorsione URGENTE

[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

[targzeta]

Ehm, l'aiuto qual'è? Vuoi che te lo facciamo per te

Emanuele

[Blallo]

Che mi diate un input, sto studiando da poco la ricorsione e non ancora entro nei meccanismi

[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

[Blallo]

giusto dimenticavo...non devo usare conversioni decimale->binario, quindi dovrei operare su un vettore allocato dinamicamente costituente le cifre del binario

[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

[Blallo]

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

[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

[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

[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);
    }
}

[targzeta]

Bhé, non c'è che dire, una soluzione bella ed elegante (solo che io avrei demandato la stampa ad una funzione a parte)

Emanuele

[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