Repository 32bit  Forum
Repository 64bit  Wiki

help ricorsione URGENTE

Forum dedicato alla programmazione.

Moderatore: Staff

Regole del forum
1) Citare in modo preciso il linguaggio di programmazione usato.
2) Se possibile portare un esempio del risultato atteso.
3) Leggere attentamente le risposte ricevute.
4) Scrivere i messaggi con il colore di default, evitare altri colori.
5) Scrivere in Italiano o in Inglese, se possibile grammaticalmente corretto, evitate stili di scrittura poco chiari, quindi nessuna abbreviazione tipo telegramma o scrittura stile SMS o CHAT.
6) Appena registrati è consigliato presentarsi nel forum dedicato.

La non osservanza delle regole porta a provvedimenti di vari tipo da parte dello staff, in particolare la non osservanza della regola 5 porta alla cancellazione del post e alla segnalazione dell'utente. In caso di recidività l'utente rischia il ban temporaneo.

help ricorsione URGENTE

Messaggioda Blallo » ven ott 09, 2009 13:32

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
Io sono il detective Arsenio Magret, e porto sempre la camicia TATUATA!
Avatar utente
Blallo
Packager
Packager
 
Messaggi: 3226
Iscritto il: ven ott 12, 2007 10:37
Località: Torino / Torremaggiore (FG)
Nome Cognome: Savino Liguori
Slackware: 14.1 / 12.2
Kernel: 3.12.2-ck
Desktop: Openbox

Re: help ricorsione URGENTE

Messaggioda targzeta » ven ott 09, 2009 13:39

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

Emanuele
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6176
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: help ricorsione URGENTE

Messaggioda Blallo » ven ott 09, 2009 13:42

Che mi diate un input, sto studiando da poco la ricorsione e non ancora entro nei meccanismi
Io sono il detective Arsenio Magret, e porto sempre la camicia TATUATA!
Avatar utente
Blallo
Packager
Packager
 
Messaggi: 3226
Iscritto il: ven ott 12, 2007 10:37
Località: Torino / Torremaggiore (FG)
Nome Cognome: Savino Liguori
Slackware: 14.1 / 12.2
Kernel: 3.12.2-ck
Desktop: Openbox

Re: help ricorsione URGENTE

Messaggioda targzeta » ven ott 09, 2009 14:00

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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6176
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: help ricorsione URGENTE

Messaggioda Blallo » ven ott 09, 2009 14:14

giusto dimenticavo...non devo usare conversioni decimale->binario, quindi dovrei operare su un vettore allocato dinamicamente costituente le cifre del binario
Io sono il detective Arsenio Magret, e porto sempre la camicia TATUATA!
Avatar utente
Blallo
Packager
Packager
 
Messaggi: 3226
Iscritto il: ven ott 12, 2007 10:37
Località: Torino / Torremaggiore (FG)
Nome Cognome: Savino Liguori
Slackware: 14.1 / 12.2
Kernel: 3.12.2-ck
Desktop: Openbox

Re: help ricorsione URGENTE

Messaggioda targzeta » ven ott 09, 2009 14:25

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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6176
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: help ricorsione URGENTE

Messaggioda Blallo » ven ott 09, 2009 14:27

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 :oops:
Io sono il detective Arsenio Magret, e porto sempre la camicia TATUATA!
Avatar utente
Blallo
Packager
Packager
 
Messaggi: 3226
Iscritto il: ven ott 12, 2007 10:37
Località: Torino / Torremaggiore (FG)
Nome Cognome: Savino Liguori
Slackware: 14.1 / 12.2
Kernel: 3.12.2-ck
Desktop: Openbox

Re: help ricorsione URGENTE

Messaggioda targzeta » ven ott 09, 2009 14:32

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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6176
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: help ricorsione URGENTE

Messaggioda targzeta » ven ott 09, 2009 14:51

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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6176
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: help ricorsione URGENTE

Messaggioda Blallo » ven ott 09, 2009 19:50

grazie mille spina :D
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);
    }
}
Io sono il detective Arsenio Magret, e porto sempre la camicia TATUATA!
Avatar utente
Blallo
Packager
Packager
 
Messaggi: 3226
Iscritto il: ven ott 12, 2007 10:37
Località: Torino / Torremaggiore (FG)
Nome Cognome: Savino Liguori
Slackware: 14.1 / 12.2
Kernel: 3.12.2-ck
Desktop: Openbox

Re: help ricorsione URGENTE

Messaggioda targzeta » ven ott 09, 2009 21:29

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

Emanuele
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6176
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM

Re: help ricorsione URGENTE

Messaggioda targzeta » ven ott 09, 2009 21:44

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
Linux Registered User #454438
Se pensi di essere troppo piccolo per fare la differenza, prova a dormire con una zanzara -- Dalai Lama
20/04/2013 - Io volevo Rodotà
Avatar utente
targzeta
Iper Master
Iper Master
 
Messaggi: 6176
Iscritto il: gio nov 03, 2005 14:05
Località: Carpignano Sal. (LE) <-> Pisa
Nome Cognome: Emanuele Tomasi
Slackware: current
Kernel: latest stable
Desktop: IceWM


Torna a Programmazione

Chi c’è in linea

Visitano il forum: Nessuno e 2 ospiti

cron